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


2 
# Copyright (C) 20042019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Eben Kenah

10 
# Aric Hagberg (hagberg@lanl.gov)

11 
# Christopher Ellison

12 
# Ben Edwards (bedwards@cs.unm.edu)

13 
"""Strongly connected components."""

14 
import warnings as _warnings 
15 
import networkx as nx 
16 
from networkx.utils.decorators import not_implemented_for 
17  
18 
__all__ = ['number_strongly_connected_components',

19 
'strongly_connected_components',

20 
'strongly_connected_component_subgraphs',

21 
'is_strongly_connected',

22 
'strongly_connected_components_recursive',

23 
'kosaraju_strongly_connected_components',

24 
'condensation']

25  
26  
27 
@not_implemented_for('undirected') 
28 
def strongly_connected_components(G): 
29 
"""Generate nodes in strongly connected components of graph.

30 

31 
Parameters

32 


33 
G : NetworkX Graph

34 
A directed graph.

35 

36 
Returns

37 


38 
comp : generator of sets

39 
A generator of sets of nodes, one for each strongly connected

40 
component of G.

41 

42 
Raises

43 


44 
NetworkXNotImplemented :

45 
If G is undirected.

46 

47 
Examples

48 


49 
Generate a sorted list of strongly connected components, largest first.

50 

51 
>>> G = nx.cycle_graph(4, create_using=nx.DiGraph())

52 
>>> nx.add_cycle(G, [10, 11, 12])

53 
>>> [len(c) for c in sorted(nx.strongly_connected_components(G),

54 
... key=len, reverse=True)]

55 
[4, 3]

56 

57 
If you only want the largest component, it's more efficient to

58 
use max instead of sort.

59 

60 
>>> largest = max(nx.strongly_connected_components(G), key=len)

61 

62 
See Also

63 


64 
connected_components

65 
weakly_connected_components

66 
kosaraju_strongly_connected_components

67 

68 
Notes

69 


70 
Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_.

71 
Nonrecursive version of algorithm.

72 

73 
References

74 


75 
.. [1] Depthfirst search and linear graph algorithms, R. Tarjan

76 
SIAM Journal of Computing 1(2):146160, (1972).

77 

78 
.. [2] On finding the strongly connected components in a directed graph.

79 
E. Nuutila and E. SoisalonSoinen

80 
Information Processing Letters 49(1): 914, (1994)..

81 

82 
"""

83 
nbrs = {} 
84 
preorder = {} 
85 
lowlink = {} 
86 
scc_found = {} 
87 
scc_queue = [] 
88 
i = 0 # Preorder counter 
89 
for source in G: 
90 
if source not in scc_found: 
91 
queue = [source] 
92 
while queue:

93 
v = queue[1]

94 
if v not in preorder: 
95 
i = i + 1

96 
preorder[v] = i 
97 
done = 1

98 
if v not in nbrs: 
99 
nbrs[v] = iter(G[v])

100 
v_nbrs = nbrs[v] 
101 
for w in v_nbrs: 
102 
if w not in preorder: 
103 
queue.append(w) 
104 
done = 0

105 
break

106 
if done == 1: 
107 
lowlink[v] = preorder[v] 
108 
for w in G[v]: 
109 
if w not in scc_found: 
110 
if preorder[w] > preorder[v]:

111 
lowlink[v] = min([lowlink[v], lowlink[w]])

112 
else:

113 
lowlink[v] = min([lowlink[v], preorder[w]])

114 
queue.pop() 
115 
if lowlink[v] == preorder[v]:

116 
scc_found[v] = True

117 
scc = {v} 
118 
while scc_queue and preorder[scc_queue[1]] > preorder[v]: 
119 
k = scc_queue.pop() 
120 
scc_found[k] = True

121 
scc.add(k) 
122 
yield scc

123 
else:

