# Strongly connected component in graph

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.

• Welcome to Code Review! Your code does not seem to be complete (i.e. runnable). Would it be correct to assume that the presented input is in df? – AlexV Apr 25 '19 at 15:26
• Do you need to use your own implementation? If not, there is the networkx graph library, which also conviniently features a SCC implementation. – AlexV Apr 25 '19 at 20:33

## 1 Answer

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.