Package networkx :: Module component
[hide private]
[frames] | no frames]

Source Code for Module networkx.component

  1  # -*- coding: utf-8 -*- 
  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  #    Copyright (C) 2004-2007 by  
  8  #    Aric Hagberg <hagberg@lanl.gov> 
  9  #    Dan Schult <dschult@colgate.edu> 
 10  #    Pieter Swart <swart@lanl.gov> 
 11  #    Distributed under the terms of the GNU Lesser General Public License 
 12  #    http://www.gnu.org/copyleft/lesser.html 
 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   
21 -def connected_components(G):
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
43 -def number_connected_components(G):
44 """Return the number of connected components in G. 45 For undirected graphs only. 46 """ 47 return len(connected_components(G))
48 49
50 -def is_connected(G):
51 """Return True if G is connected. 52 For undirected graphs only. 53 """ 54 if G.is_directed(): 55 raise networkx.NetworkXError,\ 56 """Not allowed for directed graph G. 57 Use UG=G.to_undirected() to create an undirected graph.""" 58 return len(single_source_shortest_path(G, G.nodes_iter().next()))==len(G)
59 60
61 -def connected_component_subgraphs(G):
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
78 -def node_connected_component(G,n):
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
93 -def strongly_connected_components(G):
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 # Preorder counter 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
152 -def kosaraju_strongly_connected_components(G,source=None):
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
171 -def strongly_connected_components_recursive(G):
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] # hold nodes in this component 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) # add to scc list
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
210 -def strongly_connected_component_subgraphs(G):
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
226 -def number_strongly_connected_components(G):
227 """Return the number of connected components in G. 228 For undirected graphs only. 229 """ 230 return len(strongly_connected_components(G))
231
232 -def is_strongly_connected(G):
233 """Return True if G is strongly connected. 234 """ 235 if not G.is_directed(): 236 raise networkx.NetworkXError,\ 237 """Not allowed for undirected graph G. 238 See is_connected() for connectivity test.""" 239 return len(strongly_connected_components(G)[0])==len(G)
240 241 242
243 -def _test_suite():
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 # directory of networkx package (relative to this) 257 nxbase=sys.path[0]+os.sep+os.pardir 258 sys.path.insert(0,nxbase) # prepend to search path 259 unittest.TextTestRunner().run(_test_suite()) 260