graph-tool July 2014

graph-tool@skewed.de

16 participants
27 discussions

Performance with property map
by Flavien Lambert 19 Jul '14

19 Jul '14

Hi everyone, to compute some functions I needed to loop over a bunch of edges. I realized that the call to property maps seems slow compare to a dictionary. I am a bit surprised since I was told - I am not an expert in python - that a query in a dictionary was already. So I was wondering if I made a mistake in using graph_tool. Following is an example of comparison. Best, F. In [3]: _network = gt.load_graph(_dataFolder + 'networkLTA-2.0-scc.xml') _network = gt.load_graph(_dataFolder + 'networkLTA-2.0-scc.xml') In [4]: _network.list_properties() destination (vertex) (type: long double) _graphml_vertex_id (vertex) (type: string) origin (vertex) (type: long double) _graphml_edge_id (edge) (type: string) speed (edge) (type: long double) name (edge) (type: string) time (edge) (type: long double) In [5]: _edgeIds = _network.edge_properties['_graphml_edge_id'] _times = _network.edge_properties["time"] _speeds = _network.edge_properties["speed"] _origin = _network.vertex_properties['origin'] _destination = _network.vertex_properties['destination'] In [8]: _edges = [_e for _e in _network.edges()] %time for _e in _network.edges() : a = _speeds[_e] _speedDict = {} for _e in _edges : _speedDict[_network.edge_index[_e]] = _speeds[_e] _indexes = [_network.edge_index[_e] for _e in _network.edges()] %time for _n in _indexes : a = _speedDict[_n] CPU times: user 102 ms, sys: 5 ms, total: 107 ms Wall time: 103 ms CPU times: user 2 ms, sys: 0 ns, total: 2 ms Wall time: 1.94 ms

4 12

Unexpected property map to/from gml behaviour
by ... 18 Jul '14

18 Jul '14

In the following, I noticed the data type of the property map changes. Any ideas what is going on? >>> graph_tool.all.__version__ '2.2.31 (commit 245d1e2c, Thu Mar 27 11:28:39 2014 +0100) # having already built my graph >>> graph.ep {'weight': <PropertyMap object with key type 'Edge' and value type 'int32_t', for Graph 0x7f93019b8b90, at 0x7f930058c850>} >>> graph.ep['weight'].a PropertyArray([28, 18, 32, ..., 7, 8, 8], dtype=int32) >>> graph.save(graph_file_name) >>> graph2 = Graph() >>> graph2.load(graph_file_name) >>> graph2.ep {'weight': <PropertyMap object with key type 'Edge' and value type 'double', for Graph 0x7f93001b7b10, at 0x7f92fc00b190>} >>> graph2.ep['weight'].a PropertyArray([ 28., 3., 18., ..., 11., 6., 55.]) Then it gets weirder... >>> graph.ep['ONE_WAY'] = graph.new_edge_property('string') >>> for edge in graph.edges(): ... graph.ep['ONE_WAY'][edge] = 'TEST!' >>> graph.ep {'ONE_WAY': <PropertyMap object with key type 'Edge' and value type 'string', for Graph 0x7f93019b8b90, at 0x7f9327c0dc10>, 'weight': <PropertyMap object with key type 'Edge' and value type 'int32_t', for Graph 0x7f93019b8b90, at 0x7f930058c850>} >>> graph.ep['ONE_WAY'][edge] 'TEST!' >>> graph.save(graph_file_name) >>> graph2 = Graph() >>> graph2.load(graph_file_name) >>> graph2.ep {} >>> graph.num_edges(),graph.num_vertices() (78147, 29870) >>> graph2.num_edges(),graph2.num_vertices() (1, 29870)

2 5

Regular Expressions in Graph/Subgraph Isomorphism
by Reem Mokhtar 18 Jul '14

18 Jul '14

Hi, I have a question/request: I want to be able to match certain vertex/edge labels using a regular expression notation (i.e. if the subgraph requires a string that matches a regular expression for a certain label). If that's not something that is a priority to implement, can someone steer me in the right direction so I may be able to implement it myself? I was contemplating using graph_tool.run_action or something to run the code in C++, but I'm not sure how/where to start. Thanks! Reem -- 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 2

Discovering ego-networks, efficiently.
by Panos Achlioptas 18 Jul '14

18 Jul '14

Dear all, I am using the following code to extract for a node of a graph the induced subgraph containing the node and her neighbors (aka, the ego-netwkork). Can I make it more efficiently? In particular, is there a way to avoid using python to create the neighbor list (or at least avoid the type casting). If not, could I use some code in C/C++ for doing this an embedded in graph_tool? Thanks a lot, Panos def egoNetwork(inGraph, node): ''' Compute the ego-network subgraph of the -inGraph- where the ego is the -node-. Precondition: inGraph is undirected ''' neighbors = [int(n) for n in node.out_neighbours()] neighborhood = inGraph.new_vertex_property("bool") neighborhood.a[neighbors] = 1 neighborhood.a[int(node)] = 1 return GraphView(inGraph, vfilt = neighborhood)

2 1

Using vorder
by pedrosantos 18 Jul '14

18 Jul '14

Hello to everyone, I have in a graph several separated trees, paths and cyclic graphs. When I output it, it is a really mess(sfdp layout) as I have labels as well. I would like to know if there is a clever way to order(using vorder or other resource) all of it in a way that all the components(paths, trees and cyclic graphs) are well distributed in the space of the image and not in a circular way. -- 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

