Boost logo

Boost Users :

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]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at