0

我目前有一个 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 数量。我如何修改此代码以将其生成为图形？

4

1 回答 1

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 中找到可到达的节点数。

于 2017-11-06T12:47:31.897 回答