component
==========

>>> import networkx as NX
>>> from networkx.operators import convert_node_labels_to_integers as cnlti
>>> G=cnlti(NX.grid_2d_graph(4,4),first_label=1,ordering="sorted")

    .. image:: paths_G.png

>>> H=NX.cycle_graph(7)
>>> DH=NX.cycle_graph(7,create_using=NX.DiGraph())


Connected components
--------------------

>>> G1=cnlti(NX.grid_2d_graph(2,2),first_label=0,ordering="sorted")
>>> G2=cnlti(NX.lollipop_graph(3,3),first_label=4,ordering="sorted")
>>> G3=cnlti(NX.house_graph(),first_label=10,ordering="sorted")
>>> DG=NX.DiGraph()
>>> DG.add_edges_from([(1,2),(1,3),(2,3)])
>>> G=NX.union(G1,G2)
>>> G=NX.union(G,G3)
>>> sorted(NX.connected_components(G))
[[0, 1, 2, 3], [4, 5, 6, 7, 8, 9], [10, 11, 12, 13, 14]]
>>> NX.number_connected_components(G)
3


>>> G=cnlti(NX.grid_2d_graph(4,4),first_label=1)

    .. image:: paths_G.png


>>> NX.number_connected_components(G)
1

>>> sorted(NX.connected_components(G)[0])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

>>> sorted(NX.node_connected_component(G,1))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

>>> H=NX.connected_component_subgraphs(G)[0]
>>> sorted(H.nodes())
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

>>> NX.is_connected(G)
True
>>> G.add_edge('A','B')
>>> NX.is_connected(G)
False

>>> NX.connected_components(DG)
Traceback (most recent call last):
...
NetworkXError: Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph.

>>> NX.number_connected_components(DG)
Traceback (most recent call last):
...
NetworkXError: Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph.

>>> NX.connected_component_subgraphs(DG)
Traceback (most recent call last):
...
NetworkXError: Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph.

>>> NX.node_connected_component(DG,1)
Traceback (most recent call last):
...
NetworkXError: Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph.


>>> NX.is_connected(DG)
Traceback (most recent call last):
...
NetworkXError: Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph.



Strongly Connected components
-----------------------------

>>> from networkx import *

>>> G1=NX.DiGraph()
>>> G1.add_edges_from([(1,2),(2,3),(2,8),(3,4),(3,7),(4,5),(5,3),(5,6),(7,4),(7,6),(8,1),(8,7)])
>>> C1=[[1, 2, 8], [3, 4, 5, 7], [6]]

>>> G2 = NX.DiGraph()
>>> G2.add_edges_from([(1,2),(1,3),(1,4),(4,2),(3,4),(2,3)])
>>> C2 = [[1], [2, 3, 4]]

>>> G3 = NX.DiGraph()
>>> G3.add_edges_from([(1,2),(2,3),(3,2),(2,1)])
>>> C3 = [[1, 2, 3]]

Eppstein's tests

>>> G4 = NX.DiGraph({ 0:[1],1:[2,3],2:[4,5],3:[4,5],4:[6],5:[],6:[]})
>>> C4 = [[0],[1],[2],[3],[4],[5],[6]]
    
>>> G5 = NX.DiGraph({0:[1],1:[2,3,4],2:[0,3],3:[4],4:[3]})
>>> C5 = [[0,1,2],[3,4]]



Tarjan

>>> scc=strongly_connected_components
>>> sorted([sorted(g) for g in scc(G1)])==C1
True
>>> sorted([sorted(g) for g in scc(G2)])==C2
True
>>> sorted([sorted(g) for g in scc(G3)])==C3
True
>>> sorted([sorted(g) for g in scc(G4)])==C4
True
>>> sorted([sorted(g) for g in scc(G5)])==C5
True

Tarjan Recursive

>>> scc=strongly_connected_components_recursive
>>> sorted([sorted(g) for g in scc(G1)])==C1
True
>>> sorted([sorted(g) for g in scc(G2)])==C2
True
>>> sorted([sorted(g) for g in scc(G3)])==C3
True
>>> sorted([sorted(g) for g in scc(G4)])==C4
True
>>> sorted([sorted(g) for g in scc(G5)])==C5
True

Kosaraju

>>> scc=kosaraju_strongly_connected_components
>>> sorted([sorted(g) for g in scc(G1)])==C1
True
>>> sorted([sorted(g) for g in scc(G2)])==C2
True
>>> sorted([sorted(g) for g in scc(G3)])==C3
True
>>> sorted([sorted(g) for g in scc(G4)])==C4
True
>>> sorted([sorted(g) for g in scc(G5)])==C5
True


Number of strongly connected components

>>> ncc=number_strongly_connected_components
>>> ncc(G1)==len(C1)
True
>>> ncc(G2)==len(C2)
True
>>> ncc(G3)==len(C3)
True
>>> ncc(G4)==len(C4)
True
>>> ncc(G5)==len(C5)
True


>>> is_strongly_connected(G3)
True


Subgraphs

>>> scc=strongly_connected_component_subgraphs
>>> sorted([sorted(g.nodes()) for g in scc(G1)])==C1
True
>>> sorted([sorted(g.nodes()) for g in scc(G2)])==C2
True
>>> sorted([sorted(g.nodes()) for g in scc(G3)])==C3
True
>>> sorted([sorted(g.nodes()) for g in scc(G4)])==C4
True
>>> sorted([sorted(g.nodes()) for g in scc(G5)])==C5
True



