1. Ben Edwards
  2. networkx-bedwards

Commits

Aric Hagberg  committed 539b680

Update condensation to use integer labels.
Fixes #643

  • Participants
  • Parent commits 4b5d26f
  • Branches default

Comments (0)

Files changed (6)

File doc/source/reference/api_1.6.rst

View file
 
     import networkx.algorithms.isomorphism as iso
 
+Other
+-----
 
+* condensation
 
+  The condensation algorithm now takes a second argument (scc) and returns a   
+  graph with node labeled with integers instead of node tuples.
 
+

File networkx/algorithms/components/attracting.py

View file
 """
 Attracting components.
 """
-__authors__ = "\n".join(['Christopher Ellison'])
-#    Copyright (C) 2004-2010 by 
+#    Copyright (C) 2004-2011 by 
 #    Aric Hagberg <hagberg@lanl.gov>
 #    Dan Schult <dschult@colgate.edu>
 #    Pieter Swart <swart@lanl.gov>
 #    All rights reserved.
 #    BSD license.
-
+import networkx as nx
+__authors__ = "\n".join(['Christopher Ellison'])
 __all__ = ['number_attracting_components', 
            'attracting_components',
            'is_attracting_component', 
            'attracting_component_subgraphs',
            ]
 
-import networkx as nx
-
 def attracting_components(G):
     """Returns a list of attracting components in `G`.
 
     attracting_component_subgraphs
 
     """
-    cG = nx.condensation(G)
-    attractors = [scc for scc in cG if cG.out_degree(scc) == 0]
+    scc = nx.strongly_connected_components(G)
+    cG = nx.condensation(G, scc)
+    attractors = [scc[n] for n in cG if cG.out_degree(n) == 0]
     attractors.sort(key=len,reverse=True)
     return attractors
 

File networkx/algorithms/components/strongly_connected.py

View file
 """
 Strongly connected components.
 """
-__authors__ = "\n".join(['Eben Kenah',
-                         'Aric Hagberg (hagberg@lanl.gov)'
-                         'Christopher Ellison'])
-#    Copyright (C) 2004-2010 by 
+#    Copyright (C) 2004-2011 by 
 #    Aric Hagberg <hagberg@lanl.gov>
 #    Dan Schult <dschult@colgate.edu>
 #    Pieter Swart <swart@lanl.gov>
 #    All rights reserved.
 #    BSD license.
+import networkx as nx
+__authors__ = "\n".join(['Eben Kenah',
+                         'Aric Hagberg (hagberg@lanl.gov)'
+                         'Christopher Ellison'])
 
 __all__ = ['number_strongly_connected_components', 
            'strongly_connected_components',
            'condensation',
            ]
 
-import networkx as nx
-
 def strongly_connected_components(G):
     """Return nodes in strongly connected components of graph.
 
     return len(strongly_connected_components(G)[0])==len(G)
 
 
-def condensation(G):
+def condensation(G, scc):
     """Returns the condensation of G.
 
     The condensation of G is the graph with each of the strongly connected 
-    components contracted into a single node.
+    components contracted into a single node.  
 
     Parameters
     ----------
-    G : NetworkX Graph
+    G : NetworkX DiGraph
        A directed graph.
 
+    scc:  list
+       A list of strongly connected components.  
+       Use scc=nx.strongly_connected_components(G) to compute the components.
+
     Returns
     -------
-    cG : NetworkX DiGraph
-       The condensation of G.
+    C : NetworkX DiGraph
+       The condensation of G. The node labels are integers corresponding
+       to the index of the component in the list of strongly connected 
+       components.
 
     Notes
     -----
     After contracting all strongly connected components to a single node,
