Strongly connected component algorithm in Python 2.7

Question

This is my implementation of Kosaraju's algorithm for detecting strongly connected components, post here for advice. Some special areas looking for advice,

1. Not sure if my current implementation for adjacent table of graph is efficient?
2. Any better ideas to reverse the graph to make it more efficient?
3. I use preVisited and visited to track what nodes are already reached by a strongly connected components, it there a better way?
4. Any other areas my code could improve, especially for performnace.

from collections import defaultdict
visitTimeCounter = 0

class GraphNode:
    def __init__(self, name):
        self.name=name
        self.connections = [] # list of GraphNode, directional
        self.visitTime = -1

    def DFS(self, visited):
        global visitTimeCounter
        if self.name in visited:
            return
        visited.append(self.name)

        for node in self.connections:
            if node.name in visited:
                pass
            else:
                node.DFS(visited)
        visitTimeCounter += 1
        self.visitTime = visitTimeCounter


if __name__ == "__main__":
    nodeA = GraphNode('A')
    nodeB = GraphNode('B')
    nodeC = GraphNode('C')
    nodeD = GraphNode('D')

    allNodes = [nodeA, nodeB, nodeC, nodeD]

    nodeA.connections.append(nodeB)
    nodeA.connections.append(nodeC)
    nodeB.connections.append(nodeA)
    nodeC.connections.append(nodeD)
    nodeD.connections.append(nodeC)

    visited = []

    for node in allNodes:
        if node.name not in visited:
            node.DFS(visited)

    for node in allNodes:
        print node.name, node.visitTime

    allNodesReverse=[]
    nodeIndex = defaultdict(GraphNode)
    # fork new nodes
    for node in allNodes:
        newNode=GraphNode(node.name)
        newNode.visitTime = node.visitTime
        allNodesReverse.append(newNode)
        nodeIndex[newNode.name]=newNode

    # build conections
    for node in allNodes:
        for neighbour in node.connections:
            nodeIndex[neighbour.name].connections.append(nodeIndex[node.name])

    # verify reverse connections
    for i in allNodesReverse:
        for j in i.connections:
            print i.name, '=>', j.name

    allNodesReverseOrdered = sorted(allNodesReverse, key=lambda x:x.visitTime, reverse=True)
    visited = []
    preVisited = []
    SCResults = []
    for node in allNodesReverseOrdered:
        if node.name not in visited:
            node.DFS(visited)
            # append to new SC
            sc = set()
            for node in allNodesReverseOrdered:
                if node.name in visited and not node.name in preVisited:
                    sc.add(node.name)
            for item in visited:
                preVisited.append(item)
            SCResults.append(sc)

    for sc in SCResults:
        print 'strongly connected component: '
        for i in sc:
            print i

Answer 1

1. Review

1. The code is not portable to Python 3 due to the use of the print statement.

2. The code is not organized into functions. This makes it hard to understand and hard to test.

3. Using a global variable (namely visitTimeCounter) makes code fragile (if the global variable starts out with the wrong value then it goes wrong) and hard to test (because you have to remember to reset the global variable each time you call it).

4. A graph node isn't the best choice of data structure here (it only has one attribute that you actually use, namely the list of its out-neighbours). A better data structure for this algorithm is a directed graph. A directed graph supports several methods that can be used by this algorithm: adding nodes and edges to the graph; iterating over the nodes; and getting the in- or out-neighbours of a node.

   class Graph(object):
       """A directed graph. Nodes may be any hashable values."""
   
       def __init__(self, edges=()):
           """Initialize graph from optional iterable of edges."""
           self._out = defaultdict(set) # Map from node to its out-neighbours
           self._in = defaultdict(set) # Map from node to its in-neighbours
           for u, v in edges:
               self.add_edge(u, v)
   
       def add_node(self, u):
           """Add a node u to the graph."""
           self._out[u]
           self._in[u]
   
       def add_edge(self, u, v):
           """Add a directed edge to the graph, from node u to node v."""
           self.add_node(u)
           self.add_node(v)
           self._out[u].add(v)
           self._in[v].add(u)
   
       def in_neighbours(self, u):
           """Return the set of in-neighbours of the node u."""
           return self._in[u]
   
       def out_neighbours(self, u):
           """Return the set of out-neighbours of the node u."""
           return self._out[u]
   
       def __iter__(self):
           """Return iterator over the nodes of the graph."""
           return iter(self._out)
   

   The constructor makes it very easy to create example graphs:

   Graph('AB BA CD DC AC'.split())
   

   (Compare this to the ten lines of code needed to create the graph in the post.)

