def find_bridges(self,n,low_link,visited=list(),back=list(),bridges=list()):
def get_low_link(x):
return low_link[visited.index(x)]
if n[0] not in visited:
visited.append(n[0])
if len(visited) == len(back):
return bridges
else:
for i in self.node_out_neighbours(n[0]):
if i not in visited:
print(f"NOW IN {i}")
visited.append(i)
self.find_bridges(n=[i,n,get_low_link(i),visited.index(i)],visited=visited,low_link=low_link,back=back,bridges=bridges)
break
else:
if get_low_link(i) < n[2] and i != n[1][0]:
print(f'{n[0]} low link is now {get_low_link(i)}')
low_link[visited.index(n[0])] = get_low_link(i)
n[2] = get_low_link(i)
else:
if n[0] != self.get_n()[0]: # self.get_n()[0] is the node with id 0
if n[1][2] >= n[2]:
low_link[visited.index(n[1][0])] = n[2]
print(f'{n[1][0]} low link is now {n[2]}')
n[1][2] = n[2]
if n[1][3] < n[2]:
bridges.append((n[0],n[1][0]))
back.append(n[0])
print(f"BACK TRACK FROM {n[0]}")
self.find_bridges(n=n[1],visited=visited,low_link=low_link,back=back,bridges=bridges)
well, i have been stuck with this program for nearly 2 days and i have fixed and solved a lot of problems in it. currently, the dfs part of the program is working just fine, and the low_links are accurately updated(i used some print statements in different positions in order to know that). the only problem now is the identification of the bridge. every time i run the program, it returns None, not even an empty list. and even though as i said earlier the low links are accurately updated, i dont know why the bridges arent identified
NOTE that n in this program is a list in this format [current node,predecessor in this same list format,low link,id]. remember that n[1] is also a list in this format.
thanks in advance
ProgrammingLover is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
7