[Boost-users] What is the bare minimum that needs to implemented for a Graph concept?

Subject: [Boost-users] What is the bare minimum that needs to implemented for a Graph concept?
From: W.P. McNeill (billmcn_at_[hidden])
Date: 2010-06-23 22:30:15

The concept checking code for the Graph concept seems to require more
associated types than is called for by the documentation.

According to "The Boost Graph Library" book by Siek et al. and documentation
on the boost website (
http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/Graph.html), the Graph
concept needs just four associated
types: vertex_descriptor, directed_category, edge_parallel_category,
and traversal_category.

I implemented the following bare-bones graph concept:

#include <boost/graph/graph_concepts.hpp>

struct ImplicitGraph {
// Graph concept
typedef size_t vertex_descriptor;
typedef boost::undirected_tag directed_category;
typedef boost::disallow_parallel_edge_tag edge_parallel_category;
typedef boost::adjacency_graph_tag traversal_category;
};

int main (int argc, char const *argv[]) {
boost::function_requires< boost::GraphConcept<ImplicitGraph> >();

ImplicitGraph g;
return 0;
}

However, when I try to build it I get the following errors from the concept
checking code:

graph_traits.hpp:30: error: no type named ‘edge_descriptor’ in ‘struct
ImplicitGraph’
graph_traits.hpp:31: error: no type named ‘adjacency_iterator’ in ‘struct
ImplicitGraph’
graph_traits.hpp:32: error: no type named ‘out_edge_iterator’ in ‘struct
ImplicitGraph’
graph_traits.hpp:33: error: no type named ‘in_edge_iterator’ in ‘struct
ImplicitGraph’
graph_traits.hpp:34: error: no type named ‘vertex_iterator’ in ‘struct
ImplicitGraph’
graph_traits.hpp:35: error: no type named ‘edge_iterator’ in ‘struct
ImplicitGraph’
graph_traits.hpp:41: error: no type named ‘vertices_size_type’ in ‘struct
ImplicitGraph’
graph_traits.hpp:42: error: no type named ‘edges_size_type’ in ‘struct
ImplicitGraph’
graph_traits.hpp:43: error: no type named ‘degree_size_type’ in ‘struct
ImplicitGraph’

I would not expect the concept checker to give me these errors because these
types are not part of the documented Graph concept.  Also,
the out_edge_iterator and in_edge_iterator don't make sense for the
undirected graph I have defined here.

Is the concept checking code out of sync with the documentation, or am I
misunderstanding how concept checking works?

This is Boost version 1.42 installed via Macports on OS X.