Kosaraju的算法可以找到SCC，但要跟踪SCC之间的边缘？ [英] Kosaraju's Algorithm for finding SCCs but keep track of edge between SCCs?
问题描述
我目前有一个Kosaraji算法的有效实现，在没有权重的有向图的情况下，它将在图中打印SCC。
我想适应
这是代码：
从集合中导入defaultdict
＃----定义----＃
#Graph
Graph = {}
＃图的转置
Transpose_Graph = {}
＃图的已访问节点
Visited_Nodes_Graph = {}
＃已访问转置图的节点
Visited_Nodes_Transpose_Graph = {}
＃要处理的堆栈
堆栈= []
＃----定义----＃
＃根据顶点数，创建一个字典，其中每个顶点都是键，值是从它到另一个顶点的边。
def Generate_Empty_Graphs（Number_of_Verticies）：
用于范围（1，Number_of_Verticies + 1）中的顶点：$ b $ b Graph [Vertex] = []
Transpose_Graph [Vertex] = []
Visited_Nodes_Graph [Vertex] =假
Visited_Nodes_Transpose_Graph [Vertex] = False
＃具有边的人口图
def Populate_Graphs（Head，Tail）：
Graph [Head ] .append（Tail）
Transpose_Graph [Tail] .append（Head）
＃在给定的Graph上的指定位置运行DFS。
＃这用于DFS＃2（
def Run_DFS（Vertex，Given_Graph，SCC_List）：
Visited_Nodes_Transpose_Graph [Vertex] =真
SCC_List.append（Vertex）
对于Transpose_Graph [Vertex]中的Adjacent_Vertex：
if（Visited_Nodes_Transpose_Graph [Adjacent_Vertex] == False）：
Run_DFS（Adjacent_Vertex，Transpose_Graph [Adjacent_Vertex]，SCC_List）
#TODO在这里进行记录...
return SCC_List
＃处理堆栈并运行DFS
＃这用于DFS＃1
def Populate_Stack（Vertex，Given_Graph） ：
Visited_Nodes_Graph [Vertex] = True
在Given_Graph [Vertex]中为Adjacent_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）：
用于范围（1，Number_Of_Verticies + 1）中的顶点：$ b $ b 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。我该如何修改此代码以将其生成为图形？
可以做到这一点，您可以分配每个节点组件ID。
例如，
[1，3，2] =>组件ID 1
[7，9，8] =>组件ID 2
[4、5、6] =>组件ID 3
然后使用此组件ID创建另一个图形（SCC_GRAPH）。要生成此图，您可以遍历原始图一次，并且对于每个边（u，v），如果其组件ID不同，则可以在
SCC_GRAPH中使用component_id（u）-> component_id（v）创建一个边。 / p>
在此示例中，
1-> 2
1-> 3
然后对于给定的节点，获取该节点的组件ID。然后从给定节点的组件ID开始在SCC_GRAPH中找到可到达的节点数。
I currently have a working implementation of Kosaraji's algorithm that, given a directed graph with no weights, will print the SCCs in a graph.
I would like to adapt it so it will also state where the edges between the SCCs are.
Here is the code:
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)
For the given graph:
{1,2,3} -> {8,7,9} {1,2,3} -> {4,5,6}
Meaning, there is an edge between {1,2,3} and {8,7,9}. There is also an edge between: {1,2,3} -> {4,5,6}
However, there is NO edge between {8,7,9} and {4,5,6}
The goal is to keep track of these, to determine the largest amount of SCCs possible to touch starting from any given vertex. How could I modify this code to produce this as a graph?
One thing can be done that, you can assign each node a component id. For your example, lets say,
[1, 3, 2] => component id 1
[7, 9, 8] => component id 2
[4, 5, 6] => component id 3
Then create another graph (SCC_GRAPH) using this component id. To generate this graph, you can traverse the original graph once and for each edge (u,v) if their component id is different then create an edge in SCC_GRAPH with component_id(u) -> component_id(v).
For this example,
1 -> 2
1 -> 3
Then for a given node, get the component id of this node. Then find number of node reachable in SCC_GRAPH starting from the component id of the given node.
这篇关于Kosaraju的算法可以找到SCC，但要跟踪SCC之间的边缘？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
