June 2016 - graph-tool - archives.skewed.de

Shortest_distance complexity when used with max_dist
by François 05 Sep '16

05 Sep '16

<disclaimer> I hope this question isn't too dumb, if it is please accept my apologies. </disclaimer> Hi list, The graph that I work with has ≈ 30M vertices and ≈ 60M edges. This graph has positive weights, it represents a Road network. I need to compute the shortest path form a node to any other node within a range. The documentation shortest_distance <http://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.sh…> , states that the complexity (source and weights specified) is O(VlogV). My question is: "What happens when the *max_dist* parameter is specified ?" I observed that the execution time of *shortest_distance* increases linearly with the number of vertices. The execution time goes from 19ms with a sub-sample of 1M vertices and 2M edges to 320ms with the full graph. How can it be explained ? Thanks for your help, François. -- 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.

2 17

Clarifications in docs about graph_draw edge_control_points and splines?
by Philippe Doucet Beaupre 11 Jul '16

11 Jul '16

Hi Just putting this out there as I struggled with edge splines myself. In the section about graph_tool.draw.graph_draw, in the list about edges properties, the doc has this to say about splines: > control_points > Control points of a Bézier spline used to draw the edge. Each spline segment requires 6 values corresponding to the (x,y) coordinates of the two intermediary control points and the final point. There exist several different kinds of Bézier splines. In the case of graph-tool+cairo, these appear to be composite cubic Bézier splines. It became easier to understand the concept of control points once this was known to me. Further down the graph_draw example uses the following control points > >>> for e in g.edges(): > ... d = sqrt(sum((pos[e.source()].a - pos[e.target()].a) ** 2)) / 5 > ... control[e] = [0.3, d, 0.7, d] but the output doesn’t show any curvature for the edges. Changing the control point assignments to > ... control[e] = [0.0, 0.0, 0.3, d, 0.7, d, 1.0, 0.0] produces the desired curvature. I might understand this incorrectly but in addition to the 3 pairs (x,y) for two control+end points it seems like the first two value in array should be the coordinates of the initial point, most likely (0, 0). Omitting those always produces no or unexpected results in my case. The control point array would thus supposedly hav the structure > control_points[e] = [x0, y0, s1cp1x, s1cp1y, s1cp2x, s1cp2y, s1endx, s1endy, s2cp1x, s2cp1y, …, sNcpendx, sNcpendy] where si strands for segment i and cpj for control point j. The following script shows how a spline segment is drawn. Copy-paste in an IPython notebook should work directly. > %matplotlib inline > import graph_tool.all as gt > from numpy import array, sqrt, dot > from scipy.interpolate import interp1d > > # Create property maps and define some function > foo = gt.Graph() > foopos = foo.new_vertex_property('vector<double>') > edge_ctlpts = foo.new_edge_property('vector<double>') > edge_width = foo.new_edge_property('double') > edge_color = foo.new_edge_property('vector<double>') > vertex_fill_color = foo.new_vertex_property('vector<double>') > vertex_size = foo.new_vertex_property('double') > vertex_text = foo.new_vertex_property('string') > > def add_vertex(pos, size, color, text): > i = foo.add_vertex() > foopos[i] = pos > vertex_size[i] = size > vertex_fill_color[i] = color > vertex_text[i] = text > return i > > def add_vertex_and_edge(pos0, text0, pos1, text1, vsize, vfillcolor, epenwidth, ecolor): > i0 = add_vertex(pos0, vsize, vfillcolor, text0) > i1 = add_vertex(pos1, vsize, vfillcolor, text1) > ei = foo.add_edge(i0, i1) > edge_width[ei] = epenwidth > edge_color[ei] = ecolor > return (i0, i1, ei) > > # Create two vertex, edge and its composite cubic Bézier control points > v0, v1, e01 = add_vertex_and_edge(pos0=[1, 4], text0='', pos1=[5, 2], text1='', > vsize=10, vfillcolor=[0.640625, 0, 0, 0.9], > epenwidth=4, ecolor=[0.179, 0.203,0.210, 0.4]) > ctlpts = array([[0.0, 0.0], [0.2, -0.5], [0.3, 0.5], [0.5, 0.0], [0.7, -0.9], [0.8, 2.0], [1.0, 0.0]]) > edge_ctlpts[e01] = ctlpts.flatten() > > # Define fonction to convert from the relative coordinates > # of a control points to absolute vertex coordinates > def rel2abs(absx0y0, absx1y1, relxy): > xdir = absx1y1 - absx0y0 > norm = sqrt(dot(xdir, xdir)) > ydir = dot([[0, -1.0/norm], [1.0/norm, 0]], xdir) > return absx0y0 + xdir*relxy[0] + ydir*relxy[1] > > # Draw the control points and end points for each segment > # together with the interpolation lines between control points > v = v0 > for p in ctlpts: > vlast, v = v, foo.add_vertex() > e = foo.add_edge(vlast, v) > foopos[v] = rel2abs(foopos[v0].a, foopos[v1].a, p) > vertex_fill_color[v] = [1, 1, 1, 0] > vertex_size[v] = 15 > edge_width[e] = 2 > edge_color[e] = [0.179, 0.203,0.210, 0.6] > vertex_text[v] = repr(p.tolist()) > > ### Drawing the spline ### > # The control points we've selected above create two spline > #segments each comprised of a cubic Bézier spline with > # two control points and an end point. > > # We will focus on the second segment only and we will plot > # all the intermediate steps that lead to the position of > # the tip that draws its smooth path. > # The parameter t runs from 0 to 1 and will control the progression > # of the drawing tip from the beginning of the spline segment to its end. > t = 0.6 > > # To draw a cubic Bézier spline, we first need three interpolators: > # * from the initial point to the 1st control point, > # * from the first control point to the 2nd control point, > # * and from the 2nd control point to the end point. > f2a1 = interp1d([0, 1], array([ctlpts[3], ctlpts[4]]).T) > f2a2 = interp1d([0, 1], array([ctlpts[4], ctlpts[5]]).T) > f2a3 = interp1d([0, 1], array([ctlpts[5], ctlpts[6]]).T) > > # Then we need two more interpolators: > # * between the values of the first and second interpolator from above, > # * and between the values of the second and third interpolator from above. > f2b1 = interp1d([0, 1], array([f2a1(t), f2a2(t)]).T) > f2b2 = interp1d([0, 1], array([f2a2(t), f2a3(t)]).T) > > # Finally, the drawing tip that will actually trace > # the spline comprise a last interpolator between the above two. > f2c = interp1d([0, 1], array([f2b1(t), f2b2(t)]).T) > > # With these 6 interpolators we can now draw > # the state of each intermedeate step, all driven by the parameter t. > #Draw the first order interpolators. These will appear green on the final plot > add_vertex_and_edge(pos0=rel2abs(foopos[v0].a, foopos[v1].a, f2a1(t)), text0='', > pos1=rel2abs(foopos[v0].a, foopos[v1].a, f2a2(t)), text1='', > vsize=5, vfillcolor=[0, 0, 0, 1], > epenwidth=1, ecolor=[0.179, 0.703, 0.210, 0.8]) > add_vertex_and_edge(pos0=rel2abs(foopos[v0].a, foopos[v1].a, f2a2(t)), text0='', > pos1=rel2abs(foopos[v0].a, foopos[v1].a, f2a3(t)), text1='', > vsize=5, vfillcolor=[0, 0, 0, 1], > epenwidth=1, ecolor=[0.179, 0.703, 0.210, 0.8]) > > # the second degree interpolators. These will be blue. > add_vertex_and_edge(pos0=rel2abs(foopos[v0].a, foopos[v1].a, f2b1(t)), text0='', > pos1=rel2abs(foopos[v0].a, foopos[v1].a, f2b2(t)), text1='', > vsize=5, vfillcolor=[0, 0, 0, 1], > epenwidth=1, ecolor=[0.179, 0.203, 0.710, 0.8]) > # and finally the third and last degree. This is the drawing tip tracing the actual spline. > # It will be plotted as a solid black dot. > i0 = foo.add_vertex() > foopos[i0] = rel2abs(foopos[v0].a, foopos[v1].a, f2c(t)) > vertex_size[i0] = 9 > vertex_fill_color[i0] = [0, 0, 0, 1] > vertex_text[i0] = 't='+repr(t) > > # Draw the graph > gt.graph_draw(foo, pos=foopos, > edge_control_points=edge_ctlpts, edge_pen_width = edge_width, edge_color=edge_color, > vertex_size=vertex_size, vertex_fill_color=vertex_fill_color, vertex_anchor=1, > vertex_text=vertex_text, vertex_text_position=0, vertex_text_offset=[-0.07, -0.1], > inline=True, output_size=(600, 600), fit_view=(0, 0, 6, 6)) Philippe

