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.