Size (number of edges) of strongly connected components (SCC) in a graph using Kosaraju's algorithm

1k Views Asked by At

I have coded up Kosaraju's two-pass algorithm in Python 3, the current implementation finds SCCs and determines the size of each SCC based on the number of nodes in each SCC. Then, the largest SCCs are determined. How can I change the code so it can calculate the size of each SCC based on the number of edges in each SCC.

# Input : a directed graph, G
import sys, threading, time


# Increase recursion limit and stack size in windows environment
sys.setrecursionlimit(2 ** 20)
threading.stack_size(67108864)


# Source file has one directed edge per line
# e.g. "1 5" is one line. 1 is the tail and 5 is the head
source = "???.txt"
# Number of nodes
n = ???


def main():
    def Kosaraju(G,G_rev):
        global leader, finish
        # Set leader for strongly connected group
        leader = {}
        # Set finishing time for each element
        finish = {}
        # Run first DFS Loop
        DFS_Loop(G_rev)
        # Reorder graph with nodes numbered according to finish time
        G_reordered = {}
        g_values = list(G.values())
        for i in range(1,n+1):
            temp = g_values[i-1]
            G_reordered[finish[i]] = [finish[x] for x in temp]
        # Run second DFS Loop with reordered graph
        DFS_Loop(G_reordered)
        return leader

    def DFS_Loop(G):
        global t,s, explored
        t = 0 # Number of nodes processed so far (only useful for pass 1)
        s = 0 # Current source vertex (only useful for pass 2)
        # Initialize all nodes as unexplored
        explored = {}
        for i in range(1,n+1):
            explored[i] = 0 
        # Explore each adjacent node i (if unexplored)
        for i in range(n,0,-1):
            if explored[i] == 0:
                s = i
                DFS(G,i)
        return

    def DFS(G,i):
        # Run Depth First Search
        global t, leader, finish
        explored[i] = 1 # Mark node i as explored
        leader[i] = s # Sets leader as node s (useful for second pass only)
        # For each arc (i,j) in G, if j is not yet explored, recurse on j
        for j in G[i]:
            if explored[j] == 0:
                DFS(G,j)
        t = t + 1
        finish[i] = t
        return

    def get_graph():
        # Grabs graph from input file
        # Create dictionary with a key for each node
        G, G_rev = {}, {}
        for i in range(1,n+1):
            G[i], G_rev[i]  = [], []
        # Populate dictionary with information from file
        file = open(source)
        for line in file:
            list_line = line.split()
            i = int(list_line[0])
            j = int(list_line[1])
            G[i].append(j)
            G_rev[j].append(i)
        file.close()
        return G, G_rev

    def most_common(lst,x):
        # This functions returns the 'x' most common elements from 'lst' 
        from collections import Counter
        c = Counter(lst)
        output = []        
        for number,count in c.most_common(x):
            output.append(count)
        return output               

    if __name__=="__main__":
        G, G_rev = get_graph()
        leader = Kosaraju(G,G_rev)
        print(most_common(leader.values(),x))


thread = threading.Thread(target=main)
thread.start()

for example for a graph as (presented below as a list of lists, only for the sake of simplicity): [[1,2],[2,3],[2,5],[3,4],[4,1],[5,6],[6,7],[7,5]] the first element is tail and the second element is head.

the result of the above code, including the size of SCC in decreasing order, is [4,3]

However, the current implementation results in the same numbers for a graph as: [[1,2],[1,3],[2,3],[2,5],[3,4],[4,1],[5,6],[6,7],[7,5]] which has an additional edge [1,3]. I want to have [5, 3] as the result. Any help is much appreciated.

0

There are 0 best solutions below