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