-    the resulting graph is a directed acyclic graph.
-
+    the resulting graph is a directed acyclic graph.  
     """
-    scc = strongly_connected_components(G)
-    mapping = dict([(n,tuple(sorted(c))) for c in scc for n in c])
-    cG = nx.DiGraph()
-    for u in mapping:
-        cG.add_node(mapping[u])
-        for _,v,d in G.edges_iter(u, data=True):
-            if v not in mapping[u]:
-                cG.add_edge(mapping[u], mapping[v])
-    return cG
-
+    mapping = {}
+    C = nx.DiGraph()
+    for i,component in enumerate(scc):
+        for n in component:
+            mapping[n] = i
+    C.add_nodes_from(range(len(scc)))
+    for u,v in G.edges():
+        if mapping[u] != mapping[v]:
+            C.add_edge(mapping[u],mapping[v])
+    return C

File networkx/algorithms/components/tests/test_attracting.py

View file
 
     def test_attracting_components(self):
         ac = nx.attracting_components(self.G1)
-        assert_true((2,) in ac)
-        assert_true((9,) in ac)
-        assert_true((10,) in ac)
+        assert_true([2] in ac)
+        assert_true([9] in ac)
+        assert_true([10] in ac)
 
         ac = nx.attracting_components(self.G2)
         ac = [tuple(sorted(x)) for x in ac]
-        print(ac)
         assert_true(ac == [(1,2)])
 
         ac = nx.attracting_components(self.G3)

File networkx/algorithms/components/tests/test_connected.py

View file
         ccs=nx.connected_component_subgraphs(G)
         assert_equal(len(ccs),1)
         sg=ccs[0]
-        assert_equal(sorted(sg.nodes()),range(1,17))
+        assert_equal(sorted(sg.nodes()),list(range(1,17)))
         assert_equal(sg[1][2]['eattr'],'red')
         assert_equal(sg.node[1]['nattr'],'blue')
         assert_equal(sg.graph['gattr'],'green')

File networkx/algorithms/components/tests/test_strongly_connected.py

View file
         G.add_edges_from([(1,2),(2,3),(2,11),(2,12),(3,4),(4,3),(4,5),
                           (5,6),(6,5),(6,7),(7,8),(7,9),(7,10),(8,9),
                           (9,7),(10,6),(11,2),(11,4),(11,6),(12,6),(12,11)])
-        cG = nx.condensation(G)
-        # nodes
-        assert_true((1,) in cG)
-        assert_true((2,11,12) in cG)
-        assert_true((3,4) in cG)
-        assert_true((5,6,7,8,9,10) in cG)
-        assert_true((2,11,12) in cG[(1,)])
-        # edges
-        assert_true((3,4) in cG[(2,11,12)])
-        assert_true((5,6,7,8,9,10) in cG[(2,11,12)])
-        assert_true((5,6,7,8,9,10) in cG[(3,4)])
+        scc = nx.strongly_connected_components(G)
+        cG = nx.condensation(G, scc)
         # DAG
         assert_true(nx.is_directed_acyclic_graph(cG))
+        # # nodes
+        assert_equal(sorted(cG.nodes()),[0,1,2,3])
+        # # edges
+        mapping={}
+        for i,component in enumerate(scc):
+            for n in component:
+                mapping[n] = i
+        edge=(mapping[2],mapping[3])
+        assert_true(cG.has_edge(*edge))
+        edge=(mapping[2],mapping[5])
+        assert_true(cG.has_edge(*edge))
+        edge=(mapping[3],mapping[5])
+        assert_true(cG.has_edge(*edge))
 
-    def test_contract_scc2(self):
+    def test_contract_scc_isolate(self):
         # Bug found and fixed in [1687].
         G = nx.DiGraph()
         G.add_edge(1,2)
         G.add_edge(2,1)
-        cG = nx.condensation(G)
-        assert_true((1,2) in cG)
+        scc = nx.strongly_connected_components(G)        
+        cG = nx.condensation(G, scc)
+        assert_equal(cG.nodes(),[0])
+        assert_equal(cG.edges(),[])
 
+    def test_contract_scc_edge(self):
+        G = nx.DiGraph()
+        G.add_edge(1,2)
+        G.add_edge(2,1)
+        G.add_edge(2,3)
+        G.add_edge(3,4)
+        G.add_edge(4,3)
+        scc = nx.strongly_connected_components(G)        
+        cG = nx.condensation(G, scc)
+        assert_equal(cG.nodes(),[0,1])
+        if 1 in scc[0]:
+            edge = (0,1)
+        else:
+            edge = (1,0)
+        assert_equal(cG.edges(),[edge])
 
 
 
+
+