Find the lengths of strongly connected components in a graph

Question

I wrote a code to calculate the lengths of strongly connected components in a graph. The results I get are correct but it scales horribly.

This is the code I have. I understand that the runtime complexity of a graph traversals should be O(V+E) and as far as I understand, I am not visiting any node twice. And yet it takes forever for bigger graphs (875714 nodes and 5105043 edges)

class Graph:
    def __init__(self):
        self.graph = {}
        self.rev_graph = {}
        self.num_vertices = 0
    def addEdge(self, tail, head):
        if tail in self.graph:
            self.graph[tail].append(head)
        else:
            self.graph[tail]=[head]
        if head in self.rev_graph:
            self.rev_graph[head].append(tail)
        else:
            self.rev_graph[head] = [tail]
    def dfs(self, visited, start_node, stack):
        visited[start_node] = True
        if start_node in self.graph:
            for i in self.graph[start_node]:
                if not visited[i]:
                    self.dfs(visited, i, stack)
            # del self.rev_graph[start_node]
        stack.append(start_node)
    def dfs_counter(self, visited, start_node, delim='  '):
        l1 = sum(visited)
        visited[start_node] = True
        if start_node in self.rev_graph:
            # print(delim, 'rev graph neighbors: ', start_node, self.rev_graph[start_node])
            for i in self.rev_graph[start_node]:
                if not visited[i]:
                    self.dfs_counter(visited, i, 2*delim)
        l2 = sum(visited)
        return l2 - l1
        # print(stack)
    def find_scc_lens(self):
        self.num_vertices = len(set(list(self.graph.keys()) + list(self.rev_graph.keys())))
        visited = [False]*self.num_vertices
        stack = []
        self.dfs(visited, 0, stack)
        # stack = stack[::-1]
        # print(stack)
        # del(self.graph)
        visited = [False] * self.num_vertices
        scc_lengths = []
        for k,i in enumerate(stack[::-1]):
            if not visited[i]:
                # print("rev graph node count", k, i)
                scc_lengths.append(self.dfs_counter(visited, i))
        return scc_lengths

This exercise is from an online course I am taking. I tried a few other solutions online I found elsewhere and they are really fast compared to my runtimes.

What parts of the code can I optimize to improve the runtimes?

---

Example:

g = Graph()
g.addEdge(1, 0);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.addEdge(0, 3);
g.addEdge(3, 4);
g.find_scc_lens()

Answer 1

class Graph:
    def __init__(self):
        self.graph = {}
        self.rev_graph = {}
        self.num_vertices = 0

This looks reasonable. Note that the PEP8 style guide wants you to add a blank line after each method.

---

    def addEdge(self, tail, head):
        if tail in self.graph:
            self.graph[tail].append(head)
        else:
            self.graph[tail]=[head]
        if head in self.rev_graph:
            self.rev_graph[head].append(tail)
        else:
            self.rev_graph[head] = [tail]

The failure to update self.num_vertices here does not look reasonable. I suspect that the reason is that num_vertices shouldn't be a property of the class.

---

    def dfs(self, visited, start_node, stack):
        visited[start_node] = True
        if start_node in self.graph:
            for i in self.graph[start_node]:
                if not visited[i]:
                    self.dfs(visited, i, stack)
            # del self.rev_graph[start_node]
        stack.append(start_node)

In future, please remove commented code before submitting the code for review.

I could use a comment to explain the purpose of stack, and why it adds in post-order rather than pre-order.

---

    def dfs_counter(self, visited, start_node, delim='  '):
        l1 = sum(visited)
        visited[start_node] = True
        if start_node in self.rev_graph:
            # print(delim, 'rev graph neighbors: ', start_node, self.rev_graph[start_node])
            for i in self.rev_graph[start_node]:
                if not visited[i]:
                    self.dfs_counter(visited, i, 2*delim)
        l2 = sum(visited)
        return l2 - l1
        # print(stack)

sum(visited) is expensive: too expensive to use in this method, which is called inside a loop. If you refactor to track the sum directly then I expect you'll see a notable speedup.

2*delim probably isn't really desirable: it should probably be delim + ' '.

---

    def find_scc_lens(self):
        self.num_vertices = len(set(list(self.graph.keys()) + list(self.rev_graph.keys())))

It should be possible to do this without using list.

        visited = [False]*self.num_vertices

This is buggy. num_vertices is the number of vertices, not the largest vertex. Consider the graph

g = Graph()
g.addEdge(2, 3)
g.addEdge(3, 2)

The output should be either [2] (vertices with no edges don't exist) or some permutation of [1, 1, 2] (with vertices 0 to 3).

        stack = []
        self.dfs(visited, 0, stack)
        # stack = stack[::-1]
        # print(stack)
        # del(self.graph)

This is also buggy. What about vertices which aren't reachable from 0? Even if you add documentation saying that this method only works for connected graphs, that doesn't rule out

g = Graph()
g.addEdge(1, 2)
g.addEdge(2, 1)
g.addEdge(1, 0)

        visited = [False] * self.num_vertices
        scc_lengths = []
        for k,i in enumerate(stack[::-1]):
            if not visited[i]:
                # print("rev graph node count", k, i)
                scc_lengths.append(self.dfs_counter(visited, i))
        return scc_lengths

In order to validate the correctness of this implementation, it would be immensely useful to have a comment which says which algorithm it implements (and ideally links to reference material).