Using graph-tool's BFS iterator function on graph were edges point towards the root

Question

I want to use graph-tool's bfs_iterator() on a graph where the edges point toward the root, like below:

# Create graph
g = Graph()
g.add_vertex(7)
elist=[(1,0),(2,0),(3,1),(4,1),(5,2),(6,2)]
g.add_edge_list(elist)
ind=g.new_vp('int',[0,1,2,3,4,5,6])
g.vp["label"] =g.new_vp("string",["a","b","c","d","e","f","g"])
lab1=g.vp["label"]
w=np.random.rand(len(elist))
g.ep["weight"] =g.new_ep("double",w)
epw=g.ep['weight']

# plot graph
graph_draw(g,vertex_text=lab1)

The only way I could achieve this is by creating a copy of it where all edges are reversed, but I don't think this solution is scalable.

Is there a better (more efficient) way to achieve this using graph-tool?

This is the code I came up with:

# Define a function that flips edges
def flip(G,vlabel,eps,eptypes):
  g=Graph()
  g.vp['label']=g.new_vp('string')
  lab=g.vp['label']
  N=G.num_vertices()
  g.add_vertex(N)
  Glabs=G.vp[vlabel]
  for k in range(g.num_vertices()):
    nG=G.vertex(k)
    ng=g.vertex(k)
    lab[ng]=Glabs[nG]
  for k in range(len(eps)):
    g.ep[eps[k]]=g.new_ep(eptypes[k])
  for e in G.edges(): 
    e1=[int(i) for i in e]
    e2=g.add_edge(e1[1],e1[0])
    for k in eps:
      propG=G.ep[k]
      propg=g.ep[k]
      propg[e2]=propG[e]
  return(g,lab)

# use function
[g2,lab]=flip(g,'label',['weight'],['double'])

# Plot the resulting graph
graph_draw(g2,vertex_text=lab)

# get BFS iterator
utree=bfs_iterator(g2,source=0,array=True)
print("utree:",utree)

utree: [[0 1]
 [0 2]
 [1 3]
 [1 4]
 [2 5]
 [2 6]]

Answer 1

There's a very simple and extremely efficient answer to your problem. Just call:

g.set_reversed(True)

This will reverse all the edges in the graph, and it's a fast O(1) operation.

Alternatively, you can create a graph view as follows:

u = GraphView(g, reversed=True)

The graph u will point to g but with all edges reversed. This is also a O(1) operation, and it will not copy the graph.