CODEWITHSUNDEEP
pythongraph
Janmajay
Janmajay

Reputation: 53

Reversing edges in a digraph

I have a dictionary of edges as follows;

edges={vertex1:[(neighbor1,weight1),(n2,w2),...],v2:[(neighbork,weightk).....vk:[(),()]}

Does anyone know a way of reversing the edges in O(E)? I can only think of a nested for approach which is definitely not right.

For example:

{0:[(1,5),(2,3)],1:[(2,2)]}

which is a graph where edges are 0->1 (weight 5), 0->2 (weight 3) , 1->2 (weight 2)

after reversing becomes;

{1:[(0,5)],2:[(0,3),(1,2)]}

which is a graph where edges are 1->0 (weight 5), 2->0 (weight 3) , 2->1 (weight 2)

Upvotes: 0

Views: 452

Answers (1)

John Zwinck
John Zwinck

Reputation: 249123

from collections import defaultdict

g = {0:[(1,5),(2,3)],1:[(2,2)]}
r = defaultdict(list)

for origin, targets in g.iteritems():
    for target, weight in targets:
        r[target].append((origin, weight))

Now r is basically your answer. You can do dict(r) at the end to get a regular dict instead of the defaultdict if you need.

Upvotes: 3

Related Questions