python graph inversion/reversal

Question

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

the dfs portion, although overly complicated as noted in the accepted answer, does indeed work. however, my issue was how i defined the default values in class initialization. the actual problem: when i appended to one node's neighbors list, that value was being appended to all nodes' neighbors — verybadats3x, Jul 24 '22 at 15:30

trincot · Accepted Answer · 2022-07-23T14:53:13.170

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

clear explanation on both fronts @trincot. the default value mutation is what was really throwing me off, but i also completely agree my solution was over-engineered. thanks for the insight — verybadats3x, Jul 24 '22 at 15:17

score 0 · Answer 2 · answered Jul 23 '22 at 13:49

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.

python graph inversion/reversal

2 Answers2