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 47646Your 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 csvimport sysimport threadingthreading.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_revdef DFS(graph,node1):global s, s_explored, leader, finishing_time, leaders_explored.append(node1)leader[node1]=sif 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,leaderleader = {}s_explored, finishing_time = [], []s = 0for node1 in transverse_list[::-1]:    if node1 not in s_explored:        s = node1        DFS(graph, node1)return finishing_time, leaderdef 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_lengthsif __name__ == '__main__':thread = threading.Thread(target=main)thread.start()
Calculating strongly-connected components in a directed graph using DFS
python;performance;algorithm
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 GAfter 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 functionThis 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!