What were the reasons to terminate boost graph searches via exceptions?

Question

Early exit of algorithms in boost graph such as breadth first search should be done by throwing an exception according to the FAQ:

1. How do I perform an early exit from an algorithm such as BFS?
   
   Create a visitor that throws an exception when you want to cut off the search, then put your call to breadth_first_search inside of an appropriate try/catch block. This strikes many programmers as a misuse of exceptions, however, much thought was put into the decision to have exceptions has the preferred way to exit early. See boost email discussions for more details.

I am interested in the actual "thoughts that were put into the decision". So far I failed to find the appropriate posts on the mailing list. The closest I found was this one, stating

If the graph is big, exiting the algorithm by throwing an exception might be the most efficient way ;-). Of course, if you do many invocations on small graphs, it may be the least efficient ;-(.

and this one:

If you have enough callbacks, you can surely do all the same things. I'm not sure what loss of control you fear, but from an efficiency point-of-view it might make sense to exit the algorithm by throwing an exception (no, I'm really NOT kidding).

Which, to me, are no real well-founded justifications for the design decision. Also because we do see huge slow downs when a lot of exceptions are thrown, especially while running the code in a debugger. I am also aware of similar posts on stackoverflow (such as this one or this one) asking on how to terminate the searches. But I know how (by throwing an exception). Yet, none of them provide the reasoning behind the decision.

So my question is: Does anyone know the actual thoughts that went into the decision? And does anyone have an actual link to the boost mailing list post that contains these thoughts that are alluded to in the FAQ?

Answer 1

It simplifies the implementation. It allows all searches to leverage a generic traversal algorithm.

The argument becomes amplified in the face of generics.

Note that the visitors can be implemented in several ways:

• users can implement the visitor interface
• derive from one and override some handlers

or

• compose one from different Event Visitors

Especially that case creates questions with generic composition if handlers were to return a control value. What if several handlers handle the same event, how would the return values be combined?

This situation is similar to other event-driven designs, like browser script UI events (which can bubble up or not) or Boost Signals2 signal slots, which can have user-supplied combiners instead of the default optional_last_value

The key element is multiplicity of event handlers/"slots".

You might argue that this can be summarized as "the library doesn't afford early search termination", but as the documentation reflects the designers specifically opted to allow the exceptions language feature to be used here. In addition to all the places you already mentioned, let me quote from the implementation of the BGL function is_bipartite which uses a DFS that is potentially prematurely aborted when the graph is not bipartite:

try
{
    depth_first_search(graph,
        vertex_index_map(index_map).visitor(make_dfs_visitor(
            std::make_pair(detail::colorize_bipartition(partition_map),
                std::make_pair(detail::check_bipartition(partition_map),
                    put_property(partition_map,
                        color_traits< partition_color_t >::white(),
                        on_start_vertex()))))));
}
catch (const detail::bipartite_visitor_error< vertex_descriptor_t >&)
{
    return false;
}

return true;