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