My goal is to implement Strongly Connected Components algorithm using python. I have splitted up my code on 3 parts:
Data Load:
import csv as csv import numpy as np import random as random import copy as copy import math import sys, threading import time sys.setrecursionlimit(800000) threading.stack_size(67108864) 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") data = file.readlines() 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)
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): explored.add(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)
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 explored.add(node) #node is explored 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: SSC.add(node) #if vertex is not explored, than reccursion and go to the next vertex if vertex not in explored: SSC.add(vertex) 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