6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Looks like the formatting of if __name__ == "__main__" part are not formatting properly, tried but cannot fix, anyone could help to fix the formatting? Thanks. \$\endgroup\$ – Lin Ma Oct 4 '16 at 22:56
  • 4
    \$\begingroup\$ Markdown thought that the indentation makes it part of the numbered list rather than a code block. The solution is to add a <!-- --> comment to end the list. \$\endgroup\$ – 200_success Oct 4 '16 at 23:02
  • \$\begingroup\$ @200_success, you rock! \$\endgroup\$ – Lin Ma Oct 4 '16 at 23:18
  • 1
    \$\begingroup\$ I've always wondered that but never asked. Thanks for that hint @200_success \$\endgroup\$ – яүυк Oct 6 '16 at 10:58
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks Gareth, love your Graph data structure and vote up. For your code def __init__(self, edges=()):, confused a bit by line edge=() does () mean empty tuple? \$\endgroup\$ – Lin Ma Oct 7 '16 at 5:06
  • \$\begingroup\$ BTW, Garesh, after reading your code and algorithm description on wikipedia, a bit lost here. I think (1) if there is an edge u=>v, when in the final list L, u should be before v, since elements in L is ordered in reverse order of DFS completion sequence (this is how your code works). (2) But the wikipedia said "This means it does not matter whether a vertex v was first Visited because it appeared in the enumeration of all vertices or because it was the out-neighbour of another vertex u that got Visited; either way v will be prepended to L before u is" -- does it mean if there is an edge u=>v \$\endgroup\$ – Lin Ma Oct 7 '16 at 5:41
  • \$\begingroup\$ (cont'd) in the final list of L, v should before u? If v before u, it means v complete DFS later than u? It seems some conflict before (1) and (2), any thoughts? \$\endgroup\$ – Lin Ma Oct 7 '16 at 5:42
  • 1
    \$\begingroup\$ @LinMa: See updated answer. \$\endgroup\$ – Gareth Rees Oct 7 '16 at 9:35
  • 1
    \$\begingroup\$ @LinMa: See updated answer. \$\endgroup\$ – Gareth Rees Oct 9 '16 at 20:51
3
\$\begingroup\$

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))
\$\endgroup\$
  • \$\begingroup\$ Thanks Joe, love all of your comments. There is only one issue (which I should state clearly before), I cannot change the data structure of GraphNode (you can treat it as a predefined data structure). In this way, you can not add connections_inv to the class. So, any ideas for efficient reverse the graph? \$\endgroup\$ – Lin Ma Oct 6 '16 at 4:52
  • \$\begingroup\$ BTW, for your comments "Speed isn't everything, but if you really need speed go use C, C++, C#, JAVA, etc.", for speed I mean more about algorithm time complexity (no matter what language is using), using smarted algorithm and using smarted data structures, e.g. using set in your code is a smarted solution than my original code. :) \$\endgroup\$ – Lin Ma Oct 6 '16 at 5:07
  • \$\begingroup\$ BTW, Joe, I tested your code works pretty good without __repr__ and __hash__, wondering if we can safely remove them for simpler code? \$\endgroup\$ – Lin Ma Oct 6 '16 at 5:26
  • 1
    \$\begingroup\$ @LinMa Yeah subclass GraphNode and add my changes. You don't need __repr__, I added it for easier debugging, __hash__ I added just in case, feel free to remove it if you need to. My point before "C, C++" was my main point there, and now that the code is somewhat simpler you should be able to improver performance. As for your last point, I noticed you can just yield set(node.DFS(visited, inverse=inverse)) but I was unsure whether it's correct, and so left it. \$\endgroup\$ – Peilonrayz Oct 6 '16 at 7:52
  • 1
    \$\begingroup\$ @LinMa By that I mean you can change the entire of the if to just that. So if node not in visited: yield set(node.DFS(visited, inverse=inverse)). (Which is the same as the comprehension you're doing, but yours may keep unneeded things) \$\endgroup\$ – Peilonrayz Oct 6 '16 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.