graph-tool November 2011

graph-tool@skewed.de

6 participants
6 discussions

Segmentation fault using shortest_distance
by Juan Manuel Tirado 20 Mar '16

20 Mar '16

Hi Tiago, I am trying to calculate the shortest distances of a graph after applying a filter. I have a code that looks like this: g=gt.load_graph("myGraph.xml",format="xml") #for later use distances = gt.shortest_distance(g) #extract the components of the graph comp = g.label_components(g) #This splits the graph in several components #I want to calculate the shortest distances #for the component 2 for example filtering = g.new_vertex_property("boolean") for v in g.vertices(): if comp[v]==2: filtering[v]=True else: filtering[v]=False #set the vertex filter g.set_vertex_filter(filtering) distances_comp=gt.shortest_distance(g) The last line of code rises a segmentation fault. I have plotted the graph with the filtered graph and its correct, also I can calculate the local_clustering_coefficient without problems. Am I doing something wrong? Is there any other way to filter the graph and calculate the shortest distances? Is this a bug? Thanks so much, Juan

5 9

Parallel Processing
by Derek Ditch 21 Nov '13

21 Nov '13

I want to use graph-tool using the multiprocessing library in Python 2.6. I keep running into issues though with trying to share a full graph object. I can store the graph in a multiprocessing.Namespace, but it doesn't keep the dicts of properties. Example: def initNS( ns ): _g = Graph( directed = False) ns.graph = _g ns.edge_properties = { 'genres': _g.new_edge_property("vector<string>"), 'movieid': _g.new_edge_property("int"), } ns.vertex_properties = { 'personid': _g.new_vertex_property("int32_t") } """ Build property maps for edges and vertices to hold our data The graph vertices represent actors whereas movies represent edges """ # Edges _g.edge_properties["genres"] = ns.edge_properties['genres'] _g.edge_properties["movieid"] = ns.edge_properties['movieid'] # Vertices _g.vertex_properties["personid"] = ns.vertex_properties['personid'] ns.graph = _g ########## This initializes 'ns', which is a multiprocessing.Namespace. The problem is that for example, ns.edge_properties[ * ] tells me that the type isn't pickle-able. I tried to just skip that and use the _g.edge_properties to access it, but those dicts aren't carried over to the different process in the pool. Presumably b/c they aren't pickle-able. Any thoughts about how to fix this? (For those interested, I'm attempting to use the IMDbPy library to do some graph analysis on the relationships among actors and movies. Each process has it's own db connection and trying to populate the graph with actor and movie information in parallel since it's a pretty large and dense graph. Somewhere in the neighborhood of 250,000+ vertices for just a depth of three relationships) Thanks, -- Derek

3 7

boost errors building on Mac OSX
by jesse berwald 29 Nov '11

29 Nov '11

Hi all, I've been trying to build graph-tool on my Mac (10.7.2) for the past few days. The issues occur with graph-tool-2.2.15 (though I've also had issues with the lastest code from github). At this point I have reached a bit of a dead end. Looking at what I posted below, does anyone have any suggestions?? Many thanks!! Jesse Here is my configure command: ./configure --enable-openmp --with-boost-python=boost_python_mt --with-numpy=/Library/Frameworks/Python.framework/Versions/Current/lib/python2.7/site-packages/numpy --with-scipy=/Library/Frameworks/Python.framework/Versions/Current/lib/python2.7/site-packages/scipy LDFLAGS=-L/opt/local/lib CXXFLAGS="-I/opt/local/include" The additional args stem from the fact that I'm using the Enthought python distribution and macports, both of which put stuff in non-standard places it seems. The graph-tool build error is related to boost, which I installed using macports (version 1.47) . So I doubt my problems have to do with Enthought. Now, here's the compiler/make output: jberwald@hyperion:~/src/graph-tool-2.2.15$ make make all-recursive Making all in src Making all in graph Making all in centrality CXX graph_betweenness.lo CXX graph_centrality_bind.lo CXX graph_eigentrust.lo CXX graph_eigenvector.lo CXX graph_pagerank.lo CXX graph_trust_transitivity.lo CXXLD libgraph_tool_centrality.la Making all in clustering CXX graph_clustering.lo CXX graph_extended_clustering.lo CXX graph_motifs.lo graph_motifs.hh: In member function 'void graph_tool::get_all_motifs::operator()(Graph&, size_t, boost::any&, std::vector<long unsigned int, std::allocator<long unsigned int> >&, Sampler, double, bool, bool, graph_tool::rng_t&) const [with Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::property<boost::edge_index_t, long unsigned int, boost::no_property>, boost::no_property, boost::listS>, Sampler = graph_tool::sample_all]': graph_motifs.hh:415: internal compiler error: in lower_stmt, at gimple-low.c:319 Please submit a full bug report, with preprocessed source if appropriate. See <URL:http://developer.apple.com/bugreporter> for instructions. make[4]: *** [graph_motifs.lo] Error 1 make[3]: *** [all-recursive] Error 1 make[2]: *** [all-recursive] Error 1 make[1]: *** [all-recursive] Error 1 make: *** [all] Error 2 Also, I attempted to install from macports originally. But macports tells me the following: Error: Cannot install py27-graph-tool for the arch(s) 'i386 x86_64' because > Error: its dependency py27-scipy does not build for the required > arch(s) by default > Error: and does not have a universal variant. > Error: Unable to execute port: architecture mismatch -- 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 8

