CODEWITHSUNDEEP
pythonalgorithm
SkyWalker
SkyWalker

Reputation: 14307

How to best reverse a DAG with adjacency list representation?

I have the following DAG adjacency list representation:

# this reads: b depends on a, c depends on a and d depends on b and c
graph = {'b': {'a'}, 'c': {'a'}, 'd': {'b', 'c'}}

I want to get the following inverted representation:

graph = {'a': {'b', 'c'}, 'b': {'d'}, 'c': {'d'}}

Using Python 3.x I can do the following, basically turn the graph into a list of tuples and the convert the list of tuples to a dictionary (collapsing different values into a set):

inverted_graph = {}
for k, v in [(v, k) for k in graph for v in graph[k]]:
    inverted_graph.setdefault(k, set()).add(v)

Is there a simpler / faster way to do it without double looping?

Upvotes: 0

Views: 195

Answers (1)

mkrieger1
mkrieger1

Reputation: 23209

I'm not sure why you wrote this triple loop. Two loops should be sufficient. You don't need an extra loop to swap k and v when you can just use them in opposite places.

Also, a defaultdict can simplify the code.

from collections import defaultdict

inverted_graph = defaultdict(set)
for k in graph:
    for v in graph[k]:
        inverted_graph[v].add(k)

Upvotes: 4

Related Questions