Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (10.3 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Shortest augmenting path 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
from collections import deque
12
import networkx as nx
13
from .utils import *
14
from .edmondskarp import edmonds_karp_core
15

    
16
__all__ = ['shortest_augmenting_path']
17

    
18

    
19
def shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase,
20
                                  cutoff):
21
    """Implementation of the shortest augmenting path algorithm.
22
    """
23
    if s not in G:
24
        raise nx.NetworkXError('node %s not in graph' % str(s))
25
    if t not in G:
26
        raise nx.NetworkXError('node %s not in graph' % str(t))
27
    if s == t:
28
        raise nx.NetworkXError('source and sink are the same node')
29

    
30
    if residual is None:
31
        R = build_residual_network(G, capacity)
32
    else:
33
        R = residual
34

    
35
    R_nodes = R.nodes
36
    R_pred = R.pred
37
    R_succ = R.succ
38

    
39
    # Initialize/reset the residual network.
40
    for u in R:
41
        for e in R_succ[u].values():
42
            e['flow'] = 0
43

    
44
    # Initialize heights of the nodes.
45
    heights = {t: 0}
46
    q = deque([(t, 0)])
47
    while q:
48
        u, height = q.popleft()
49
        height += 1
50
        for v, attr in R_pred[u].items():
51
            if v not in heights and attr['flow'] < attr['capacity']:
52
                heights[v] = height
53
                q.append((v, height))
54

    
55
    if s not in heights:
56
        # t is not reachable from s in the residual network. The maximum flow
57
        # must be zero.
58
        R.graph['flow_value'] = 0
59
        return R
60

    
61
    n = len(G)
62
    m = R.size() / 2
63

    
64
    # Initialize heights and 'current edge' data structures of the nodes.
65
    for u in R:
66
        R_nodes[u]['height'] = heights[u] if u in heights else n
67
        R_nodes[u]['curr_edge'] = CurrentEdge(R_succ[u])
68

    
69
    # Initialize counts of nodes in each level.
70
    counts = [0] * (2 * n - 1)
71
    for u in R:
72
        counts[R_nodes[u]['height']] += 1
73

    
74
    inf = R.graph['inf']
75

    
76
    def augment(path):
77
        """Augment flow along a path from s to t.
78
        """
79
        # Determine the path residual capacity.
80
        flow = inf
81
        it = iter(path)
82
        u = next(it)
83
        for v in it:
84
            attr = R_succ[u][v]
85
            flow = min(flow, attr['capacity'] - attr['flow'])
86
            u = v
87
        if flow * 2 > inf:
88
            raise nx.NetworkXUnbounded(
89
                'Infinite capacity path, flow unbounded above.')
90
        # Augment flow along the path.
91
        it = iter(path)
92
        u = next(it)
93
        for v in it:
94
            R_succ[u][v]['flow'] += flow
95
            R_succ[v][u]['flow'] -= flow
96
            u = v
97
        return flow
98

    
99
    def relabel(u):
100
        """Relabel a node to create an admissible edge.
101
        """
102
        height = n - 1
103
        for v, attr in R_succ[u].items():
104
            if attr['flow'] < attr['capacity']:
105
                height = min(height, R_nodes[v]['height'])
106
        return height + 1
107

    
108
    if cutoff is None:
109
        cutoff = float('inf')
110

    
111
    # Phase 1: Look for shortest augmenting paths using depth-first search.
112

    
113
    flow_value = 0
114
    path = [s]
115
    u = s
116
    d = n if not two_phase else int(min(m ** 0.5, 2 * n ** (2. / 3)))
117
    done = R_nodes[s]['height'] >= d
118
    while not done:
119
        height = R_nodes[u]['height']
120
        curr_edge = R_nodes[u]['curr_edge']
121
        # Depth-first search for the next node on the path to t.
122
        while True:
123
            v, attr = curr_edge.get()
124
            if (height == R_nodes[v]['height'] + 1 and
125
                    attr['flow'] < attr['capacity']):
126
                # Advance to the next node following an admissible edge.
127
                path.append(v)
128
                u = v
129
                break
130
            try:
131
                curr_edge.move_to_next()
132
            except StopIteration:
133
                counts[height] -= 1
134
                if counts[height] == 0:
135
                    # Gap heuristic: If relabeling causes a level to become
136
                    # empty, a minimum cut has been identified. The algorithm
137
                    # can now be terminated.
138
                    R.graph['flow_value'] = flow_value
139
                    return R
140
                height = relabel(u)
141
                if u == s and height >= d:
142
                    if not two_phase:
143
                        # t is disconnected from s in the residual network. No
144
                        # more augmenting paths exist.
145
                        R.graph['flow_value'] = flow_value
146
                        return R
147
                    else:
148
                        # t is at least d steps away from s. End of phase 1.
149
                        done = True
150
                        break
151
                counts[height] += 1
152
                R_nodes[u]['height'] = height
153
                if u != s:
154
                    # After relabeling, the last edge on the path is no longer
