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

Efficient Bipartite Projection
by Carlos Andrade 17 Sep '15

17 Sep '15

Dear all, I have a bipartite graph, directed and with weightened edges. It is very large, I believe 36k nodes and 52k edges. I am trying to make a projection of it, but I could not find any function or way to do so with graph-tool. Is there any way I am not aware of? If there is no current way, where would you recommend try with such a big graph? I am currently trying to run this on a 8gb RAM 2012 macbook pro 15` (2.2 ghz or something like that). I started of from (1) Gephi plugin ( https://marketplace.gephi.org/plugin/multimode-networks-transformations-2/) which after running for a couple hours almost froze my computer and output no graph (I had to force quit it). My second attempt was (and is) on igraph ( http://igraph.org/python/doc/igraph.Graph-class.html#bipartite_projection ) I came across this post: http://stackoverflow.com/questions/606516/python-graph-library And read about graph-tool and how efficient it is compared to the igraph and networkx (which I was about to try but given up when I saw the time table). Thank you for your attention,

5 8

graph-tool graphml and networkx
by tcb 17 Aug '15

17 Aug '15

Hi, I am trying to read the graphml output of graph-tool's graphml using networkx. https://github.com/networkx/networkx/issues/843 Unfortunately this does not work with any of the vector_* type property maps which graph-tool uses. Have you encountered this issue before? It seems the right thing to do might be to extend your graphml to hold the vector_* attributes as detailed: http://graphml.graphdrawing.org/primer/graphml-primer.html#EXT Is there some reason why it was done the way it is? How do you manage read/writing graphml data to other tools? In the meantime, it might be possible to hack some read support for graph-tool's xml into networkx. To this end, could you please advise how to parse the 'key1' data (should be two floats) <node id="n1"> <data key="key0">6</data> <data key="key1">0x1.5c71d0cb8d943p+3, 0x1.70db7f4083655p+3</data> </node> thanks - -- 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 12

How to increase canvas size?
by Ryan Compton 22 Jun '15

22 Jun '15

I'm having trouble with my vertex text running off the edge of the canvas. For an example see: http://ryancompton.net/assets/darknet-market-basket-analysis/evo_market_lab… I got the impression that "fit_view" with a float would scale things properly but it does not seem to change anything.

2 5

graph_tool.spectral.adjacency() returns the transpose of the adjacency of a directed graph
by Smith, Steven - 1004 - MITLL 31 May '15

31 May '15

The function graph_tool.spectral.adjacency<http://graph-tool.skewed.de/static/doc/spectral.html?highlight=adjacency#gr…> returns transpose of the adjacency matrix of a directed graph that is commonly used. Is this intentional? A misinterpretation of column-major versus row-major on my part? Compare a few standard examples: http://en.wikipedia.org/wiki/Adjacency_matrix#Examples http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture2/lecture2.h… with the output of gt.adjacency(): import graph_tool.all as gt g = gt.Graph() v0 = g.add_vertex() v1 = g.add_vertex() e01 = g.add_edge(v0,v1) A = gt.adjacency(g) A.todense() [e for e in g.edges()] ## -- End pasted text -- Out[2]: [<Edge object with source '0' and target '1' at 0x11fb10d60>] A.todense() Out[3]: matrix([[ 0., 0.], [ 1., 0.]]) A in this case is most commonly defined as [[0, 1], [0, 0]]

2 3

vertex.in_edges() on undirected graphs throws a segmentation fault
by Smith, Steven - 1004 - MITLL 31 May '15

31 May '15

This is python 2.7 and graph-tool 2.2.38_0 Code: > import graph_tool as gt > > g = gt.Graph() > g.set_directed(False) > v0 = g.add_vertex() > v1 = g.add_vertex() > e01 = g.add_edge(v0,v1) > v = g.vertex(0) > [e for e in v.out_edges()] > [<Edge object with source '0' and target '1' at 0x104d110e8>] > [e for e in v.in_edges()] > Segmentation fault: 11

2 4

Accessing property array containing string
by Joel Moberg 29 May '15

29 May '15

I can't figure out how I am doing this wrong: ``` from graph_tool.all import * graph = collection.data['polbooks'] a = graph.vp['value'] print a a.get_2d_array([0]) ``` I get this trace: ``` <PropertyMap object with key type 'Vertex' and value type 'string', for Graph 0x7fd6f9440f90, at 0x7fd6f37322d0> --------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-122-19dc354c8941> in <module>() 2 a = graph.vp['value'] 3 print a ----> 4 a.get_2d_array([0]) /home/joelmo/.nix-profile/lib/python2.7/site-packages/graph_tool/__init__.pyc in get_2d_array(self, pos) 663 for v in iters: 664 for i in range(len(p)): --> 665 a[i][int(v)] = p[i][v] 666 if len(a) == 1: 667 a = a[0] IndexError: list assignment index out of range ```

2 1

High performance astar search
by Jeremy Herbert 27 May '15

27 May '15

Hi all, First, thanks very much for creating this library. It has helped me a great deal to fiddle with graph algorithms in the comfort of my favourite language! I'm currently having trouble performing an astar search on an explicit undirected graph. The graph I have is not crazy large (50,000 vertices with ~150,000 edges), but I need to perform a large number of astar searches (on the order of the number of vertices). As the python visitor class instance is required for the astar to terminate, it seems I'm having quite poor performance as a result of many calls back to python: ncalls tottime percall cumtime percall filename:lineno(function) 88138526 116.708 0.000 153.115 0.000 __init__.py:113(wrapped_visitor_member) 4202 110.596 0.026 302.442 0.072 __init__.py:1195(astar_search) 88138526 34.008 0.000 38.130 0.000 __init__.py:107(__getattr__) 264384698 30.718 0.000 30.718 0.000 {method 'update' of 'dict' objects} 88090728 5.512 0.000 5.512 0.000 __init__.py:1132(initialize_vertex) 88138690 4.122 0.000 4.122 0.000 {built-in method callable} 33616 0.146 0.000 0.152 0.000 __init__.py:1415(vertex) In this case, the only function in my visitor class that is defined is: def edge_relaxed(self, e): if e.target() == self.end: raise StopSearch() I've also tried looking at doing the search implicitly, but I can't for the life of me get it to work. I tried to copy the original euclidean astar example from the documentation and convert it to implicit, but it doesn't seem to work. Could anyone tell me what I'm doing wrong here? I'm guessing that some of the function arguments listed as optional are not so ;) from graph_tool.search import StopSearch, AStarVisitor, astar_search import graph_tool.generation as gt from numpy.random import random from math import sqrt class VisitorExample(AStarVisitor): def __init__(self, touched_v, touched_e, target): self.touched_v = touched_v self.touched_e = touched_e self.target = target def discover_vertex(self, u): self.touched_v[u] = True def examine_edge(self, e): self.touched_e[e] = True def edge_relaxed(self, e): if e.target() == self.target: raise StopSearch() def h(v, target, pos): return sqrt(sum((pos[v].a - pos[target].a) ** 2)) points = random((500, 2)) * 4 points[0] = [-0.01, 0.01] points[1] = [4.01, 4.01] g, pos = gt.triangulation(points, type="delaunay") weight = g.new_edge_property("double") # Edge weights corresponding to # Euclidean distances for e in g.edges(): weight[e] = sqrt(sum((pos[e.source()].a - pos[e.target()].a) ** 2)) touch_v = g.new_vertex_property("bool") touch_e = g.new_edge_property("bool") target = g.vertex(1) dist, pred = astar_search(g, g.vertex(0), weight, VisitorExample(touch_v, touch_e, target), implicit=True, heuristic=lambda v: h(v, target, pos)) print(pred.a) # output is: [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] -- I'd rather not implement my solution in C++, because BGL looks complex to say the least! Thanks, Jeremy

2 1

bfs_search performance on big graphs
by Ilkka Rajala 15 May '15

15 May '15

Hi, I stumbled on a bit of a performance bottleneck when trying bfs_search on a big graph. The problem is with initialize_vertex function, which is called for every vertex of the graph. Even if the function itself is empty, there's a bunch of work that's done for each vertex in VisitorWrapper.__getattr__, before that empty function is even called. Just doing: g = Graph() g.add_vertex(10000000) %timeit bfs_search(g, 0, BFSVisitor()) 1 loops, best of 3: 37.6 s per loop Now I have a graph with 350M vertices and some 550M edges. It takes 21 minutes of initialize_vertex calls that I don't need, before doing a few millisecond search :-/ Seems like my only option is to compile a custom version, with initialize_vertex disabled from all search functions, or implement BFS myself in python. Hopefully I'm doing something terribly wrong? What I'm trying to do, is find all vertices reachable from a given root vertex. Graph is undirected and not fully connected. I thought BFS would be a convenient way to do that, but maybe there's a better way to get that information? I'm not very familiar with graphs :-) - Ilkka

2 2

Degree Centrality
by dushyanthbn 14 May '15

14 May '15

Is degree centrality available in graph tool? Thanks -- 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

Updating Graph Widget
by srichmo1 07 May '15

07 May '15

Hello, I'm trying to create a Widget containing a graph using GraphWidget to use in a larger application that will be able to show subgraphs of the larger, but I'm having some trouble finding any info on how to go about it. I've dabbled a little in Graph-Tool before, but I'm still noob with it all. When I create the widget I first start with loading the graph from a dot file. The problem starts with pos. I'm loading directed acyclic graphs (ideally displayed with the edges generally pointing downward so the graph ends at the bottom), but I don't see an easy way to pull coordinates for them besides using graphviz_draw(). Is that the only way? And when I do have the vertices I want (assuming I just use find_vector_range()) can I pass a filtered graph to some redraw function along with the old pos or do I need to call graphviz_draw() again for updated pos? I'm seeing a draw(da, cr) function under GraphWidget that can be used to redraw the widget, but what are da and cr exactly? Regards, Steve -- 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.

1 0