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>
# All rights reserved.
# BSD license.
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.add_edge(v, u, {capacity: path_capacity})
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()
auxiliary.add_nodes_from(G)
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:
auxiliary.add_edge(*edge)
else:
auxiliary.add_edge(*edge)
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:
auxiliary.add_edge(*edge)
auxiliary.add_edge(edge[1], edge[0], edge[2])
else:
auxiliary.add_edge(*edge)
auxiliary.add_edge(edge[1], edge[0], edge[2])
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