Documentation bugs, comments for graph library

From: kevin_vanhorn_at_[hidden]
Date: 2001-03-27 13:30:52

1. The documentation talks about a random_access_iterator_property_map
class template, but there is no such thing -- the library defines
iterator_property_map.  The documentation also has the type arguments
in the wrong order.

2. The documentation for identity_property_map does not tell in which
header file it is declared, nor does it mention any constructors.

3. I would very much like to see on the top-level documentation page
links to *all* functions and types provided in the library.  As it
currently stands, it is often hard to find the information you need. 
For example, the only links to identity_property_map and
random_access_iterator_property_map (aka iterator_property_map) are
buried several layers deep.

4. Going further, I would like to see a table of contents that has
links to *every* page of documentation for the library.  Otherwise,
it's easy to miss pages unless you're fanatical about clicking on
every link you see, as soon as you see it.

5. This is a great library and one I anticipate using a lot, but the
learning curve is steep.  I spent several hours on Sunday and Monday
studying it, and then it took me over three hours this morning to put
together a simple uniform-cost shortest-path demo program.

6. Although it's simple enough to write (once you figure out how
everything works in the library), it would be nice to have a
uniform-cost (all edge weights 1) shortest-paths algorithm provided by
the library.  This can run in O(V + E) time, avoiding a factor of
log(V) required by Dijkstra's general algorithm.

7. It would be nice to have convenience functions for some of the
algorithms that require you to pass in a color map.  The convenience
functions would use a color map local to the function.  The color map
is really an internal implementation detail, and it would be
preferable if users didn't have to concern themselves with it.  (Yes,
I understand that sometimes you want to avoid repeatedly allocating
and deallocating the color map when algorithms are called repeatedly.)

8. Creating a property map from a random-access iterator (or
random-access container) is horrendously painful.  How about adding
some convenience functions similar to the following:

template <class PropertyGraph, class RandomAccessIterator> inline
iterator_property_map<
  RandomAccessIterator,
  typename property_map<PropertyGraph, vertex_index_t>::type,
  typename iterator_traits<RandomAccessIterator>::value_type,
  typename iterator_traits<RandomAccessIterator>::reference
>
it_to_vertex_map(RandomAccessIterator it, PropertyGraph const & g)
{
  return make_iterator_property_map(it, get(vertex_index, g));
}

// Use this next function when vertex_descriptor is known to be an
// integer type, with values ranging from 0 to num_vertices(g).
//
template <class RandomAccessIterator> inline
iterator_property_map<
  RandomAccessIterator,
  identity_property_map,
  typename iterator_traits<RandomAccessIterator>::value_type,
  typename iterator_traits<RandomAccessIterator>::reference
>
it_to_vertex_map(RandomAccessIterator it)
{
  return make_iterator_property_map(it, identity_property_map());
}

template <class PropertyGraph, class RandomAccessContainer> inline
iterator_property_map<
  typename RandomAccessContainer::iterator,
  typename property_map<PropertyGraph, vertex_index_t>::type,
  typename RandomAccessContainer::value_type,
  typename RandomAccessContainer::reference
>
cont_to_vertex_map(RandomAccessContainer & c, PropertyGraph const & g)
{
  assert(c.size() >= num_vertices(g));
  return it_to_vertex_map(c.begin(), g);
}

template <class RandomAccessContainer> inline
iterator_property_map<
  typename RandomAccessContainer::iterator,
  identity_property_map,
  typename RandomAccessContainer::value_type,
  typename RandomAccessContainer::reference
>
cont_to_vertex_map(RandomAccessContainer & c)
{
  return it_to_vertex_map(c.begin());
}