Package networkx :: Module component

[frames] | no frames]

Module component

source code

Connected components and strongly connected components.

Author: Eben Kennah (ekenah@t7.lanl.gov) Aric Hagberg (hagberg@lanl.gov)

Functions

[hide private]

connected_components(G)
Return a list of lists of nodes in each connected component of G.

source code

number_connected_components(G)
Return the number of connected components in G.

source code

is_connected(G)
Return True if G is connected.

source code

connected_component_subgraphs(G)
Return a list of graphs of each connected component of G.

source code

node_connected_component(G, n)
Return a list of nodes of the connected component containing node n.

source code

strongly_connected_components(G)
Returns list of strongly connected components in G.

source code

kosaraju_strongly_connected_components(G, source=None)
Returns list of strongly connected components in G.

source code

strongly_connected_components_recursive(G)
Returns list of strongly connected components in G.

source code

strongly_connected_component_subgraphs(G)
Return a list of graphs of each strongly connected component of G.

source code

number_strongly_connected_components(G)
Return the number of connected components in G.

source code

is_strongly_connected(G)
Return True if G is strongly connected.

source code

_test_suite()

source code

Variables

[hide private]

___revision__ = ''

Function Details

[hide private]

connected_components(G)

source code

Return a list of lists of nodes in each connected component of G.

The list is ordered from largest connected component to smallest. For undirected graphs only.

number_connected_components(G)

source code

Return the number of connected components in G. For undirected graphs only.

is_connected(G)

source code

Return True if G is connected. For undirected graphs only.

connected_component_subgraphs(G)

source code

Return a list of graphs of each connected component of G. The list is ordered from largest connected component to smallest. For undirected graphs only.

For example, to get the largest connected component: >>> H=connected_component_subgraphs(G)[0]

node_connected_component(G, n)

source code

Return a list of nodes of the connected component containing node n.

For undirected graphs only.

strongly_connected_components(G)

source code

Returns list of strongly connected components in G. Uses Tarjan's algorithm with Nuutila's modifications. Nonrecursive version of algorithm.

References:

R. Tarjan (1972). Depth-first search and linear graph algorithms. SIAM Journal of Computing 1(2):146-160.

E. Nuutila and E. Soisalon-Soinen (1994). On finding the strongly connected components in a directed graph. Information Processing Letters 49(1): 9-14.

kosaraju_strongly_connected_components(G, source=None)

source code

Returns list of strongly connected components in G. Uses Kosaraju's algorithm.

strongly_connected_components_recursive(G)

source code

Returns list of strongly connected components in G. Uses Tarjan's algorithm with Nuutila's modifications. this recursive version of the algorithm will hit the Python stack limit for large graphs.

strongly_connected_component_subgraphs(G)

source code

Return a list of graphs of each strongly connected component of G. The list is ordered from largest connected component to smallest.

For example, to get the largest strongly connected component: >>> H=strongly_connected_component_subgraphs(G)[0]

number_strongly_connected_components(G)

source code

Return the number of connected components in G. For undirected graphs only.