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 :) 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 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 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). Or should I be able to check the number of edges in the filtered version of G as per my method 1? How? Thanks for your assistance! Jelle Veraa On 3 January 2013 11:42, Tiago Peixoto [via Main discussion list for the graph-tool project] <ml-node+s982480n4024890h64@n3.nabble.com> wrote:

Hi there,

It seems the configure script cannot find some libraries:

c:/users/jelle.veraa/dropbox/ke-works-jelleveraa/random/mingw/bin/../lib/gcc/mingw32/4.7.2/../../../../mingw32/bin/ld.exe:

cannot find -lbz2 c:/users/jelle.veraa/dropbox/ke-works-jelleveraa/random/mingw/bin/../lib/gcc/mingw32/4.7.2/../../../../mingw32/bin/ld.exe:

cannot find -lexpat

and it screws up finding extra link flags for python:

configure:17030: checking python extra linking flags configure:17037: result: None configure:17044: checking consistency of all components of python development environment configure:17070: gcc -o conftest.exe -g -O2 -Ic:\Python27\include conftest.c -lm -Lc:\Python27\Lib\config -lpython27 None >&5 gcc.exe: error: None: No such file or directory

Make sure all the necessary libraries are installed in the correct path. For the last bug, the check is done in m4/ax_python_devel.m4:

if test -z "$PYTHON_EXTRA_LDFLAGS"; then PYTHON_EXTRA_LDFLAGS=`$PYTHON -c "import distutils.sysconfig; \ conf = distutils.sysconfig.get_config_var; \ print (conf('LINKFORSHARED'))"` fi

For some reason, it is printing 'None', instead of an empty string. This could be changed to something like,

if test -z "$PYTHON_EXTRA_LDFLAGS"; then PYTHON_EXTRA_LDFLAGS=`$PYTHON -c "import distutils.sysconfig; \ conf = distutils.sysconfig.get_config_var; \ x = conf('LINKFORSHARED'); \ x = x if x is not None else ''; \ print (x)"` fi

But this is unlikely to fix the problem, since I think it is very strange that this value points to None in the first place.

It would be nice to have graph-tool working on windows, but it is a very weird platform, and I do not have access to a windows machine to understand all its idiosyncrasies.

Cheers, Tiago

On 01/02/2013 02:27 PM, Jelle Veraa wrote:

...

Dear all,

Happy new year!

Starting of with what I'd actually like to do (building the program is of course a means to an end :) - I'd like to use the library for its subgraph isomorphism algorithm specifically - should you be able to provide me a binary of the library or know of another fast implementation for subgraph isomorphism that might help me as well.

I'm trying to install the library on a 64 bit Windows 7 machine running 32 bit python 2.7. Installing the dependencies (from binaries) works, but running ./config from MinGW/MSys gives me an error. it exits with "Could not link test program to Python. Maybe the main Python library has been installed in some non-standard library path. If so, pass it to configure, via the LDFLAGS environment variable.", but the solution seems less straightforward - I've already tried all kinds of LDFLAGS versions pointing towards my Python folder (at C:\Python27, or /c/Python27 in MinGW).

here is the log: http://bpaste.net/show/82ASZHcSnWmGsBIglFEo/

From line 2055/configure:16996 things start going wrong (a bit is posted below). There is a reference to Lib\config, but the config directory does not exist. Furthermore the output 'None' at configure:17037 is injected into the command line for gcc.exe which also gives an error.

I've been googling for an answer for some hours now bu no luck. I see that you need python-dev on linux for instance, but I've got Windows so 'apt-get python-dev' won't work :)

Can anyone help me?

thanks, Jelle

configure:16996: result: -Lc:\Python27\Lib\config -lpython27 configure:17003: checking for Python site-packages path configure:17009: result: c:\Python27\Lib\site-packages configure:17016: checking python extra libraries configure:17023: result: configure:17030: checking python extra linking flags configure:17037: result: None configure:17044: checking consistency of all components of python development environment configure:17070: gcc -o conftest.exe -g -O2 -Ic:\Python27\include conftest.c -lm -Lc:\Python27\Lib\config -lpython27 None >&5 gcc.exe: error: None: No such file or directory

_______________________________________________ graph-tool mailing list [hidden email] <http://user/SendEmail.jtp?type=node&node=4024890&i=0> http://lists.skewed.de/mailman/listinfo/graph-tool

-- Tiago de Paula Peixoto <[hidden email]<http://user/SendEmail.jtp?type=node&node=4024890&i=1>>

_______________________________________________ graph-tool mailing list [hidden email] <http://user/SendEmail.jtp?type=node&node=4024890&i=2> 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/4024890/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.

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.

Excellent, that does exactly what I need! I had implemented my own version of this in Java (VF2 algorithm) which literally takes an hour to do something this does in 5 minutes, even on a virtual host with only 1 out of 4 cores. Thanks, Jelle On 3 January 2013 22:37, Tiago Peixoto [via Main discussion list for the graph-tool project] <ml-node+s982480n4024894h88@n3.nabble.com> wrote:

On 01/03/2013 02:36 PM, jcjveraa wrote:

...

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 :) This can be done simply as follows, if I understood correctly:

from graph_tool.all import *

g = Graph(directed=False) g.add_vertex(7) edges = [(5, 6), (5, 3), (6, 3), (3, 4), (3, 2), (4, 2), (4, 0), (4, 1), (2, 0), (1, 0)] for e in edges: g.add_edge(e[0], e[1])

def get_cycle(n): u = Graph(directed=False) u.add_vertex(n) for i in range(n - 1): u.add_edge(i, i + 1) u.add_edge(n - 1, 0) return u

S = get_cycle(3)

vmaps, emaps = subgraph_isomorphism(S, g)

for vm, em in zip(vmaps, emaps): vmask, emask = mark_subgraph(g, S, vm, em)

F = Graph(GraphView(g, vfilt=vmask), prune=True)

if isomorphism(F, S): print("found: ", vm.a)

For this I get:

found: [5 6 3] found: [5 3 6] found: [1 4 0] found: [1 0 4] found: [6 5 3] found: [6 3 5] found: [2 4 3] found: [2 4 0] found: [2 3 4] found: [2 0 4] found: [4 1 0] found: [4 2 3] found: [4 2 0] found: [4 3 2] found: [4 0 1] found: [4 0 2] found: [3 5 6] found: [3 6 5] found: [3 2 4] found: [3 4 2] found: [0 1 4] found: [0 2 4] found: [0 4 1] found: [0 4 2]

And indeed, if I make S = get_cycle(4), no induced subgraphs are found.

Does this help?

Cheers, Tiago

-- Tiago de Paula Peixoto <[hidden email]<http://user/SendEmail.jtp?type=node&node=4024894&i=0>>

_______________________________________________ graph-tool mailing list [hidden email] <http://user/SendEmail.jtp?type=node&node=4024894&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/4024894/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.