Kosarajas Algorithmus für das Finden von SCCs, aber behalten Sie den Überblick zwischen den SCCs?

Question

Ich habe derzeit eine funktionierende Implementierung von Kosarajis Algorithmus, der bei einem gerichteten Graphen ohne Gewichte die SCCs in einem Graphen ausgibt.

Ich möchte es so anpassen, dass es auch angibt, wo die Kanten zwischen den SCCs sind.

Hier ist der 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) 

Für das gegebene Diagramm:

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

Das bedeutet, es gibt eine Kante zwischen {1,2,3} und {8,7,9}. Es gibt auch eine Kante zwischen: {1,2,3} -> {4,5,6}

Es gibt jedoch keine Kante zwischen {8,7,9} und {4,5,6}

Ziel ist es, diese zu verfolgen, um die größtmögliche Anzahl an SCCs zu bestimmen, die von einem gegebenen Scheitelpunkt aus berührt werden können. Wie kann ich diesen Code ändern, um ihn als Diagramm zu erstellen?

Answer 1

Eine Sache kann getan werden, dass Sie jedem Knoten eine Komponenten-ID zuweisen können. Für Ihr Beispiel können sagen,

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

Dann ein weiteres Diagramm (SCC_GRAPH) unter Verwendung dieser Komponenten-ID erstellen. Um dieses Diagramm zu erzeugen, können Sie das ursprüngliche Diagramm einmal und für jede Kante (u, v) durchlaufen, wenn ihre Komponenten-ID unterschiedlich ist, und dann eine Kante in SCC_GRAPH mit component_id (u) -> component_id (v) erstellen.

Für dieses Beispiel

1 -> 2 
1 -> 3 

Dann für einen bestimmten Knoten, die Komponenten-ID dieses Knotens erhalten. Dann finden Sie die Nummer des Knotens, der in SCC_GRAPH erreichbar ist, beginnend mit der Komponenten-ID des gegebenen Knotens.