ioftools / networkxMiCe / networkxmaster / networkx / algorithms / flow / utils.py @ 5cef0f13
History  View  Annotate  Download (5.74 KB)
1 
# * coding: utf8 *


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 outedges 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 
selfloop, 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 
# infinitecapacity 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 
# infinitecapacity edge is always at least 2/3 of inf, while that of an

116 
# finitecapacity 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 infinitecapacity

118 
# st 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 infinitecapacity st 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
