1
\$\begingroup\$

For Coursera's Algorithms course, I have written Kosaraju's algorithms which calculates strongly-connected components in a directed graph using depth first search. The code itself is correct but apparently not very efficient, because it took me almost 24 hours to get the answer for the file SCC.txt which contains about 800.000 edges. Most of the other students could get the answer in well under a minute, so there is definitely something wrong with my code.

The file contains the edges of a directed graph. Vertices are labeled as positive integers from 1 to 875714. Every row indicates an edge, the vertex label in first column is the tail and the vertex label in second column is the head (recall the graph is directed, and the edges are directed from the first column vertex to the second column vertex). So for example, the 11th row looks liks : “2 47646″. This just means that the vertex with label 2 has an outgoing edge to the vertex with label 47646

Your task is to code up the algorithm from the video lectures for computing strongly connected components (SCCs), and to run this algorithm on the given graph.

Output Format: You should output the sizes of the 5 largest SCCs in the given graph, in decreasing order of sizes, separated by commas (avoid any spaces). So if your algorithm computes the sizes of the five largest SCCs to be 500, 400, 300, 200 and 100, then your answer should be “500,400,300,200,100″. If your algorithm finds less than 5 SCCs, then write 0 for the remaining terms. Thus, if your algorithm computes only 3 SCCs whose sizes are 400, 300, and 100, then your answer should be “400,300,100,0,0″.

Could someone take a look? Any critique or advice is welcome.

import csv
import sys
import threading
threading.stack_size(67108864)
sys.setrecursionlimit(2**20)

def read_graph(filename):
g, g_rev = {}, {}
edge_list = []


for line in open(filename):
    edge = [int(num.strip()) for num in line.split()]
    edge_list.append(edge)
    g.setdefault(edge[0], []).append(edge[1])

for ii in range(0,len(edge_list)):
    edge_list[ii][0],edge_list[ii][1]=edge_list[ii][1],edge_list[ii][0]
    g_rev.setdefault(edge_list[ii][0],[]).append(edge_list[ii][1])

return g, g_rev


def DFS(graph,node1):
global s, s_explored, leader, finishing_time, leader
s_explored.append(node1)
leader[node1]=s
if node1 in graph.keys():
    for node2 in graph[node1]:
        if node2 not in s_explored:
            DFS(graph,node2)
finishing_time.append(node1)

def DFS_loop(graph, transverse_list):
global s,s_explored,finishing_time,leader
leader = {}
s_explored, finishing_time = [], []
s = 0
for node1 in transverse_list[::-1]:
    if node1 not in s_explored:
        s = node1
        DFS(graph, node1)
return finishing_time, leader


def main():
    filename = sys.argv[1]
    g, g_rev = read_graph(filename)

    #Define the global variables
    leader = {}
    s_explored, finishing_time = [], []
    s = 0

    #define the inputs and outputs of first DFS-loop

    #f_t is a list with the finishing times of the nodes according to the first DFS
    #this list of finishing times will be used in the second loop
    #lead is a dictionary with the leaders; {[9]:8} for example means that the leader                                   
    #of node 9 is node 8.
    #the leader-dict coming from the first loop is not used, but the leader-dict coming
    #from the second loop is used to calculate which nodes have the same leader and  
    #therefore are part of the same SCC.
    grev_nodes = [key for key in g_rev.keys()]
    f_t, lead = [], {} 
    f_t, lead = DFS_loop(g_rev, grev_nodes)

    #define the inputs and outputs of second DFS-loop
    f_t2, lead2 = [],{}
    f_t2, lead2 = DFS_loop(g, f_t)

    #print out result
    SCC = {}
    for ii in range(0,len(lead2.values())):
            SCC.setdefault(lead2.values()[ii],[]).append(ii)
    SCC_lengths = []
    for key in SCC.keys():
            SCC_lengths.append(len(SCC[key]))
    SCC_lengths.sort(reverse=True)
    if len(SCC_lengths)<5:
            for ii in range(5-len(SCC_lengths)):
                    SCC_lengths.append(0)
    print SCC_lengths






