gmane.comp.science.graph.graph-tool.general

bridge detection in graph-tool

Peng Yu — 2012-05-24T15:52:11

Hi,

I'm not able to find a bridge detection algorithm implemented in
graph-tool. In case that I missed anything, could anybody confirm with
me whether there is an implementation available?

RuntimeError: Gtk couldn't be initialized

Alasdair Macmillan — 2012-05-21T23:07:14

Hi there

Just installed graph-tool for the first time & get this error. What does it mean? How can i fix? I'm on Ubuntu Server 12.04

Much appreciated
Al

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.7/dist-packages/graph_tool/all.py", line 31, in <module>
    from graph_tool.draw import *
  File "/usr/lib/python2.7/dist-packages/graph_tool/draw/__init__.py", line 589, in <module>
    from cairo_draw import graph_draw, GraphWidget, GraphWindow, \
  File "/usr/lib/python2.7/dist-packages/graph_tool/draw/cairo_draw.py", line 59, in <module>
    from gi.repository import Gtk, Gdk, GdkPixbuf
  File "/usr/lib/python2.7/dist-packages/gi/importer.py", line 76, in load_module
    dynamic_module._load()
  File "/usr/lib/python2.7/dist-packages/gi/module.py", line 224, in _load
    overrides_modules = __import__('gi.overrides', fromlist=[self._namespace])
  File "/usr/lib/python2.7/dist-packages/gi/overrides/Gtk.py", line 1517, in <module>
    raise RuntimeError("G

libcairomm1.0 dependency in debian squeeze

Rodrigo Agerri — 2012-05-16T10:58:25

Hi,

I tried to install the graph-tool .deb package in debian squeeze from
the following repository

deb http://downloads.skewed.de/apt/squeeze squeeze main

but I cannot solve a libcairomm.10 dependency:

The following packages have unmet dependencies:
 graph-tool : Depends: libcairomm-1.0 but it is not installable

However, I do have  installed the appropriate debian packages which
should satisfy the dependency:

libcairomm-1.0-1 - C++ wrappers for Cairo (shared libraries)
libcairomm-1.0-dev - C++ wrappers for Cairo (development files)

The package dependencies are listed as:

Depends: libboost-iostreams1.42.0 (>= 1.42.0-1), libboost-python1.42.0
(>= 1.42.0-1), libboost-regex1.42.0 (>= 1.42.0-1), libc6 (>= 2.2.5),
libcairo2 (>= 1.2.4), libcairomm-1.0-1 (>= 1.6.4), libcgal5, libexpat1
(>= 1.95.8), libfontconfig1 (>= 2.8.0), libfreetype6 (>= 2.2.1),
libgcc1 (>= 1:4.1.1), libgmp3c2, libgomp1 (>= 4.2.1), libpng12-0 (>=
1.2.13-4), libpython2.6 (>= 2.6), libsigc++-2.0-0c2a (>= 2.0.2),
libstdc++6 (>= 4.4.0), libx

from graph_tool.all import * failed

mlacencio — 2012-05-15T19:59:30

Dear all,

I'm trying to take the first steps on using graph-tool. For this purpose,
I'm following the instructions in the "Quick start using graph-tool".
However, I could not advance to next steps due to the following error:

Python 2.7.2+ (default, Oct  4 2011, 20:06:09) 
[GCC 4.6.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
/usr/lib/python2.7/dist-packages/gobject/constants.py:24: Warning:
g_boxed_type_register_static: assertion `g_type_from_name (name) == 0'
failed
  import gobject._gobject

When I import graph-tool just typing "import graph-tool", everything seems
ok:
Python 2.7.2+ (default, Oct  4 2011, 20:06:09) 
[GCC 4.6.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.

Please, let me know what is possibly going wrong!

Thank you in advance!

Marcio


--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/from-graph-tool-all-import-failed-tp3989652.html
Sent from the Main di

Problem with new version on ubuntu oneiric

Giuseppe Profiti — 2012-05-14T12:55:40

Hi all,
I'm trying to install the new binary package but I'm having troubles with
the dependency from libcairomm-1.0. I already have libcairomm-1.0-1
(version 1.10-0-1) installed, along with libcairomm-1.0-dev (installed
while trying to solve this problem).

Before installing the binary release I removed (via make uninstall) a
custom build made from git sources.

Any hint? I can't build it from source, because I run out of memory while
compiling graph_sfdp.lo (even having 2GB of ram free before running make).

Thanks in advance,
Giuseppe
_______________________________________________
graph-tool mailing list
graph-tool< at >skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool

Package for Precise Pangolin

Phil.Tillet — 2012-05-05T15:26:45

Hello there,

The new Ubuntu 12.04 was released a few days ago and I still need graph tool
on my computer.
Is there any release planned on Precise?

Thanks a lot,
Keep up the good work :)

--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Package-for-Precise-Pangolin-tp3964750.html
Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.

Installing graph-tool using pip

Peng Yu — 2012-05-04T16:04:01

Hi,

I don't see a way to install graph-tool using pip. Port on Mac OS X is
not updated as frequently as pip. I'd recommend adding a way to
install graph-tool using pip. Right now, I see the following error.


/tmp$ pip install graph-tool
Downloading/unpacking graph-tool
  Downloading graph-tool-2.2.15.tar.bz2 (520Kb): 520Kb downloaded
  Running setup.py egg_info for package graph-tool
    Traceback (most recent call last):
      File "<string>", line 14, in <module>
    IOError: [Errno 2] No such file or directory:
'/private/tmp/build/graph-tool/setup.py'
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):

  File "<string>", line 14, in <module>

IOError: [Errno 2] No such file or directory:
'/private/tmp/build/graph-tool/setup.py'

----------------------------------------
Command python setup.py egg_info failed with error code 1

A* search extension

Guillaume Lemaître — 2012-04-21T09:19:45

  Hi Tiago,

In my opinion, the astar_search function contract could be extended to
accept a set of source vertices instead of a single one, without any
loss of generality.

In my particular need, I search the best path reaching a goal,
considering various start points. The trivial way to do that is:

for each eligible start point:
  run astar_search with this start point as 'source'
  memorize best path if better than ever

But, the astar_search algorithm, particularly when associated to a
AStarVisitor that build the graph locally to the examined vertices,
tends to limit the combinatorial explosion of searching. So that
iterating over eligible start points is necessarily sub-optimal.

So, currently, I introduce a pseudo-vertex as the source point, which
links to all my real eligible source points for no additional cost, and
benefit from the automatic scope restriction from astar_search which may
directly select the best start point by itself.

Another way to do that (and simplify user code) is to extend the

Community detection: how do 'ghost' edges appear?

Mikhail Spivakov — 2012-04-17T14:14:24

Hi Tiago and everyone,

I'm trying the community detection algorithm following the example
from the docs.

Brifely, with a graph g, I'm running the following:

# Plot the full graph
graph_draw(g, size=(15,15), output=output_folder+"/full_graph.png")
# Detect communities
spins = community_structure(g, n_iter=1000, n_spins=N) ### note the N parameter
ng = condensation_graph(g, spins)
size = ng[0].new_vertex_property("double")
size.a = log(ng[1].a+1)
# Plot the community graph
graph_draw(ng[0], vsize=size, vcolor=size, splines=True,
eprops={"len":20, "penwidth":10}, vprops={"penwidth":10},
output=output_folder+"/community_graph.png", size=(10,10))

I notice that when n_spins is small (say, n_spins=6), the resulting
community graph shows links that do not appear on the full graph.
See, for example, this pair of plots:

http://www.ebi.ac.uk/~spivakov/testX/full_graph.png
http://www.ebi.ac.uk/~spivakov/testX/community_graph.png

I'm a little confused as to how this is possible - am I right that
with this algorithm

subgraph_isomorphism bug: misses occurrences

Ingo Lohmar — 2012-04-15T16:06:09

Hi Tiago,

I was puzzled by some results of my tests failing when compared to
subgraph_isomorphism.  Finally I've narrowed it down to a (fairly) small example:

#####
from graph_tool.all import *

sub = Graph()
sub.add_vertex(3)
sub.add_edge(sub.vertex(0), sub.vertex(1))
sub.add_edge(sub.vertex(0), sub.vertex(2))

G = Graph()
G.add_vertex(4)
G.add_edge(G.vertex(0), G.vertex(1))
G.add_edge(G.vertex(0), G.vertex(2))
G.add_edge(G.vertex(1), G.vertex(2))
G.add_edge(G.vertex(3), G.vertex(2))
G.add_edge(G.vertex(1), G.vertex(3))

vmap, emap = subgraph_isomorphism(sub, G, random=False)
for e in G.edges(): print G.edge_index[e], e
for vm, em in zip(vmap, emap): print vm.a, em.a

G.add_vertex()
G.add_edge(G.vertex(1), G.vertex(4))

vmap, emap = subgraph_isomorphism(sub, G, random=False)
for e in G.edges(): print G.edge_index[e], e
for vm, em in zip(vmap, emap): print vm.a, em.a
#####

We search for sub, 

0 --> 1
 \
  \
   -> 2 

G first looks like this:

0 --> 1 --> 3
 \    |    /
  \   v   /
   -> 2 <-

when subgra

Purging vertices after filter

zkaiwen — 2012-04-10T21:04:56

Hi,

I have a question about purging. After filtering out certain vertices using
set_vertex_filter, I want to remove all filter vertices. However, after
removing them by calling the purge_vertices function, the property maps for
the vertices doesn't seem to line up anymore. For example:

Initial Graph:  with vertex and property map

Vertex    Property Map   
V1:        1                     Filtered
V2:        2                     Filtered
V3:        3                     Not Filtered
V4:        4                     Not Filtered

After calling purge I see

Vertex    Property Map   
V3:        1                     
V4:        2                     

This is not correct because V3's mapping is 3 and not 1. Is there a simple
fix to this issue or a suitable workaround without having to go back and
relabel all the property maps. Thanks.




--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Purging-vertices-after-filter-tp3900840p3900840.html
Sent from

Adding a subgraph into a graph

Kavya Shagrithaya — 2012-04-09T19:35:34

Hi,

I have one query about modifications with graphs.
There is a subgraph that I identify using pattern matching and remove it.
The intention is to replace that part with another graph. Using the
graph_union function
the graphs are combined structurally, however, all the properties of the
graph being
inserted are lost. Is there any way for insertion of subgraphs with the
properties preserved?

--
Thanks,
Kavya
_______________________________________________
graph-tool mailing list
graph-tool< at >skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool

How to access properties (stackoverflow question)?

Mikhail Spivakov — 2012-04-09T11:46:38

Hello Tiago and everyone,

I'd like to bring your attention to a question on stackoverflow, which
I'd also like to know the answer to:

http://stackoverflow.com/questions/9526827/graph-tool-how-to-access-properties

In particular, this bit:

"How do I get an object [vertex] with a certain title back from the
graph ? One way seems to be to create a vertex filter using
graph.set_edge_filter(...) and apply that - which seems a pretty
expensive operation considering all I want is to get one single object
back. I really don't want to maintain my own object title / vertex
index mapping as IMO, that is one of the tasks of the graph".

Consider, for example, the following simple situation: I've got an
existing set of vertices and then obtain information on edges between
them from somewhere, which may sometimes also involve vertices not yet
in the graph. In networkx, I would simply do: add_edge(x,y), where x
and y are vertex names (that have or have not been defined a priori
using add_node(x)).
Is there a straightfor

subgraph_isomorphism on filtered graph / GraphView =>segfaults

Ingo Lohmar — 2012-04-08T18:29:04

Dear Tiago,

Thank you for your great work on this very useful library!  I have
played with it for a project over the last few days, and today I have
discovered a real roadblock: subgraph_isomorphism seems to segfault (at
least very often, have not found any pattern yet) when searching on a
graph with filtered vertices (or the equivalent GraphView) --- this has
never occurred to me for an unfiltered graph.  Here is a minimal
example:

#####
from graph_tool.all import *

G = price_network(100)

sub = Graph()
sub.add_vertex(3)
sub.add_edge(sub.vertex(0), sub.vertex(1))
sub.add_edge(sub.vertex(1), sub.vertex(2))

# WORKS FINE:
print G
print subgraph_isomorphism(sub, G, random=False)

# FILTER FOR "OLDEST" VERTICES
vmap = G.new_vertex_property("bool")
for i in range(20):
    vmap[G.vertex(i)] = True

# EITHER THIS...
G.set_vertex_filter(vmap)
print G
print subgraph_isomorphism(sub, G, random=False)   # segmentation fault!
G.set_vertex_filter(None)

# OR THIS...
H = GraphView(G, vfilt=vmap)
print H
print subgraph

graph-tool can't find Graphviz renderer

Mikhail Spivakov — 2012-04-08T13:52:24

Hello!

I've got graphviz installed with python and python27 bindings.
However, when I do:

graph_draw(ug, vprops={"label": ug.vertex_index},
output="two-nodes.pdf", layout="fdp")

I get the following error:

graph G {
graph [outputorder=edgesfirst, mode=major, overlap=true, ratio=fill,
size="5.905512,5.905512", start=3019255687130444316];
node [label="\N", shape=circle, width="0.105", height="0.105",
style=filled, color="#2e3436", fillcolor="#a40000"];
edge [arrowsize="0.3", color="#2e3436", penwidth="1.0"];
graph [bb="0,0,425,425"];
0 [label=0, width="0.47", height="0.47", pos="330,101"];
1 [label=1, width="0.47", height="0.47", pos="93,324"];
0 -- 1 [pos="318,113 277,152 147,274 106,312"];
}
Error: renderer for pdf is unavailable
Out[8]: <PropertyMap object with key type 'Vertex' and value type
'vector<double>', for Graph 0x5ff3f90, at 0x6001290>

At the same time, if I save the above dot expression as test1.dot and
run the following command from the command line:

$ dot -Tpng test1.dot -o graph1.p

astar_search and weights as Python objects

Guillaume Lemaître — 2012-04-02T20:38:23

  Hi,

I'm trying to use the astar_search algorithm for my own problem, and I
get the following error:

====>

  File
"/usr/lib64/python2.7/site-packages/graph_tool/search/__init__.py", line
125, in wrap
    ret = func(*args, **kwargs)
  File
"/usr/lib64/python2.7/site-packages/graph_tool/search/__init__.py", line
1528, in astar_search
    compare, combine, zero, infinity, h)
RuntimeError: No static implementation was found for the desired
routine. This is a graph_tool bug. :-( Please follow but report
instructions at http://graph-tool.skewed.de. What follows is debug
information.

Graph view: boost::adjacency_list<boost::vecS, boost::vecS,
boost::bidirectionalS, boost::no_property,
boost::property<boost::edge_index_t, unsigned long, boost::no_property>,
boost::no_property, boost::listS>*

Action: boost::_bi::bind_t<void, do_astar_search,
boost::_bi::list9<boost::arg<1>, boost::_bi::value<unsigned long>,
boost::arg<2>, boost::_bi::value<std::pair<boost::any, boost::any> >,
boost::arg<3>, boost::_bi::value<gr

paths output from search algorithms?

Matthias Ekman — 2012-03-02T08:02:32

Hi,

is there a way to get the actual paths itself - instead of the distance - 
from the search algorithms like e.g. dijkstra_search?

As a related question, in a weighted adjacency matrix, how are the weights 
interpreted for dijkstra and centrality functions (pagerank, betweenness 
centrality) that rely on it. Is it low weight = easier to "travel", or is 
it the other way around?

Thanks in advance!
 Matthias
_______________________________________________
graph-tool mailing list
graph-tool< at >skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool

ImportError: No module named graph_tool.all

Oscar Vargas Torres — 2012-02-23T17:44:05

Hi Tiago!

$ $PYTHON_VERSION
bash: 2.7: command not found
$ uname -a
Linux compu4 3.2.6-2-ARCH #1 SMP PREEMPT Thu Feb 16 10:10:02 CET 2012
x86_64 AMD Phenom(tm) II X6 1055T Processor AuthenticAMD GNU/Linux
$ pacman -Q boost
boost 1.48.0-2
$ pacman -Q boost-libs
boost-libs 1.48.0-2
$ pacman -Q python2
python2 2.7.2-5
$ pacman -Q autoconf
autoconf 2.68-2
$ pacman -Q automake
automake 1.11.3-1
$ pacman -Q libtool
libtool 2.4.2-3
$ pacman -Q gcc
gcc 4.6.2-7
$ pacman -Q openmpi
openmpi 1.5.4-4
$ pacman -Q expat
expat 2.0.1-7
$ pacman -Q python2-numpy
python2-numpy 1.6.1-1
$ pacman -Q python2-scipy
python2-scipy 0.10.0-1
$ pacman -Q cgal
cgal 3.9-4
$ pacman -Q graphviz
graphviz 2.28.0-8

$ git clone git://git.skewed.de/graph-tool
$ cd graph-tool

$ autoreconf -f -i
configure.ac:34: warning: AC_ARG_PROGRAM was called before
AC_CANONICAL_TARGET
../../lib/autoconf/general.m4:1834: AC_CANONICAL_TARGET is expanded from...
configure.ac:34: the top level
configure.ac:34: warning: AC_ARG_PROGRAM was called before
AC_CANON

Configure error python development version needed??

jsia18 — 2012-02-20T12:29:03

I'm running centos 6.0

Using python 2.7 and boost 1.44 installed numpy scipy, expat and other
dependencies

when I run configure

./configure --prefix=/opt LDFLAGS=-L/opt/lib CPPFLAGS=-I/opt/include
CXXFLAGS=-I/opt/include 

I am producing an error: (I have Python.h installed since I compiled
python2.7 from source)

checking consistency of all components of python development environment...
no
configure: error:
  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.
  Example: ./configure LDFLAGS="-L/usr/non-standard-path/python/lib"
 
============================================================================
   ERROR!
   You probably have to install the development version of the Python
package
   for your distribution.  The exact name of this package varies among them.
 
============================================================================


--
View this mess

Ubuntu first configuration - Price Network example

Fabio — 2012-02-11T21:35:29

Hello,
I'm really really new to Ubuntu and Python, so be gentle with me, and
moreover don't give anything for granted with me, thank you!
I installed graph tool via 'sudo apt-get install graph-tool', and everything
seemed to go fine.
I'm now trying to run the example code from the documentation (Price Network
example), but I cannot make it work :-( 
These are the steps I followed:
1 - sudo gedit first.py
2 - copy and paste of example code
3 - save (so it gets in my home)
4 - python first.py
Here I get the following error:
/Traceback (most recent call last):
File "first.py", line 10, in <module>
from graph_tool.all import *
ImportError: No module named graph_tool.all/

I tried the following:
1: reissue the installing command, but it says that graph-tool is already
installed with last version
2: if I write 'graph-tool --help' it says command not found
3: gcc -v says

/Target: i686-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro
4.6.1-9ubuntu3' --with-bugurl=file:///usr/share/doc

Apt installation fails on Debian Sid

Tue V Jensen — 2012-01-27T13:25:30

Hi!

I tried installing the graph_tool package as per the instructions on the
download page, but apt-get fails with the following error:

Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 graph-tool : Depends: libcgal7 but it is not installable

It seems libcgal7 was recently renamed to libcgal8, as this is the only
available package in both testing and Wheezy.
Can I install using libcgal8, or will  have to wait for a version compatible
with this?

Thanks!
Tue

--
View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Apt-installation-fails-on-Debian-Sid-tp3693256p3693256.html
Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com