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


Not sure if my current implementation for adjacent table of graph is efficient?
Any better ideas to reverse the graph to make it more efficient?
I use preVisited and visited to track what nodes are already reached by a strongly connected components, it there a better way?
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, '=&gt;', 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
1. Review


The code is not portable to Python 3 due to the use of the print statement.
The code is not organized into functions. This makes it hard to understand and hard to test.
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).
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.)
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:


  
  For each vertex \$u\$ of the graph, mark \$u\$ as unvisited. Let \$L\$ be empty.
  For each vertex \$u\$ of the graph do \$Visit(u)\$, where \$Visit(u)\$ is the recursive subroutine:
  If \$u\$ is unvisited then:
  
  
  Mark \$u\$ as visited.
  For each out-neighbour \$v\$ of \$u\$, do \$Visit(v)\$.
  Prepend \$u\$ to \$L\$.
  
  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:
  
  
  Assign \$u\$ as belonging to the component whose root is \$root\$.
  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:

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



2. Answers to questions


() is the empty tuple. See the documentation.
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).
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.