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

Re: [graph-tool] Meaning of vertex_corr in block stochastic?
by Tiago Peixoto 03 Oct '16

03 Oct '16

Sorry for the late reply, but there was a problem with the mailing list. ttfoley wrote > I can't figure out the precise meaning of 'proportional' to, and would > like to know where/how it enters into the the actual formulae for > stochastic blocks. I have tried playing with various limits, and of course > tried scaling the 'probability' to account for graph size. For example, > there does not appear to be a limit where all edges are within blocks, > though surely this should be possible(assuming the number of edges fits > within the blocks)? Any help would be greatly appreciated. Proportional means exactly that: The probability will be what you give, up to an overall constant, which is unimportant since the total number of edges is always fixed. To force the edges to always be inside the groups, you should set the probability to zero, whenever r != s. ----- -- Tiago de Paula Peixoto <tiago(a)skewed.de> -- 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 2

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

Re: [graph-tool] Re index edges
by Tiago Peixoto 29 Jul '16

29 Jul '16

See: https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.re… ----- -- Tiago de Paula Peixoto <tiago(a)skewed.de> -- 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

Eigenvector centrality runtime/complexity
by Philipp Singer 27 Jul '16

27 Jul '16

Hi all, I have run into a runtime/complexity question where I am wondering if someone can give me insights into why this might happen. I have conducted the following steps: 1.) Create some random network 2.) Calculate eigenvector centrality 3.) Sample 10% random nodes 4.) Filter graph by nodes 5.) Calculate eigenvector centrality on sample I have observed that for the sample, the eigenvector centrality calculation takes much longer, in some cases (dependent e.g., on block structure) it takes way longer (like 30 times longer). I am now trying to figure out why this is the case. I assume it has something to do with the convergence which might be probably because links are missing in the sample. If I do the same for e.g., PageRank the difference is not that drastic (it still takes longer in the sample). Does anyone have an idea what is going on here? Thanks, Philipp

3 7

Ubuntu 14.04 and Boost::Coroutine Library
by nicole 25 Jul '16

25 Jul '16

config.log <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> Hello, I read the discussions and suggestions regarding this topic but still struggle with the Boost Coroutine Lib. I built the Boost Library 1.55 (and afterwards also 1.60) without errors from source. The Libs were built into the directory /usr/local/lib and the corresponding header files are located in /usr/local/include/boost. Especially, the file libboost_coroutine.so (versions 1.55.0 and 1.60.0 and a link libboost_coroutine.so) is available in /usr/local/lib. Afterwards, I tried to configure the graph-tool project (following the advices in http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com… <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> ) with the command ./configure LDFLAGS="-L/usr/local/lib" CPPFLAGS config.log <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> ="-I/usr/local/include/boost/". But I still get the message "checking whether the Boost::Coroutine library is available... no configure: WARNING: No usable boost::coroutine found! Some functionality will be disabled in the library" (see attached config.log). Am I miss an obvious aspect? Thank you in advance. Best regards, Nicole -- 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 13

Simple node access runtime
by killver 21 Jul '16

21 Jul '16

I am currently implementing an existing networkx implementation in graph-tool and observed that the new implementation runs slower than the networkx one. I then found out that a simple node access is already slower. So I have the exact same undirected graph with 1000 nodes and avg. degree of 2 in nx and gt, and then run: def select(g): for i in range(1000): n = g.vertex(0) def select_nx(g): for i in range(1000): n = g.nodes(0) %time select(gt) CPU times: user 75.6 ms, sys: 69 µs, total: 75.6 ms Wall time: 72.6 ms %time select_nx(g) CPU times: user 3.82 ms, sys: 0 ns, total: 3.82 ms Wall time: 3.46 ms So I am wondering whether this is to be expected and that I can only see the drastic runtime improvements when working with calculations like shortest paths etc. -- 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 3

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

Re: [graph-tool] Best Practice for Installing graph-tool-2.16 on CentOS 7 for Non-Tech Sophisticated Researcher
by Yu Zheng 06 Jul '16

06 Jul '16

