Hoping someone has some insight here.
First half of the Kosaraju algorithm implementation with a graph and node class.
I'm Iterating through a list of nodes each with a list of heads and a list of tails to allow moving forwards or backwards.
As you move through a Graph a newly explored vertex is explored
and then you access the head_list
:
for j in i.head_list:
DFS(my_graph, j, T, S)
What is interesting is that i.head_list
is sometimes an empty list although in the Graph Test Data every nodes has at least one head and one tail.
Example (from Test Data below): first call should be '9' with a head_list
of [6] but [] is returned and the tail_list
is [3, 7]. In debugging drilling into into variable 3 as part of th tail_list
, head_list
is populated with [9] but tail_list
is []. Sort of flip flopping between populating head and tail lists.
I thought there was some global variable mix up but I haven't found it. I thought maybe copy.deepcopy might have fixed it but it's not that. It just seems vey unusual behavior. What is even more interesting is that it only seems to produce an empty list when a node has already been included in a head_list
. For example: Node 4 is the first fails and
I expected to be able to drill continuously through nodes and head_list
's or tail_list
's indefinitely but the presence of the lists in iteration changes bank and forth. Any insight would be greatly appreciated.
Test Data
Node | Tail |
---|---|
1 | 4 |
2 | 8 |
3 | 6 |
4 | 7 |
5 | 2 |
6 | 9 |
7 | 1 |
8 | 5 |
8 | 6 |
9 | 3 |
9 | 7 |
class Graph():
def __init__(self, graph):
self.graph = graph
self.node_list = []
def add_node(self, node):
self.node_list.append(node)
def __repr__(self):
return (f'_{self.graph} + {[node for node in self.node_list]} + {[node.head_list for node in self.node_list]}')
class Node():
def __init__(self, head):
self.head = head
self.explored = False
self.head_list = []
self.tail_list = []
self.leader = None
self.finish_time = 0
def __repr__(self):
return f'{self.head}'
def add_node_edge(self, Node, lst):
if lst == 'head':
self.head_list.extend([Node])
else:
self.tail_list.extend([Node])
def DFS_loop(my_graph):
global T
global S
T = 0 # number of nodes processed so far
S = None # current source vertex
for node in my_graph.node_list[::-1]:
if node.explored == False:
S = node
DFS(my_graph, node, T, S)
def DFS(my_graph, i, T, S):
i.explored = True
i.leader = S.head
for j in i.head_list:
DFS(my_graph, j, T, S)
T += 1
i.finish_time = T
file1 = open('C:/Downloads/test_Data.txt', 'r')
Lines = file1.readlines()
my_graph = Graph('A')
default_node = Node(0)
my_graph.node_list = [default_node]*9
unexplored_queue = []
for line in Lines:
h, t = line.strip().split()
h = int(h)
t = int(t)
new_node = Node(h)
new_head_node = Node(h)
new_tail_node = Node(t)
new_node.add_node_edge(new_tail_node, 'tail')
new_tail_node.add_node_edge(new_node, 'head')
if my_graph.node_list[h-1].head == 0:
my_graph.node_list[h-1] = new_node
else:
my_graph.node_list[h-1].add_node_edge(new_tail_node, 'tail')
if my_graph.node_list[t-1].head == 0:
my_graph.node_list[t-1] = new_tail_node
else:
my_graph.node_list[t-1].add_node_edge(new_node, 'head')
DFS_loop(my_graph)
for node in my_graph.node_list:
print(node, node.finish_time)```
In this code:
you are assuming that the tail node does not already exist in the graph. That's not a safe assumption. If the tail node already exists, you need to adjust its links, not assign a new one.