graph-tool March 2016

graph-tool@skewed.de

18 participants
31 discussions

How to control the orientation of the graph topology
by Xun Xiao 26 Feb '22

26 Feb '22

Hi Tiago, sometimes, when delete the graph and create a new one, then plot it, the plotted graph is shown upside down (in terms of the node text). So how could we control the orientation of the graph? Or which parameter we should use to always make node text shown in a correct orientation. Thanks a lot. -- 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

Upside down labels
by charlie 26 Feb '22

26 Feb '22

Hi, I'm suffering from the same issue mentioned in this post: https://git.skewed.de/count0/graph-tool/issues/174 Namely, I'm trying to draw a graph that includes a lot of self-looping edges, and my labels are being printed upside down. If I remove the self-loops the labels are shown the right way up. Is there a fix for it? Thanks, Charlie -- 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

What formula is used for std in vertex_average and edge_average?
by VaSa 16 Jul '20

16 Jul '20

I am curious what is being used to calculate the standard deviation of the average in gt.vertex_average and gt.edge_average >>> t2=gt.Graph() >>> t2.add_vertex(2) >>> t2.add_edge(t2.vertex(0), t2.vertex(1)) >>> gt.vertex_average(t2, "in") (0.5, 0.35355339059327373) Now, shouldn't std be σ(n)=sqrt(((0-0.5)^2+(1-0.5)^2)/2)=0.5 ? also q(n-1)=sqrt((0.5^2+0.5^2)/(2-1))~=0.70710 0.3535 is sqrt(2)/4 which happens to be σ(n-1)/2, so it seems there is some relation to that. A little bigger graph. >>> t3=gt.Graph() >>> t3.add_vertex(5) >>> t3.add_edge(t3.vertex(0), t3.vertex(1)) >>> gt.vertex_average(t3, "in") (0.2, 0.17888543819998318) Now, we should have 0,1,0,0,0 series for vertex incoming degree. So Windows calc gives σ(n)=0.4 and σ(n-1)~=0.44721, so where does 0.1788854 come from ? Reason, I am asking because, I have a large graph, where the average looks quite alright but the std makes no sense, as going by the histogram, degree values are quite a bit more distributed than the std would indicate. -- 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

Problem with add_edge_list(eprop=x)
by JHickey 04 Oct '18

04 Oct '18

I'd like to use the "add_edge_list" function to add edges to my graph, and simultaneously assign a value for an edge property map for each of the added edges. When I try the following example (with no edge property map information) works fine: elist1 = np.array([[0,1], [1, 2]]) #edge list with no value for edge property map data (only the source and target for the edges) g = gt.Graph() my_eprop = g.new_edge_property('bool') g.add_edge_list(elist) But with the following example, I get the error below: elist2 = np.array([[0,1, 1], [1, 2, 0]]) #edge list with edge property map value in 3rd column g = gt.Graph() my_eprop = g.new_edge_property('bool') g.add_edge_list(elist2, eprops=my_eprop) Error: --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-48-6a949ea52c9b> in <module>() ----> 1 g.add_edge_list(elist2, eprops=my_eprop) /usr/lib/python2.7/dist-packages/graph_tool/__init__.pyc in add_edge_list(self, edge_list, hashed, string_vals, eprops) 1969 eprops = () 1970 else: -> 1971 convert = [_converter(x.value_type()) for x in eprops] 1972 eprops = [_prop("e", self, x) for x in eprops] 1973 if not isinstance(edge_list, numpy.ndarray): /usr/lib/python2.7/dist-packages/graph_tool/__init__.pyc in __getitem__(self, k) 534 kt = "Graph" 535 raise ValueError("invalid key '%s' of type '%s', wanted type: %s" --> 536 % (str(k), str(type(k)), kt) ) 537 538 def __setitem__(self, k, v): ValueError: invalid key '0' of type '<type 'int'>', wanted type: Edge --------------------------------------------------------------------------- Please help! -- 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.

4 9

Debian package and boost at compile-time
by Alcolo Alcolo 12 Mar '17

12 Mar '17

