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

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

Questions about inference algorithms
by Andrea Briega 08 Jun '16

08 Jun '16

Dear Dr Peixoto, I would like to solve some questions I have about inference algorithms for the identification of large-scale network structure via the statistical inference of generative models. Minimize_blockmodel algorithm takes an hour to finish using my network with 21000 nodes (like the hierarchical version), and it spends two days and a half with overlap. However, I have run an hierarchical analysis with overlap, and it is still running since 14 days ago. So my first question is: is this time normal, or maybe there is any problem? Do you know how long could it ussually takes? Secondly, I have repeated some of these analysis with exactly same options but I get different solutions (similar but different), so I wonder if the algorithm is heuristic (I thought it was exact). My last question question regards bipartite analysis. I have two types of nodes in my network and I wonder if there are any analytical difference when running these algorithms with the bipartite option (clabel=True, and different labels in each group of nodes) or not, because it seems that the program “knows” my network is bipartite in any case. If there are differences between bipartite and “unipartite” analysis (clabel=False), is it possible to compare description length between them to model selection? Thank you very much for your help! Best regards, Andrea

2 10

Graph-tool configure error: Boost::Iostreams library is available but no usable boost::iostreams is found
by Bretsky 29 May '16

29 May '16

Disclaimer: I am a Linux noob and I don't know anything about C++. I'm trying to configure graph-tool on Ubuntu 16.04 with Python 3.5.1. I have installed all of the prerequisites, and I ran Everything worked up until I got this error: I tried using the fix suggested here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> , but I got the same error when I ran which is the path I got from my Boost installation I am not sure how to fix this and would really appreciate if someone who knows more about Linux and graph-tool could help me. -- 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

About the blocks from the minimize_nested_blockmodel_dl
by Rogelio Basurto 28 May '16

28 May '16

Hello, I've been using graph tool for about 3 weeks now. I just ran into it while searching for a modularity method for a bipartite network. I am amazed by graph tool and the algorithms within. But I am having truble with a basic question (at least I think it is). I am reading a bipartite network from a graphml file, then I do some filtering and finally I construct the minimize_nested_blockmodel_dl as in the example. Then I draw it, just like in the example, and it looks great. I manage to draw it with the node names and they are fine. Then, I would like to check the names of the nodes in the different blocks, by the levels they are arranged from the stochastic nested block model. But I do not know how to do that. I found the function get_bstack() for the NestedBlockState object, but the index in those vertices are from 0 to N, where N is the number of vertices per level (of the model, not from my graph, I think), then how do I associate my original vertex index (which has its name) to those graphs from the different levels? In short, I want to write down (terminal or file) the vertices from the graph (with its node names) for each level and respective block. I suppose it can be done, because the info is in the draw, but I do not know how. Thanks in advance! Great job with graph tool, and the stochastic block model (which I haven't completely understood, but I will). Tech info: I work with graph-tool 2.16-1 under Arch Linux, with Python 3.5, if that matters. The bipartite network have 2230 vertices and 246764 edges . >From the state summary: l: 0, N: 2230, B: 174 l: 1, N: 174, B: 68 l: 2, N: 68, B: 26 l: 3, N: 26, B: 9 l: 4, N: 9, B: 3 l: 5, N: 3, B: 1 Have a great day! ____ *Rogelio Basurto Flores* Laboratorio de Sistemas Complejos *Unidad Profesional Interdisciplinaria en Ingeniería y * *Tecnologías Avanzadas,* *Instituto Politécnico Nacional,* *Av. IPN # 2580, Col. Laguna Ticoman,* *Ciudad de México, 07340, México* *Mobile Phone: 33 1551 3665* *E-Mail: rogelio.basurto(a)gmail.com <rogelio.basurto(a)gmail.com>*

3 2

Re: [graph-tool] About the blocks from the minimize_nested_blockmodel_dl
by Rogelio Basurto 27 May '16

27 May '16