155
                    # admissible. Retreat one step to look for an alternative.
156
                    path.pop()
157
                    u = path[-1]
158
                    break
159
        if u == t:
160
            # t is reached. Augment flow along the path and reset it for a new
161
            # depth-first search.
162
            flow_value += augment(path)
163
            if flow_value >= cutoff:
164
                R.graph['flow_value'] = flow_value
165
                return R
166
            path = [s]
167
            u = s
168

    
169
    # Phase 2: Look for shortest augmenting paths using breadth-first search.
170
    flow_value += edmonds_karp_core(R, s, t, cutoff - flow_value)
171

    
172
    R.graph['flow_value'] = flow_value
173
    return R
174

    
175

    
176
def shortest_augmenting_path(G, s, t, capacity='capacity', residual=None,
177
                             value_only=False, two_phase=False, cutoff=None):
178
    r"""Find a maximum single-commodity flow using the shortest augmenting path
179
    algorithm.
180

181
    This function returns the residual network resulting after computing
182
    the maximum flow. See below for details about the conventions
183
    NetworkX uses for defining residual networks.
184

185
    This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$
186
    edges.
187

188

189
    Parameters
190
    ----------
191
    G : NetworkX graph
192
        Edges of the graph are expected to have an attribute called
193
        'capacity'. If this attribute is not present, the edge is
194
        considered to have infinite capacity.
195

196
    s : node
197
        Source node for the flow.
198

199
    t : node
200
        Sink node for the flow.
201

202
    capacity : string
203
        Edges of the graph G are expected to have an attribute capacity
204
        that indicates how much flow the edge can support. If this
205
        attribute is not present, the edge is considered to have
206
        infinite capacity. Default value: 'capacity'.
207

208
    residual : NetworkX graph
209
        Residual network on which the algorithm is to be executed. If None, a
210
        new residual network is created. Default value: None.
211

212
    value_only : bool
213
        If True compute only the value of the maximum flow. This parameter
214
        will be ignored by this algorithm because it is not applicable.
215

216
    two_phase : bool
217
        If True, a two-phase variant is used. The two-phase variant improves
218
        the running time on unit-capacity networks from $O(nm)$ to
219
        $O(\min(n^{2/3}, m^{1/2}) m)$. Default value: False.
220

221
    cutoff : integer, float
222
        If specified, the algorithm will terminate when the flow value reaches
223
        or exceeds the cutoff. In this case, it may be unable to immediately
224
        determine a minimum cut. Default value: None.
225

226
    Returns
227
    -------
228
    R : NetworkX DiGraph
229
        Residual network after computing the maximum flow.
230

231
    Raises
232
    ------
233
    NetworkXError
234
        The algorithm does not support MultiGraph and MultiDiGraph. If
235
        the input graph is an instance of one of these two classes, a
236
        NetworkXError is raised.
237

238
    NetworkXUnbounded
239
        If the graph has a path of infinite capacity, the value of a
240
        feasible flow on the graph is unbounded above and the function
241
        raises a NetworkXUnbounded.
242

243
    See also
244
    --------
245
    :meth:`maximum_flow`
246
    :meth:`minimum_cut`
247
    :meth:`edmonds_karp`
248
    :meth:`preflow_push`
249

250
    Notes
251
    -----
252
    The residual network :samp:`R` from an input graph :samp:`G` has the
253
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
254
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
255
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
256
    in :samp:`G`.
257

258
    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
259
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
260
    in :samp:`G` or zero otherwise. If the capacity is infinite,
261
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
262
    that does not affect the solution of the problem. This value is stored in
263
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
264
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
265
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
266

267
    The flow value, defined as the total flow into :samp:`t`, the sink, is
268
    stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
269
    specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
270
    that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
271
    :samp:`s`-:samp:`t` cut.
272

273
    Examples
274
    --------
275
    >>> import networkx as nx
276
    >>> from networkx.algorithms.flow import shortest_augmenting_path
277

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

282
    >>> G = nx.DiGraph()
283
    >>> G.add_edge('x','a', capacity=3.0)
284
    >>> G.add_edge('x','b', capacity=1.0)
285
    >>> G.add_edge('a','c', capacity=3.0)
286
    >>> G.add_edge('b','c', capacity=5.0)
287
    >>> G.add_edge('b','d', capacity=4.0)
288
    >>> G.add_edge('d','e', capacity=2.0)
289
    >>> G.add_edge('c','y', capacity=2.0)
290
    >>> G.add_edge('e','y', capacity=3.0)
291
    >>> R = shortest_augmenting_path(G, 'x', 'y')
292
    >>> flow_value = nx.maximum_flow_value(G, 'x', 'y')
293
    >>> flow_value
294
    3.0
295
    >>> flow_value == R.graph['flow_value']
296
    True
297

298
    """
299
    R = shortest_augmenting_path_impl(G, s, t, capacity, residual, two_phase,
300
                                      cutoff)
301
    R.graph['algorithm'] = 'shortest_augmenting_path'
302
    return R