2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – AlexV Apr 25 at 15:26
  • \$\begingroup\$ Do you need to use your own implementation? If not, there is the networkx graph library, which also conviniently features a SCC implementation. \$\endgroup\$ – AlexV Apr 25 at 20:33
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.