Re: [boost] google SoC

From: John D Lamb (J.D.Lamb_at_[hidden])
Date: 2006-05-07 03:34:08

Andrew Sutton wrote:
> i had originally thought to work on a generic tree library since i  
> wrote a generic binary tree library last semester, but since the wiki  
> now reports about 5 proposals, i decided agaisnt it. instead, i  
> decided that i might give a shot at working with the boost graph  
> library since i've been using it lately for large network measures.  
> specifically, i'm interested developing directed and undirected graph  
> interfaces to the adjacency list class.
>
> if there's any interest, please let me know. i could write and submit  
> a proposal sometime over the weekend.
If you're interested in BGL, there are quite a few algorithms that I'd 
like. The easiest would probably be something to handle tours. I have a 
crude implementation that can handle some of the travelling salesman 
problem methods, but Euler tours are also important. Writing the 
algorithms gets easy when you have a good data structure. I think the 
best structure is to think of the tour as a trail (not necessarily 
closed) and store it as a hash_multimap. The hash_multimap elements are 
then (linked) list elements. Then I use two interfaces. Both can be 
dealt with as property_maps. One treats the structure like a linked list 
and allows rapid insertion and removal. This is the obvious one. The 
less obvious one is the hash_multimap, which allows you to find quickly 
if a particular vertex is in the trail and if so where it is.

My implementation is very crude and uses a void* where a template class 
should really derive from a base of itself. Once you have the 
structures, trails can be used for lots of algorithms. For example, they 
are a good place to store a shortest path, they can be split, joined, 
rotated, reversed and traversed.

Another missing set of algorithms are the general matching algorithms. 
The bipartite case can be done by flow algorithms. Here I think the 
starting point would be to find a good data structure for holding blossoms.

JDL