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?

[andreacassioli]

I can share some experiences

1. Dijkstra termination
   We use Dijkstra extensively, at the moment with no need for early termination. But we have a couple of future use cases that could benefit for that: we will need to run one-to-many SP where "many" means a only a say 15% of the nodes! More a one-to-some you can say. In that case elegant early termination will be much appreciated!

2. RCSP termination
   The resource-constrained shortest path is our work-horse. In a special version of our optimisation engine, it runs on loose limits and searching for non dominated solutions, resulting in long-running searches that need a time out. Also a user can limit the number of routes, that means also a way to stop when that value is reached. We managed to implement both combining extension function checks and visitors, but far from elegant and robust. I can provide details if of interest.

3. Optimisation Solvers
   In the optimisation solver world, the idea of a backdoor to algorithm execution has been a staple for decades, and key to many research breakthroughs. It is usually referred as 'callback', but it works like a visitor that receives a view of the algorithm state at that point and can read/modify/return some information to steer the algorithm and/or collect information. Solvers like Gurobi, and CPLEX have been exposing such a machinery for decades. For instance see https://www.ibm.com/docs/en/icos/22.2.0?topic=callbacks-what-can-you-do-generic-callback - it is a no go to just raise an exception.

Maybe what a visitor should return and what an algorithm should are two separated, though connected, topics.

The control_flow idea looks nice. I guess each algorithm will need its own return struct so to speak, as some thing would not make sense to other.

[Becheler]

Thank you @andreacassioli ! For your two first use cases, do you think something like the Done predicate in PageRank could fit the bill ? From what I understand, the authors of PageRank added a separate predicate because visitors were non-returning.

Thanks to @maniospas work we could have some proof of concept it's fairly extensible to non-trivial termination criteria on #493 : https://godbolt.org/z/qof5azrf7

Allowing visitors hooks to operate as predicates (or more) would possibly shorten the signature of the algorithms needing both, at the risk of mixing responsibilities:

template <typename Graph, typename WeightMap, typename Quality, typename DoneLocal, typename DoneAggregation, typename Visitor>
void louvain_clustering(
    const Graph& g, 
    WeightMap w, 
    Quality quality,
    DoneLocal done1,
    DoneAggregation done2,
    Visitor vis);

with visitors-as-predicates:

template <typename Graph, typename WeightMap, typename Visitor>
void louvain_clustering(
    const Graph& g,
    Quality quality,
    WeightMap w, 
    Visitor vis);

with visitors-as-whatever:

template <typename Graph, typename WeightMap, typename Visitor>
void louvain_clustering(
    const Graph& g,
    WeightMap w, 
    Visitor vis);

I am getting unconfortable about visitors-as-whatever, including control-flows and complex structures. They look too nice in theory to be true or maintainable in practice ahahah 😆
They would. indeed require per-algorithm documentation, that would superpose to the already daunting visitor documentation.

Maybe visitors-as-predicates could be a first door to try ? It could solve your two first problems I believe (so could a Done predicate parameter in Dijkstra)

[andreacassioli]

A separate predicate will make the signature quite long I think, but maybe clearer. Maybe it is a matter to see how it will look like.

Also in some algorithms there might be multiple points where can stop.

[jeremy-murphy]

I read through quickly, so I might have missed something, but my impression is that there should be no problem with using visitors to dictate early termination of an algorithm. The only subtle considerations might be the different states that an algorithm is in for each visitor when it terminates.

I don't think we need to introduce any new predicates to our Dijkstra algorithm? We just change the existing one to return bool and the default value of true for each event point. Because of inlining, there shouldn't be any extra code generated for trivial visitors that always return true.

[jeremy-murphy]

Sorry, I have slightly mixed up the meaning of "visitor" with "event point" in my first paragraph.

[Becheler]

So you would be ok testing with one Dijkstra visitor hook returning a bool and we see from there ?

We just change the existing one to return bool and the default value of true for each event point

Wouldn't that break all existing users visitors whose hook happens to return void ? We need the algorithm to be ready to receive both void or bool, right ?

[jeremy-murphy]

Yes, I would look at trying to change them all to return bool, but if some of them feel too awkward to be part of the core algorithm logic then leave them be.

[jeremy-murphy]

I'm saying this without having looked at the algorithm for a long time. 😅

[andreacassioli]

Just found this PR that is somehow related #280