November 2014 - graph-tool - archives.skewed.de

Property maps: Type name: Safe to use "bool" type to store values between 1 and 100?
by Didier Guillevic 02 Dec '14

02 Dec '14

Hi, I want to add a ‘weight’ edge attribute with weights ranging from 1 to 100 (values that fit in an unsigned char). In order to save some space, I would like to store those weights in an uint8_t instead of int16_t. The uint8_t is accessible through the ‘bool’ type name for the Property Maps. - I checked that serializing and de-serializing ‘bool’ type names with values in the range [1-100] works fine. - I also checked that running PageRank using the ‘weight’ edge property gives the same result whether the weights ([1-100]) are stored as type ‘bool’ or type ‘int16_t’. My question is it safe to assume that it will always work. Do some of the algorithms check the type name of the property and seeing ‘bool’, those algorithms could decide to use true/false values rather than an integer in range [0-255]. Thanks for any feedback, Didier

2 2

Fixing position of root vertex
by luistavares 25 Nov '14

25 Nov '14

Hi, I'm using the code below to fix the position of a root vertex. I'm developing an application and I wanna make sure that the root vertex is always located in the same place. g = Graph() v_pin = g.new_vertex_property("bool") v = g.add_vertex() v_pin[v] = True #root vertex ... pos = sfdp_layout(g, pin=v_pin) graph_draw(g, ...) I suppose it's working, but how I can confirm which one is the root vertex in my result? <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> -- 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 21

maxflow - Proportionality constraint for multiple sources
by LearnedByError 21 Nov '14

21 Nov '14

I am investigating using maxflow to calculate the max flow from multiple sources based upon network constraints. Is there a way to insure that all nodes upstream of a constraint are reduced proportionately instead of having the constraint being honored by reducing the flow on just the minimum number of nodes needed to meet the constraint value. Consider the following directed graph: <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> When I calculate the maxflow with the attached program gt-test001.py <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com…> , I receive the following results (minus the super nodes and reformatted for clarity). max flow = 39.0 E6 = 8.0 E7 = 8.0 E8 = 11.0 E9 = 12.0 E10 = 16.0 E11 = 21.0 E12 = 39.0 However, the treatment that I am looking for results in: max flow = 39.0 E6 = 7.53 E7 = 8.47 E8 = 11.0 E9 = 12.0 E10 = 16.0 E11 = 21.0 E12 = 39.0 In this case V1 and V2 can deliver 17 but is restricted to 16 by E10 on the outbound side of V3. I want to reduce V1 & V2 proportionately to their capacity such that E6 = (Capacity of E10) * (Capacity of E6)/((Capacity of E6) + (Capacity of E7)) E6 = 16 * (8/(8+9)) = 7.53 And similarly: E7 = (Capacity of E10) * (Capacity of E7)/((Capacity of E6) + (Capacity of E7)) E7 = 16 * (9/(8+9)) = 8.47 I can implement this using a Linear Programming solver like glpk by adding explicit constraints that enforce the proportionality between E6 & E7. How should I model this when using a graph model? Thanks in advance for your help and your tolerance of my ignorance :) lbe -- 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

release?
by lmz 21 Nov '14

21 Nov '14

Hi again -- Just thought i'd request again a release graph_tool, in the most polite possible way. I really appreciate the work you put into the package and I'd love to be able to use the code with the bug fix from https://git.skewed.de/count0/graph-tool/issues/188 on our amazon servers. Alternatively, are there instructions one how to package it up myself? I could do that if that's faster... Thanks so much, -Lisa -- 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

Graph products in graph-tool: does implementation exist?
by Rasmus K. Rendsvig 19 Nov '14

19 Nov '14

Dear graph-tool mailing list, Do either of you know of an implementation of standard graph products, using graph-tool? I'm referring to graph products like Cartesian product, lexicographic product, etc. I have searched the documentation and mailing list archives, but have come up empty handed. Kind regards, Rasmus

3 3

interactive_window not defined
by charlie 19 Nov '14

19 Nov '14

Hi, I'm trying to plot a graph in an interactive window using the graph_draw command with no output, and I get an error that says "interactive_window is not defined". The same thing happens when I run from a notebook with the kwarg inline=False. I assume that this is an installation issue? I installed on a Mac via Homebrew, roughly following the recommended tutorial, and I'm pretty sure I have all the listed dependencies – boost, boost-python, cairo, cairomm, py2cairo, graphviz and many others are all installed via Homebrew. This problem is independent of MatPlotLib; in any case the backend is set to MacOSX in my matplotlibrc file. Please can you help me narrow it down? The error trace is below. Thanks! Charlie --------------------------------------------------------------------------- NameError Traceback (most recent call last) <ipython-input-18-450166b22c69> in <module>() ----> 1 gt.graph_draw(g) #, inline=False) /usr/local/lib/python2.7/site-packages/graph_tool/draw/cairo_draw.pyc in graph_draw(g, pos, vprops, eprops, vorder, eorder, nodesfirst, output_size, fit_view, inline, output, fmt, **kwargs) 875 eprops[p] = _convert(edge_attrs.__dict__[p], val, 876 kwargs.get("ecmap", default_cm)) --> 877 return interactive_window(g, pos, vprops, eprops, vorder, eorder, 878 nodesfirst, **kwargs) 879 else: NameError: global name 'interactive_window' is not defined -- 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 12

