Алгоритм Косараю для поиска SCC, но отслеживать границу между SCC?

Question

В настоящее время у меня есть рабочая реализация алгоритма Косараджи, которая, учитывая ориентированный граф без весов, будет печатать SCC в графе.

Я хотел бы адаптировать его так, чтобы он также указывал, где находятся границы между SCC.

Вот код:

from collections import defaultdict

#---- Definitions ----#

#Graph
Graph = {}

#Transpose of Graph
Transpose_Graph = {}

#Visited Nodes for Graph
Visited_Nodes_Graph = {}

#Visited Nodes for Transpose Graph
Visited_Nodes_Transpose_Graph = {}


#Stack to process
Stack = []

#---- Definitions ----#

#Based on the number of verticies, create a dictionary where every vertex is the key, and the value are the edges from it to another vertex.
def Generate_Empty_Graphs(Number_of_Verticies):
    for Vertex in range(1, Number_of_Verticies+1):
        Graph[Vertex] = []
        Transpose_Graph[Vertex] = []
        Visited_Nodes_Graph[Vertex] = False
        Visited_Nodes_Transpose_Graph[Vertex] = False

#Populate Graph with edges
def Populate_Graphs(Head, Tail):
    Graph[Head].append(Tail)
    Transpose_Graph[Tail].append(Head)

#Run DFS on given Graph, at provided position.
#This is used for DFS #2 (
def Run_DFS(Vertex, Given_Graph, SCC_List):
    Visited_Nodes_Transpose_Graph[Vertex] = True
    SCC_List.append(Vertex)
    for Adjacent_Vertex in Transpose_Graph[Vertex]:
        if(Visited_Nodes_Transpose_Graph[Adjacent_Vertex] == False):
            Run_DFS(Adjacent_Vertex, Transpose_Graph[Adjacent_Vertex], SCC_List)
        #TODO something here to log it...
    return SCC_List


#Process Stack and run DFS
#This is used for DFS #1
def Populate_Stack(Vertex, Given_Graph):
    Visited_Nodes_Graph[Vertex] = True
    for Adjacent_Vertex in Given_Graph[Vertex]:
        if (Visited_Nodes_Graph[Adjacent_Vertex] == False):
            Populate_Stack(Adjacent_Vertex, Given_Graph)
    Stack.append(Vertex)


def Detect_SCCs(Given_Graph, Number_Of_Verticies):
    for Vertex in range(1, Number_Of_Verticies+1):
        if(Visited_Nodes_Graph[Vertex] == False):
            Populate_Stack(Vertex, Given_Graph)

    SCC = []
    while(len(Stack) != 0):
        Current_Vertex = Stack.pop()
        if(Visited_Nodes_Transpose_Graph[Current_Vertex] == False):
            SCC = Run_DFS(Current_Vertex, Transpose_Graph, [])
            print(SCC)


Number_Of_Verticies = 9
Generate_Empty_Graphs(Number_Of_Verticies)

Populate_Graphs(1, 2)
Populate_Graphs(2, 3)
Populate_Graphs(3, 1)
Populate_Graphs(3, 4)
Populate_Graphs(3, 7)
Populate_Graphs(4, 6)
Populate_Graphs(6, 5)
Populate_Graphs(5, 4)
Populate_Graphs(7, 8)
Populate_Graphs(8, 9)
Populate_Graphs(9, 7)

Detect_SCCs(Graph, Number_Of_Verticies)

Для данного графика:

{1,2,3} -> {8,7,9} {1,2,3} -> {4,5,6}

Это означает, что между {1,2,3} и {8,7,9} есть грань. Также есть грань между: {1,2,3} -> {4,5,6}

Однако между {8,7,9} и {4,5,6} НЕТ грани

Цель состоит в том, чтобы отслеживать их, чтобы определить наибольшее количество SCC, которых можно коснуться, начиная с любой данной вершины. Как я мог изменить этот код, чтобы получить его в виде графика?

Answer 1

Можно сделать одну вещь: вы можете назначить каждому узлу идентификатор компонента. Для вашего примера, скажем,

[1, 3, 2] => component id 1
[7, 9, 8] => component id 2
[4, 5, 6] => component id 3

Затем создайте еще один график (SCC_GRAPH), используя этот идентификатор компонента. Чтобы сгенерировать этот график, вы можете пройти исходный график один раз и для каждого ребра (u,v), если их идентификатор компонента отличается, тогда создайте ребро в SCC_GRAPH с помощью component_id(u) -> component_id(v).

Для этого примера

1 -> 2
1 -> 3

Затем для данного узла получите идентификатор компонента этого узла. Затем найдите номер достижимого узла в SCC_GRAPH, начиная с идентификатора компонента данного узла.