Re: [Boost-users] [Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph

Subject: Re: [Boost-users] [Graph] filtered_graph of IncidenceGraph is not an IncidenceGraph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-19 09:25:54

On Sun, 18 Mar 2012, Luke Meyers wrote:

> Hello, list.  First time poster, sometime reader.  Today I finally achieved a milestone I've been working towards in
> my BGL-oriented project: I got astar_search_no_init working on an implicit graph.  Now I want to filter the input
> graph to restrict the search, and I'm running into trouble with filtered_graph.  My implicit graph class is a model
> of IncidenceGraph, as required by astar_search_no_init, but when I apply filtered_graph to it I find that the result
> is no longer an IncidenceGraph (according to BOOST_CONCEPT_ASSERT).
> The filtered_graph documentation saith:
>
>       If the underlying Graph type models VertexAndEdgeListGraph and PropertyGraph then so does the filtered
>       graph. If the underlying Graph type models fewer or smaller concepts than these, then so does the
>       filtered graph.
> 
> 
> From this, I would assume that if I run filtered_graph on an IncidenceGraph, the result will be a model of
> IncidenceGraph, not just of Graph.

That is how it is supposed to work.

> Also, if my input is an IncidenceGraph and not a VertexAndEdgeListGraph, I'd
> hope compilation would not fail if I don't have graph_traits defined for types required by VertexAndEdgeListGraph,
> but it does:
>
>       c:\src\boost_1_49_0\boost\graph\filtered_graph.hpp(181) : error C2039: 'in_edge_iterator' : is not a
>       member of 'boost::graph_traits<XYGraph>'

You need to provide the dummy typedefs because it is difficult (and was 
not possible when BGL was written) to determine exactly which concepts 
your graph models and use only those typedefs.

> When I provide a bunch of dummy typedefs to get around this error, I can get to the point of doing a
> BOOST_CONCEPT_ASSERT((IncidenceGraphConcept<FilteredGraphType>)).  This fails:
>
>       c:\src\boost_1_49_0\boost\graph\graph_concepts.hpp(94) : error C2679: binary '=' : no operator found
>       which takes a right-hand operand of type 'XY' (or there is no acceptable conversion)

You are using the wrong parameters to forward_iterator_helper (you put
in XY as the value type rather than std::pair<XY, XY>).  You might also
want to use Boost.Iterator since that is much easier to use.

> XY here is my vertex descriptor type.  The edge descriptor is a pair<XY,XY>, but for some reason it's getting XY out
> of the graph_traits instead and failing in this strange way.
> 
> Am I missing something?  Are my expectations incorrect?  Is this actually a bug (or two)?  At the bottom is a
> decently small example that fails for me (some function bodies excised for brevity -- my concerns are pre-link).  Is
> there a way to work around this without making my graph into a model of VertexAndEdgeListGraph?  Since my graph is
> infinite, this would hardly seem sensible.

I think it should work the way you expect after fixing some minor
things.

> Thanks in advance for any assistance.  Incidentally, if anyone's interested to see a working example of
> astar_search_no_init over an implicit graph, I'd be happy to clean up the code a little and post it.

That would be nice; we have A* examples and implicit graph examples, but
I don't think we have one on an infinite graph.

-- Jeremiah Willcock