2 1

find community classes/labels
by yinjunjun 04 Jul '16

04 Jul '16

Hi, I am trying to use graph tool to extract communities, and I used the minimize_blockmodel_dl function. However, after it has been executed successfully, I wish to know each vertex and information of which community it belongs to, and I can not figure out how. For example, state = graph_tool.community.minimize_blockmodel_dl(g, parallel=True) ##print state.b print state.get_blocks().get_array() it give me an array of all the vertex in zero. Could any one point me to the right directions. Thank you very much. Best Regards Junjun -- 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.

3 5

graph-tool Boost/OpenMP Algorithm Native Extensions
by Steve 30 Jun '16

30 Jun '16

I'd like to add a fast, compiled boost/openmp algorithm to my local graph-tool installation. Is there any guidance for how to modify the autoconf and/or setup.py/__init__.py files to accomplish this? -- 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.

2 1

Problem with graph tool visualization
by mmoein 30 Jun '16

30 Jun '16

I tried to plot a graph or run the animation example. But, I always get this error cairo_surface_set_device_scale. Importing graph_tool,gi and pygtk is not a problem in python. Has anyone had this problem before? I am using ubuntu 14.04 and python 2.7* (anaconda distribution). -- 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.

2 1

Regarding the reliability of graph tool for research applications
by vineesh vs 29 Jun '16

