Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / flow / edmondskarp.py @ 5cef0f13

History | View | Annotate | Download (8.01 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Edmonds-Karp algorithm for maximum flow problems.
4
"""
5

    
6
__author__ = """ysitu <ysitu@users.noreply.github.com>"""
7
# Copyright (C) 2014 ysitu <ysitu@users.noreply.github.com>
8
# All rights reserved.
9
# BSD license.
10

    
11
import networkx as nx
12
from networkx.algorithms.flow.utils import *
13

    
14
__all__ = ['edmonds_karp']
15

    
16

    
17
def edmonds_karp_core(R, s, t, cutoff):
18
    """Implementation of the Edmonds-Karp algorithm.
19
    """
20
    R_nodes = R.nodes
21
    R_pred = R.pred
22
    R_succ = R.succ
23

    
24
    inf = R.graph['inf']
25

    
26
    def augment(path):
27
        """Augment flow along a path from s to t.
28
        """
29
        # Determine the path residual capacity.
30
        flow = inf
31
        it = iter(path)
32
        u = next(it)
33
        for v in it:
34
            attr = R_succ[u][v]
35
            flow = min(flow, attr['capacity'] - attr['flow'])
36
            u = v
37
        if flow * 2 > inf:
38
            raise nx.NetworkXUnbounded(
39
                'Infinite capacity path, flow unbounded above.')
40
        # Augment flow along the path.
41
        it = iter(path)
42
        u = next(it)
43
        for v in it:
44
            R_succ[u][v]['flow'] += flow
45
            R_succ[v][u]['flow'] -= flow
46
            u = v
47
        return flow
48

    
49
    def bidirectional_bfs():
50
        """Bidirectional breadth-first search for an augmenting path.
51
        """
52
        pred = {s: None}
53
        q_s = [s]
54
        succ = {t: None}
55
        q_t = [t]
56
        while True:
57
            q = []
58
            if len(q_s) <= len(q_t):
59
                for u in q_s:
60
                    for v, attr in R_succ[u].items():
61
                        if v not in pred and attr['flow'] < attr['capacity']:
62
                            pred[v] = u
63
                            if v in succ:
64
                                return v, pred, succ
65
                            q.append(v)
66
                if not q:
67
                    return None, None, None
68
                q_s = q
69
            else:
70
                for u in q_t:
71
                    for v, attr in R_pred[u].items():
72
                        if v not in succ and attr['flow'] < attr['capacity']:
73
                            succ[v] = u
74
                            if v in pred:
75
                                return v, pred, succ
76
                            q.append(v)
77
                if not q:
78
                    return None, None, None
79
                q_t = q
80

    
81
    # Look for shortest augmenting paths using breadth-first search.
82
    flow_value = 0
83
    while flow_value < cutoff:
84
        v, pred, succ = bidirectional_bfs()
85
        if pred is None:
86
            break
87
        path = [v]
88
        # Trace a path from s to v.
89
        u = v
90
        while u != s:
91
            u = pred[u]
92
            path.append(u)
93
        path.reverse()
94
        # Trace a path from v to t.
95
        u = v
96
        while u != t:
97
            u = succ[u]
98
            path.append(u)
99
        flow_value += augment(path)
100

    
101
    return flow_value
102

    
103

    
104
def edmonds_karp_impl(G, s, t, capacity, residual, cutoff):
105
    """Implementation of the Edmonds-Karp algorithm.
106
    """
107
    if s not in G:
108
        raise nx.NetworkXError('node %s not in graph' % str(s))
109
    if t not in G:
110
        raise nx.NetworkXError('node %s not in graph' % str(t))
111
    if s == t:
112
        raise nx.NetworkXError('source and sink are the same node')
113

    
114
    if residual is None:
115
        R = build_residual_network(G, capacity)
116
    else:
117
        R = residual
118

    
119
    # Initialize/reset the residual network.
120
    for u in R:
121
        for e in R[u].values():
122
            e['flow'] = 0
123

    
124
    if cutoff is None:
125
        cutoff = float('inf')
126
    R.graph['flow_value'] = edmonds_karp_core(R, s, t, cutoff)
127

    
128
    return R
129

    
130

    
131
def edmonds_karp(G, s, t, capacity='capacity', residual=None, value_only=False,
132
                 cutoff=None):
133
    """Find a maximum single-commodity flow using the Edmonds-Karp algorithm.
134

135
    This function returns the residual network resulting after computing
136
    the maximum flow. See below for details about the conventions
137
    NetworkX uses for defining residual networks.
138

139
    This algorithm has a running time of $O(n m^2)$ for $n$ nodes and $m$
140
    edges.
141

142

143
    Parameters
144
    ----------
145
    G : NetworkX graph
146
        Edges of the graph are expected to have an attribute called
147
        'capacity'. If this attribute is not present, the edge is
148
        considered to have infinite capacity.
149

150
    s : node
151
        Source node for the flow.
152

153
    t : node
154
        Sink node for the flow.
155

156
    capacity : string
157
        Edges of the graph G are expected to have an attribute capacity
158
        that indicates how much flow the edge can support. If this
159
        attribute is not present, the edge is considered to have
160
        infinite capacity. Default value: 'capacity'.
161

162
    residual : NetworkX graph
163
        Residual network on which the algorithm is to be executed. If None, a
164
        new residual network is created. Default value: None.
165

166
    value_only : bool
167
        If True compute only the value of the maximum flow. This parameter
168
        will be ignored by this algorithm because it is not applicable.
169

170
    cutoff : integer, float
171
        If specified, the algorithm will terminate when the flow value reaches
172
        or exceeds the cutoff. In this case, it may be unable to immediately
173
        determine a minimum cut. Default value: None.
174

175
    Returns
176
    -------
177
    R : NetworkX DiGraph
178
        Residual network after computing the maximum flow.
179

180
    Raises
181
    ------
182
    NetworkXError
183
        The algorithm does not support MultiGraph and MultiDiGraph. If
184
        the input graph is an instance of one of these two classes, a
185
        NetworkXError is raised.
186

187
    NetworkXUnbounded
188
        If the graph has a path of infinite capacity, the value of a
189
        feasible flow on the graph is unbounded above and the function
190
        raises a NetworkXUnbounded.
191

192
    See also
193
    --------
194
    :meth:`maximum_flow`
195
    :meth:`minimum_cut`
196
    :meth:`preflow_push`
197
    :meth:`shortest_augmenting_path`
198

199
    Notes
200
    -----
201
    The residual network :samp:`R` from an input graph :samp:`G` has the
202
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
203
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
204
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
205
    in :samp:`G`.
206

207
    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
208
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
209
    in :samp:`G` or zero otherwise. If the capacity is infinite,
210
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
211
    that does not affect the solution of the problem. This value is stored in
212
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
213
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
214
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
215

216
    The flow value, defined as the total flow into :samp:`t`, the sink, is
217
    stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
218
    specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
219
    that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
220
    :samp:`s`-:samp:`t` cut.
221

222
    Examples
223
    --------
224
    >>> import networkx as nx
225
    >>> from networkx.algorithms.flow import edmonds_karp
226

227
    The functions that implement flow algorithms and output a residual
228
    network, such as this one, are not imported to the base NetworkX
229
    namespace, so you have to explicitly import them from the flow package.
230

231
    >>> G = nx.DiGraph()
232
    >>> G.add_edge('x','a', capacity=3.0)
233
    >>> G.add_edge('x','b', capacity=1.0)
234
    >>> G.add_edge('a','c', capacity=3.0)
235
    >>> G.add_edge('b','c', capacity=5.0)
236
    >>> G.add_edge('b','d', capacity=4.0)
237
    >>> G.add_edge('d','e', capacity=2.0)
238
    >>> G.add_edge('c','y', capacity=2.0)
239
    >>> G.add_edge('e','y', capacity=3.0)
240
    >>> R = edmonds_karp(G, 'x', 'y')
241
    >>> flow_value = nx.maximum_flow_value(G, 'x', 'y')
242
    >>> flow_value
243
    3.0
244
    >>> flow_value == R.graph['flow_value']
245
    True
246

247
    """
248
    R = edmonds_karp_impl(G, s, t, capacity, residual, cutoff)
249
    R.graph['algorithm'] = 'edmonds_karp'
250
    return R