Add option to reuse residual networks in maxflow algorithms

1 files changed, 26 insertions, 19 deletions

diff --git a/networkx/algorithms/flow/utils.py b/networkx/algorithms/flow/utils.py
index 3fa9289b..54fa1b21 100644
--- a/networkx/algorithms/flow/utils.py
+++ b/networkx/algorithms/flow/utils.py
@@ -12,7 +12,7 @@ from collections import deque
 import networkx as nx
 
 __all__ = ['CurrentEdge', 'Level', 'GlobalRelabelThreshold',
-           'build_residual_network', 'build_flow_dict']
+           'build_residual_network', 'detect_unboundedness', 'build_flow_dict']
 
 
 class CurrentEdge(object):
@@ -75,7 +75,7 @@ def build_residual_network(G, s, t, capacity):
     """
     if G.is_multigraph():
         raise nx.NetworkXError(
-                'MultiGraph and MultiDiGraph not supported (yet).')
+            'MultiGraph and MultiDiGraph not supported (yet).')
 
     if s not in G:
         raise nx.NetworkXError('node %s not in graph' % str(s))
@@ -85,19 +85,23 @@ def build_residual_network(G, s, t, capacity):
         raise nx.NetworkXError('source and sink are the same node')
 
     R = nx.DiGraph()
-    R.add_nodes_from(G, excess=0)
+    R.add_nodes_from(G)
 
     inf = float('inf')
     # Extract edges with positive capacities. Self loops excluded.
     edge_list = [(u, v, attr) for u, v, attr in G.edges_iter(data=True)
                  if u != v and attr.get(capacity, inf) > 0]
-    # Simulate infinity with twice the sum of the finite edge capacities or any
-    # positive value if the sum is zero. This allows the infinite-capacity
-    # edges to be distinguished for unboundedness detection and directly
-    # participate in residual capacity calculation. If the maximum flow is
-    # finite, these edges cannot appear in the minimum cut and thus guarantee
-    # correctness.
-    inf = 2 * sum(attr[capacity] for u, v, attr in edge_list
+    # Simulate infinity with three times the sum of the finite edge capacities
+    # or any positive value if the sum is zero. This allows the
+    # infinite-capacity edges to be distinguished for unboundedness detection
+    # and directly participate in residual capacity calculation. If the maximum
+    # flow is finite, these edges cannot appear in the minimum cut and thus
+    # guarantee correctness. Since the residual capacity of an
+    # infinite-capacity edge is always at least 2/3 of inf, while that of an
+    # finite-capacity edge is at most 1/3 of inf, if an operation moves more
+    # than 1/3 of inf units of flow to t, there must be an infinite-capacity
+    # s-t path in G.
+    inf = 3 * sum(attr[capacity] for u, v, attr in edge_list
                   if capacity in attr and attr[capacity] != inf) or 1
     if G.is_directed():
         for u, v, attr in edge_list:
@@ -105,8 +109,8 @@ def build_residual_network(G, s, t, capacity):
             if not R.has_edge(u, v):
                 # Both (u, v) and (v, u) must be present in the residual
                 # network.
-                R.add_edge(u, v, capacity=r, flow=0)
-                R.add_edge(v, u, capacity=0, flow=0)
+                R.add_edge(u, v, capacity=r)
+                R.add_edge(v, u, capacity=0)
             else:
                 # The edge (u, v) was added when (v, u) was visited.
                 R[u][v]['capacity'] = r
@@ -114,28 +118,31 @@ def build_residual_network(G, s, t, capacity):
         for u, v, attr in edge_list:
             # Add a pair of edges with equal residual capacities.
             r = min(attr.get(capacity, inf), inf)
-            R.add_edge(u, v, capacity=r, flow=0)
-            R.add_edge(v, u, capacity=r, flow=0)
+            R.add_edge(u, v, capacity=r)
+            R.add_edge(v, u, capacity=r)
 
     # Record the value simulating infinity.
     R.graph['inf'] = inf
 
-    # Detect unboundedness by determining reachability of t from s using only
-    # infinite-capacity edges.
+    return R
+
+
+def detect_unboundedness(R, s, t):
+    """Detect an infinite-capacity s-t path in R.
+    """
     q = deque([s])
     seen = set([s])
+    inf = R.graph['inf']
     while q:
         u = q.popleft()
         for v, attr in R[u].items():
             if attr['capacity'] == inf and v not in seen:
                 if v == t:
                     raise nx.NetworkXUnbounded(
-                            'Infinite capacity path, flow unbounded above.')
+                        'Infinite capacity path, flow unbounded above.')
                 seen.add(v)
                 q.append(v)
 
-    return R
-
 
 def build_flow_dict(G, R):
     """Build a flow dictionary from a residual network.