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: Luke Meyers (n.luke.meyers_at_[hidden])
Date: 2012-03-20 01:56:17

Thanks, that did the trick!  I'd suspected a problem in those template args
before but guess I forgot to follow up.  I've got the A* example working
now with filtering, and will post it in a separate thread for visibility.
 Wonderful to have such a responsive and expert user community!

On Mon, Mar 19, 2012 at 6:25 AM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>