hello fellow stackoverflowians,
i'm trying to implement kosaraju's algo, which requires inversion of the og directed (and in my case weighted) graph. i've successfully handled this a while back using edge lists and primitive types (idk if that's python's terminology, sorry if that's technically incorrect). however, i'm having trouble with implementing this when using adjacency lists
trying to create a dict with structure { node.val : GraphNode } and append to the GraphNode's neighbors within the dict as necessary. then, set Graph's node list = dict.values()
could be how i define my structs, could be overlooking something obvious in the code, could be my python ineptitudes showing, idk. i'm pretty close to a temper tantrum though
i think i covered all my bases and provided code below, but lmk if more detail is needed. thanks in advance, much appreciated
class GraphNode:
def __init__(self,val,neighbors=[]) -> None:
self.val = val
self.neighbors = neighbors
class Graph:
def __init__(self, nodes=[]) -> None:
self.nodes = nodes
def invert_graph(self):
visited_edge_set = set()
node_map = {}
def dfs(node: GraphNode):
if node.val not in node_map:
node_map[node.val] = GraphNode(node.val)
new_end_node = node_map[node.val]
for (neigh,weight) in node.neighbors:
if (neigh.val,node.val) in visited_edge_set or (node.val,neigh.val) in visited_edge_set:
continue
visited_edge_set.add((neigh.val,node.val))
if neigh.val not in node_map:
node_map[neigh.val] = GraphNode(neigh.val)
new_start_node = node_map[neigh.val]
new_start_node.neighbors.append((new_end_node, weight))
dfs(neigh)
for node in self.nodes:
node.val not in node_map and dfs(node)
self.nodes = node_map.values()
if __name__ == "__main__":
zero = GraphNode(0)
one = GraphNode(1)
two = GraphNode(2)
three = GraphNode(3)
four = GraphNode(4)
five = GraphNode(5)
six = GraphNode(6)
zero.neighbors = [(two, 2), (four, 3)]
one.neighbors = [(three, 1)]
two.neighbors = [(six, 6)]
three.neighbors = [(four, 4)]
four.neighbors = [(one, 1), (six, 4)]
six.neighbors = [(five, 2)]
arr = [zero,one,two,three,four,five,six]
g = Graph(arr)
g.invert_graph()
Two issues:
The reason you get the wrong is result is that your constructor's default value for neighbors is mutated. This is a typical "feature" in Python, where default values for parameters are only evaluated once, not at the time of the actual call. So change that constructor to this:
class GraphNode:
def __init__(self,val,neighbors=None) -> None:
self.val = val
self.neighbors = neighbors or []
This algorithm is overly complex. There is no need to do a depth-first traversal of the graph. The edges can be visited in any order, so no recursion is needed, nor a concept of "visited". You could even do without creating new nodes, and just add a separator to the neighbors list and then just add the new edges after that separator to finally delete all the edges from that list up to the separator.
def invert_graph(self):
for node in self.nodes:
node.neighbors.append((None, 0)) # separator
for node in self.nodes:
for i, (neighbor, weight) in enumerate(node.neighbors):
if neighbor is None: # Separator
del node.neighbors[:i + 1] # Remove original edges
break
neighbor.neighbors.append((node, weight))