3
\$\begingroup\$

I implemented Kosaraju's algorithm on a graph with 800k vertices and 5100k edges. The time taken by various operations are: building graph took 11.84 seconds ordering took 2.54 seconds finding SCCs took 2.63 seconds My computer has an i7 with 4GB RAM. I would like to know if my code can be made more efficient. How can I improve the way I've approached the problem?

def makeGraph(txtfile):
    '''Makes a graph(defaultdict) from given text file
        Input: txt, each line's first element gives tail, next is head of an edge
        Output: defaultdict, each vertex as a key with two values'''
    Graph = defaultdict(lambda:[[],[]])
    with open(txtfile) as graphRep:
        for line in graphRep:
            tail,head = line.split()
            tail,head = int(tail),int(head)
            Graph[tail][0].append(head) #edge from key(tail) to head
            Graph[head][1].append(tail) #above edge reversed
    return Graph

def dfs_Order_main(G):
    ''' outer loop for dfs call, iterates through each vertex
        calls dfs on it if has not been explored
        Input: Graph(defaultdict)
        Output: Order(dict)'''
    Order = {} #stores time taken to explore a vertex
    count =[1] 
    toVisit = []
    visited = set()
    for vert in range(1,len(G.keys())+1):
        if vert not in visited:
            dfs_Order(G,vert,Order,visited,count)
    return Order

def dfs_Order(G,vert,Order,visited,count):
    toVisit = [vert]
    while len(toVisit)>0:
        nextNode = toVisit[-1] #LIFO
        if G[nextNode][1] == []: #no more edges to explore (terminating condition)
            visited.add(nextNode) # completed exploring
            v = toVisit.pop() 
            Order[count[0]]=v #store time
            count[0] +=1
        else:
            visited.add(nextNode)
            for i in G[nextNode][1]:
                if i not in visited:
                    visited.add(i)
                    toVisit.append(i)
            G[nextNode][1] = [] #after adding a vertex's edges, set it to []
    return                                    #used as terminating condition 

def dfs_scc_main(G,order):
    ''' outer loop for dfs call, iterates through each vertex
        calls dfs on it if has not been explored
        Input: Graph(defaultdict),order in which vertices are to be explored
        Output: scc(defaultdict), strongly connected components'''
    scc = defaultdict(int)
    toVisit = []
    visited = set()
    for i in range(len(order),0,-1): #traverse in decreasing order of time 
        vert = order[i]                         #taken to explore a vertex
        if vert not in visited:
            dfs_scc(G,vert,scc,visited)
    return scc

def dfs_scc(G,lead,scc,visited):
    toVisit = [lead]
    scc[lead] +=1 #increments the value for a leader
    while len(toVisit)>0:
        nextNode = toVisit[-1]
        if G[nextNode][0] == []:
            visited.add(nextNode)
            toVisit.pop()
        else:
            visited.add(nextNode)
            for i in G[nextNode][0]:
                if i not in visited:
                    scc[lead] +=1
                    visited.add(i)
                    toVisit.append(i)
            G[nextNode][0] = []
    return
\$\endgroup\$

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.