Color normalization with increasing number of used colors
by Leonardo Chiquitto 17 Nov '14

17 Nov '14

Hello, I'm using graph-tool to create demonstrations of how a few graph coloring algorithms work. To do so, I'm creating snapshot images at each step of the coloring process. While pinning the vertices' positions is trivial, I couldn't find a nice solution to "pin the colors": every time a new color is used, the normalization process picks new colors for all vertices, giving the false impression that the algorithm has changed them. The code sample below probably explains the problem better: it creates files ex-vcolor-{0,1,2}.png showing that the vertex color changes: g = Graph(directed=False) v_color = g.new_vertex_property("int") g.add_vertex(3) g.add_edge_list([(0,1),(1,2),(2,0)]) pos = sfdp_layout(g) for v in g.vertices(): v_color[v] = int(v) graph_draw(g, vertex_fill_color=v_color, pos=pos, output="ex-vcolor-" + str(int(v)) + ".png") What I would like to have is: use the normalization process only once for n colors (to pick "spaced" colors) and then stick to them even when just a few are used in the graph being draw. Is this possible? Any ideas? Thanks, Leonardo PS. And thanks a lot for graph-tool! It is a real time saver :-)

2 2

Using a EdgePropertyMap('object') as weights
by ambasta 17 Nov '14

17 Nov '14

Hi, I have two problems class Weights: ... g = Graph(directed=True) weights = g.new_edge_property('object') vertex_one = g.add_vertex() vertex_two = g.add_vertex() edge = g.add_edge(vertex_one, vertex_two) weights[edge] = Weights(1) g.shortest_path(vertex_one, vertex_two, weights) This raises ValueError: property map 'dist_map' is not of scalar type. Is there a function I can implement in Weights for it to return a scalar value to be used during calculation of shortest path. Secondly, consider a directed graph where the edge weight is a function of cost at edge's origin vertex, i.e. the weight class is defined as: class Weights: .... def get_weight(current_cost): return self.cost * current_cost Hence during calculation of shortest_path/distance, is it possible to pass the weight at the traversed/visited edge to get the cost of the edge. -- 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 12

Size for edges and properties vweight and eweight
by luistavares 17 Nov '14

17 Nov '14

Please, I would like to know if there is any way to set a visual size for each edge in the graph. Also like to know what is the role of the vweight and eweight properties. I didn't find this information in the documentation. Thanks in advance. -- 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 5

graph_draw
by charlie 17 Nov '14

17 Nov '14

Hi, I've just installed graph_tool on my Mac via Homebrew, more-or-less according to the walkthrough recommended on the graph-tool installation page (https://gist.github.com/openp2pdesign/8864593) When I try to use the graph_draw function I get an error. Please help! Thanks. Here is my command and the error traceback: graph_draw(g, vertex_text=node_map.keys(), inline=True) --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-33-2279357ad581> in <module>() ----> 1 graph_draw(g, vertex_text=node_map.keys(), inline=True) /usr/local/lib/python2.7/site-packages/graph_tool/draw/cairo_draw.pyc in graph_draw(g, pos, vprops, eprops, vorder, eorder, nodesfirst, output_size, fit_view, inline, output, fmt, **kwargs) 928 929 cairo_draw(g, pos, cr, vprops, eprops, vorder, eorder, --> 930 nodesfirst, **kwargs) 931 932 if fmt == "png": /usr/local/lib/python2.7/site-packages/graph_tool/draw/cairo_draw.pyc in cairo_draw(g, pos, cr, vprops, eprops, vorder, eorder, nodesfirst, vcmap, ecmap, loop_angle, parallel_distance, fit_view, **kwargs) 512 libgraph_tool_draw.cairo_draw(g._Graph__graph, _prop("v", g, pos), 513 _prop("v", g, vorder), _prop("e", g, eorder), --> 514 nodesfirst, vattrs, eattrs, vdefs, edefs, cr) 515 cr.restore() 516 TypeError: No registered converter was able to produce a C++ rvalue of type std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > from this Python object of type list -- 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