Hi, I have installed the package python3-graph-tool and when I use graph_tool.search.dfs_iterator I got the error: Traceback (most recent call last): File "/home/steph/bin/superGraph.py", line 160, in <module> gg.create_revdep(gg.getPackage('umda')) File "/home/steph/bin/superGraph.py", line 88, in create_revdep for e in bfs_iterator(self.graph, node): File "/usr/lib/python3/dist-packages/graph_tool/search/__init__.py", line 345, in bfs_iterator return libgraph_tool_search.bfs_search_generator(g._Graph__graph, int(source)) RuntimeError: This functionality is not available because boost::coroutine was not found at compile-time Ubuntu: 14.04 python3-graph-tool version 2.12-1 (from deb http://downloads.skewed.de/apt/trusty trusty universe) There is a way to install python3-graph-tool binaries compiled with boost ? Of course I can compile myself graph-tool, but it is not my goal.

6 26

apt-get fail to download index files
by Andy Maloney 10 Mar '17

10 Mar '17

I am trying to install graph-tool on a Trusty Ubuntu virtualbox being hosted on a Mac. I've added the requisite lines deb http://downloads.skewed.de/apt/trusty trusty main deb-src http://downloads.skewed.de/apt/trusty trusty main to my /etc/apt/sources.list, but when I run a sudo apt-get update, I get the following errors: W: Failed to fetch http://downloads.skewed.de/apt/trusty/dists/trusty/Release Unable to find expected entry 'main/source/Sources' in Release file (Wrong sources.list entry or malformed file) E: Some index files failed to download. They have been ignored, or old ones used instead. I have the main, universe, and multiverse repositories available. If any one has come across this problem before, please let me know how to fix it. Thanks. Andy_

4 4

Images in vertices
by Nils Hachmeister 15 Nov '16

15 Nov '16

Hello, I'm using graph_tool in a scenario, in which the meaning of a vertex cannot be easily be explained by a label or a text. To get a meaningful graph I would need to display a image inside the vertices. Has anyone an idea, how could this be achieved? Thanks Soraltan

3 3

Building graph-tool on CentOS 7
by Smith, Steven - 1004 - MITLL 28 Oct '16

28 Oct '16

The graph-tool make command on CentOS 7 fails at this point: $ cd graph-tool-2.2.35 $ ./configure --with-sparsehash-prefix=google $ make make all-recursive make[1]: Entering directory `/home/user/Downloads/graph-tool-2.2.35' Making all in src … make[4]: Entering directory `/home/user/Downloads/graph-tool-2.2.35/src/graph/topology' CXX graph_subgraph_isomorphism.lo graph_subgraph_isomorphism.cc: In instantiation of 'void get_subgraphs::operator()(const Graph1&, const Graph2*, VertexLabel, boost::any, EdgeLabel, boost::any, std::vector<VertexMap>&, size_t, bool, bool) const [with Graph1 = boost::adj_list<long unsigned int>; Graph2 = boost::adj_list<long unsigned int>; VertexLabel = boost::unchecked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >; EdgeLabel = boost::unchecked_vector_property_map<int, boost::adj_edge_index_property_map<long unsigned int> >; VertexMap = boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >; size_t = long unsigned int]': /usr/include/c++/4.8.2/functional:1305:50: required from '_Result std::_Bind<_Functor(_Bound_args ...)>::__call_c(std::tuple<_Args2 ...>&&, std::_Index_tuple<_Indexes ...>) const [with _Result = void; _Args = {boost::adj_list<long unsigned int>&, boost::adj_list<long unsigned int>*&, boost::unchecked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >&, boost::unchecked_vector_property_map<int, boost::adj_edge_index_property_map<long unsigned int> >&}; long unsigned int ..._Indexes = {0ul, 1ul, 2ul, 3ul, 4ul, 5ul, 6ul, 7ul, 8ul, 9ul}; _Functor = get_subgraphs; _Bound_args = {std::_Placeholder<1>, std::_Placeholder<2>, std::_Placeholder<3>, boost::any, std::_Placeholder<4>, boost::any, std::reference_wrapper<std::vector<boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> >, std::allocator<boost::checked_vector_property_map<int, boost::typed_identity_property_map<long unsigned int> > > > >, long unsigned int, bool, bool}]’ … _descriptor>, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_:: na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_:: na, mpl_::na, mpl_::na, mpl_::na>}]' graph_subgraph_isomorphism.cc:178:56: required from here graph_subgraph_isomorphism.cc:108:114: error: 'vf2_subgraph_mono' was not declared in this scope vertices_equivalent(make_property_map_equivalent(vertex_label1, vertex_label2))); ^ … , graph_tool::ConstantPropertyMap<bool, boost::adj_list<long unsigned int>::edge_descriptor>, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na>}]' graph_subgraph_isomorphism.cc:178:56: required from here graph_subgraph_isomorphism.cc:108:114: error: 'vf2_subgraph_mono' was not declared in this scope Any help fixing this would be greatly appreciated. I’m building graph-tool from the latest source, graph-tool-2.2.35.tar.bz2. CGAL is built successfully from source (there aren’t any cgal-devel packages yet in the .el7 repos), and because the .el 7 sparsehash-devel package puts its libraries in /usr/include/google, the specific ./configure command for CentOS 7 above is necessary. This runs successfully, and every compile up to graph_subgraph_isomorphism is successful.

3 13

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

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool March 2016