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.