Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# Source code for networkx.algorithms.flow.fordfulkerson

# -*- coding: utf-8 -*-
"""
Legacy implementation of the Edmonds-Karp algorithm for maximum flow problems.
"""

__author__ = """Loïc Séguin-C. <loicseguin@gmail.com>"""
# Copyright (C) 2010 Loïc Séguin-C. <loicseguin@gmail.com>

import networkx as nx

__all__ = ['ford_fulkerson']

def ford_fulkerson_impl(G, s, t, capacity):
"""Legacy implementation of the Edmonds-Karp algorithm"""
if G.is_multigraph():
raise nx.NetworkXError(
'MultiGraph and MultiDiGraph not supported (yet).')

if s not in G:
raise nx.NetworkXError('node %s not in graph' % str(s))
if t not in G:
raise nx.NetworkXError('node %s not in graph' % str(t))
if s == t:
raise nx.NetworkXError('source and sink are the same node')

auxiliary = _create_auxiliary_digraph(G, capacity=capacity)
inf_capacity_flows = auxiliary.graph['inf_capacity_flows']

flow_value = 0   # Initial feasible flow.

# As long as there is an (s, t)-path in the auxiliary digraph, find
# the shortest (with respect to the number of arcs) such path and
# augment the flow on this path.
while True:
try:
path_nodes = nx.bidirectional_shortest_path(auxiliary, s, t)
except nx.NetworkXNoPath:
break

# Get the list of edges in the shortest path.
path_edges = list(zip(path_nodes[:-1], path_nodes[1:]))

# Find the minimum capacity of an edge in the path.
try:
path_capacity = min([auxiliary[u][v][capacity]
for u, v in path_edges
if capacity in auxiliary[u][v]])
except ValueError:
# path of infinite capacity implies no max flow
raise nx.NetworkXUnbounded(
"Infinite capacity path, flow unbounded above.")

flow_value += path_capacity

# Augment the flow along the path.
for u, v in path_edges:
edge_attr = auxiliary[u][v]
if capacity in edge_attr:
edge_attr[capacity] -= path_capacity
if edge_attr[capacity] == 0:
auxiliary.remove_edge(u, v)
else:
inf_capacity_flows[(u, v)] += path_capacity

if auxiliary.has_edge(v, u):
if capacity in auxiliary[v][u]:
auxiliary[v][u][capacity] += path_capacity
else:

auxiliary.graph['inf_capacity_flows'] = inf_capacity_flows
return flow_value, auxiliary

def _create_auxiliary_digraph(G, capacity='capacity'):
"""Initialize an auxiliary digraph and dict of infinite capacity
edges for a given graph G.
Ignore edges with capacity <= 0.
"""
auxiliary = nx.DiGraph()
inf_capacity_flows = {}
if nx.is_directed(G):
for edge in G.edges(data = True):
if capacity in edge[2]:
if edge[2][capacity] > 0:
else:
inf_capacity_flows[(edge[0], edge[1])] = 0
else:
for edge in G.edges(data = True):
if capacity in edge[2]:
if edge[2][capacity] > 0:
else:
inf_capacity_flows[(edge[0], edge[1])] = 0
inf_capacity_flows[(edge[1], edge[0])] = 0

auxiliary.graph['inf_capacity_flows'] = inf_capacity_flows
return auxiliary

def _create_flow_dict(G, H, capacity='capacity'):
"""Creates the flow dict of dicts on G corresponding to the
auxiliary digraph H and infinite capacity edges flows
inf_capacity_flows.
"""
inf_capacity_flows = H.graph['inf_capacity_flows']
flow = dict([(u, {}) for u in G])

if G.is_directed():
for u, v in G.edges_iter():
if H.has_edge(u, v):
if capacity in G[u][v]:
flow[u][v] = max(0, G[u][v][capacity] - H[u][v][capacity])
elif G.has_edge(v, u) and not capacity in G[v][u]:
flow[u][v] = max(0, inf_capacity_flows[(u, v)] -
inf_capacity_flows[(v, u)])
else:
flow[u][v] = max(0, H[v].get(u, {}).get(capacity, 0) -
G[v].get(u, {}).get(capacity, 0))
else:
flow[u][v] = G[u][v][capacity]

