如何高效在边指向根的图上使用graph-tool的bfs_iterator？

问题背景 #

我需要在一个边指向根节点的图（如下方代码创建的结构）上使用graph-tool的bfs_iterator()函数。目前我只能通过创建一个反转所有边的图副本来实现需求，但这种方案扩展性不佳，想找更高效的方法。

原始图创建代码 #

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

原始图效果：反向树（所有边指向根节点a）

当前实现方式（创建反转图副本） #

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

反转后的图效果：正向树（边从根节点a向外指向子节点）
运行结果：

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

更高效的解决方案：使用反向图视图 #

graph-tool提供了Graph.reverse()方法，它会返回一个反向的图视图，而非创建新的图副本。这个视图会共享原有的顶点和边属性，无需额外复制数据，内存占用和执行效率都远高于手动创建反转图。

优化后的代码 #

# 获取反向图视图，无需复制整个图
g_reversed = g.reverse()

# 直接在反向视图上执行BFS
utree = bfs_iterator(g_reversed, source=0, array=True)
print("utree:", utree)

效果验证 #

运行上述代码会得到和之前完全一致的输出：

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

如果需要绘制反向视图的图，直接使用原有的顶点属性即可：

graph_draw(g_reversed, vertex_text=g.vp["label"])

内容的提问来源于stack exchange，提问作者Adriana LE