5. To make the code for the algorithm easy to understand, it would make sense to closely follow the algorithm description. Wikipedia describes the algorithm like this:

   1. For each vertex \$u\$ of the graph, mark \$u\$ as unvisited. Let \$L\$ be empty.
   2. For each vertex \$u\$ of the graph do \$Visit(u)\$, where \$Visit(u)\$ is the recursive subroutine: If \$u\$ is unvisited then:
      1. Mark \$u\$ as visited.
      2. For each out-neighbour \$v\$ of \$u\$, do \$Visit(v)\$.
      3. Prepend \$u\$ to \$L\$.
   3. For each element \$u\$ of \$L\$ in order, do \$Assign(u,u)\$ where \$Assign(u,root)\$ is the recursive subroutine: If \$u\$ has not been assigned to a component then:
      1. Assign \$u\$ as belonging to the component whose root is \$root\$.
      2. For each in-neighbour \$v\$ of \$u\$, do \$Assign(v,root)\$.

   which can be translated directly into Python like this:

   def components(self):
       """Return list of strongly connected components."""
       visited = set()         # Set of visited nodes.
       L = []                  # Nodes in topological order.
       def visit(u):
           if u not in visited:
               visited.add(u)
               for v in self.out_neighbours(u):
                   visit(v)
               L.insert(0, u)
       for u in self:
           visit(u)
       component = defaultdict(set) # Map from root to its component.
       assigned = set()       # Set of nodes assigned to a component.
       def assign(u, root):
           if u not in assigned:
               component[root].add(u)
               assigned.add(u)
               for v in self.in_neighbours(u):
                   assign(v, root)
       for u in L:
           assign(u, u)
       return list(component.values())
   

   It's much easier to compare and check this kind of directly translated code against the algorithm description than it is to check the more complicated translation in the post.

   (Note that the directly translated code above has the correct functionality, but not the right complexity: inserting an item at the beginning of a list with L.insert(0, u) is inefficient (it takes time proportional to the length of the list). We can fix this by adding nodes to the end of the list instead (which is efficient). This requires three changes. First, the comment becomes:

   L = []           # Nodes in reverse topological order.
   

   Second, L.insert(0, u) becomes L.append(u). Third, the iteration over the list L proceeds in reverse order:

   for u in reversed(L):
   

   If you don't like the idea of maintaining this list in reverse order, then an alternative would be to switch L from a list to a collections.deque, which has an efficient appendleft method.)

   Some quick tests:

   >>> Graph('AB BA CD DC AC'.split()).components()
   [{'D', 'C'}, {'B', 'A'}]
   >>> Graph('AB BC CD DA AE FB DG'.split()).components()
   [{'D', 'B', 'C', 'A'}, {'E'}, {'F'}, {'G'}]
   >>> Graph('AB BC CD DE'.split()).components()
   [{'D'}, {'B'}, {'E'}, {'C'}, {'A'}]
   

2. Answers to questions

1. () is the empty tuple. See the documentation.

2. Your (1) is correct. If there is a directed edge from \$u\$ to \$v\$, then \$u\$ appears before \$v\$ in the list \$L\$ (unless \$u\$ and \$v\$ belong to the same strongly connected component, in which case they could appear in either order).

   But in your (2), I think you have been confused by the wording of the sentence you quoted. When Wikipedia says,

   either way \$v\$ will be prepended to \$L\$ before \$u\$ is

   what it means is,

   either way \$v\$ will be prepended to \$L\$ at an earlier time than \$u\$ is prepended to \$L\$.

   In other words, if there is a directed edge from \$u\$ to \$v\$, then when step 2 is complete, \$u\$ appears before \$v\$ in the list \$L\$. Hence this has the same interpretation as your (1).

3. The "in-neighbours" of a node \$u\$ are the nodes \$v\$ such that there is an edge from \$v\$ to \$u\$. So the in-neighbours are the set of nodes that can be reached from \$u\$ by following one edge in the reverse direction.

Answer 2

You need more functions. I found this code hard to understand as I didn't know what it was doing. Without functions all I know is there are a lot of possibly independent calls in a bunch of for loops. This makes understanding the code very hard.

The creation of all the following should be in their own function:

• visited,
• all_nodes_reverse and the mutation of node_index.
• The display of the reversed graph.
• The creation of 'strongly connected component's.

After doing this to your code it became much easier to understand.

A word explanation of your algorithm is:

1. Create graph.
2. Find visit_time.
3. Display nodes with their visit_time.
4. Invert graph.
   The graph a -> b becomes b -> a.
5. Print inverted graph's edges.
6. Find strongly connected components from inverted graph.
7. Display strongly connected components.

And so we should aim to remove (4). To do this is we can add a list that adds the inverse connections. To then make the addition to both the connections and the inverse connections, we can add the function append to GraphNode. This can simply be:

def append(self, node):
    self.connections.append(node)
    node.connections_inv.append(self)

After this I aimed to simplify DFS, this is as it's a core part of the algorithm. I mostly dislike the addition of visit_time_counter to make it work. Instead you can append to visited where you assign to self.visit_time. This utilizes the ordered aspect of visited to hold the visit_time. This however means you'll need to pass two lists to DFS. And so I'd add a public interface to the current, to be, private function.

To also make DFS more efficient you can change visited to a set. This allows you to have \$O(1)\$ look up on the in operator rather than \$O(n)\$. And I'd also change DFS to return nodes rather than node names.

This can result in:

def _DFS(self, to_add, visited, inverse=False):
    if self in visited:
        return
    visited.add(self)
    for node in self.connections_inv if inverse else self.connections:
        if node not in visited:
            node._DFS(to_add, visited)
    to_add.append(self)

def DFS(self, visited, inverse=False):
    to_add = []
    self._DFS(to_add, set(visited), inverse=inverse)
    visited.extend(to_add)
    return to_add

Usage is pretty much the same as it was before, but we can get a list of new additions. And we get nodes back rather than strings in visited.

After this we can change strongly_connected. As we know that the input list is already sorted we can just flat out reverse it. I'd also make the function a generator, just as it makes the code simpler.

I'd change the algorithm to remove from the nodes when you've visited them. This allows you to remove the pre_visited as those nodes won't be in the list any more. I'd also change sc to be created by a set comprehension, as the way you're doing it now is quite long-winded. And so I'd write:

def strongly_connected(nodes, inverse=True):
    nodes_ = set(nodes)
    visited = []
    for node in reversed(nodes):
        if node not in visited:
            to_remove = node.DFS(visited, inverse=inverse)
            yield {node for node in nodes_ if node in visited}
            for item in to_remove:
                nodes_.remove(item)

After this I'd make the functions:

• all_DFS which creates visited which is just the for loop. And
• display_connections which is the for loop to display the edges of the graph.

This leaves us with just the code that inverts the graph. As we can and have added a keyword to use the inversed connections, we can now just remove the code that creates a new inverted graph.

---

I'd also make this code Python 3 compatible by using __future__.print_function. And I'd change the class to a new-style class by inheriting from object, so that you don't have any problems with the old-style class. If you add more to it.

I'd also recommend that you use lower_case_with_underscores rather than mixedCase for your variables and functions. And for you to follow other things highlighted in PEP8. This is as it makes your code more consistent by following it, and makes your code easier to read.

As for your questions, you should focus more on writing better and cleaner code. Speed isn't everything, but if you really need speed go use C, C++, C#, JAVA, etc.

---

My final code was:

from __future__ import print_function

class GraphNode(object):
    def __init__(self, name):
        self.name = name
        self.connections = []
        self.connections_inv = []

    def __repr__(self):
        return 'GraphNode({!r})'.format(self.name)

    def __hash__(self):
        return hash(self.name)

    def append(self, node):
        self.connections.append(node)
        node.connections_inv.append(self)

    def _DFS(self, to_add, visited, inverse=False):
        if self in visited:
            return
        visited.add(self)
        for node in self.connections_inv if inverse else self.connections:
            if node not in visited:
                node._DFS(to_add, visited)
        to_add.append(self)

    def DFS(self, visited, inverse=False):
        to_add = []
        self._DFS(to_add, set(visited), inverse=inverse)
        visited.extend(to_add)
        return to_add


def all_DFS(nodes, inverse=False):
    visited = []
    for node in nodes:
        if node not in visited:
            node.DFS(visited, inverse=inverse)
    return visited


def strongly_connected(nodes, inverse=True):
    nodes_ = set(nodes)
    visited = []
    for node in reversed(nodes):
        if node not in visited:
            to_remove = node.DFS(visited, inverse=inverse)
            yield {node for node in nodes_ if node in visited}
            for item in to_remove:
                nodes_.remove(item)


def display_connections(nodes, inverse=False):
    for i in nodes:
        for j in i.connections_inv if inverse else i.connections:
            print(i.name, '=>', j.name)


if __name__ == "__main__":
    node_a = GraphNode('A')
    node_b = GraphNode('B')
    node_c = GraphNode('C')
    node_d = GraphNode('D')
    all_nodes = [node_a, node_b, node_c, node_d]
    node_a.append(node_b)
    node_a.append(node_c)
    node_b.append(node_a)
    node_c.append(node_d)
    node_d.append(node_c)

    visited = all_DFS(all_nodes)

    for node in all_nodes:
        print(node.name, visited.index(node) + 1)

    display_connections(all_nodes, inverse=True)
    for sc in strongly_connected(visited):
        print('strongly connected component: ' + ' '.join(i.name for i in sc))