Kosaraju's Algorithm for finding SCCs but keep

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.