if __name__ == '__main__':
thread = threading.Thread(target=main)
thread.start()
\$\endgroup\$
  • \$\begingroup\$ You missed placing the links in the paragraphs after the code. BTW you can use Ctrl + L to place links on text. There are other shortcuts that you can see at the topwhen you use edit button. It is cleaner that way instead of pure markup and easier to edit. \$\endgroup\$ – Aseem Bansal Aug 5 '13 at 18:34
  • \$\begingroup\$ I cannot tell you why it is slow, but I can tell you that the code is hard to read. What is g, the difference between g_rev and edge_list. I would start by using meaninful variables for everything before finding out what slows this down. \$\endgroup\$ – konijn Aug 5 '13 at 21:06
1
\$\begingroup\$

Generally, with Kasuraju's algorithm (and other graph search algorithms), the biggest bottleneck is reading in the edges and then holding these in memory. If I understand this correctly, you have about 800,000 VERTEXES, which will lead to a few million edges. Holding both G and G_rev in memory at the same time will be a big call. You could consider writing a helper function to read in the graph (either G or G_rev). As an example:

def read_graph(input_file, reverse=False):

    G = defaultdict(list)

    for line in open(input_file):
        i, j = line.split()

        # initialise each node:
        # G = { node : [False, [outgoing arcs], ...}
        # where False indicates whether visited or not
        G[int(i)] = [False] if not G[int(i)] else G[int(i)]
        G[int(j)] = [False] if not G[int(j)] else G[int(j)]

        # read in the directed edges
        # read in straight for second DFS, read in reversed for first DFS
        if not reverse:
            G[int(i)].append(int(j))
        else:
            G[int(j)].append(int(i))

    return G

After your first DFS loop (using G_rev) you could flush G_rev from memory and then call read_graph() again to read in the forward directed graph.

I haven't had a good look through the rest of the code, but I will do later today. As a first thought, you are keeping a list of explored nodes - again I think this is using more memory than you really need and could be replaced with a flag in the dictionary (see the boolean True / False flag in the dictionary above).

-- DFS function This looks like it may be one of your biggest bottlenecks. Recursion is not particularly well supported in Python - this is a problem for an algorithm that runs this deep! You might have to consider an iterative approach to calculating the "magic ordering" in the first DFS loop. Perhaps something like:

def magic_order():

    global stack  # Last In, First Out data stucture
    global ranks  # the finishing times for each node
    global G

    keys = sorted(G.keys(), reverse=True)
    for node in keys:
        if not G[node][0]:
            stack.append(node)

            while stack:
                leader = stack[-1]
                try:
                    G[leader][0] = True
                    outgoing = []
                    try:
                        outgoing = [j for j in G[leader][1:] if not G[j][0]]
                    except IndexError:
                        pass
                    if outgoing:
                        stack.extend(outgoing)
                    else:
                        ranks.append(leader)
                        stack.pop()
                except KeyError:
                    ranks.append(leader)

Hopefully this will help put you on the right track. The original graph will need to be re-sorted to match the finishing times calculated, and a second DFS call coded to calculate the SCCs (which should be less memory intensive than these first two steps). Good luck!

\$\endgroup\$
0
\$\begingroup\$

my fellow Algo classmate.

You need be careful picking the right data structure for your variables. Considering the large size of the input file and the purpose of variables, I would generally avoid using list, lookups in list is order of O(n) while O(1) in dict and set.

That being said, a set is perfect for your s_explored, and you can make finishing_time a dict. I bet these alone would make a big difference. And you can follow the same principle to refactor your code. Overall, I don't see a problem in your implementation of the algorithm, so the performance is all about handling the data.

I think tomdemuyt made a good point about readability, which is important especially when you want your code reviewed.

BTW, here is my personal implementation of the algorithm, you may want to take a look.

\$\endgroup\$

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.