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
Andrew Sutton wrote: 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