Error installing graph-tool on windows

graph-tool
1

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 :slight_smile: - 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 :slight_smile:

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

attachment.html (2.32 KB)

2

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

3

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 :slight_smile:

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.subgraph_isomorphism,
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

attachment.html (10.7 KB)

4

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 :slight_smile:

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

5

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 :slight_smile:

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 :slight_smile:

attachment.html (7.93 KB)

6

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

7

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

attachment.html (6.32 KB)