Boost Graph Library Challenge and To-Do Items

• Dynamic graph algorithms such as described in Dynamic Graph Algorithms and A Software Library of Dynamic Graph Algorithms.

• Polish up code/docs for pending items and champion the formal review. The pending items are:

• container_traits.hpp (this should also include the work done by Matt Austern on this topic)

• The queues and heaps: queue.hpp, mutable_queue.hpp, fibonacci_heap.hpp. Somehow merge implementation with Dietmer's heaps and queues.

• disjoint_sets

• Construct a set of planar graph algorithms.

• Is the graph planar?

• "Walk around the block" and similar open and closed neighborhood traversals. Note that edge traversals need to resolve to particular ends and sides (see below), not just to the edge as a whole.

• Given a point, find the nearest vertex, edge, or bounded polygon. Again, edges are viewed as having left and right sides.

• Given a line segment, find intersecting vertices, edges, or bounded polygons.

• Given a polygon, find intersecting whatever...

• Various minimum bounding rectangle and clipping problems.

• Construct a planar embedding of a planar graph.

• Find a balanced separator of a graph.

• Modify adjacency_list so that the out-edges can be ordered according to a user defined comparison object.

• Rewrite the Qhull algorithm using the Boost Graph Library (this is high difficulty challenge). Or, for a more manageable challenge, write an interface for Qhull with the BGL. Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram, and halfspace intersection about a point. Qhull runs in 2-d, 3-d, 4-d, and higher dimensions. Qhull is used for collision detection, animation, plate tectonics, 3-d modeling, robot motion planning, and other applications. It is currently difficult to use from a C++ program.

• Explore the use of Algorithm Objects as an alternative to the current approach with visitors.

• Analyze the algorithms that do not yet have visitors, and come up with visitor interfaces for them.

• Add a check in the adjacency_list class to make sure all the vertex property template arguments have kind=vertex_property_tag and all edge property template arguments have kind=edge_property_tag.

• Clean up the output functions in graph_utility.hpp to use streams, and document all the utility functions. Replace the random number stuff with calls to the boost random number generator.

• Modularize the tests in test/graph.cpp to apply to particular concepts. Make sure there are run-time tests for every BGL concept.

• Write tests for the BGL algorithms. There are a few, but more are needed. The example provide a sanity check but do not provide full coverage.

• Write up the examples from Knuth's Stanford GraphBase using the BGL. The file examples/miles_span.cpp is a start.

• Further testing of the subgraph class and add more features.

• Implement a minimum-cost maximum-flow algorithm.

• Make the type of all (internal) property maps convertible to the const_type of the property maps.

• Add static functions to adjacency_list to return the per-vertex, per-edge, and per-graph overhead.