NetworkX

NetworkXを用いて第4章

Pythonのネットワーク解析用ライブラリNetworkXを用いて第4章の問題を解きます。

（zorinOS。 Python 2.7.4。networkx 1.7-2）

最短路問題

1
python
1
import networkx as nx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if __name__ == '__main__':
	graph = nx.Graph()
	# ノードを追加する
	graph.add_node('1')
	graph.add_node('2')
	graph.add_node('3')
	graph.add_node('4')
	graph.add_node('5')
	graph.add_node('6')
	# ノード間をエッジでつなぐ
	graph.add_edge('1','2', weight=1)
	graph.add_edge('1','3', weight=5)
	graph.add_edge('2','3', weight=2)
	graph.add_edge('2','4', weight=2)
	graph.add_edge('3','4', weight=3)
	graph.add_edge('3','5', weight=1)
	graph.add_edge('4','6', weight=3)
	graph.add_edge('5','6' ,weight=4)
	# ダイクストラ法で最短経路を探す
	print nx.dijkstra_path(graph, '1', '5')
	print nx.dijkstra_path_length(graph, '1', '5')

[‘1’, ‘2’, ‘3’, ‘5’]
4

最大流問題

1
python
1
import networkx as nx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if __name__ == '__main__':
    graph = nx.DiGraph()
    # ノードを追加する
    graph.add_node('1')
    graph.add_node('2')
    graph.add_node('3')
    graph.add_node('4')
    graph.add_node('5')
    graph.add_node('6')
    graph.add_node('7')
    # ノード間をエッジでつなぐ
    graph.add_edge('1', '2', capacity=3)
    graph.add_edge('1', '3', capacity=5)
    graph.add_edge('2', '5', capacity=2)
    graph.add_edge('2', '4', capacity=2)
    graph.add_edge('3', '4', capacity=3)
    graph.add_edge('3', '6', capacity=3)
    graph.add_edge('4', '7', capacity=2)
    graph.add_edge('5', '7', capacity=3)
    graph.add_edge('6', '7', capacity=4)
    # 最大流問題を解く
    print nx.maximum_flow(graph, '1', '7')

(7, {‘1’: {‘3’: 5, ‘2’: 2}, ‘3’: {‘4’: 2, ‘6’: 3}, ‘2’: {‘5’: 2, ‘4’: 0}, ‘5’: {‘7’: 2}, ‘4’: {‘7’: 2}, ‘7’: {}, ‘6’: {‘7’: 3}})

最小費用流問題

（注）ノードのdemandの指定はプラマイを逆にする

1
python
1
import networkx as nx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
if __name__ == '__main__':
	G = nx.DiGraph()
	# ノードを追加する
	G.add_node('1', demand = -40)
	G.add_node('2', demand = 0)
	G.add_node('3', demand = 0)
	G.add_node('4', demand = 0)
	G.add_node('5', demand = 0)
	G.add_node('6', demand = 0)
	G.add_node('7', demand = 30)
	G.add_node('8', demand = 10)
	# ノード間をエッジでつなぐ
	G.add_edge('1', '2', weight = 3, capacity = 20)
	G.add_edge('1', '3', weight = 5, capacity = 25)
	G.add_edge('2', '4', weight = 2, capacity = 15)
	G.add_edge('2', '5', weight = 2, capacity = 20)
	G.add_edge('3', '4', weight = 3, capacity = 20)
	G.add_edge('3', '6', weight = 3, capacity = 15)
	G.add_edge('4', '7', weight = 3, capacity = 30)
	G.add_edge('5', '7', weight = 2, capacity = 20)
	G.add_edge('6', '8', weight = 4, capacity = 15)
	#network_simplex(G, demand='demand', capacity='capacity', weight='weight')
	#Find a minimum cost flow satisfying all demands in digraph G.
	flowCost, flowDict = nx.network_simplex(G)
	flowCost
	flowDict

370
{‘1’: {‘3’: 20, ‘2’: 20}, ‘3’: {‘4’: 10, ‘6’: 10}, ‘2’: {‘5’: 20, ‘4’: 0}, ‘5’: {‘7’: 20}, ‘4’: {‘7’: 10}, ‘7’: {}, ‘6’: {‘8’: 10}, ‘8’: {}}