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.
df
? \$\endgroup\$ – AlexV Apr 25 '19 at 15:26