Hi Csongor, I actually can do that. And when building the state and drawing it I use the name label, so the problem really is how to map the information I originally have to the levels and states I get from the NestedBlockModel. The model is very interesting, I am still reading about it and is not bad to check it out in case yo ever get a network like those in the examples: http://arxiv.org/pdf/1310.4377.pdf Thanks for the answer! ____ *Rogelio Basurto Flores* Laboratorio de Sistemas Complejos *Unidad Profesional Interdisciplinaria en Ingeniería y * *Tecnologías Avanzadas,* *Instituto Politécnico Nacional,* *Av. IPN # 2580, Col. Laguna Ticoman,* *Mexico D. F., 07340, Mexico* *Mobile Phone: 33 1551 3665* *E-Mail: rogelio.basurto(a)gmail.com <rogelio.basurto(a)gmail.com>* On Fri, May 27, 2016 at 5: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: About the blocks from the minimize_nested_blockmodel_dl > (Matyas, Csongor) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Thu, 26 May 2016 15:23:38 -0230 > From: "Matyas, Csongor" <cfm482(a)mun.ca> > To: Main discussion list for the graph-tool project > <graph-tool(a)skewed.de> > Subject: Re: [graph-tool] About the blocks from the > minimize_nested_blockmodel_dl > Message-ID: > < > CAHCsTsazu6bhZRUAv5HgCvQj0FhYnaN1JGNZ2TdAwYLi1_dZbw(a)mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > Hi Rogelio > > I'm just another user of graph tool, and I'm not familiar with the function > that you've mentioned, but I can tell you how I do my naming. > > I create a vertex property map for my vertices and add a string value to > each vertex which is going to be their name (the vertex number as integer > transformed into a string). Now if I remove a vertex, or something changes, > the property map will stay with the vertices and I can call them. > If the function you are talking about will generate a new graph, I don't > know how to solve that, but if you make your graph to be simplified to that > graph, you will have the names. > I'm sure there is an easier way, but I will leave that to the experts :) > > Good luck > > Csongor > > On Wed, May 25, 2016 at 11:52 PM, Rogelio Basurto < > rogelio.basurto(a)gmail.com > > wrote: > > > Hello, > > > > I've been using graph tool for about 3 weeks now. I just ran into it > while > > searching for a modularity method for a bipartite network. > > > > I am amazed by graph tool and the algorithms within. But I am having > > truble with a basic question (at least I think it is). > > > > I am reading a bipartite network from a graphml file, then I do some > > filtering and finally I construct the minimize_nested_blockmodel_dl as in > > the example. Then I draw it, just like in the example, and it looks > great. > > I manage to draw it with the node names and they are fine. > > > > Then, I would like to check the names of the nodes in the different > > blocks, by the levels they are arranged from the stochastic nested block > > model. But I do not know how to do that. > > > > I found the function get_bstack() for the NestedBlockState object, but > the > > index in those vertices are from 0 to N, where N is the number of > vertices > > per level (of the model, not from my graph, I think), then how do I > > associate my original vertex index (which has its name) to those graphs > > from the different levels? > > > > In short, I want to write down (terminal or file) the vertices from the > > graph (with its node names) for each level and respective block. I > suppose > > it can be done, because the info is in the draw, but I do not know how. > > > > Thanks in advance! Great job with graph tool, and the stochastic block > > model (which I haven't completely understood, but I will). > > > > Tech info: > > I work with graph-tool 2.16-1 under Arch Linux, with Python 3.5, if that > > matters. > > The bipartite network have 2230 vertices and 246764 edges . > > From the state summary: > > l: 0, N: 2230, B: 174 > > l: 1, N: 174, B: 68 > > l: 2, N: 68, B: 26 > > l: 3, N: 26, B: 9 > > l: 4, N: 9, B: 3 > > l: 5, N: 3, B: 1 > > > > Have a great day! > > ____ > > *Rogelio Basurto Flores* > > > > Laboratorio de Sistemas Complejos > > *?Unidad Profesional Interdisciplinaria en Ingenier?a y * > > *Tecnolog?as Avanzadas,* > > *Instituto Polit?cnico Nacional,* > > *Av. IPN # 2580, Col. Laguna Ticoman,* > > *?Ciudad de ?M???xico, 07340, M???xico* > > *Mobile Phone: 33 1551 3665* > > *E-Mail: rogelio.basurto(a)gmail.com <rogelio.basurto(a)gmail.com>* > > > > _______________________________________________ > > graph-tool mailing list > > graph-tool(a)skewed.de > > https://lists.skewed.de/mailman/listinfo/graph-tool > > > > >

1 0

Extract a neighborhood of a randomly selected node
by gogurt 11 May '16

11 May '16

