RFC: Should BGL visitors be allowed to participate in algorithm control flow?

[Becheler]

This RFC discusses a starter proposal to contrast

• observer visitors (today, void-returning) versus
• flow-controlling visitors (proposed, bool-returning, discussing extensions).

Motivation

Algorithms rely on visitors to inspect the internal algorithm state. Users can override visitor methods to log progress, inspect statistics etc. But visitors today are strict observers: they take immutable parameters in, their hook methods return void.

For example, workshop participants asking to stop Dijkstra early hit the same wall: the only supported mechanism is to throw an exception from inside the visitor and catch it outside the algorithm call. The pattern works, is documented, but it is:

• Surprising to newcomers
• Slow on platforms where exception throw is expensive
• Inconsistent with how flow control is expressed elsewhere in modern C++
• A poor fit for -fno-exceptions builds

Also, iterative optimization algorithms rely on more complex state(s) that dictate their termination criterion. Numerous variations of such algorithms in the literature are actually variations on the trade-off quality versus runtime, that is degrading output quality by lowering iterations for better runtime. Currently there is no clear design decision in BGL on how to generalize such criteria.

This RFC asks whether BGL visitors should be allowed to influence algorithm flow more directly for example by returning a value from their hooks that the algorithm acts on.

Current state

Visitors today are strict observers. Hook methods return void. To terminate early, users currently write:

struct stop_when_found {
    Vertex target;
    void examine_vertex(Vertex v, const Graph&) const {
        if (v == target) throw found_target{};
    }
};

try {
    dijkstra_shortest_paths(g, source, visitor(stop_when_found{target}));
} catch (found_target&) { /* recover state */ }

This is documented but actively rejected by users in workshop settings and in #466 .

Proposed convention

Allow visitor hooks to return bool instead of void. A return of false signals "do not continue"; true means continue normally. Existing void-returning hooks remain valid and are interpreted as true.

struct stop_at_visitor {
    int target;
    bool examine(int v) const {
        std::cout << "visiting " << v << "\n";
        return v != target;
    }
};

template <typename Sequence, typename Visitor>
void traverse(const Sequence& seq, Visitor& vis) {
    for (const auto& item : seq) {
            if (!vis.examine(item)) return;
    }
}

The exact meaning of "do not continue" (terminate the algorithm immediately, terminate at the next safe point, skip the current iteration only) is documented per-hook per-algorithm. For Dijkstra's examine_vertex, the natural meaning is "the algorithm exits as soon as the current vertex's processing completes."

This is additive, not a redesign. The existing void-returning visitor concept stays exactly as it is.

Backwards compatibility

• All existing visitors returning void must continue to work without modification .
• The candidate algorithm for flow-controlling visitors must be modified to detect which form is in use at the call site, with tag dispatch (C++14) or more easily with if constexpr (C++17) :

if constexpr (std::is_void_v<decltype(vis.examine_vertex(v, g))>) {
    vis.examine_vertex(v, g);
} else {
    if (!vis.examine_vertex(v, g)) {
        // exit path
    }
}

• C++14 with tag dispatch: See on Compiler Explorer: https://godbolt.org/z/TThc3fasr
• C++17 with constexpr if : See on Compiler Explorer: https://godbolt.org/z/zrEzx8sWr

Algorithms where flow control from visitors would be useful

Three concrete cases. Each surfaces a different shape of the same underlying need.

Early termination with Dijkstra or BFS

Single-source shortest path is overkill when the user only wants a single-pair path: they need to stop as soon as the target is finalized. Today the only mechanism is to throw from examine_vertex and catch outside. This is costly on large graphs.

struct stop_when_found {
    Vertex target;
    void examine_vertex(Vertex v, const Graph&) const {
        if (v == target) throw Found{};
    }
};

  try {
    dijkstra_shortest_paths(g, source, visitor(stop_when_found{target}));
  } catch (const Found&) {
    std::cout << "stopped at target\n";
 }   

With bool-returning visitors:

struct stop_at_target {
    Vertex target;
    bool examine_vertex(Vertex v, const Graph&) const {
        return v != target;
    }
};

Termination criterion with Louvain

Modularity-optimizing community detection alternates two phases: local moving and network reduction. Each admits several natural stopping conditions:

• gain below a static (or adaptive) threshold
• no community changed this pass
• max iterations reached
• arbitrary user criteria

