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.subgraph_isomorphism, > 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 <[email protected]>
signature.asc
Description: OpenPGP digital signature
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
