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

Question

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

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: ¿Debería cada uno de estos bordes tener un borde residual o el borde dirigido "opuesto" es el borde residual?

He asumido el último pero mi algoritmo parece ir en un bucle infinito. Espero que alguno de ustedes me pueda ayudar. Debajo está mi propia implementación. Estoy usando DFS en 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) 

Answer 1

Su enfoque utilizando dos bordes antiparalelos 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 b tiene la capacidad restante 3).

El borde posterior original (desde b hasta a) puede dejarse tal cual o el borde residual nuevo y el borde posterior original pueden derretirse en un borde.

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