最大流量 - 福特 - 富尔克森：无向图 [英] Maximum flow - Ford-Fulkerson: Undirected graph
问题描述
我要解决的最大信号流问题，使用福特Fulkerson算法的曲线图。该算法只与一个有向图说明。什么时候是无向图？
我所做的模拟无向图是使用一对顶点之间的两个向边。什么困惑我的是：如果每个边再有残留的边缘或者说是相对向边的残留边
我已经承担了最后，但我的算法似乎走在一个无限循环。我希望你们中的任何可以给我一些帮助。下面是我自己的实现。我在查找使用DFS。
进口SYS
进口的FileInput
一流的顶点（对象）：
高清__init __（个体经营，名）：
self.name =名称
self.edges = []
高清发现（个体经营，水槽，路径）：
如果（个体经营==汇）：
返回路径
在self.edges优势：
剩余= edge.capacity - edge.flow
如果（剩余大于0或edge.inf）：
如果（没有路径和edge.oppositeEdge不在路径边）：
toVertex = edge.toVertex
path.append（边）
结果= toVertex.find（水槽，路径）
如果结果=无！
返回结果
类边缘（对象）：
高清__init __（个体经营，fromVertex，toVertex，容量）：
self.fromVertex = fromVertex
self.toVertex = toVertex
self.capacity =能力
self.flow = 0
self.inf =假
如果（容量== -1）：
self.inf = TRUE
高清__repr __（个体经营）：
返回self.fromVertex.name.strip（）+ - + self.toVertex.name.strip（）
高清buildGraph（顶点，边）：
在边缘的边缘：
sourceVertex =顶点[INT（边缘[0]）]
sinkVertex =顶点[INT（边缘[1]）
容量= INT（边缘[2]）
边沿1 =边缘（sourceVertex，sinkVertex，容量）
EDGE2 =边缘（sinkVertex，sourceVertex，容量）
sourceVertex.edges.append（边沿1）
sinkVertex.edges.append（EDGE2）
edge1.oppositeEdge = EDGE2
edge2.oppositeEdge = EDGE1
高清maxFlow（源汇）：
PATH = source.find（水槽，[]）
而路径=无！
minCap =所有的sys.maxint
为电子商务的路径：
如果（e.capacity＆LT; minCap而不是e.inf）：
minCap = e.capacity
在路径的边缘：
edge.flow + = minCap
edge.oppositeEdge.flow - = minCap
PATH = source.find（水槽，[]）
返回总和（e.flow为电子在source.edges）
顶点，边=解析（）
buildGraph（顶点，边）
来源=顶点[0]
汇=顶点[LEN（顶点）-1]
maxFlow = maxFlow（源汇）
使用两个反向平行的边缘作品你的方法。如果你的优势是 A-＆GT; b （容量10，我们送7在它），我们引入一个新的剩余边缘（距离 B 到 A 拥有剩余容量17，从残留的边缘 A 到 B 的剩余容量3）。
原来的背边缘（距离 B 到 A ）可以保持原样或新的残留边缘和原始回边可熔为一体的边缘
我能想象，加入剩余容量到原来的背缘是有点简单，但不知道这一点。
I am trying to solve the maxium flow problem for a graph using Ford–Fulkerson algorithm. The algorithm is only described with a directed graph. What about when the graph is undirected?
What I have done to mimic an undirected graph is to use two directed edges between a pair of vertices. What confuses me is: Should each of these edges then have a residual edge or is the "opposite" directed edge the residual edge?
I have assumed the last but my algorithm seems to go in an infinite loop. I hope any of you can give me some help. Below is my own implementation. I am using DFS in find.
import sys
import fileinput
class Vertex(object):
def __init__(self, name):
self.name = name
self.edges = []
def find(self, sink, path):
if(self == sink):
return path
for edge in self.edges:
residual = edge.capacity - edge.flow
if(residual > 0 or edge.inf):
if(edge not in path and edge.oppositeEdge not in path):
toVertex = edge.toVertex
path.append(edge)
result = toVertex.find(sink, path)
if result != None:
return result
class Edge(object):
def __init__(self, fromVertex, toVertex, capacity):
self.fromVertex = fromVertex
self.toVertex = toVertex
self.capacity = capacity
self.flow = 0
self.inf = False
if(capacity == -1):
self.inf = True
def __repr__(self):
return self.fromVertex.name.strip() + " - " + self.toVertex.name.strip()
def buildGraph(vertices, edges):
for edge in edges:
sourceVertex = vertices[int(edge[0])]
sinkVertex = vertices[int(edge[1])]
capacity = int(edge[2])
edge1 = Edge(sourceVertex, sinkVertex, capacity)
edge2 = Edge(sinkVertex, sourceVertex, capacity)
sourceVertex.edges.append(edge1)
sinkVertex.edges.append(edge2)
edge1.oppositeEdge = edge2
edge2.oppositeEdge = edge1
def maxFlow(source, sink):
path = source.find(sink, [])
while path != None:
minCap = sys.maxint
for e in path:
if(e.capacity < minCap and not e.inf):
minCap = e.capacity
for edge in path:
edge.flow += minCap
edge.oppositeEdge.flow -= minCap
path = source.find(sink, [])
return sum(e.flow for e in source.edges)
vertices, edges = parse()
buildGraph(vertices, edges)
source = vertices[0]
sink = vertices[len(vertices)-1]
maxFlow = maxFlow(source, sink)
Your approach using two antiparallel edges works. If your edge is a->b (capacity 10, we send 7 over it), we introduce a new residual edge (from b to a that has residual capacity 17, the residual edge from a to b has the remaining capacity 3).
The original back-edge (from b to a) can be left as it is or the new residual edge and the original backedge can be melt into one edge.
I could imagine that adding the residual capacity to the original back-edge is a bit simpler, but not sure about that.
这篇关于最大流量 - 福特 - 富尔克森：无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
