python - 最大流量 - Ford-Fulkerson : Undirected graph

Question

我正在尝试使用 Ford-Fulkerson 算法解决图的最大流量问题。该算法仅用有向图描述。当图是无向的时候呢？

我模拟无向图的方法是在一对顶点之间使用两条有向边。让我感到困惑的是:这些边中的每一个是否应该有一个剩余边，或者“相反”的有向边是剩余边吗？

我假设是最后一个，但我的算法似乎陷入了无限循环。我希望你们中的任何人都可以给我一些帮助。下面是我自己的实现。我在查找中使用 DFS。

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)

Answer 1

您使用两个反平行边的方法有效。如果你的边是 a->b(容量 10，我们在上面发送 7)，我们引入一个新的剩余边(从 b 到 a 具有剩余容量 17，从 a 到 b 的剩余边具有剩余容量 3)。

原来的后边(从b到a)可以保持原样，或者新的残边和原来的后边可以融合成一条边。

我可以想象将剩余容量添加到原始后端会更简单一些，但不确定。