Unlike PageRank's single Done predicate, these are heterogeneous, often combined, and impractical to expose as separate callables: the API would grow a parameter per criterion. The current Louvain implementation hard-codes some criteria, gives a fixed-function variant taking two phase-specific thresholds, but this can't match the flexibility found in NetworkX, igraph, and other reference implementations.

A bool-returning per-iteration hook collapses the policy into one user-pluggable extension point:

struct stop_when_stalled {
    double threshold;
    bool finish_iteration(double gain, const Graph& graph) const {
        return gain >= threshold;
        // or: return complex_stopping_criterion(gain, graph);
    }
};

Generic Louvain also generalizes the quality function beyond modularity. That's currently a separate policy parameter, which would have redundant responsibility with a value-returning visitor (a natural extension beyond this RFC's bool case).

Termination criterion with Personalized PageRank

Power-method iteration converges (or diverges) based on a residual the caller wants to control. Today this lives in a separate Done predicate (a mechanism that exists precisely because visitors can't influence flow). If visitors return bool, the convergence check becomes a natural visitor hook, removing the special-case parameter and unifying stopping mechanisms across traversal and iterative algorithms:

struct stop_when_converged {
    double tol;
    bool finish_iteration(const RankMap& curr, const RankMap& prev, const Graph& g) const {
        return mean_abs_diff(curr, prev, g) >= tol;
    }
};

The same visitor pattern extends to value-returning hooks (see Question 1 below). The concept sketched here for PersonalizedPageRank #493 illustrates that design where hooks return values used by the algorithm, for example a per-iteration rescale factor:

struct personalized_page_rank_visitor_concept {
    T initialize(const P& p0, const G& g); // strip from p0
    void start_iteration(const P& p, const G& g);
    T rescale_factor(const P& p, const G& g); // per-iteration scale
    bool should_continue(const P& p, const G& g); // flow control
    T finalize(const P& p, const G& g); // restore to output
};

And the algorithm could be coded against this concept (pseudo-code below, not literal C++):

void personalized_page_rank(g, p0, rank_map, weight, damping, n, rank_map2, vis)
{
    strip = vis.initialize(p0, g)
    p0_view = view of p0 divided by strip

    rank_map <- p0_view

    loop:
        vis.start_iteration(current, g)

        next <- (1 - damping) * A_weighted * current + damping * p0_view

        s = vis.rescale_factor(next, g)
        next <- next / s

        if not vis.should_continue(next, g): break

        swap(current, next)

    final_scale = vis.finalize(rank_map, g)
    rank_map <- rank_map * final_scale
}

Related

Rust's standard library formalizes this pattern as the ControlFlow<B, C> enum. C++ has no equivalent in the standard library, it would look like:

template <typename B, typename C = std::monostate>
struct control_flow {
    std::variant<C, B> value;
    bool is_break() const { return std::holds_alternative<B>(value); }
};

The idea would be to allow users to write things like:

auto result = some_algorithm(g, [&](Vertex v) {
    if (v == target) return control_flow<Vertex>::break_(v);
    return control_flow<Vertex>::continue_();
});

if (result.is_break()) {
    std::cout << "found at " << result.break_value() << "\n";
}

Or things like:

enum class stop_reason { found_target, max_iterations, diverged };
using flow = control_flow<stop_reason>;
return flow::break_(stop_reason::diverged);

Worth knowing about for Question 1 below: if return-type scope broadens beyond bool, a ControlFlow-style sum type sits between a flat enum and arbitrary types in the design space.

Questions

1. Return-type scope. What may visitor hooks return?

   • bool only : simple + covers Dijkstra-style early termination but may not cover iterative convergence checks (PPR, Louvain).
   • Arithmetic types : supports residual < tol convergence style directly, but conflates termination criterion with metrics.
   • Enums (Rust's ControlFlow shape: Continue / Stop / Diverged) : explicit, library-wide vocabulary, most discoverable.
   • Arbitrary types : maximally flexible, no enforced contract, harder to reason about across the library.

2. Hook scope. Which existing hooks may return non-void? Dijkstra's examine_vertex is canonical. Enumerate per algorithm, or allow any hook?

3. Semantics of "stop." "Terminate at next safe point" as one library-wide convention, or specified per hook?

4. Relationship to Done predicates. Does a flow-controlling visitor subsume the existing Done callable in page_rank-style algorithms (Done becomes redundant), or do they stay orthogonal?

5. Migration of throw-to-terminate. Deprecate, keep both indefinitely, or just recommend the new way going forward?