1
2 """
3 Connected components and strongly connected components.
4 """
5 __authors__ = """Eben Kennah (ekenah@t7.lanl.gov)\nAric Hagberg (hagberg@lanl.gov)"""
6 ___revision__ = ""
7
8
9
10
11
12
13 import networkx
14 from networkx.path import \
15 single_source_shortest_path,\
16 single_source_shortest_path_length
17 from networkx.search import \
18 dfs_postorder,dfs_preorder
19
20
22 """
23 Return a list of lists of nodes in each connected component of G.
24
25 The list is ordered from largest connected component to smallest.
26 For undirected graphs only.
27 """
28 if G.is_directed():
29 raise networkx.NetworkXError,\
30 """Not allowed for directed graph G.
31 Use UG=G.to_undirected() to create an undirected graph."""
32 seen={}
33 components=[]
34 for v in G:
35 if v not in seen:
36 c=single_source_shortest_path_length(G,v)
37 components.append(c.keys())
38 seen.update(c)
39 components.sort(lambda x, y: cmp(len(y),len(x)))
40 return components
41
42
44 """Return the number of connected components in G.
45 For undirected graphs only.
46 """
47 return len(connected_components(G))
48
49
59
60
62 """
63 Return a list of graphs of each connected component of G.
64 The list is ordered from largest connected component to smallest.
65 For undirected graphs only.
66
67 For example, to get the largest connected component:
68 >>> H=connected_component_subgraphs(G)[0]
69
70 """
71 cc=connected_components(G)
72 graph_list=[]
73 for c in cc:
74 graph_list.append(G.subgraph(c,inplace=False))
75 return graph_list
76
77
79 """
80 Return a list of nodes of the connected component containing node n.
81
82 For undirected graphs only.
83
84 """
85 if G.is_directed():
86 raise networkx.NetworkXError,\
87 """Not allowed for directed graph G.
88 Use UG=G.to_undirected() to create an undirected graph."""
89 return single_source_shortest_path_length(G,n).keys()
90
91
92
94 """Returns list of strongly connected components in G.
95 Uses Tarjan's algorithm with Nuutila's modifications.
96 Nonrecursive version of algorithm.
97
98 References:
99
100 R. Tarjan (1972). Depth-first search and linear graph algorithms.
101 SIAM Journal of Computing 1(2):146-160.
102
103 E. Nuutila and E. Soisalon-Soinen (1994).
104 On finding the strongly connected components in a directed graph.
105 Information Processing Letters 49(1): 9-14.
106
107 """
108 neighbors=G.neighbors
109 preorder={}
110 lowlink={}
111 scc_found={}
112 scc_queue = []
113 scc_list=[]
114 i=0
115 for source in G:
116 if source not in scc_found:
117 queue=[source]
118 while queue:
119 v=queue[-1]
120 if v not in preorder:
121 i=i+1
122 preorder[v]=i
123 done=1
124 for w in neighbors(v):
125 if w not in preorder:
126 queue.append(w)
127 done=0
128 break
129 if done==1:
130 lowlink[v]=preorder[v]
131 for w in neighbors(v):
132 if w not in scc_found:
133 if preorder[w]>preorder[v]:
134 lowlink[v]=min([lowlink[v],lowlink[w]])
135 else:
136 lowlink[v]=min([lowlink[v],preorder[w]])
137 queue.pop()
138 if lowlink[v]==preorder[v]:
139 scc_found[v]=True
140 scc=[v]
141 while scc_queue and preorder[scc_queue[-1]]>preorder[v]:
142 k=scc_queue.pop()
143 scc_found[k]=True
144 scc.append(k)
145 scc_list.append(scc)
146 else:
147 scc_queue.append(v)
148 scc_list.sort(lambda x, y: cmp(len(y),len(x)))
149 return scc_list
150
151
153 """Returns list of strongly connected components in G.
154 Uses Kosaraju's algorithm.
155 """
156 components=[]
157 post=dfs_postorder(G,source=source,reverse_graph=True)
158 seen={}
159 while post:
160 r=post.pop()
161 if r in seen:
162 continue
163 c=dfs_preorder(G,r)
164 new=[v for v in c if v not in seen]
165 seen.update([(u,True) for u in new])
166 components.append(new)
167 components.sort(lambda x, y: cmp(len(y),len(x)))
168 return components
169
170
172 """Returns list of strongly connected components in G.
173 Uses Tarjan's algorithm with Nuutila's modifications.
174 this recursive version of the algorithm will hit the
175 Python stack limit for large graphs.
176
177 """
178 def visit(v,cnt):
179 root[v]=cnt
180 visited[v]=cnt
181 cnt+=1
182 stack.append(v)
183 for w in G[v]:
184 if w not in visited: visit(w,cnt)
185 if w not in component:
186 root[v]=min(root[v],root[w])
187 if root[v]==visited[v]:
188 component[v]=root[v]
189 tmpc=[v]
190 while stack[-1]!=v:
191 w=stack.pop()
192 component[w]=root[v]
193 tmpc.append(w)
194 stack.remove(v)
195 scc.append(tmpc)
196 scc=[]
197 visited={}
198 component={}
199 root={}
200 cnt=0
201 stack=[]
202 for source in G:
203 if source not in visited:
204 visit(source,cnt)
205
206 scc.sort(lambda x, y: cmp(len(y),len(x)))
207 return scc
208
209
211 """
212 Return a list of graphs of each strongly connected component of G.
213 The list is ordered from largest connected component to smallest.
214
215 For example, to get the largest strongly connected component:
216 >>> H=strongly_connected_component_subgraphs(G)[0]
217
218 """
219 cc=strongly_connected_components(G)
220 graph_list=[]
221 for c in cc:
222 graph_list.append(G.subgraph(c,inplace=False))
223 return graph_list
224
225
231
240
241
242
244 import doctest
245 suite = doctest.DocFileSuite('tests/component.txt',package='networkx')
246 return suite
247
248
249 if __name__ == "__main__":
250 import os
251 import sys
252 import unittest
253 if sys.version_info[:2] < (2, 4):
254 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
255 sys.exit(-1)
256
257 nxbase=sys.path[0]+os.sep+os.pardir
258 sys.path.insert(0,nxbase)
259 unittest.TextTestRunner().run(_test_suite())
260