Edge properties
by Flavien Lambert 18 Jul '14

18 Jul '14

Hi, is there a way to get the key 'id' of edges in the spirit of the vertices one like the following? _vertexIds works but not _edgeIds. g=load_graph(dataFolder+'networkFullyConnected.xml') _vertexIds = g.vertex_properties["_graphml_vertex_id"] _edgeIds = g.edge_properties["_graphml_edge_id"] The result is Traceback (most recent call last): File "edgesProperties.py", line 18, in <module> _edgeIds = g.edge_properties["_graphml_edge_id"] File "/usr/lib/python2.7/site-packages/graph_tool/__init__.py", line 995, in __getitem__ val = self.get_func(self.g, key) File "/usr/lib/python2.7/site-packages/graph_tool/__init__.py", line 1469, in <lambda> lambda g, k: g.__properties[("e", k)], KeyError: ('e', '_graphml_edge_id') And the network in graphml framework reads as <edge id="1" source="65091" target="65221"> <data key="w">192.49624317</data> </edge> <node id="16071"> <data key="o">5.41539461304e-05</data> <data key="d">2.03027821579e-05</data> </node> Thanks, F.

2 10

Setting Edge Gradient
by Elleroth 18 Jul '14

18 Jul '14

Hello, Say I have an edge property (of type double) with values ranging from 0.0 to 1.0. I want this value to be set as the alpha for my edges or at least be used as the offset with the gradient option in the graph_draw function. The idea is that for edges with stronger weights, I can reduce the alpha. (Edges weighted at 0.0 will disappear.) How can I make that happen? Using graph_draw(..., gradient=[values, 0, 0, 0, 1.0]) will not work, as the 0th index in the gradient option list must be a value from 0.0-1.0, and not some set or list or properties. There's got to be a way to do this, though. It's simple enough; I'm probably just missing something. Thanks, -John -- 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

vertex_label and edge_label in subgraph-isomorphism
by yandim601 17 Jul '14

17 Jul '14

I've faced difficulties using the package graph_tool.topology - Assessing graph topology. Specifically, I am trying to use the function graph_tool.topology.subgraph_isomorphism, but incorporating the values of the arguments vertex_label edge_labels. At the documentation provided at the graph-tool web site does not appear explicit examples of how these value can be defined. The aim is to identify isomorphisms, with coincidence on vertices and edges labels. Can you give me an example or page where this is explained clearly? Thanks, I hope I have been clear in my question!! Regards -- 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 3

Order of motifs, counts and vertex mappings in clustering.motifs
by sabrina 16 Jul '14

16 Jul '14

Hi, I have a question about the order of motifs, their counts and maps returned by clustering.motifs. I have a graph in which vertices and edges have some properties: (Pdb) grafo <Graph object, undirected, with 23 vertices and 19 edges at 0xb06088c> I asked the motifs of this graph, with the following instruction: (Pdb) motivos, counts, vm = gt.motifs(grafo, k, return_maps=True) And I got the motifs, counts an vertex mappings as described below: *** 6 mofits (Pdb) motivos [<Graph object, undirected, with 4 vertices and 3 edges at 0xb066cec>, <Graph object, undirected, with 4 vertices and 3 edges at 0xb066cac>, <Graph object, undirected, with 4 vertices and 3 edges at 0xb066aec>, <Graph object, undirected, with 4 vertices and 3 edges at 0xb066bcc>, <Graph object, undirected, with 4 vertices and 3 edges at 0xb066d8c>, <Graph object, undirected, with 4 vertices and 3 edges at 0xb066e2c>] (Pdb) len(motivos) 6 *** The counts of these motifs (Pdb) counts [6, 1, 7, 9, 2, 2] ***The vertex mappings (Pdb) len(vm) 6 (Pdb) len(vm[0]) 7 (Pdb) len(vm[1]) 6 (Pdb) len(vm[2]) 9 (Pdb) len(vm[3]) 1 (Pdb) len(vm[4]) 2 (Pdb) len(vm[5]) 2 I thougth that there was a correspondence between the positions of motifs, counts and vertex mappings. For instance: The motif in the position motivos[0] occurs counts[0] times (which means 6 times) and the 6 occurrences of this motif is in vm[0]. Inspecting the length of vm, I realized that it is according to values in the counts, but not in the same order. Is it the expected behavior of clustering.motifs? Thank you for any help you can provide. Sabrina -- 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 2

shortest_distance anomalies?
by Gareth Simons 14 Jul '14

14 Jul '14

I am trying to run the shortest_path function on various nodes on a graph. I am using a starting vertex, and returning all vertices within a certain threshold distance. The edges are weighted by a distance metric. My dilemma is that it works as intended except for some nodes. All I can think of is that the problematic edges have an edge that exceeds the threshold distance, in which case it is returning only one edge, instead of all edges that are less than the threshold distance. Is it possible that once the algorithm reaches an edge that exceeds the cutoff distance, that it stops then-and-there, instead of searching the remaining vertices? I am attaching my python file and the graph file that I’m testing this on. - The file prints information about two test vertices to the console, one of a working vertex (A) and the other of a vertex (B) that doesn’t work as anticipated. (I can’t see anything suspiciously different between them.) - It also plots three copies of the graph: A) filtered graph of vertex (A); B) filtered graph of vertex (B); C) non-filtered copy of the entire graph showing index numbers and weights Thanks.

2 6

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

graph-tool July 2014