CODEWITHSUNDEEP
pythongraphigraphdata-manipulation
DEner
DEner

Reputation: 95

How can I change the direction of edges in python igraph?

I have a directed tree graph with a single root vertice, where the directions seem arbitrary. I want all edges to be directed from the single root, towards the ends of the respective branches.

My first primitive attempt was to swap the source and target vertices like below (but as assumed, it would not work.

temp = g.es[e_idx].source
g.es[e_idx].source = g.es[e_idx].target
g.es[e_idx].target = temp

Is there a function or a set of functions that allow to swap the direction of a specific edge available?

Or a way to manipulate the source / target attributes of edges, without needing to change any vertice attributes?

Please let me know if I need to specify anything further.

Your help would be greatly appreciated.

Upvotes: 3

Views: 982

Answers (1)

Szabolcs
Szabolcs

Reputation: 25703

Here is a possible solution that preserves all graph attributes:

  • We are going to reorder vertices so that those closer to the root come first
  • Then we use to_directed with the "acyclic" mode, which directs edges from lower to higher index vertices
  • Finally we restore the original vertex order
import igraph as ig
from igraph import Graph

# Set seed for reproducibility
import random
random.seed(123)

# Create an undirected tree. If your tree is not undirected, 
# convert it to undirected first.
g = Graph.Tree_Game(10)

# Our chosen root:
root = 3

ig.plot(g, vertex_label=range(g.vcount()), layout = g.layout_reingold_tilford(root=root), bbox=(300,300))

# Distances from the root, will be used for ordering:
dist=g.shortest_paths(source=root)[0]

# This function computes the permutation that would
# sort 'elems'. It also serves as a way to invert
# permutations.

def ordering(elems):
    return sorted(range(len(elems)), key=elems.__getitem__)

# Compute orderings based on the distance from the root:
perm = ordering(dist)
invperm = ordering(perm)

# Reorder, direct, restore order:
dg = g.permute_vertices(invperm)
dg.to_directed('acyclic')
dg = dg.permute_vertices(perm)

# Plot again.
# Now the root does not need to be given,
# as it is auto-detected from the directions.
ig.plot(dg, vertex_label=range(g.vcount()), layout='reingold_tilford', bbox=(300,300))

enter image description here

Upvotes: 2

Related Questions