Kosaraju 用于查找 SCC 但跟踪 SCC 之间的边缘的算法？

Question

我目前有一个 Kosaraji 算法的工作实现，给定一个没有权重的有向图，将在图中打印 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

有一件事可以做到，您可以为每个节点分配一个组件 ID。对于您的示例，假设

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

然后使用此组件 ID 创建另一个图表 (SCC_GRAPH)。要生成此图，您可以遍历原始图一次并为每条边 (u,v) 如果它们的组件 ID 不同，则在中创建一条边 SCC_GRAPH 与 component_id(u) -> component_id(v).

对于这个例子，

1 -> 2
1 -> 3

然后对于给定的节点，获取该节点的组件id。然后从给定节点的组件 ID 开始，在 SCC_GRAPH 中找到可到达的节点数。

Kosaraju 用于查找 SCC 但跟踪 SCC 之间的边缘的算法？

Kosaraju's Algorithm for finding SCCs but keep track of edge between SCCs?

python

algorithm

python-2.7

graph-algorithm

kosaraju-algorithm