graph-tool, I want to remove cycles in a graph by unfolding them. That is, if there is a cycle, pick a node as root and make a copy of it such that the last edge in the path from root to root now has the copy as target. Something like the example below, where the node copy is highlighted with a green contour.
# define graph with cycle g = Graph() v1 = g.add_vertex() v2 = g.add_vertex() v3 = g.add_vertex() e1 = g.add_edge(v1, v2) e2 = g.add_edge(v2, v3) e3 = g.add_edge(v3, v1) g.vp["foo"] =g.new_vp("int",[1,2,3]) g.ep["bar"] =g.new_ep("string",["a","e","i"])
|A cycle with root=1||A cycle, unfolded|
To solve this, I wrote the function below.
def cyunfold(g,cycle,vps=None,eps=None): # get edge to "unfold" last=ifelse(len(cycle)==1,cycle,cycle[-1]) first=cycle # create new vertex newv=g.add_vertex() # copy vertex properties for v in vps: prop=g.vp[v] prop[newv]=prop[first] olde=g.edge(last,first) # create new edges newe=g.add_edge(g.vertex(last),g.vertex(newv)) # copy edge properties for e in eps: prope=g.ep[e] prope[newe]=prope[olde] # remove old edge g.remove_edge(olde) # add copy indicator as vertex property if g.vp.get("iscopy")==None: g.vp["iscopy"]=g.new_vp("bool") iscopy=g.vp["iscopy"] iscopy[newv]=True return(iscopy)
Which, when applied to this example, works:
However, I'm not sure this solution is scalable.
Is there a graph-tool function, something like
infect_vertex_property that could help me achieve this efficiently? Or maybe using loopless iteration?