How to remove cycles in a graph by *unfolding* them using `graph-tool`?

75 views Asked by At

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?

0

There are 0 answers