fork(1) download 
  1. from collections import defaultdict
  2.  
  3. #---- Definitions ----#
  4.  
  5. #Graph
  6. Graph = {}
  7.  
  8. #Transpose of Graph
  9. Transpose_Graph = {}
  10.  
  11. #Visited Nodes for Graph
  12. Visited_Nodes_Graph = {}
  13.  
  14. #Visited Nodes for Transpose Graph
  15. Visited_Nodes_Transpose_Graph = {}
  16.  
  17. #Component Id
  18. Component_Id = dict()
  19.  
  20. #Stack to process
  21. Stack = []
  22.  
  23. #---- Definitions ----#
  24.  
  25. #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.
  26. def Generate_Empty_Graphs(Number_of_Verticies):
  27.     for Vertex in range(1, Number_of_Verticies+1):
  28.         Graph[Vertex] = []
  29.         Transpose_Graph[Vertex] = []
  30.         Visited_Nodes_Graph[Vertex] = False
  31.         Visited_Nodes_Transpose_Graph[Vertex] = False
  32.  
  33. #Populate Graph with edges
  34. def Populate_Graphs(Head, Tail):
  35.     Graph[Head].append(Tail)
  36.     Transpose_Graph[Tail].append(Head)
  37.  
  38. #Run DFS on given Graph, at provided position.
  39. #This is used for DFS #2 (
  40. def Run_DFS(Vertex, Given_Graph, SCC_List):
  41.     Visited_Nodes_Transpose_Graph[Vertex] = True
  42.     SCC_List.append(Vertex)
  43.     for Adjacent_Vertex in Transpose_Graph[Vertex]:
  44.         if(Visited_Nodes_Transpose_Graph[Adjacent_Vertex] == False):
  45.             Run_DFS(Adjacent_Vertex, Transpose_Graph[Adjacent_Vertex], SCC_List)
  46.         #TODO something here to log it...
  47.     return SCC_List
  48.  
  49.  
  50. #Process Stack and run DFS
  51. #This is used for DFS #1
  52. def Populate_Stack(Vertex, Given_Graph):
  53.     Visited_Nodes_Graph[Vertex] = True
  54.     for Adjacent_Vertex in Given_Graph[Vertex]:
  55.         if (Visited_Nodes_Graph[Adjacent_Vertex] == False):
  56.             Populate_Stack(Adjacent_Vertex, Given_Graph)
  57.     Stack.append(Vertex)
  58.  
  59.  
  60. def Detect_SCCs(Given_Graph, Number_Of_Verticies):
  61.     for Vertex in range(1, Number_Of_Verticies+1):
  62.         if(Visited_Nodes_Graph[Vertex] == False):
  63.             Populate_Stack(Vertex, Given_Graph)
  64.  
  65.     SCC = []
  66.  
  67.     Current_Component_Id = 0
  68.  
  69.     while(len(Stack) != 0):
  70.         Current_Vertex = Stack.pop()
  71.         if(Visited_Nodes_Transpose_Graph[Current_Vertex] == False):
  72.             SCC = Run_DFS(Current_Vertex, Transpose_Graph, [])
  73.             Current_Component_Id += 1
  74.             for SCC_Vertex in SCC:
  75.                 Component_Id[SCC_Vertex] = Current_Component_Id
  76.  
  77.             print(SCC)
  78.  
  79.  
  80. Number_Of_Verticies = 9
  81. Generate_Empty_Graphs(Number_Of_Verticies)
  82.  
  83. Populate_Graphs(1, 2)
  84. Populate_Graphs(2, 3)
  85. Populate_Graphs(3, 1)
  86. Populate_Graphs(3, 4)
  87. Populate_Graphs(3, 7)
  88. Populate_Graphs(4, 6)
  89. Populate_Graphs(6, 5)
  90. Populate_Graphs(5, 4)
  91. Populate_Graphs(7, 8)
  92. Populate_Graphs(8, 9)
  93. Populate_Graphs(9, 7)
  94.  
  95. Detect_SCCs(Graph, Number_Of_Verticies)
  96.  
  97. #Components generated here. Now build new graph using component ids
  98. #Component Graph
  99. Component_Graph = {}
  100.  
  101. #Reset visited for next DFS
  102. def Reset_Visited(Number_of_Verticies):
  103.     for Vertex in range(1, Number_of_Verticies+1):
  104.         Visited_Nodes_Graph[Vertex] = False
  105.  
  106. def Generate_Component_Graph_DFS(u, Given_Graph):
  107.     if (Visited_Nodes_Graph[u]==True):
  108.         return
  109.     Visited_Nodes_Graph[u] = True
  110.  
  111.     for v in Given_Graph[u]:
  112.         if (Component_Id[u] != Component_Id[v]):
  113.             Component_U = Component_Id[u]
  114.             Component_V = Component_Id[v]
  115.             if Component_U not in Component_Graph:
  116.                 Component_Graph[Component_U] = []
  117.             Component_Graph[Component_U].append(Component_V)
  118.         Generate_Component_Graph_DFS(v, Given_Graph)
  119.  
  120. def Generate_Component_Graph(Given_Graph):
  121.     for u in Given_Graph:
  122.         Generate_Component_Graph_DFS(u, Given_Graph)
  123.  
  124. Reset_Visited(Number_Of_Verticies)
  125. Generate_Component_Graph(Graph)
  126.  
  127. #Now for a given vertex, get component id of that vertex
  128. #And travarse for number of reachable nodes in Component_Graph for this component id
  129.  
  130. def Reachable_SCC_DFS(Given_Component_Id, Generated_Component_Graph):
  131.     Reachable_SCC_Count = 1
  132.     if (Given_Component_Id not in Generated_Component_Graph):
  133.         return Reachable_SCC_Count
  134.  
  135.     for Component_Vertex in Generated_Component_Graph[Given_Component_Id]:
  136.         Reachable_SCC_Count += Reachable_SCC_DFS(Component_Vertex, Generated_Component_Graph)
  137.  
  138.     return Reachable_SCC_Count
  139.  
  140. def Reachable_SCC(Given_Vertex, Generated_Component_Graph):
  141.     return Reachable_SCC_DFS(Component_Id[Given_Vertex], Generated_Component_Graph)
  142.  
  143. for Vertex in range(1, Number_Of_Verticies+1):
  144.     print ('Vertex ' + str(Vertex) + ' => ' + str(Reachable_SCC(Vertex, Component_Graph)) + ' reachable SCC')
  145.  
  146.  
  147. #Note: for Reachable_SCC_DFS visited falg will not be necessary because there will not be any loop in this graph. If there would be any loop then it would had been a merged SCC.
Success #stdin #stdout 0.02s 28384KB
comments (?)
stdin 
Standard input is empty
stdout 
[1, 3, 2]
[7, 9, 8]
[4, 5, 6]
Vertex 1 => 3 reachable SCC
Vertex 2 => 3 reachable SCC
Vertex 3 => 3 reachable SCC
Vertex 4 => 1 reachable SCC
Vertex 5 => 1 reachable SCC
Vertex 6 => 1 reachable SCC
Vertex 7 => 1 reachable SCC
Vertex 8 => 1 reachable SCC
Vertex 9 => 1 reachable SCC
https://ideone.com/veSoSC
language:
Python 3 (python  3.12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!