Repository: andrenarchy/stellar-observatory

Issue:
Return scc graph from get_sccs()
After finding the SCCs there should be a post-processing step that returns all (directed) edges between the SCCs.

Discussion:

Patch:
diff --git a/stellarobservatory/utils/scc.py b/stellarobservatory/utils/scc.py
index 1d13f16..82b6822 100644
--- a/stellarobservatory/utils/scc.py
+++ b/stellarobservatory/utils/scc.py
@@ -4,16 +4,10 @@ from scipy.sparse import csr_matrix
 from scipy.sparse.csgraph import connected_components
 
 
-def get_strongly_connected_components(graph):
+def get_graph_csr_matrix(graph, nodes, node_index_by_node):
     """
-    Get strongly connected components for a directed graph
-
-    The returned list of components is in reverse topological order, i.e.,
-    such that the nodes in the first component have no dependencies on
-    other components.
+    Get CSR matrix representation of graph
     """
-    nodes = list(graph.keys())
-    node_index_by_node = {node: index for index, node in enumerate(nodes)}
     row_indexes = []
     col_indexes = []
     for node, targets in graph.items():
@@ -21,9 +15,39 @@ def get_strongly_connected_components(graph):
         col_indexes += [node_index_by_node[target] for target in targets]
     data = numpy.ones((len(row_indexes)), dtype=int)
     n_nodes = len(nodes)
-    csgraph = csr_matrix((data, (row_indexes, col_indexes)), shape=(n_nodes, n_nodes))
-    n_components, labels = connected_components(csgraph, directed=True, connection='strong')
+    return csr_matrix((data, (row_indexes, col_indexes)), shape=(n_nodes, n_nodes))
+
+def get_scc_graph(graph, nodes, node_index_by_node, labels, n_components):
+    """
+    Get SCCs as graph
+    """
     sccs = [[] for i in range(n_components)]
+    scc_graph = dict()
     for index, label in enumerate(labels):
-        sccs[label] += [nodes[index]]
-    return [frozenset(scc) for scc in sccs]
+        node = nodes[index]
+        sccs[label] += [node]
+        if label not in scc_graph:
+            scc_graph[label] = set()
+        for target_node in graph[node]:
+            target_index = node_index_by_node[target_node]
+            target_label = labels[target_index]
+            if target_label != label:
+                scc_graph[label].add(labels[target_index])
+    return sccs, scc_graph
+
+
+def get_strongly_connected_components(graph):
+    """
+    Get strongly connected components for a directed graph
+
+    The returned list of components is in reverse topological order, i.e.,
+    such that the nodes in the first component have no dependencies on
+    other components.
+    """
+    nodes = list(graph.keys())
+    node_index_by_node = {node: index for index, node in enumerate(nodes)}
+    csgraph = get_graph_csr_matrix(graph, nodes, node_index_by_node)
+    n_components, labels = connected_components(csgraph, directed=True, connection='strong')
+    sccs, scc_graph = get_scc_graph(graph, nodes, node_index_by_node, labels, n_components)
+    return [frozenset(scc) for scc in sccs], \
+        {scc: frozenset(target_sccs) for scc, target_sccs in scc_graph.items()}


Test patch:
diff --git a/stellarobservatory/utils/scc_test.py b/stellarobservatory/utils/scc_test.py
index 60d42ba..d22421e 100644
--- a/stellarobservatory/utils/scc_test.py
+++ b/stellarobservatory/utils/scc_test.py
@@ -16,5 +16,6 @@ def test_get_strongly_connected_components():
         8: {9},
         9: {5}
     }
-    sccs = get_strongly_connected_components(graph)
+    sccs, scc_graph = get_strongly_connected_components(graph)
     assert sccs == [{1, 2, 3, 4}, {5, 6, 7, 8, 9}]
+    assert scc_graph == {0: set(), 1: {0}}