Strongly connected component in graph

Question

My goal is to calculate the length of each strongly connected component (SCC)

I have an input that looks like this:

[['1', '2'],
 ['1', '2'],
 ['1', '5'],
 ['1', '6'],
 ['1', '7'],
 ['1', '3'],
 ['1', '8'],
 ['1', '4'],
 ['2', '47646'],
 ['2', '47647'],
 ['2', '13019']...

where lists inside big list means edge and elements of inside lists mean first and second vertex respectively.

Here is my code:

#1.Create reverse graph: changing directions of the directed graph
#a)
df_reverse = [None] * len(df)
for i in range(len(df)):
    df_reverse[i] = [int(df[i][1])]
    df_reverse[i].append(int(df[i][0]))
#b) Sort the array according to df_reverse[i][0]
df_reverse = sorted(df_reverse,reverse = True)

#2. Run DFS-loop on reversed Graph:

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

def DFS(graph,node):
    explored.append(node)
    global s
    leader = s 
    print('Node:',node)
    print('Leader:',leader)
    #index = [ind for ind,vertex  in enumerate(df_reverse) if vertex[0] == node]
    for second_vert in graph:
        print('Second_vert:',second_vert)
        print('Second_vert[0] == node:',second_vert[0] == node)
        if second_vert[0] == node:
            print('second_vert[1] not in explored :',second_vert[1] not in explored)
            if second_vert[1] not in explored:
                print('---------------------------------')
                print('NEXT ITERATION OF THE INNER LOOP')
                print('-------------------------------------')
                DFS(graph,second_vert[1])


    global t
    print('t was:',t)
    t+= 1
    print('t is :',t)
    print('Index:',index)
    finish_time[node] = t

    print('LEADER TO THE NODE ',node,' IS ASSIGNED!')
    print('-------------------------------------------')

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


#mapping finishing time to nodes
for ind,val in enumerate(df_reverse):
    df_reverse[ind][0] = finish_time[df_reverse[ind][0]]
    df_reverse[ind][1] = finish_time[df_reverse[ind][1]]




#3. Run DFS-loop on Graph with original directions(but with labeled finishing times):
df_reversed_back = [None] * len(df_reverse)
for i in range(len(df_reverse)):
    df_reversed_back[i] = [int(df_reverse[i][1])]
    df_reversed_back[i].append(int(df_reverse[i][0]))
#b) Sort the array according to df_reverse[i][0]
df_reversed_back = sorted(df_reversed_back,reverse = True)

all_components = []
SSC = []
explored= []
#c)modification of DFS
def DFS_2_Path(graph,node):
    #global SSC
    global all_components
    explored.append(node)
    print('Node:',node)
    #index = [ind for ind,vertex  in enumerate(df_reverse) if vertex[0] == node]
    for second_vert in graph:
        print('Second_vert:',second_vert)
        print('Second_vert[0] == node:',second_vert[0] == node)
        if second_vert[0] == node:
            print('second_vert[1] not in explored :',second_vert[1] not in explored)
            if second_vert[1] not in explored:
                print('SSC was:',SSC)
                SSC.append(second_vert[1])
                print('SSC is:',SSC)
                print('---------------------------------')
                print('NEXT ITERATION OF THE INNER LOOP')
                print('-------------------------------------')
                DFS_2_Path(graph,second_vert[1])
            if second_vert[1] in explored and len(SSC)> 0: #check if second vert is not explored and if it's not a new SSC
                print('SSC was:',SSC)
                SSC.append(second_vert[1])
                print('SSC is:',SSC)

                all_components.append(SSC[:])
                print('All_components is :',all_components)
                SSC[:] = []

    print('All_components was:',all_components)


for i in range(max(df_reversed_back[0]),0,-1):
    if i not in explored:
        s = i
        DFS_2_Path(df_reversed_back,i)

The problem is, that my code is very slow. I would appreciate any improvements and suggestions.

Answer 1

The debug logging is not going to help performance. You should really remove debugging code (and commented out code) before you ask for code review.

---

df_reverse = [None] * len(df)
for i in range(len(df)):
    df_reverse[i] = [int(df[i][1])]
    df_reverse[i].append(int(df[i][0]))

is hard to read and understand.

def reversed_edge:
    return [int(edge[1]), int(edge[0])]


df_reverse = [reversed_edge(edge) for edge in df]

is clearer (although neither makes clear why the input isn't already using ints). And the meaning of df in df_reverse is opaque to me.

---

DFS contains two lines of code which just assign to unused variables, and some commented out code. Removing those, we get

def DFS(graph,node):
    explored.append(node)
    for second_vert in graph:
        if second_vert[0] == node:
            if second_vert[1] not in explored:
                DFS(graph,second_vert[1])

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

There are two red flags here:

1.     for second_vert in graph:
           if second_vert[0] == node:
   

   graph (which is really df_reverse) is going to be filtered for every node in the graph, which means that it's using the wrong data structure. It should be a dict. This is almost certainly a major cause of the performance problem.

2. t and finish_time are defined in the same global scope, but only one of them is declared global here. That may or may not be a bug, but it's certainly confusing.

---

As for the rest of the code, I can't understand what it's doing without some more helpful comments. Comments indicating that the following section of code implements step #1.a) are useless without an initial comment indicating the resource which the code follows. But since it's apparently doing two DFSs I rather hope that it's possible to refactor the code so that (a) it only implements DFS once, and calls it twice; (b) it does so with clearer scopes.