Reputation: 11
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.
Upvotes: 1
Views: 1079