Re: [graph-tool] graph-tool Digest, Vol 46, Issue 4
by Matthias Ekman 29 Nov '11

29 Nov '11

>> I was wondering if the max_cardinality_matching functions is defined >> for /directed/ graphs as suggested by the documentation example [0]? I >> am asking, because the linked boost reference [1] describes the >> matching only for /undirected/ graphs. > The algorithm is only defined for undirected graphs, and if one passes a > directed graph, as in the documentation, the direction of the edges is > ignored. alright, thanks for clearing that up! > Note that maximum matching on _directed_ graphs, as defined in your > reference [2], can be mapped to the _undirected_ problem using an > undirected bipartite graph [...] Indeed, but as far as I know graph_tool doesn't offer any bipartite representations, right? Sorry, may be I am missing something trivial, both graph_tool and bipartite graphs are somehow new to me, ... or is it simple as creating a new adjacency matrix A', where an example graph A (n=3 vertices): 0 1 1 0 1 0 0 0 1 becomes: A' with n' = n*2 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 vertices A'_i and A'_i+n represent the same vertex, but appear twice, once as starting- and once as ending vertex A' could be than used as input for the maximum matching algorithm? Best, Matthias

2 2

max_cardinality_matching for directed graphs and "controllability"
by Matthias Ekman 23 Nov '11

23 Nov '11

Hi, I was wondering if the max_cardinality_matching functions is defined for * directed* graphs as suggested by the documentation example [0]? I am asking, because the linked boost reference [1] describes the matching only for *undirected* graphs. I am trying to get the "driver nodes" of a network as described by [2]. The authors showed, that the amount of "driver nodes needed to maintain full control of the network is determined by the ‘maximum matching’ in the network". May be even anyone has seen an implementation of this approach somewhere? [0] http://projects.skewed.de/graph-tool/doc/flow.html#graph_tool.flow.max_card… [1] http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/maximum_matching.html [2] Liu, Y.-Y., Slotine, J.-J., & Barabási, A.-L. (2011). Controllability of complex networks. *Nature*, *473*(7346), 167–173. doi:10.1038/nature10011 Thanks, Matthias

2 1

Help calculating best path
by akn 04 Nov '11

04 Nov '11

Hi I am trying to graph-tool solve specific path finding problems. I have been using NetworkX in past but found it too slow and read good thing about graph-tool's speed. Basically I have 2 million + vertices and I want to find best path between 2 points (considering their weight and travel time i.e. cost). Now Im really interested in astar I can't seem to get it work for some reason. So in my scenario Im trying to do this: from graph_tool.all import * g = Graph() v0 = g.add_vertex() v1 = g.add_vertex() v2 = g.add_vertex() v3 = g.add_vertex() v4 = g.add_vertex() weight = g.new_edge_property("double") e_1_2 = g.add_edge(v1,v2) weight[e_1_2] = 1000 e_1_3 = g.add_edge(v1,v3) weight[e_1_3] = 100 e_3_4 = g.add_edge(v3,v4) weight[e_3_4] = 200 e_4_2 = g.add_edge(v4,v2) weight[e_4_2] = 40 class VisitorExample(graph_tool.search.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 gt.StopSearch() touch_v = g.new_vertex_property("bool") touch_e = g.new_edge_property("bool") target = v2 gt = graph_tool.search time = g.new_vertex_property("int") pred = g.new_vertex_property("int") dist, pred = gt.astar_search(g, v1, weight, VisitorExample(touch_v, touch_e, target), heuristic=lambda v: 1) Now I would "astar" to consider weights and choose the best path based on weight. For example weight for edge (1 & 2) = 1000, so travel from 1 -> 2 I would like to get a path 1 -> 3 -> 4 > 2 because combined weight of this is still less than that of 1 -> 2. But when I get the results it only gives edge 1 & 2 and wouldn't consider the above path. Could you also shed some light on setting up heuristics and costing functions for the above scenario. Thank you. -- 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

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool November 2011