3
\$\begingroup\$

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

  1. 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)
    
  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):
        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)
    
  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 
        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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – AlexV Jun 14 at 9:12
  • \$\begingroup\$ What do you mean with reversed graph? \$\endgroup\$ – dfhwze Jun 14 at 9:13
  • \$\begingroup\$ @dfhwze By reversed graph I meant, that we reverse all of the arcs in our original graph \$\endgroup\$ – Daniel Yefimov Jun 14 at 9:38
  • \$\begingroup\$ @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 :) \$\endgroup\$ – Daniel Yefimov Jun 14 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.