This post originated from an RSS feed registered with Python Buzz
by maxim khesin.
Original Post: graph adaptors and an interesting bug
Feed Title: python and the web
Feed URL: http://feeds.feedburner.com/PythonAndTheWeb
Feed Description: blog dedicated to python and the networks we live in
I wanted to allow using a dict of list as the simplest graph data storage mechanizm for graphs. BGL supports a similar concept by allowing the usage of vector[list[T]] via overloading free functions (see here). While overloading can be hacked in Python using decorators or other techniques I think it is not very Pythonic . If something is not natural to do in a language I try to avoid doing it unless there is a great benefit. So instead of supporting GraphConcepts via free functions, like BGL, I am inclined to do it right in the 'graph' parameter to the algorithms in my lib. For example, while BGL would get the outgoing edges of a vertex with
// ei & ei_end are iterators, u is the vertex, g - the graph tie(ei, ei_end) = out_edges(u, g); for(;ei!=ei_end;) { //do stuff }
I would do
for e in g.out_edges(u): # do stuff
This does come at a cost of some flexibility, because implementing the GraphConcepts in free functions via overloading allows to use a wider variety of data structures for the graph's data. The alternative that I am leaning on is using an adaptor. Here is the sample dict-of-list adaptor just good enough for the breadth-first-search algo:
Please note the quirky-looking last line. It actually started off its life looking like this:
return zip(vertex*len(nbrs), nbrs)
Basically it creates a list of tuples representing the edges, zipping the current edge with its every downwind vertex. The line worked find as long as vertecies were strings, but it a vertex is an int *len would just multiply its value - NOT the desired result. Putting it in a tuple (vertex,) does the trick.
Previous Topic