Thank you so much, Frank! All the best for your research. And thank you so much for the step-by-step guide! If I had a choice, I would not use CentOS 7. Unfortunately, this is not up to me. On Wed, Jul 6, 2016 at 2:05 PM, <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: Best Practice for Installing graph-tool-2.16 on CentOS 7 > for Non-Tech Sophisticated Researcher (Tiago de Paula Peixoto) > 2. Re: Best Practice for Installing graph-tool-2.16 on CentOS 7 > for Non-Tech Sophisticated Researcher (Frank Takes) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Wed, 6 Jul 2016 19:30:35 +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] Best Practice for Installing graph-tool-2.16 > on CentOS 7 for Non-Tech Sophisticated Researcher > Message-ID: <ed1693d4-2490-80e0-7871-fd3dc09d2756(a)skewed.de> > Content-Type: text/plain; charset="utf-8" > > On 06.07.2016 19:28, Yu Zheng wrote: > > I wonder if you have any recommendation or general comments for us > > non-CS trained researchers installing graph-tool-2.16 on CentOS7? Much > > appreciated, > > Don't use CentOS 7, I guess... > > -- > Tiago de Paula Peixoto <tiago(a)skewed.de> > >

1 0

Re: [graph-tool] Best Practice for Installing graph-tool-2.16 on CentOS 7 for Non-Tech Sophisticated Researcher
by Yu Zheng 06 Jul '16

06 Jul '16

Hi Tiego, I hear your concern about using a deprecated version of graph-tool. Unfortunately, I found out that nothing on CentOS7 meet the pre-requisite of graph-tool-2.16, not even the GCC compiler. And after many hours of reading Linux textbook and browsing the internet, we simply did not manage to build graph-tool-2.16 from source. And that's why we opted for graph-tool-2.8 as a far from perfect solution. I wonder if you have any recommendation or general comments for us non-CS trained researchers installing graph-tool-2.16 on CentOS7? Much appreciated, Yu On Wed, Jul 6, 2016 at 3:00 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 (Yu Zheng) > 2. Re: Installation error: graph_triangulation.Io > (Tiago de Paula Peixoto) > 3. Simple node access runtime (killver) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Tue, 5 Jul 2016 14:01:25 -0700 > From: Yu Zheng <yz2235(a)stanford.edu> > To: graph-tool(a)skewed.de > Subject: Re: [graph-tool] Installation error: graph_triangulation.Io > Message-ID: > < > CAKaJjmXNrzXRywDfRXvGyg27o_voUagJxx1u5sBgbMm_bZGtWg(a)mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > Hi Tiego, > > Thank you so much for helping us out! You were right, CGAL were not > properly configured on the server. > > Instead of building everything from source on CentOS7, I built > graph-tool-2.8 instead of the latest release, following the step-by-step > directions here: > https://gist.github.com/sbonner0/2138f2e3e2b249df51c765e1656f9d48. I hope > this link will help others in similar situations. > > Much obliged, > Yu > > On Wed, Jun 29, 2016 at 3:00 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: Installation error: graph_triangulation.Io > > (Tiago de Paula Peixoto) > > > > > > ---------------------------------------------------------------------- > > > > Message: 1 > > Date: Tue, 28 Jun 2016 18:43:00 +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: <a116a57c-3de4-32bc-f666-7ff9b4e3933f(a)skewed.de> > > Content-Type: text/plain; charset="utf-8" > > > > On 28.06.2016 18:38, Yu Zheng wrote: > > > CGAL version: 4.9 > > > > This might be some incompatibility with version 4.9. I will investigate. > > > > In the mean time, you may downgrade to version 4.8, which should solve > > the problem. > > > > Best, > > Tiago > > > > -- > > Tiago de Paula Peixoto <tiago(a)skewed.de> > > > >

3 2

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

05 Jul '16

Hi Tiego, Thank you so much for helping us out! You were right, CGAL were not properly configured on the server. Instead of building everything from source on CentOS7, I built graph-tool-2.8 instead of the latest release, following the step-by-step directions here: https://gist.github.com/sbonner0/2138f2e3e2b249df51c765e1656f9d48. I hope this link will help others in similar situations. Much obliged, Yu On Wed, Jun 29, 2016 at 3:00 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: Installation error: graph_triangulation.Io > (Tiago de Paula Peixoto) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Tue, 28 Jun 2016 18:43:00 +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: <a116a57c-3de4-32bc-f666-7ff9b4e3933f(a)skewed.de> > Content-Type: text/plain; charset="utf-8" > > On 28.06.2016 18:38, Yu Zheng wrote: > > CGAL version: 4.9 > > This might be some incompatibility with version 4.9. I will investigate. > > In the mean time, you may downgrade to version 4.8, which should solve > the problem. > > Best, > Tiago > > -- > Tiago de Paula Peixoto <tiago(a)skewed.de> > >

2 1