Using 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[0],cycle[-1])
first=cycle[0]
# 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:
iscopy=cyunfold(g,cypath,['foo'],['bar'])
However, I'm not sure this solution is scalable.
Is there a graph-tool function, something like gt
's infect_vertex_property
that could help me achieve this efficiently? Or maybe using loopless iteration?