prune filtered graph, return subgraph isomorphism

The proposed function works like gt.Graph(g,prune=True), however additionally returns a subgraph isomorphism (vmap,emap) from the pruned graph to the original graph.

Example:

import graph_tool.all as gt

def choose_subgraph(G):
  import random
  sel = random.sample(xrange(G.num_vertices()), int(G.num_vertices()/2))
  selmap = G.new_vertex_property("bool")
  selmap.a = False
  for idx in sel: selmap[G.vertex(idx,use_index=False)] = True # IMPORTANT: use_index=False
  return gt.GraphView(G,vfilt=selmap)
  

def format_vmap(vmap):
  return ", ".join(["{}->{}".format(v,vmap[v]) for v in vmap.get_graph().vertices()])

def format_vlist(G):
  return ",".join(map(str,G.vertices()))
  

g1  = gt.complete_graph(10,directed=True)
g1s = choose_subgraph(g1)

s1, vmap, emap = prune(g1s)

g1m = gt.mark_subgraph(g1,s1,vmap,emap)

print "G1: " + format_vlist(g1)
print "G1s:" + format_vlist(g1s)
print "G1m:" + format_vlist(g1s)
print "S1: " + format_vlist(s1)
print "S1 -> G1s: " + format_vmap(vmap)

And the function:

def prune(g):
  """ Returns a copy s of the filtered graph g, and a mapping (vmap,emap) from s to g """
  ng = gt.Graph()
  vmap = ng.new_vertex_property("int")
  emap = ng.new_edge_property("int")
  rvmap = g.new_vertex_property("object")
  
  # copy internal properties
  vp = []  
  for name,p in g.vp.iteritems():
    ng.vp[name] = ng.new_vertex_property(p.value_type())    
    vp += [(ng.vp[name],p)]
    
  ep = []
  for name,p in g.ep.iteritems():
    ng.ep[name] = ng.new_edge_property(p.value_type())
    ep += [(ng.ep[name],p)]
    
  for name,p in g.gp.iteritems():
    ng.gp[name] = p.copy()
  
  # copy vertices
  for v in g.vertices():
    nv = ng.add_vertex()
    vmap[nv] = g.vertex_index[v]
    rvmap[v] = nv
    for np,p in vp: np[nv] = p[v]
    
  # copy edges
  for e in g.edges():
    ne = ng.add_edge(rvmap[e.source()],rvmap[e.target()])
    emap[ne] = g.edge_index[e]
    for np,p in ep: np[ne] = p[e]
    
  return ng, vmap, emap