Размер (число ребер) сильно связанных компонентов (SCC) в графе с использованием алгоритма Косараю - PullRequest
Новая
       35

Размер (число ребер) сильно связанных компонентов (SCC) в графе с использованием алгоритма Косараю

0 голосов
/ 17 января 2019

Я кодировал двухпроходный алгоритм Косараджу в Python 3, текущая реализация находит SCC и определяет размер каждого SCC на основе количества узлов в каждом SCC. Затем определяются самые большие SCC. Как я могу изменить код, чтобы он мог рассчитать размер каждого SCC на основе количества ребер в каждом 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()

например, для графика как (представлен ниже как список списков, только для простоты): [[1,2], [2,3], [2,5], [3,4], [4,1], [5,6], [6,7], [7,5]] первый элемент - это tail, а второй - head.

Результат приведенного выше кода, включая размер SCC в порядке убывания, равен [4,3]

Однако текущая реализация приводит к тем же числам для графа, что и: [[1,2], [1,3], [2,3], [2,5], [3,4], [4,1], [5,6], [6,7], [ 7,5]] который имеет дополнительное ребро [1,3]. Я хочу получить [5, 3] в результате. Любая помощь очень ценится.

...