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] <[email protected]> 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.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 <[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 <[email protected]>
>
>
> ------------------------------
> 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/Error-installing-graph-tool-on-windows-tp4024889p4024892.html
> 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/Error-installing-graph-tool-on-windows-tp4024889p4024893.html
Sent from the Main discussion list for the graph-tool project mailing list
archive at Nabble.com.
_______________________________________________
graph-tool mailing list
[email protected]
http://lists.skewed.de/mailman/listinfo/graph-tool
