On 01/03/2013 12:30 PM, jcjveraa wrote:
Thanks for the quick reply! I might be even better off just installing Linux, I've tried it on a virtual instance and it was more or less just an apt-get install on Ubuntu which is quite a bit easier :)
It is... One day I might install windows on a virtual machine and sort these problems, but it is not very high on my priority list, I must confess.
I was wondering: the specific graphs I'm looking for are induced isomorphic subgraphs. G can be any undirected graph, and subgraph S is a chorless cycle (i.e. a 'ring' with n vertices). I specifically want to find all (unique) vertex induced subgraphs of S in G, or in other words all chordless subgraphs of length n in G.
With vm, em = gt.subgraph_isomorphism(S,G) I can find subgraphs, but they are not neccesarily vertex induced: the found isomorphic subgraph (lets call them F) can have more edges than S
Note that the motifs() function will probably do just what you want. A "motif" is what some non-mathematicians call an induced subgraph.
I can see two ways to detect if the found subgraph F is isomorphic to S
1. (for this specific case) check if the number of edges in S == number of edges in F - as they are cyclic this works 2. check with gt.isomorphism(S,F)
Only: how do I get F?
I use vmask, emask = gt.mark_subgraph(G,S, vm[i], em[i]) in a loop as in
http://projects.skewed.de/graph-tool/doc/topology.html#graph_tool.topology.s...,
but after masking G.set_vertex_filter(vmask) still gt.isomorphism(S,G) == False
The function gt.isomorphism() tests for isomorphism, not subgraph ismorphism. So it should return False in this case, unless it is induced, as you desire. I imagine you want to use the edge filter here as well.
How do I generate a new graph from the output of gt.subgraph_isomorphism(S,G) which has all vertices and edges of F but no more (i.e. how do I define F as a graph which will possibly give gt.isomorphism(F,S) == True when this is the case).
From what I can see, in the above gt.isomorphism(F,S) == True should happen if F is an induced subgraph....
Or should I be able to check the number of edges in the filtered version of G as per my method 1? How?
After you have masked the vertices/edges you get this simply from g.num_edges(). Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>