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] <[hidden email]> 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]>


_______________________________________________
graph-tool mailing list
[hidden email]
http://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (565 bytes) Download Attachment
--
Tiago de Paula Peixoto <[hidden email]>


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.
NAML


View this message in context: Re: Error installing graph-tool on windows
Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.