else: # undirected
for u, v in G.edges_iter():
if H.has_edge(u, v):
if capacity in G[u][v]:
flow[u][v] = abs(G[u][v][capacity] - H[u][v][capacity])
else:
flow[u][v] = abs(inf_capacity_flows[(u, v)] -
inf_capacity_flows[(v, u)])
else:
flow[u][v] = G[u][v][capacity]
flow[v][u] = flow[u][v]

return flow

[docs]def ford_fulkerson(G, s, t, capacity='capacity'): """Find a maximum single-commodity flow using the Ford-Fulkerson algorithm. This is the legacy implementation of maximum flow. See Notes below. This algorithm uses Edmonds-Karp-Dinitz path selection rule which guarantees a running time of O(nm^2) for n nodes and m edges. Parameters ---------- G : NetworkX graph Edges of the graph are expected to have an attribute called 'capacity'. If this attribute is not present, the edge is considered to have infinite capacity. s : node Source node for the flow. t : node Sink node for the flow. capacity : string Edges of the graph G are expected to have an attribute capacity that indicates how much flow the edge can support. If this attribute is not present, the edge is considered to have infinite capacity. Default value: 'capacity'. Returns ------- R : NetworkX DiGraph The residual network after computing the maximum flow. This is a legacy implementation, se Notes and Examples. Raises ------ NetworkXError The algorithm does not support MultiGraph and MultiDiGraph. If the input graph is an instance of one of these two classes, a NetworkXError is raised. NetworkXUnbounded If the graph has a path of infinite capacity, the value of a feasible flow on the graph is unbounded above and the function raises a NetworkXUnbounded. See also -------- :meth:maximum_flow :meth:minimum_cut :meth:edmonds_karp :meth:preflow_push :meth:shortest_augmenting_path Notes ----- This is a legacy implementation of maximum flow (before 1.9). This function used to return a tuple with the flow value and the flow dictionary. Now it returns the residual network resulting after computing the maximum flow, in order to follow the new interface to flow algorithms introduced in NetworkX 1.9. Note however that the residual network returned by this function does not follow the conventions for residual networks used by the new algorithms introduced in 1.9. This residual network has edges with capacity equal to the capacity of the edge in the original network minus the flow that went throught that edge. A dictionary with infinite capacity edges can be found as an attribute of the residual network. Examples -------- >>> import networkx as nx >>> from networkx.algorithms.flow import ford_fulkerson The functions that implement flow algorithms and output a residual network, such as this one, are not imported to the base NetworkX namespace, so you have to explicitly import them from the flow package. >>> G = nx.DiGraph() >>> G.add_edge('x','a', capacity=3.0) >>> G.add_edge('x','b', capacity=1.0) >>> G.add_edge('a','c', capacity=3.0) >>> G.add_edge('b','c', capacity=5.0) >>> G.add_edge('b','d', capacity=4.0) >>> G.add_edge('d','e', capacity=2.0) >>> G.add_edge('c','y', capacity=2.0) >>> G.add_edge('e','y', capacity=3.0) This function returns the residual network after computing the maximum flow. This network has graph attributes that contain: a dictionary with edges with infinite capacity flows, the flow value, and a dictionary of flows: >>> R = ford_fulkerson(G, 'x', 'y') >>> # A dictionary with infinite capacity flows can be found as an >>> # attribute of the residual network >>> inf_capacity_flows = R.graph['inf_capacity_flows'] >>> # There are also attributes for the flow value and the flow dict >>> flow_value = R.graph['flow_value'] >>> flow_dict = R.graph['flow_dict'] You can use the interface to flow algorithms introduced in 1.9 to get the output that the function ford_fulkerson used to produce: >>> flow_value, flow_dict = nx.maximum_flow(G, 'x', 'y', ... flow_func=ford_fulkerson) """ flow_value, R = ford_fulkerson_impl(G, s, t, capacity=capacity) flow_dict = _create_flow_dict(G, R, capacity=capacity) R.graph['flow_value'] = flow_value R.graph['flow_dict'] = flow_dict R.graph['algorithm'] = 'ford_fulkerson_legacy' return R