Home | History | Annotate | Download | only in tests 
      1 #!/usr/bin/env python
      2 from nose.tools import *
      3 import networkx as nx
      4 from networkx import NetworkXError 
      5 
      6 class TestStronglyConnected:
      7 
      8     def setUp(self):
      9         self.gc=[]
     10         G=nx.DiGraph()
     11         G.add_edges_from([(1,2),(2,3),(2,8),(3,4),(3,7),
     12                           (4,5),(5,3),(5,6),(7,4),(7,6),(8,1),(8,7)])
     13         C=[[3, 4, 5, 7], [1, 2, 8],  [6]]
     14         self.gc.append((G,C))
     15 
     16         G= nx.DiGraph()
     17         G.add_edges_from([(1,2),(1,3),(1,4),(4,2),(3,4),(2,3)])
     18         C = [[2, 3, 4],[1]]
     19         self.gc.append((G,C))
     20 
     21         G = nx.DiGraph()
     22         G.add_edges_from([(1,2),(2,3),(3,2),(2,1)])
     23         C = [[1, 2, 3]]
     24         self.gc.append((G,C))
     25 
     26         # Eppstein's tests
     27         G = nx.DiGraph({ 0:[1],1:[2,3],2:[4,5],3:[4,5],4:[6],5:[],6:[]})
     28         C = [[0],[1],[2],[3],[4],[5],[6]]
     29         self.gc.append((G,C))
     30     
     31         G = nx.DiGraph({0:[1],1:[2,3,4],2:[0,3],3:[4],4:[3]})
     32         C = [[0,1,2],[3,4]]
     33         self.gc.append((G,C))
     34 
     35 
     36     def test_tarjan(self):
     37         scc=nx.strongly_connected_components
     38         for G,C in self.gc:
     39             assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C))
     40 
     41 
     42     def test_tarjan_recursive(self):
     43         scc=nx.strongly_connected_components_recursive
     44         for G,C in self.gc:
     45             assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C))
     46 
     47 
     48     def test_kosaraju(self):
     49         scc=nx.kosaraju_strongly_connected_components
     50         for G,C in self.gc:
     51             assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C))
     52 
     53     def test_number_strongly_connected_components(self):
     54         ncc=nx.number_strongly_connected_components
     55         for G,C in self.gc:
     56             assert_equal(ncc(G),len(C))
     57 
     58     def test_is_strongly_connected(self):            
     59         for G,C in self.gc:
     60             if len(C)==1:
     61                 assert_true(nx.is_strongly_connected(G))
     62             else:
     63                 assert_false(nx.is_strongly_connected(G))
     64 
     65 
     66     def test_strongly_connected_component_subgraphs(self):
     67         scc=nx.strongly_connected_component_subgraphs
     68         for G,C in self.gc:
     69             assert_equal(sorted([sorted(g.nodes()) for g in scc(G)]),sorted(C))
     70         G,C=self.gc[0]
     71         G.add_edge(1,2,eattr='red')
     72         G.node[1]['nattr']='blue'
     73         G.graph['gattr']='green'
     74         sgs=scc(G)[1]
     75         assert_equal(sgs[1][2]['eattr'],'red')
     76         assert_equal(sgs.node[1]['nattr'],'blue')
     77         assert_equal(sgs.graph['gattr'],'green')
     78         sgs[1][2]['eattr']='blue'
     79         assert_equal(G[1][2]['eattr'],'red')
     80         assert_equal(sgs[1][2]['eattr'],'blue')
     81 
     82     def test_contract_scc1(self):
     83         G = nx.DiGraph()
     84         G.add_edges_from([(1,2),(2,3),(2,11),(2,12),(3,4),(4,3),(4,5),
     85                           (5,6),(6,5),(6,7),(7,8),(7,9),(7,10),(8,9),
     86                           (9,7),(10,6),(11,2),(11,4),(11,6),(12,6),(12,11)])
     87         scc = nx.strongly_connected_components(G)
     88         cG = nx.condensation(G, scc)
     89         # DAG
     90         assert_true(nx.is_directed_acyclic_graph(cG))
     91         # # nodes
     92         assert_equal(sorted(cG.nodes()),[0,1,2,3])
     93         # # edges
     94         mapping={}
     95         for i,component in enumerate(scc):
     96             for n in component:
     97                 mapping[n] = i
     98         edge=(mapping[2],mapping[3])
     99         assert_true(cG.has_edge(*edge))
    100         edge=(mapping[2],mapping[5])
    101         assert_true(cG.has_edge(*edge))
    102         edge=(mapping[3],mapping[5])
    103         assert_true(cG.has_edge(*edge))
    104 
    105     def test_contract_scc_isolate(self):
    106         # Bug found and fixed in [1687].
    107         G = nx.DiGraph()
    108         G.add_edge(1,2)
    109         G.add_edge(2,1)
    110         scc = nx.strongly_connected_components(G)        
    111         cG = nx.condensation(G, scc)
    112         assert_equal(cG.nodes(),[0])
    113         assert_equal(cG.edges(),[])
    114 
    115     def test_contract_scc_edge(self):
    116         G = nx.DiGraph()
    117         G.add_edge(1,2)
    118         G.add_edge(2,1)
    119         G.add_edge(2,3)
    120         G.add_edge(3,4)
    121         G.add_edge(4,3)
    122         scc = nx.strongly_connected_components(G)        
    123         cG = nx.condensation(G, scc)
    124         assert_equal(cG.nodes(),[0,1])
    125         if 1 in scc[0]:
    126             edge = (0,1)
    127         else:
    128             edge = (1,0)
    129         assert_equal(cG.edges(),[edge])
    130     
    131     def test_connected_raise(self):
    132         G=nx.Graph()
    133         assert_raises(NetworkXError,nx.strongly_connected_components,G)
    134         assert_raises(NetworkXError,nx.kosaraju_strongly_connected_components,G)
    135         assert_raises(NetworkXError,nx.strongly_connected_components_recursive,G)
    136         assert_raises(NetworkXError,nx.strongly_connected_component_subgraphs,G)
    137         assert_raises(NetworkXError,nx.is_strongly_connected,G)
    138         assert_raises(NetworkXError,nx.condensation,G)
    139