install
pip install pyMaxflow
グラフの作り方
sample.py
# グラフの定義
g=maxflow.Graph[int]() # or g=maxflow.Graph[float]()
# ノードを格子状に追加
nodeids = g.add_grid_nodes((5, 5))
structure = np.array([[np.inf, 0, 0],
[np.inf, 0, 0],
[np.inf, 0, 0]
])
# edgeをstructure指定した構造に
g.add_grid_edges(nodeids, structure=structure, symmetric=False)
# weight edgeの重みを定義
weights = np.array([[100, 110, 120, 130, 140]]).T + np.array([0, 2, 4, 6, 8])
# edgeを伸ばす方向を決める
structure = np.zeros((3, 3))
structure[1, 2] = 1
# structureで指定した方向にweightの重みでedgeを伸ばす
g.add_grid_edges(nodeids, structure=structure, weights=weights, symmetric=False)
structure = np.zeros((3, 3))
structure[0, 1] = 1
g.add_grid_edges(nodeids, structure=structure, weights=weights + 100, symmetric=False)
structure = np.zeros((3, 3))
structure[2, 1] = 1
g.add_grid_edges(nodeids, structure=structure, weights=weights + 200, symmetric=False)
left = nodeids[:, 0]
# sからleftで指定したノードに
g.add_grid_tedges(left, np.inf, 0)
right = nodeids[:, -1]
g.add_grid_tedges(right, 0, np.inf)
可視化
view.py
def plot_graph(nxgraph):
X, Y = np.mgrid[:5, :5]
aux = np.array([Y.ravel(), X[::-1].ravel()]).T
positions = {i: aux[i] for i in range(25)}
positions['s'] = (-1, 2)
positions['t'] = (5, 2)
# nxgraph.remove_nodes_from(['s', 't'])
edge_labels = {}
for u, v, d in nxgraph.edges(data=True):
edge_labels[(u, v)] = d['weight']
plt.clf()
nx.draw(nxgraph, pos=positions)
nx.draw_networkx_edge_labels(nxgraph, pos=positions, edge_labels=edge_labels, label_pos=0.3, font_size=7)
plt.axis('equal')
plt.show()
nxg = g.get_nx_graph()
plot_graph(nxg)
詳しくは動作させながらだと分かりやすいです。