networkX

パイソンでグラフを扱うための定番モジュールはNetworkXだ．枝上にラベルの情報を付加できるようになったようだ．

こんな感じでやると，上のような図が描画できる．中身は最小費用流問題を定義してネットワーク単体法で解いているだけだ．

G = nx.DiGraph()
G.add_node('s', demand = -10)
G.add_node('t', demand = 10)
G.add_edge('s', 1, weight = 10, capacity = 5)
G.add_edge('s', 2, weight = 5,  capacity = 8)
G.add_edge(2, 1, weight = 3, capacity = 2)
G.add_edge(1, 't', weight = 1, capacity = 8)
G.add_edge(2, 3, weight = 2, capacity = 5)
G.add_edge(3, 't', weight = 6, capacity = 6)
z, x =  nx.network_simplex(G) 
pos = {"s":(0,1),1:(1,2),2:(1,0),3:(2,0),"t":(2,2)}
edge_labels = {}
for (i,j) in G.edges():
   edge_labels[i,j] = f"{G[i][j]['weight']} ({x[i][j]}/{G[i][j]['capacity']})"
plt.figure()
nx.draw(G, pos=pos,with_labels=True, node_size=1000)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)
plt.show()

今度書く予定の「実務で役に立つ100の最適化問題」という本で使おう．英語と日本語で出す予定だが，いつになるかは分からない．