124 
scc_queue.append(v) 
125  
126  
127 
@not_implemented_for('undirected') 
128 
def kosaraju_strongly_connected_components(G, source=None): 
129 
"""Generate nodes in strongly connected components of graph.

130 

131 
Parameters

132 


133 
G : NetworkX Graph

134 
A directed graph.

135 

136 
Returns

137 


138 
comp : generator of sets

139 
A genrator of sets of nodes, one for each strongly connected

140 
component of G.

141 

142 
Raises

143 


144 
NetworkXNotImplemented:

145 
If G is undirected.

146 

147 
Examples

148 


149 
Generate a sorted list of strongly connected components, largest first.

150 

151 
>>> G = nx.cycle_graph(4, create_using=nx.DiGraph())

152 
>>> nx.add_cycle(G, [10, 11, 12])

153 
>>> [len(c) for c in sorted(nx.kosaraju_strongly_connected_components(G),

154 
... key=len, reverse=True)]

155 
[4, 3]

156 

157 
If you only want the largest component, it's more efficient to

158 
use max instead of sort.

159 

160 
>>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len)

161 

162 
See Also

163 


164 
strongly_connected_components

165 

166 
Notes

167 


168 
Uses Kosaraju's algorithm.

169 

170 
"""

171 
with nx.utils.reversed(G):

172 
post = list(nx.dfs_postorder_nodes(G, source=source))

173  
174 
seen = set()

175 
while post:

176 
r = post.pop() 
177 
if r in seen: 
178 
continue

179 
c = nx.dfs_preorder_nodes(G, r) 
180 
new = {v for v in c if v not in seen} 
181 
yield new

182 
seen.update(new) 
183  
184  
185 
@not_implemented_for('undirected') 
186 
def strongly_connected_components_recursive(G): 
187 
"""Generate nodes in strongly connected components of graph.

188 

189 
Recursive version of algorithm.

190 

191 
Parameters

192 


193 
G : NetworkX Graph

194 
A directed graph.

195 

196 
Returns

197 


198 
comp : generator of sets

199 
A generator of sets of nodes, one for each strongly connected

200 
component of G.

201 

202 
Raises

203 


204 
NetworkXNotImplemented :

205 
If G is undirected.

206 

207 
Examples

208 


209 
Generate a sorted list of strongly connected components, largest first.

210 

211 
>>> G = nx.cycle_graph(4, create_using=nx.DiGraph())

212 
>>> nx.add_cycle(G, [10, 11, 12])

213 
>>> [len(c) for c in sorted(nx.strongly_connected_components_recursive(G),

214 
... key=len, reverse=True)]

215 
[4, 3]

216 

217 
If you only want the largest component, it's more efficient to

218 
use max instead of sort.

219 

220 
>>> largest = max(nx.strongly_connected_components_recursive(G), key=len)

221 

222 
See Also

223 


224 
connected_components

225 

226 
Notes

227 


228 
Uses Tarjan's algorithm[1]_ with Nuutila's modifications[2]_.

229 

230 
References

231 


232 
.. [1] Depthfirst search and linear graph algorithms, R. Tarjan

233 
SIAM Journal of Computing 1(2):146160, (1972).

234 

235 
.. [2] On finding the strongly connected components in a directed graph.

236 
E. Nuutila and E. SoisalonSoinen

237 
Information Processing Letters 49(1): 914, (1994)..

238 

239 
"""

240 
def visit(v, cnt): 
241 
root[v] = cnt 
242 
visited[v] = cnt 
243 
cnt += 1

244 
stack.append(v) 
245 
for w in G[v]: 
246 
if w not in visited: 
247 
for c in visit(w, cnt): 
248 
yield c

249 
if w not in component: 
250 
root[v] = min(root[v], root[w])

251 
if root[v] == visited[v]:

252 
component[v] = root[v] 
253 
tmpc = {v} # hold nodes in this component

254 
while stack[1] != v: 
255 
w = stack.pop() 
256 
component[w] = root[v] 
257 
tmpc.add(w) 
258 
stack.remove(v) 
259 
yield tmpc

260  
261 
visited = {} 
262 
component = {} 
263 
root = {} 
264 
cnt = 0

265 
stack = [] 
266 
for source in G: 
267 
if source not in visited: 
268 
for c in visit(source, cnt): 
269 
yield c

270  
271  
272 
@not_implemented_for('undirected') 
273 
def strongly_connected_component_subgraphs(G, copy=True): 
274 
"""DEPRECATED: Use ``(G.subgraph(c) for c in strongly_connected_components(G))``

275 

276 
Or ``(G.subgraph(c).copy() for c in strongly_connected_components(G))``

277 
"""

