python - fulkerson - max flow algorithm

Flujo máximo-Ford-Fulkerson: gráfico no dirigido

Question

Estoy tratando de resolver el problema del flujo de maxium para un gráfico utilizando el algoritmo Ford-Fulkerson. El algoritmo solo se describe con un grafo dirigido. ¿Qué pasa cuando la gráfica no está dirigida?

Lo que he hecho para imitar un gráfico no dirigido es usar dos bordes dirigidos entre un par de vértices. Lo que me confunde es: ¿cada uno de estos bordes debe tener un borde residual o es el borde dirigido "opuesto" el borde residual?

He asumido lo último, pero mi algoritmo parece ir en un bucle infinito. Espero que alguno de ustedes pueda ayudarme. A continuación se muestra mi propia implementación. Estoy usando DFS en encontrar.

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

Su aproximación utilizando dos aristas antiparalelas funciona. Si su borde es a->b (capacidad 10, enviamos 7 sobre él), introducimos un nuevo borde residual (de b a a que tiene capacidad residual 17, el borde residual de a a tiene la capacidad restante 3).

El borde posterior original (de b a a ) se puede dejar como está o el nuevo borde residual y el fondo original se puede fundir en un borde.

Podría imaginar que agregar la capacidad residual al borde posterior original es un poco más simple, pero no estoy seguro de eso.