3
\$\begingroup\$

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()
\$\endgroup\$
  • 2
    \$\begingroup\$ Graph traversal is an NP class of problem. That ALL algorithms we are aware off scale horribly. While I can't claim to be intimately familiar with graph traversal, I also don't see any glaring issues. How big, exactly, is the size of the Graphs when you get MemoryErrors? Does "really big" mean 1000 nodes or 1000000 nodes? \$\endgroup\$ – Gloweye Oct 23 '19 at 11:12
  • 1
    \$\begingroup\$ Also, welcome to Code Review. Please read the tour if you haven't, or How to Ask if you want to know more about what questions exactly we want. Note that if it turns out you're looking for mathematical help, this question may be migrated towards a more suitable site. \$\endgroup\$ – Gloweye Oct 23 '19 at 11:14
  • 2
    \$\begingroup\$ I understand there might be a need for a little bit more information but I really don't think this post should be closed, the code is there, works to OPs knowledge and the title is fine. \$\endgroup\$ – IEatBagels Oct 23 '19 at 13:54
  • \$\begingroup\$ @Gloweye, graph traversal is indeed in NP, but it's also in P, and OP is correct to say that it's in \$O(V + E)\$ (although this particular implementation isn't). \$\endgroup\$ – Peter Taylor Oct 23 '19 at 16:10
2
\$\begingroup\$
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).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the nice detailed comments, Peter. I didn't realize the sum could be a potential issue. That was sort of a revelation. I went through a couple of videos online after this post and realized the implementation is indeed buggy and works only for a few cases which I was using as examples. I am not sure if we are supposed to keep up the posts that are coming out of incorrect understanding. I threw away this code and rewrote it which resolves all the current issues. I was going through meta posts and meanwhile, you answered. It's a pickle for me now. I.... \$\endgroup\$ – Clock Slave Oct 23 '19 at 16:29
  • \$\begingroup\$ If the sequence of operations had been different, you could have deleted your question temporarily, edited it with the fixed code, and undeleted it. But once you have an answer, that option is removed. What you can do now is to post a new question with the new code and link back to this one for context. \$\endgroup\$ – Peter Taylor Oct 23 '19 at 16:32
  • \$\begingroup\$ Okay. But my new question wouldn't have any issues (as far as I know). I have fixed the code since I put up the post. Is it okay to put up posts with no real issues? And wouldn't I be downvoted a lot? \$\endgroup\$ – Clock Slave Oct 23 '19 at 16:38
  • \$\begingroup\$ If you think the new version is fine, you don't have to ask for it to be reviewed, but the option is there if you want it. There's a sense in which the better the code, the more advanced the review can be, so you might still learn something. See codereview.stackexchange.com/search?q=Iterative+review for reassurance about downvotes. \$\endgroup\$ – Peter Taylor Oct 23 '19 at 22:58

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.