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()

CodePudding user response：

Generally, one doesn't need a DFS to invert a graph. Rather, in pseudocode, to convert G into H:

for every vertex v in G:
    for every edge (to, len) from v in G:
        add edge (v, len) from to in H

Initially, H would have all the same vertices as G, but no edges.

Perhaps it would make sense to construct a new graph H, rather than change the existing graph G.

CodePudding user response：

I think your approch is fine, but syntax wise there're some errors.

Basically to perform depth-first search on the reversed graph. (inverted)

Start from the top vertex of the stack. Traverse through all of its child vertices. Once the already visited vertex is reached, one strongly connected component is formed.

Like this way pop vertex-0 from the stack. Starting from vertex-0, traverse through its child vertices (vertex-0, vertex-1, vertex-2, vertex-3 in sequence) and mark them as visited. The child of vertex-3 is already visited, so these visited vertices form one strongly connected component.

CodePudding user response：

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))