April 2012 - graph-tool - archives.skewed.de

graph-tool can't find Graphviz renderer
by Mikhail Spivakov 07 Apr '16

07 Apr '16

Hello! I've got graphviz installed with python and python27 bindings. However, when I do: graph_draw(ug, vprops={"label": ug.vertex_index}, output="two-nodes.pdf", layout="fdp") I get the following error: graph G { graph [outputorder=edgesfirst, mode=major, overlap=true, ratio=fill, size="5.905512,5.905512", start=3019255687130444316]; node [label="\N", shape=circle, width="0.105", height="0.105", style=filled, color="#2e3436", fillcolor="#a40000"]; edge [arrowsize="0.3", color="#2e3436", penwidth="1.0"]; graph [bb="0,0,425,425"]; 0 [label=0, width="0.47", height="0.47", pos="330,101"]; 1 [label=1, width="0.47", height="0.47", pos="93,324"]; 0 -- 1 [pos="318,113 277,152 147,274 106,312"]; } Error: renderer for pdf is unavailable Out[8]: <PropertyMap object with key type 'Vertex' and value type 'vector<double>', for Graph 0x5ff3f90, at 0x6001290> At the same time, if I save the above dot expression as test1.dot and run the following command from the command line: $ dot -Tpng test1.dot -o graph1.png I get a beautiful graph1.png. Graphviz is installed in a non-standard location as I don't have admin rights. However, the graphviz folder is in LD_LIBRARY_PATH and gv.py is in PYTHONPATH. Would very much appreciate your advice on what else graph-tool might need to find the libraries and/or how to test it better. Many thanks, Mikhail

3 5

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

A* search extension
by Guillaume Lemaître 25 Apr '12

25 Apr '12

Hi Tiago, In my opinion, the astar_search function contract could be extended to accept a set of source vertices instead of a single one, without any loss of generality. In my particular need, I search the best path reaching a goal, considering various start points. The trivial way to do that is: for each eligible start point: run astar_search with this start point as 'source' memorize best path if better than ever But, the astar_search algorithm, particularly when associated to a AStarVisitor that build the graph locally to the examined vertices, tends to limit the combinatorial explosion of searching. So that iterating over eligible start points is necessarily sub-optimal. So, currently, I introduce a pseudo-vertex as the source point, which links to all my real eligible source points for no additional cost, and benefit from the automatic scope restriction from astar_search which may directly select the best start point by itself. Another way to do that (and simplify user code) is to extend the 'source' parameter notion from a single vertex to a set of vertices (in order to initialize the open vertices list). What do you think? Regards, Guillaume -- Si les dauphins étaient si malins, ils ne vivraient pas dans des igloos.

2 2

Re: [graph-tool] Community detection: how do 'ghost' edges appear?
by Mikhail Spivakov 17 Apr '12

17 Apr '12

Hi Tiago, Thanks for your quick reply! You were right - the algorithm just didn't converge to anything meaningful: http://www.ebi.ac.uk/~spivakov/testX/full_graph2.png >This is a hard problem to solve in general. It is usually the case that >you should have some insight on the total number of communities, and >AFAIK there is no known reliable method which will give you this >information easily. If your networks are not too large, you can try >increasing n_spins values, and stop if the modularity no longer changes >appreciably. Thanks for your advice! My networks are large, so I can't really afford multiple iterations... I have so far also tried the MOSES tool that is quite fast, but the downside (for me) is that it produces overlapping communities and that the granularity is too small for my liking... Cheers, Mikhail

1 0

Community detection: how do 'ghost' edges appear?
by Mikhail Spivakov 17 Apr '12

17 Apr '12

Hi Tiago and everyone, I'm trying the community detection algorithm following the example from the docs. Brifely, with a graph g, I'm running the following: # Plot the full graph graph_draw(g, size=(15,15), output=output_folder+"/full_graph.png") # Detect communities spins = community_structure(g, n_iter=1000, n_spins=N) ### note the N parameter ng = condensation_graph(g, spins) size = ng[0].new_vertex_property("double") size.a = log(ng[1].a+1) # Plot the community graph graph_draw(ng[0], vsize=size, vcolor=size, splines=True, eprops={"len":20, "penwidth":10}, vprops={"penwidth":10}, output=output_folder+"/community_graph.png", size=(10,10)) I notice that when n_spins is small (say, n_spins=6), the resulting community graph shows links that do not appear on the full graph. See, for example, this pair of plots: http://www.ebi.ac.uk/~spivakov/testX/full_graph.png http://www.ebi.ac.uk/~spivakov/testX/community_graph.png I'm a little confused as to how this is possible - am I right that with this algorithm communities are non-overlapping? With larger n_spins (such as n_spins=50), the ghost link disappears, but lots of very small communities appear that segment the data too much: http://www.ebi.ac.uk/~spivakov/testX/community_graph50.png More generally, my problem is that I'd like to use this algorithm in a tool that would need to have a good enough guess of n_spins without using a trial-and-error approach. It doesn't need to be the best possible community detection ever, though. So I would also very much appreciate your thoughts on estimating the most optimal n_spins from the data. Thanks a lot! Best wishes, Mikhail

2 1

subgraph_isomorphism bug: misses occurrences
by Ingo Lohmar 16 Apr '12

16 Apr '12

