[BGL] Online Graph Algorithms (fwd)

From: David Pearce (djp1_at_[hidden])
Date: 2003-05-02 08:38:01

Hello,

I am interested in how boosters think online graph algorithms should
be written. I have looked at the connected_components algorithm and
feel that it breaks some of the ideas behind generic programming. For
example, consider the following:

 > typedef adjacency_list <vecS, vecS, undirectedS> Graph;
 > Graph G(6);
 > add_edge(0, 1, G);
 > add_edge(1, 4, G);
 >
 > // create the disjoint-sets structure, which requires
 > // rank and parent vertex properties
 > ...
 > initialize_incremental_components(G, ds);
 > incremental_components(G, ds);
 >
 > generic_algorithm_which_adds_edges(G);

At this point, the connected_components data structures may be
out-of-sync.  Now, I suppose that we could write a wrapper class which
looked like a "Graph" and provides its own add_edge to update "ds"
correctly.  However, this seems overly cumbersome.

It strikes me that a better way of doing this would be to use an
abstract base class, like so:

 > template<class T, ...>
 > class connected_components : public T {
 > ...
 > };
 >
 > template<class T>
 > pair<T::edge_descriptor, bool>
 > add_edge(connected_components<T>::vertex_descriptor t, ...) {
 >  // do stuff
 >  return add_edge(static_cast<T::vertex_descriptor>(t), ...);
 > }

Thus, we supply "Graph" as the base class and can then safely pass it
to "generic_algorithm_which...".

So, does anyone know of any reasons not to do this?

Cheers,

David J. Pearce