ここでは,Edmonds-Karpアルゴリズムを,NetworkXを使わずに実装する.
まず,有向グラフと枝容量をまとめて保存できるクラスDiGraphを作る.
class DiGraph:
def __init__(self):
self.node = {}
self.edge = {}
return
def add_node(self, node_name, node_attributes={}):
self.node[node_name] = node_attributes
if node_name not in self.edge: # node_nameが枝集合のキーになければ,
self.edge[node_name] = {} # とりあえず加えておく.
return
def add_edge(self, tail_name, head_name, edge_attributes={}):
if tail_name not in self.edge: # tailの名前が枝集合のキーになければ
self.edge[tail_name] = {} # まず,キーとして加える.
if head_name not in self.edge: # headの名前が枝集合のキーにない場合も
self.edge[head_name] = {} # キーとして加える.
self.edge[tail_name][head_name] = edge_attributes # その上で,枝を辞書として保存する.
if tail_name not in self.node: # tailの名前が頂点集合にまだない場合には,
self.node[tail_name] = {} # 頂点集合にもtailの名前を加える.
if head_name not in self.node: # headの名前に関しても同様である.
self.node[head_name] = {}
return
def nodes(self):
return self.node.keys()
def edges(self):
edge_list = []
for tail in self.edge:
for head in self.edge[tail]:
edge_list.append((tail, head))
return edge_list
def successors(self, tail_name):
return self.edge[tail_name].keys()
容量はedge_attributesとして保存することにする.
例えば,以下のようにグラフと枝容量を保存する.
G = DiGraph()
G.add_node(1, {'position': (0, 1)})
G.add_node(2, {'position': (1, 2)})
G.add_node(3, {'position': (3, 2)})
G.add_node(4, {'position': (1, 0)})
G.add_node(5, {'position': (3, 0)})
G.add_node(6, {'position': (4, 1)})
G.add_edge(1, 2, {'capacity': 5})
G.add_edge(1, 4, {'capacity': 20})
G.add_edge(2, 3, {'capacity': 15})
G.add_edge(2, 5, {'capacity': 3})
G.add_edge(3, 5, {'capacity': 10})
G.add_edge(3, 6, {'capacity': 15})
G.add_edge(4, 2, {'capacity': 7})
G.add_edge(4, 5, {'capacity': 13})
G.add_edge(5, 6, {'capacity': 10})
import math # math.infを使いたいのでimportする.
def shortest_path(G, source, target):
'''幅優先探索で
グラフ上の最短路を計算'''
shortest_distance = {v: math.inf for v in G.nodes()}
prev = {} # 最短路長だけでなく,最短路における頂点vの手前の頂点も覚える.
shortest_distance[source] = 0
visited = set([source])
queue = [source]
while len(queue) > 0:
v = queue.pop(0)
for w in G.successors(v): # 有向グラフGにおいて,頂点vから出る枝の先の頂点集合
if w not in visited:
visited |= set([w])
queue.append(w)
shortest_distance[w] = shortest_distance[v] + 1
prev[w] = v # このとき,頂点wへの最短路における,頂点wの1つ前は頂点v
'''幅優先探索が完了した状態でtargetへの最短路長が無限大ならば,
sourceからtargetへの有向歩道は存在しない.'''
if shortest_distance[target] == math.inf:
return DiGraph()
'''sourceからtargetへの最短路を
これまたDiGraphとして保存する.
後の都合のため,枝容量も付けておく.'''
path = DiGraph()
v = target
while v != source:
u = prev[v]
path.add_edge(prev[v], v, {'capacity': G.edge[u][v]['capacity']})
v = u
return path
def residual_network(G, flow):
'''与えられた問題例Gとflowからresidual networkを作る関数.
'''
residual_net = DiGraph()
for tail, head in G.edges():
amount = flow.edge[tail][head]['flow']
capacity = G.edge[tail][head]['capacity']
if amount < capacity:
residual_net.add_edge(tail, head, {'capacity': capacity-amount}) # ここだけNetworkX利用時と違う.
if amount > 0:
residual_net.add_edge(head, tail, {'capacity': amount}) # ここだけNetworkX利用時と違う.
return residual_net
def augmenting_path(residual_net, source, target):
'''与えられた残余ネットワークとsourceとtargetからaugmenting pathを見つける関数.
Edmonds-Karpアルゴリズム用に,枝数最小のaugmenting pathを見つける.
Augmenting pathがある場合には,(augmenting path上の最小枝容量,DiGraphとしてのaugmenting path)を返す.
Augmenting pathがない場合には,(0,空グラフ)を返す.
'''
aug_path = shortest_path(residual_net, source, target)
if len(aug_path.edges()) == 0:
return (0, aug_path)
minimum_capacity = math.inf
for tail, head in aug_path.edges():
minimum_capacity = min(minimum_capacity, aug_path.edge[tail][head]['capacity'])
return (minimum_capacity, aug_path)
def edmonds_karp(G, source, target):
'''Edmonds-Karpアルゴリズムを実行する関数.
最大流を自前のDiGraph形式で返す.
'''
flow = DiGraph()
for tail, head in G.edges():
flow.add_edge(tail, head, {'flow': 0}) # ここだけNetworkX利用時と違う.
while True:
residual_net = residual_network(G, flow)
min_capa, aug_path = augmenting_path(residual_net, source, target)
if min_capa == 0:
break
for tail, head in aug_path.edges():
flow.edge[tail][head]['flow'] += min_capa
return flow
flow = edmonds_karp(G, 1, 6)
flow.edge
{1: {2: {'flow': 5}, 4: {'flow': 17}}, 2: {3: {'flow': 12}, 5: {'flow': 0}}, 3: {5: {'flow': 0}, 6: {'flow': 12}}, 4: {2: {'flow': 7}, 5: {'flow': 10}}, 5: {6: {'flow': 10}}, 6: {}}
NetworkXを利用した場合と同じ結果が得られた.