# Calculating strongly-connected components in a directed graph using DFS

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
sys.setrecursionlimit(2**20)

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):
s_explored.append(node1)
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):
s_explored, finishing_time = [], []
s = 0
for node1 in transverse_list[::-1]:
if node1 not in s_explored:
s = node1
DFS(graph, node1)

def main():
filename = sys.argv[1]

#Define the global variables
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
#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()]

#define the inputs and outputs of second DFS-loop

#print out result
SCC = {}
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__':

• 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. Aug 5, 2013 at 18:34
• 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. Aug 5, 2013 at 21:06

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:
try:
outgoing = []
try:
outgoing = [j for j in G[leader][1:] if not G[j][0]]
except IndexError:
pass
if outgoing:
stack.extend(outgoing)
else:
stack.pop()
except KeyError:

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.