Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.74 KB)

1
# -*- coding: utf-8 -*-
2
"""
3
Utility classes and functions for network flow algorithms.
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

    
14
__all__ = ['CurrentEdge', 'Level', 'GlobalRelabelThreshold',
15
           'build_residual_network', 'detect_unboundedness', 'build_flow_dict']
16

    
17

    
18
class CurrentEdge(object):
19
    """Mechanism for iterating over out-edges incident to a node in a circular
20
    manner. StopIteration exception is raised when wraparound occurs.
21
    """
22
    __slots__ = ('_edges', '_it', '_curr')
23

    
24
    def __init__(self, edges):
25
        self._edges = edges
26
        if self._edges:
27
            self._rewind()
28

    
29
    def get(self):
30
        return self._curr
31

    
32
    def move_to_next(self):
33
        try:
34
            self._curr = next(self._it)
35
        except StopIteration:
36
            self._rewind()
37
            raise
38

    
39
    def _rewind(self):
40
        self._it = iter(self._edges.items())
41
        self._curr = next(self._it)
42

    
43

    
44
class Level(object):
45
    """Active and inactive nodes in a level.
46
    """
47
    __slots__ = ('active', 'inactive')
48

    
49
    def __init__(self):
50
        self.active = set()
51
        self.inactive = set()
52

    
53

    
54
class GlobalRelabelThreshold(object):
55
    """Measurement of work before the global relabeling heuristic should be
56
    applied.
57
    """
58

    
59
    def __init__(self, n, m, freq):
60
        self._threshold = (n + m) / freq if freq else float('inf')
61
        self._work = 0
62

    
63
    def add_work(self, work):
64
        self._work += work
65

    
66
    def is_reached(self):
67
        return self._work >= self._threshold
68

    
69
    def clear_work(self):
70
        self._work = 0
71

    
72

    
73
def build_residual_network(G, capacity):
74
    """Build a residual network and initialize a zero flow.
75

76
    The residual network :samp:`R` from an input graph :samp:`G` has the
77
    same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
78
    of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
79
    self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
80
    in :samp:`G`.
81

82
    For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
83
    is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
84
    in :samp:`G` or zero otherwise. If the capacity is infinite,
85
    :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
86
    that does not affect the solution of the problem. This value is stored in
87
    :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
88
    :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
89
    satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
90

91
    The flow value, defined as the total flow into :samp:`t`, the sink, is
92
    stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
93
    specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
94
    that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
95
    :samp:`s`-:samp:`t` cut.
96

97
    """
98
    if G.is_multigraph():
99
        raise nx.NetworkXError(
100
            'MultiGraph and MultiDiGraph not supported (yet).')
101

    
102
    R = nx.DiGraph()
103
    R.add_nodes_from(G)
104

    
105
    inf = float('inf')
106
    # Extract edges with positive capacities. Self loops excluded.
107
    edge_list = [(u, v, attr) for u, v, attr in G.edges(data=True)
108
                 if u != v and attr.get(capacity, inf) > 0]
109
    # Simulate infinity with three times the sum of the finite edge capacities
110
    # or any positive value if the sum is zero. This allows the
111
    # infinite-capacity edges to be distinguished for unboundedness detection
112
    # and directly participate in residual capacity calculation. If the maximum
113
    # flow is finite, these edges cannot appear in the minimum cut and thus
114
    # guarantee correctness. Since the residual capacity of an
115
    # infinite-capacity edge is always at least 2/3 of inf, while that of an
116
    # finite-capacity edge is at most 1/3 of inf, if an operation moves more
117
    # than 1/3 of inf units of flow to t, there must be an infinite-capacity
118
    # s-t path in G.
119
    inf = 3 * sum(attr[capacity] for u, v, attr in edge_list
120
                  if capacity in attr and attr[capacity] != inf) or 1
121
    if G.is_directed():
122
        for u, v, attr in edge_list:
123
            r = min(attr.get(capacity, inf), inf)
124
            if not R.has_edge(u, v):
125
                # Both (u, v) and (v, u) must be present in the residual
126
                # network.
127
                R.add_edge(u, v, capacity=r)
128
                R.add_edge(v, u, capacity=0)
129
            else:
130
                # The edge (u, v) was added when (v, u) was visited.
131
                R[u][v]['capacity'] = r
132
    else:
133
        for u, v, attr in edge_list:
134
            # Add a pair of edges with equal residual capacities.
135
            r = min(attr.get(capacity, inf), inf)
136
            R.add_edge(u, v, capacity=r)
137
            R.add_edge(v, u, capacity=r)
138

    
139
    # Record the value simulating infinity.
140
    R.graph['inf'] = inf
141

    
142
    return R
143

    
144

    
145
def detect_unboundedness(R, s, t):
146
    """Detect an infinite-capacity s-t path in R.
147
    """
148
    q = deque([s])
149
    seen = set([s])
150
    inf = R.graph['inf']
151
    while q:
152
        u = q.popleft()
153
        for v, attr in R[u].items():
154
            if attr['capacity'] == inf and v not in seen:
155
                if v == t:
156
                    raise nx.NetworkXUnbounded(
157
                        'Infinite capacity path, flow unbounded above.')
158
                seen.add(v)
159
                q.append(v)
160

    
161

    
162
def build_flow_dict(G, R):
163
    """Build a flow dictionary from a residual network.
164
    """
165
    flow_dict = {}
166
    for u in G:
167
        flow_dict[u] = {v: 0 for v in G[u]}
168
        flow_dict[u].update((v, attr['flow']) for v, attr in R[u].items()
169
                            if attr['flow'] > 0)
170
    return flow_dict