Hi Tiago, I was puzzled by some results of my tests failing when compared to subgraph_isomorphism. Finally I've narrowed it down to a (fairly) small example: ##### from graph_tool.all import * sub = Graph() sub.add_vertex(3) sub.add_edge(sub.vertex(0), sub.vertex(1)) sub.add_edge(sub.vertex(0), sub.vertex(2)) G = Graph() G.add_vertex(4) G.add_edge(G.vertex(0), G.vertex(1)) G.add_edge(G.vertex(0), G.vertex(2)) G.add_edge(G.vertex(1), G.vertex(2)) G.add_edge(G.vertex(3), G.vertex(2)) G.add_edge(G.vertex(1), G.vertex(3)) vmap, emap = subgraph_isomorphism(sub, G, random=False) for e in G.edges(): print G.edge_index[e], e for vm, em in zip(vmap, emap): print vm.a, em.a G.add_vertex() G.add_edge(G.vertex(1), G.vertex(4)) vmap, emap = subgraph_isomorphism(sub, G, random=False) for e in G.edges(): print G.edge_index[e], e for vm, em in zip(vmap, emap): print vm.a, em.a ##### We search for sub, 0 --> 1 \ \ -> 2 G first looks like this: 0 --> 1 --> 3 \ | / \ v / -> 2 <- when subgraph_isomorphism gets both occurrences correctly. But after adding a link (1, 4), it gets the two new occurrences involving vertex 4, but suddenly misses the one with edges [(1,3), (1,2)]. This is with a git clone of graph-tool from last Tuesday (after the segfault fix). Also, I would be grateful for some clarification: 1) subgraph_isomorphism is supposed to deliver all (not only the induced) occurrences, right? 2) Does it give several subgraphs which are isomorphic to each other as separate occurrences or not? My tests suggest this is not consistent between different situations. 3) What is the purpose of the random=True default? It bit me badly when I first tried the function :) Thanks for your dedication to this library! Regards, Ingo

2 2

Purging vertices after filter
by zkaiwen 11 Apr '12

11 Apr '12

Hi, I have a question about purging. After filtering out certain vertices using set_vertex_filter, I want to remove all filter vertices. However, after removing them by calling the purge_vertices function, the property maps for the vertices doesn't seem to line up anymore. For example: Initial Graph: with vertex and property map Vertex Property Map V1: 1 Filtered V2: 2 Filtered V3: 3 Not Filtered V4: 4 Not Filtered After calling purge I see Vertex Property Map V3: 1 V4: 2 This is not correct because V3's mapping is 3 and not 1. Is there a simple fix to this issue or a suitable workaround without having to go back and relabel all the property maps. 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 3

Adding a subgraph into a graph
by Kavya Shagrithaya 11 Apr '12

11 Apr '12

Hi, I have one query about modifications with graphs. There is a subgraph that I identify using pattern matching and remove it. The intention is to replace that part with another graph. Using the graph_union function the graphs are combined structurally, however, all the properties of the graph being inserted are lost. Is there any way for insertion of subgraphs with the properties preserved? -- Thanks, Kavya

3 6

Re: [graph-tool] How to access properties (stackoverflow
by Mikhail Spivakov 10 Apr '12

10 Apr '12

Hi Tiago, Thanks for your advice - in particular, on using defaultdict, will try it out! M ========================================== Date: Mon, 09 Apr 2012 15:23:22 +0200 From: Tiago de Paula Peixoto <tiago(a)skewed.de> To: Main discussion list for the graph-tool project <graph-tool(a)skewed.de> Subject: Re: [graph-tool] How to access properties (stackoverflow question)? Message-ID: <4F82E2CA.9030700(a)skewed.de> Content-Type: text/plain; charset="utf-8" On 04/09/2012 01:46 PM, Mikhail Spivakov wrote: > Hello Tiago and everyone, > > I'd like to bring your attention to a question on stackoverflow, which > I'd also like to know the answer to: > > http://stackoverflow.com/questions/9526827/graph-tool-how-to-access-propert… I've posted an answer there. > In particular, this bit: > > "How do I get an object [vertex] with a certain title back from the > graph ? One way seems to be to create a vertex filter using > graph.set_edge_filter(...) and apply that - which seems a pretty > expensive operation considering all I want is to get one single object > back. I really don't want to maintain my own object title / vertex > index mapping as IMO, that is one of the tasks of the graph". > > Consider, for example, the following simple situation: I've got an > existing set of vertices and then obtain information on edges between > them from somewhere, which may sometimes also involve vertices not yet > in the graph. In networkx, I would simply do: add_edge(x,y), where x > and y are vertex names (that have or have not been defined a priori > using add_node(x)). > Is there a straightforward way to do the same in graph_tool? This question is asked frequently, so I should probably put it in the documentation. Differently from networkx, graph-tool's vertices have only one canonical "name", which is its index number. One may define arbitrary property maps, but this mapping is inherently one-way only, since it does not need to be unique. Thus, in order to find a vertex with a given property, one needs to search the graph, or maintain a reverse mapping by hand, with a dictionary object, for instance. This way of doing things makes the underlying graph data structure very straightforward, and allows for very efficient algorithms. On the other hand, it is slightly less convenient for the user, if he needs to constantly lookup vertices based on property values. In my use, I've always been able to solve this by creating a single dict object which implements the reverse mapping, and keeping it together with the graph. Note that there is no easy way of implementing this in the library itself, since the property values are often exposed in a "bare bones" way as C++ vectors to the underlying algorithms, or as Numpy arrays. In order for the mapping to be consistent, one would need to check every time a value in the map has been changed, essentially killing the performance of any algorithm which needs to modify property values (basically all of them). If you want to make the lookup more convenient, more or less in the way you have described, could use a defaultdict, as follows, name_map = defaultdict(lambda: g.add_vertex()) v = name_map["foo"] # 'foo' gets created g.add_edge(v, name_map["bar"]) # 'bar' gets created In my view, this is sufficiently straightforward... But people may have different opinions. Cheers, Tiago

1 0