29 Jun '16

Dear all, I have been trying to install graph tool for past 2 days. Have met with many errors in installing it and its dependencies (still solving). Also I have seen many errors posted by the community regarding the usage of package. I was planning to use it for my research work since the tools seems promising. But it might take some time to change to another graph tool if I find out at a later stage that there are too many bugs in Python-graph tool and is not yet ready to relied on for a Ph.D level work. Hence I would really like to hear from the people who have used this tool for some work before I begin. Thanks a lot.

4 4

libboost_iostreams.so.1.61.0: cannot open shared object file: No such file or directory
by P-M 29 Jun '16

29 Jun '16

I am using Anaconda as my main python distribution (though also have the system's default python installed) so have to compile graph-tool from source to get it to work with Anaconda. I am using Ubuntu 14.04 so also have to compile boost from source to be able to use the full functionality of graph-tool. I have done so and they have both installed without any error messages, however, when then importing graph-tool in python using `from graph_tool.all import *` I get the error message `ImportError: libboost_iostreams.so.1.61.0: cannot open shared object file: No such file or directory`. How could I go about solving that problem/what is this caused by? Best wishes, Philipp -- 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.

3 11

Re: [graph-tool] Installation error: graph_triangulation.Io
by Yu Zheng 28 Jun '16

28 Jun '16

CGAL version: 4.9 G++ version: 5.3.0 Thanks for the tips in the reply message. Please excuse the rookie mistakes. We will follow the tips from now on. On Tue, Jun 28, 2016 at 12:07 AM, <graph-tool-request(a)skewed.de> wrote: > Send graph-tool mailing list submissions to > graph-tool(a)skewed.de > > To subscribe or unsubscribe via the World Wide Web, visit > https://lists.skewed.de/mailman/listinfo/graph-tool > or, via email, send a message with subject or body 'help' to > graph-tool-request(a)skewed.de > > You can reach the person managing the list at > graph-tool-owner(a)skewed.de > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of graph-tool digest..." > > > Today's Topics: > > 1. Re: Installation error: graph_triangulation.Io > (Tiago de Paula Peixoto) > 2. Re: from graph_tool.all import * gives ImportError > (Tiago de Paula Peixoto) > 3. Re: Error related to 'numpy_bind.hh' while doing 'make' > (Tiago de Paula Peixoto) > 4. Re: Regarding the reliability of graph tool for research > applications (Tiago de Paula Peixoto) > 5. Re: libboost_iostreams.so.1.61.0: cannot open shared object > file: No such file or directory (Tiago de Paula Peixoto) > 6. Re: Error related to 'numpy_bind.hh' while doing 'make' > (vineesh vs) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Tue, 28 Jun 2016 08:12:26 +0200 > From: Tiago de Paula Peixoto <tiago(a)skewed.de> > To: Main discussion list for the graph-tool project > <graph-tool(a)skewed.de> > Subject: Re: [graph-tool] Installation error: graph_triangulation.Io > Message-ID: <e6fb0308-232c-a706-232a-47811e20adef(a)skewed.de> > Content-Type: text/plain; charset="utf-8" > > On 27.06.2016 20:43, Yu Zheng wrote: > > Having installed every pre-requisite, including CGAL on my Linux server, > I still encounter the following error during installation. The specific > error message is: > > > > */usr/local/include/CGAL/Periodic_3_Delaunay_triangulation_3.h:266:60:* > *error: *no match for call to > ?*(CGAL::internal::Static_filters<CGAL::Filtered_kernel_base<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double, > CGAL::Epick>, CGAL::Epick> >, false>::Side_of_oriented_sphere_3 {aka > CGAL::internal::Static_filters_predicates::Side_of_oriented_sphere_3<CGAL::Filtered_kernel_base<CGAL::Type_equality_wrapper<CGAL::Cartesian_base_no_ref_count<double, > CGAL::Epick>, CGAL::Epick> > >}) (const Point&, const Point&, const Point&, > const Point&, const Point&, const Offset&, const Offset&, const Offset&, > const Offset&, const Offset&)*? > > > > Please do not post multiple times to the list with the same > question. Any lack of answer is most likely due to lack of time, rather > than the question not being seen. > > Whenever having problems with compilation, it very important to give > basic information, such as what compiler version is being used, library > versions, etc. In this case, it would be important to know which version > of CGAL do you have installed. > > Also, please not do not post terminal error messages or log files in RTF > format, which makes it very cumbersome to inspect. Please just use plain > text. > > Best, > Tiago > > -- > Tiago de Paula Peixoto <tiago(a)skewed.de> > >

2 2

Numpy 1.11 version gives error during 'make' of graph-tool
by vineesh vs 28 Jun '16

28 Jun '16

I removed the Python 1.60 which comes by default while doing _sudo apt-get install python-numpy_ and installed Python 1.11.1 from Sourceforge and then tried to do _make_ for graph-tool. Getting the following error Commands used (in graph tool directory) ------------------------------------------------------- ./configure make ------------------------------------------------------- Errors ------------------------------------------------------- make all-recursive make[1]: Entering directory `/home/wecare/Downloads/transferred/graph-tool-2.16' Making all in src make[2]: Entering directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src' Making all in graph make[3]: Entering directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph' Making all in centrality make[4]: Entering directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph/centrality' make[4]: Nothing to be done for `all'. make[4]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph/centrality' Making all in clustering make[4]: Entering directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph/clustering' CXX graph_motifs.lo In file included from ./../graph_python_interface.hh:47:0, from graph_motifs.cc:26: ./../numpy_bind.hh:30:31: fatal error: numpy/arrayobject.h: No such file or directory compilation terminated. make[4]: *** [graph_motifs.lo] Error 1 make[4]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph/clustering' make[3]: *** [all-recursive] Error 1 make[3]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph' make[2]: *** [all-recursive] Error 1 make[2]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src' make[1]: *** [all-recursive] Error 1 make[1]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16' make: *** [all] Error 2 -------------------------------------------------------

3 4

Error related to 'numpy_bind.hh' while doing 'make'
by vineesh vs 28 Jun '16

28 Jun '16

Commands used ------------ ./configure make ------------ Errors ---------------------------------------------------------------------------------- CXX graph_motifs.lo In file included from ./../graph_python_interface.hh:47:0, from graph_motifs.cc:26: ./../numpy_bind.hh: In function ‘boost::python::api::object wrap_vector_owned(std::vector<T>&)’: ./../numpy_bind.hh:83:34: error: ‘NPY_ARRAY_ALIGNED’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray, NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:83:54: error: ‘NPY_ARRAY_C_CONTIGUOUS’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray, NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:84:25: error: ‘NPY_ARRAY_OWNDATA’ was not declared in this scope NPY_ARRAY_OWNDATA | NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh:84:45: error: ‘NPY_ARRAY_WRITEABLE’ was not declared in this scope NPY_ARRAY_OWNDATA | NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh:84:64: error: there are no arguments to ‘PyArray_ENABLEFLAGS’ that depend on a template parameter, so a declaration of ‘PyArray_ENABLEFLAGS’ must be available [-fpermissive] NPY_ARRAY_OWNDATA | NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh:84:64: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated) ./../numpy_bind.hh: In function ‘boost::python::api::object wrap_vector_not_owned(std::vector<T>&)’: ./../numpy_bind.hh:101:33: error: ‘NPY_ARRAY_ALIGNED’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray,NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:101:53: error: ‘NPY_ARRAY_C_CONTIGUOUS’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray,NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:102:25: error: ‘NPY_ARRAY_WRITEABLE’ was not declared in this scope NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh:102:44: error: there are no arguments to ‘PyArray_ENABLEFLAGS’ that depend on a template parameter, so a declaration of ‘PyArray_ENABLEFLAGS’ must be available [-fpermissive] NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh: In function ‘boost::python::api::object wrap_multi_array_owned(boost::multi_array<ValueType, Dim>&)’: ./../numpy_bind.hh:121:34: error: ‘NPY_ARRAY_ALIGNED’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray, NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:121:54: error: ‘NPY_ARRAY_C_CONTIGUOUS’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray, NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:122:25: error: ‘NPY_ARRAY_OWNDATA’ was not declared in this scope NPY_ARRAY_OWNDATA | NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh:122:45: error: ‘NPY_ARRAY_WRITEABLE’ was not declared in this scope NPY_ARRAY_OWNDATA | NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh:122:64: error: there are no arguments to ‘PyArray_ENABLEFLAGS’ that depend on a template parameter, so a declaration of ‘PyArray_ENABLEFLAGS’ must be available [-fpermissive] NPY_ARRAY_OWNDATA | NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh: In function ‘boost::python::api::object wrap_multi_array_not_owned(boost::multi_array<ValueType, Dim>&)’: ./../numpy_bind.hh:135:34: error: ‘NPY_ARRAY_ALIGNED’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray, NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:135:54: error: ‘NPY_ARRAY_C_CONTIGUOUS’ was not declared in this scope PyArray_ENABLEFLAGS(ndarray, NPY_ARRAY_ALIGNED | NPY_ARRAY_C_CONTIGUOUS | ^ ./../numpy_bind.hh:136:25: error: ‘NPY_ARRAY_WRITEABLE’ was not declared in this scope NPY_ARRAY_WRITEABLE); ^ ./../numpy_bind.hh:136:44: error: there are no arguments to ‘PyArray_ENABLEFLAGS’ that depend on a template parameter, so a declaration of ‘PyArray_ENABLEFLAGS’ must be available [-fpermissive] NPY_ARRAY_WRITEABLE); ^ make[4]: *** [graph_motifs.lo] Error 1 make[4]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph/clustering' make[3]: *** [all-recursive] Error 1 make[3]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src/graph' make[2]: *** [all-recursive] Error 1 make[2]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16/src' make[1]: *** [all-recursive] Error 1 make[1]: Leaving directory `/home/wecare/Downloads/transferred/graph-tool-2.16' make: *** [all] Error 2 ---------------------------------------------------------------------------------- What could be the reason?

2 2