Thanks again for the reply. I've tried the motifs function, but it doesn't do quite what I need yet. It seems to output the number of motifs with a certain number of vertices, and the motif itself as a graph, but I also required the exact vertices. My graphs represent real world (CAD) data, and I need to be able map the found subgraphs back to the CAD model. I'm working on engineering data for a university project, and I essentially need to detect the 'smallest chorless cycles' in data that represents electrical wiring, which (as far as i know) is the same as finding. I'm an aerospace engineer and not a mathematician, so any help in defining the proper mathematical wording for this is greatly appreciated :) To illustrate what I'd need: in this graph https://www.dropbox.com/s/8nlnqcvhb150utt/example_graph-tool.PNG I for instance want to get all cyclic induced subgraphs with 3 vertices. The algorithm should return [0,1,4], [0,2,4], [2,3,4] and [3,5,6]. Of course it's fine if it finds [4,1,0], [1,0,4] and [4,0,1] and suchlike as well, I can filter easily based on the vertices contained in the subgraph. If I look for a subgraph with 4 vertices, I want 0 hits because [0,1,2,4] has a chord due to edge [0,4]. Any suggestions on a combination of functions to achieve this would be greatly appreciated :) On 3 January 2013 13:07, Tiago Peixoto [via Main discussion list for the graph-tool project] <ml-node+s982480n4024892h26@n3.nabble.com> wrote:
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 <[hidden email]<http://user/SendEmail.jtp?type=node&node=4024892&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http://user/SendEmail.jtp?type=node&node=4024892&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (565 bytes) Download Attachment<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4024892/0/signature.asc> -- Tiago de Paula Peixoto <tiago@skewed.de>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To unsubscribe from Error installing graph-tool on windows, click here<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4024889&code=amVsbGUudmVyYWFAa2Utd29ya3MuY29tfDQwMjQ4ODl8MTk0ODgyODA5> . NAML<http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.