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

Subject: Re: [Boost-users] What is the bare minimum that needs to implemented for a Graph concept?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-24 09:54:24

On Wed, 23 Jun 2010, W.P. McNeill wrote:

> 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?

I believe what is required is that all of the members are defined, but 
their values are not used.  This is so that typedefs to those members (in 
the graph_traits class, most likely) will work correctly.  You can 
probably get rid of the errors by specializing graph_traits<ImplicitGraph> 
directly.  I believe (without checking) that Graph requires that you have 
an edge descriptor type defined, plus source() and target() functions. 
You will need to model VertexListGraph and IncidenceGraph anyway to have a 
graph that is useful for many algorithms, and so you will need to define 
the other typedefs for those concepts even if you do not need them for 
Graph.

You do want out_edge_iterator, by the way, since that is the way to get 
the adjacent edges to a given vertex (even for undirected graphs).  The 
edge_iterator is to get all of the edges in the graph, not just neighbors 
of one vertex.

-- Jeremiah Willcock