[Boost-users] [BGL] - filtered_graph EdgePredicate performance

Subject: [Boost-users] [BGL] - filtered_graph EdgePredicate performance
From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2009-01-16 16:11:15

filtered_graph documentation says:

[1] The reason for requiring Default Constructible in the
EdgePredicate and VertexPredicate types is that these predicates are
stored by-value (for performance reasons) in the filter iterator
adaptor, and iterators are required to be Default Constructible by the
C++ Standard.

http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/filtered_graph.html

I only noticed this after scouring the documentation for hints as to
why dijkstra_shortest_paths was taking 2 hours with a filtered_graph
compared to 2 seconds with my adjacency_list.  The reason for this
huge difference was my filter's EdgePredicate had a
boost::unordered_set member that returned true if the edge was in it.
Changing that member to a pointer to an unordered_set reduced running
time back down to the 2 second range.

As I now understand it, every time a filtered graph iterator adaptor
is incremented, it actually incrememts in a loop while the
EdgePredicate returns false (or end is reached).  This implies that
the EdgePredicate should be extremely lightweight, since it is stored
by-value in the iterator.  What is the general recommendation when
writing filter_graph predicates?  My use case is filtering out all
edges that reside inside a polygonal region.  To do this, I do the
intersection, then store the edges that are inside that region in an
unordered_set.  This requires that my EdgePredicate store a pointer to
the graph and a pointer to the unordered_set since I can't hash an
edge_descriptor without a reference to the graph (to get the target
and source).  That still seems big to me, given that it will be copied
per iterator increment.  On top of that, to ensure proper release of
the unordered_set, I need to use shared_ptr or something similar,
instead of just having the predicate own the unordered_set like it
logically should, introducing yet more overhead in reference counting.

The footnote states that it is stored by value for performance
reasons.  What types of predicate implementations were in mind when
that was decided?  I can't see a realistic filtering predicate that
could say true/false with no member variables - at the very least it
must store a pointer to the graph so that it can use the
edge_descriptor.

Is there a different, preferred way of writing EdgePredicates?

Is there a way to get target/source from an edge_descriptor without
the graph instance?

Thanks,

--Michael Fawcett