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@skewed.de To: Main discussion list for the graph-tool project graph-tool@skewed.de Subject: Re: [graph-tool] How to access properties (stackoverflow question)? Message-ID: 4F82E2CA.9030700@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-properti...

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