# Strongly Connected component algorithm implementation(Python)

My goal is to implement Strongly Connected Components algorithm using python. I have splitted up my code on 3 parts:

import csv as csv
import numpy as np
import random as random
import copy as copy
import math
import time
sys.setrecursionlimit(800000)

start = time.time()

num_nodes = 160000
graph = [[] for i in range(num_nodes)]
reverse_graph = [[] for i in range(num_nodes)]
graph_2_step = [[] for i in range(num_nodes)]

file = open("C:\\Users\\yefida\\Desktop\\Study_folder\\Online_Courses\\Algorithms\\Project 5\\test7.txt", "r")
for line in data:
if line.strip():
items = line.split()
if int(items[1]) not in reverse_graph[int(items[1]) - 1]:
reverse_graph[int(items[1]) - 1].append(int(items[1]))
reverse_graph[int(items[1]) - 1].append(int(items[0]))
else:
reverse_graph[int(items[1]) - 1].append(int(items[0]))

if int(items[0]) not in graph[int(items[0]) - 1]:
graph[int(items[0]) - 1].append(int(items[0]))
graph[int(items[0]) - 1].append(int(items[1]))
else:
graph[int(items[0]) - 1].append(int(items[1]))

for i in range(len(graph)):
if len(graph[i]) == 0:
graph[i] = [i+1,i+1]
if len(reverse_graph[i]) == 0:
reverse_graph[i] = [i+1,i+1]

end = time.time()
time_taken = end - start
print('Time: ',time_taken)

2. Depth-first search algorithm on the reversed graph:

#2. Run DFS-loop on reversed Graph:
start = time.time()

t = 0 # for finishing lines: how many nodes are processed so far
s = None # current source vertex
explored = set()
finish_time = {}

def DFS(graph,node):
global s

for vertex in graph[node - 1][1:]:
if vertex not in explored:
DFS(graph,vertex)

global t
t+= 1
finish_time[node] = t

#Nodes starts from n to 1
for i in range(max(reverse_graph)[0],0,-1):
if i not in explored:
s = i
DFS(reverse_graph,i)

#Mapping to the new list in increasing order
for edge in range(len(graph)):
for vertex in range(len(graph[edge])):
graph[edge][vertex] = finish_time[graph[edge][vertex]]

graph_2_step[graph[edge][0] - 1] = graph[edge]

end = time.time()
time_taken = end - start
print('Time: ',time_taken)

3. Depth-first-search algortihm on the graph after step 2:

  #3. Run DFS-loop on Graph with original directions(but with labeled finishing times):
all_components = []#Saves all strongly connected components
all_comp_elem = set()#check if element is in Strongly Connected Components(already explored)
SSC = set() # strongly connected component, that will be saved in "all_components"
explored= set()  # variables, that are already explored
next_elem = 0 # contains information how many elements have to be checked, before making a decision
#c)modification of DFS
def DFS_2_Path(graph,node):
global all_components
global SSC
global next_elem

next_elem += len(graph[node - 1][1:]) # add number elements, that must be explored from the current node
#checking one vertex -> minus one element that must be explored
for vertex in graph[node - 1][1:]:
next_elem -= 1
#check if element is in Strongly Connected Components(already explored)
if node not in all_comp_elem:

#if vertex is not explored, than reccursion and go to the next vertex
if vertex not in explored:

DFS_2_Path(graph,vertex)

#if vertex is not the last element in the chain(Ex: [6,5,1,7] -> 6 is a main Node, and 7 is the last element, to which
#node 6 is connected)
elif vertex in explored and vertex != graph[node - 1][1:][len(graph[node - 1][1:]) - 1]:
continue
#if vertex is the last element in the chain(Ex: [6,5,1,7] -> 6 is a main Node, and 7 is the last element, to which
#node 6 is connected) -> update stringly connected components
elif vertex in explored and vertex == graph[node - 1][1:][len(graph[node - 1][1:]) - 1] and next_elem == 0:
all_components.append(SSC)
all_comp_elem.update(SSC)
SSC = set()

#Main loop
for i in range(max(graph_2_step)[0],0,-1):
if i not in explored:
DFS_2_Path(graph_2_step,i)

end = time.time()
time_taken = end - start
print('Time: ',time_taken)


I have tested my algorithm on different test cases -> it works correct. First two parts of the algorithm work fast(on the data set with 160000 nodes). But when I run the third part -> kernel in Jupyter dies.

I have improved the speed of the code as much as I could. I definitely need a fresh look on my code.

P.S Don't look at first 2 parts of the code. I provided them to you only for the test, if you want to test.

P.S.S The link to the file, that I have used for the test: https://github.com/beaunus/stanford-algs/blob/master/testCases/course2/assignment1SCC/input_mostlyCycles_64_160000.txt

• Have you had a look at the networkx library and especially its strongly_connected_components function? Not that I wanted to discourage you from trying it yourself, but depending on your needs that could make it a lot easier. – AlexV Jun 14 '19 at 9:12
• What do you mean with reversed graph? – dfhwze Jun 14 '19 at 9:13
• @dfhwze By reversed graph I meant, that we reverse all of the arcs in our original graph – Daniel Yefimov Jun 14 '19 at 9:38
• @AlexV I know, that special library exists. I am coding this algorithm in order to improve my skills in Python and to understand algorithms better :) – Daniel Yefimov Jun 14 '19 at 9:39