278 
msg = "strongly_connected_component_subgraphs is deprecated and will be removed in 2.2" \

279 
"use (G.subgraph(c).copy() for c in strongly_connected_components(G))"

280 
_warnings.warn(msg, DeprecationWarning)

281 
for c in strongly_connected_components(G): 
282 
if copy:

283 
yield G.subgraph(c).copy()

284 
else:

285 
yield G.subgraph(c)

286  
287  
288 
@not_implemented_for('undirected') 
289 
def number_strongly_connected_components(G): 
290 
"""Returns number of strongly connected components in graph.

291 

292 
Parameters

293 


294 
G : NetworkX graph

295 
A directed graph.

296 

297 
Returns

298 


299 
n : integer

300 
Number of strongly connected components

301 

302 
Raises

303 


304 
NetworkXNotImplemented:

305 
If G is undirected.

306 

307 
See Also

308 


309 
strongly_connected_components

310 
number_connected_components

311 
number_weakly_connected_components

312 

313 
Notes

314 


315 
For directed graphs only.

316 
"""

317 
return sum(1 for scc in strongly_connected_components(G)) 
318  
319  
320 
@not_implemented_for('undirected') 
321 
def is_strongly_connected(G): 
322 
"""Test directed graph for strong connectivity.

323 

324 
A directed graph is strongly connected if and only if every vertex in

325 
the graph is reachable from every other vertex.

326 

327 
Parameters

328 


329 
G : NetworkX Graph

330 
A directed graph.

331 

332 
Returns

333 


334 
connected : bool

335 
True if the graph is strongly connected, False otherwise.

336 

337 
Raises

338 


339 
NetworkXNotImplemented:

340 
If G is undirected.

341 

342 
See Also

343 


344 
is_weakly_connected

345 
is_semiconnected

346 
is_connected

347 
is_biconnected

348 
strongly_connected_components

349 

350 
Notes

351 


352 
For directed graphs only.

353 
"""

354 
if len(G) == 0: 
355 
raise nx.NetworkXPointlessConcept(

356 
"""Connectivity is undefined for the null graph.""")

357  
358 
return len(list(strongly_connected_components(G))[0]) == len(G) 
359  
360  
361 
@not_implemented_for('undirected') 
362 
def condensation(G, scc=None): 
363 
"""Returns the condensation of G.

364 

365 
The condensation of G is the graph with each of the strongly connected

366 
components contracted into a single node.

367 

368 
Parameters

369 


370 
G : NetworkX DiGraph

371 
A directed graph.

372 

373 
scc: list or generator (optional, default=None)

374 
Strongly connected components. If provided, the elements in

375 
`scc` must partition the nodes in `G`. If not provided, it will be

376 
calculated as scc=nx.strongly_connected_components(G).

377 

378 
Returns

379 


380 
C : NetworkX DiGraph

381 
The condensation graph C of G. The node labels are integers

382 
corresponding to the index of the component in the list of

383 
strongly connected components of G. C has a graph attribute named

384 
'mapping' with a dictionary mapping the original nodes to the

385 
nodes in C to which they belong. Each node in C also has a node

386 
attribute 'members' with the set of original nodes in G that

387 
form the SCC that the node in C represents.

388 

389 
Raises

390 


391 
NetworkXNotImplemented:

392 
If G is undirected.

393 

394 
Notes

395 


396 
After contracting all strongly connected components to a single node,

397 
the resulting graph is a directed acyclic graph.

398 

399 
"""

400 
if scc is None: 
401 
scc = nx.strongly_connected_components(G) 
402 
mapping = {} 
403 
members = {} 
404 
C = nx.DiGraph() 
405 
# Add mapping dict as graph attribute

406 
C.graph['mapping'] = mapping

407 
if len(G) == 0: 
408 
return C

409 
for i, component in enumerate(scc): 
410 
members[i] = component 
411 
mapping.update((n, i) for n in component) 
412 
number_of_components = i + 1

413 
C.add_nodes_from(range(number_of_components))

414 
C.add_edges_from((mapping[u], mapping[v]) for u, v in G.edges() 
415 
if mapping[u] != mapping[v])

416 
# Add a list of members (ie original nodes) to each node (ie scc) in C.

417 
nx.set_node_attributes(C, members, 'members')

418 
return C