Hi all, I have a pretty large graph G from which want to do the following: 1) Randomly select a node from G 2) Get the vertices that lie within radius 2 of the node 3) Extract the subgraph induced by those vertices My code for doing this is the following: / randnode = random.randint(0,G.num_vertices()) pred_map = gt.shortest_distance(G, source=G.vertex(randnode), max_dist=2, pred_map=True) pred_tree = gt.predecessor_tree(G, pred_map[1]) # DEBUG #print(pred_tree.num_vertices()) verts = pred_tree.vertices() vmap = G.new_vertex_property('bool') for i in verts: vmap[G.vertex_index[i]] = True / Then using vmap, I plan to do a GraphView on G and get the subgraph. But something is clearly going wrong here. If I uncomment the line under the # DEBUG comment, then I clearly see that pred_tree always has the same number of vertices as the original graph. Am I missing something about how predecessor_tree() works? I expected it to only return a subgraph of the original graph, which should have a lot fewer vertices... -- 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

Re: [graph-tool] graph-tool Digest, Vol 99, Issue 13
by Matyas, Csongor 09 May '16

09 May '16

Hi Tiago and all Thank you very much for adding this functionality to graph-tool, I could use this for sure. The only problem is, that since you've sent this email, I'm trying to recompile the newest version of graph-tool and after lots of trouble I managed to get it compiled and working, (without sparsehash unfortunately) (the bigges problems I faced with not enough memory, but never mind), now I have the working graph-tool 2.16 and stil if I try to call the: planar_position = graph_tool.draw.planar_layout(Graph_of_the_knot, pos=None) function it prints: Traceback (most recent call last): File "./knot_representations.py", line 1947, in <module> Crossings_adjacency_matrix = CrossingsAdjacencyMatrix(Nr_of_crossings, Nr_of_ropes, Starting_points, Rope_path_length, Crossings_chirality, Connections_dict_inv, Connections_dict) File "./knot_representations.py", line 1526, in CrossingsAdjacencyMatrix planar_position = graph_tool.draw.planar_layout(Graph_of_the_knot, pos=None) AttributeError: 'module' object has no attribute 'planar_layout' Am I doing something wrong, or I'm not using the right version? I've downloaded graph-tool 2.16 from the site. I would also like to ask something about the sfdp.layout in the draw tool. Can I set the C parameter, *C* : float (optional, default: 0.2) Relative strength of repulsive forces. separately for some vertices? I assume that I can't, because it's not a property map, but I thought I'll ask. Thx Csongor On Mon, Apr 25, 2016 at 9:30 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: First question - Planarity (Tiago de Paula Peixoto) > 2. Re: First question - Planarity (Alexandre Hannud Abdo) > 3. Re: First question - Planarity (Tiago de Paula Peixoto) > 4. Re: How to see the relations between two groups of blocks in > a bipartite network? (Andrea Briega) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Sun, 24 Apr 2016 21:48:43 +0200 > From: Tiago de Paula Peixoto <tiago(a)skewed.de> > To: graph-tool(a)skewed.de > Subject: Re: [graph-tool] First question - Planarity > Message-ID: <cb99c96b-6dd5-e142-8e14-4efc7f97969b(a)skewed.de> > Content-Type: text/plain; charset="utf-8" > > On 20.04.2016 17:01, Tiago de Paula Peixoto wrote: > > On 20.04.2016 14:20, Matyas, Csongor wrote: > >> I will also post my first question, this was the main reason why I > registered for this mailing list. The description and examples were usually > more than enough for me to use graph_tool, nice job ;) I have a question > though. > >> In the "|graph_tool.topology.||is_planar|(/g/, /embedding=True///)" how > do I use the embedding information to print my graphs planar. Do I have to > do that for myself, or there is a built in function that I didn't find? Do > I have to add the edges following the order that they come using the > embedding somehow? > > > > Here is one way it can be used to draw the graph: > > > > > http://www.boost.org/doc/libs/1_60_0/libs/graph/doc/straight_line_drawing.h… > > > > However, this function is not yet implemented in graph-tool. > > FYI, I have just added this functionality to graph-tool: > > > https://graph-tool.skewed.de/static/doc/dev/draw.html#graph_tool.draw.plana… > > Best, > Tiago > > -- > Tiago de Paula Peixoto <tiago(a)skewed.de> > >

2 1