How To Contribute an Algorithm

[Becheler]

How to Contribue An Algorithm to Boost.Graph

Welcome, and thanks for thinking about adding an algorithm to Boost.Graph! 🎉

This guide is here to help your first algorithm contribution go smoothly. It's a companion to CONTRIBUTING.md (which covers the mechanics of forking, building, and running tests) and walks through the design conversation that usually happens in the issue thread before any pull request is opened.

Working on something smaller (a bug fix, an improvement to an existing algorithm, or a documentation update) ? Chances are you don't need this guide and that CONTRIBUTING.md or the issue templates have you covered.

---

How algorithm contributions work

Open-source maintainers are busy people, and Boost.Graph is a large library that evolves carefully. To make the most of everyone's time (yours and the reviewers') algorithm contributions move through three phases, each ending with a clear deliverable that everyone can look at:

• Phase A: Design. Discussion in the issue, sketches in Compiler Explorer, until a minimum viable signature is agreed. Output is a Compiler Explorer link that compiles and runs.
• Phase B: Working code. The signature is implemented in the BGL idiom, lives in the right place in the source tree, and passes a minimal test. Output is a Pull Request marked as Draft.
• Phase C: Production polish. Concept checks, broader test coverage, documentation, and (when relevant) performance benchmarks. Output is a Pull Request marked as Ready for Review. This is what gets merged.

Two maintainers handle algorithm contributions, and they come in at different points:

• @Becheler is currently full-time on Boost.Graph and is the first point of contact for design discussions, triage, and early code review. Expect them throughout Phase A and Phase B. Don't be shy about pinging them with half-formed ideas or "is this the right direction?" questions 😄
• @jeremy-murphy is the project's long-time principal maintainer and his bandwidth is more limited, so he comes in during Phase C, once the contribution is close to merge-ready. Helping us get there before tagging him keeps the review queue moving for everyone.

The rest of this guide walks through each phase: what to do, what to share, and how to know you're ready for the next one.

---

Phase A Design

The goal of Phase A is to converge on a signature that everyone agrees with, before any production code is written. The deliverable at the end of this phase is a Compiler Explorer link with a working draft of the signature you and the maintainer have agreed on. No PR yet.

A.1 Open the feature-request issue

Open an issue and use the Feature Request template. The "I'd like to submit the implementation as a pull request" checkbox is your signal to the maintainers that the issue is also a design thread.

Two things make the rest of the workflow much smoother:

• Find a sibling algorithm. Almost every graph algorithm has a close cousin already in BGL:
  • Iterative scoring? Look at Page Rank.
  • Shortest paths? Dijkstra.
  • Isomorphism? Look at Mc Gregor Common Subgraphs.
    Your minimum viable signature should look very much like the cousin's: same parameter order, same conventions, same helpers (graph::n_iterations, etc.).
• List the extension points explicitly, and defer them. In the issue, write down everything that could be customized (normalization strategy, stopping criterion, edge-weight caching, visitor hooks, parallel/distributed support, alternative quality functions, …). For each, decide: first PR or future PR. Default every extension point to "future PR" unless a maintainer pushes back.

Open-ended brainstorming ("should BGL have spectral filters at all?") belongs in a Discussion, not an issue. The issue templates will redirect you there if needed 😉

A.2 Iterate in Compiler Explorer

The agreed medium for early design review is this Compiler Explorer skeleton: https://godbolt.org/z/fq1z9z9T8

• fill in the marked sections
• save a short link ("Share → Short link")
• and paste it in the issue.

Reviewers can then edit the same skeleton, save their own short link, and reply with counter-proposals. This is much faster than a PR and produces a record everyone can compile.

When using the skeleton, set the compiler flag to -std=c++14 : Boost.Graph still builds against C++14, and catching C++17-only constructs (like if constexpr or structured bindings) at this stage saves a round of feedback later.

What a productive iteration looks like:

• You post a pseudo-code signature in the issue.
• A maintainer suggests replacing an enum with a property map, collapsing two overloads into one, or matching an existing helper.
• You update the godbolt link, paste the new short link, and summarise what changed in one or two sentences.
• Repeat until the maintainer says: "this signature is good, please open a PR."

Most first-time contributions iterate quite a few times in the issue before that signal. It's expected and a sign the early review is working: it's the part of the work that's easiest to do collaboratively, so we do as much of it as possible here rather than in a PR review.

A.3 The minimum viable signature

A minimum viable signature has these properties:

• One overload, fully positional. Named-parameter overloads are being deprecated.
• Mirrors a sibling algorithm's argument order. If the sibling takes (g, rank_map, done, damping, n, rank_map2), you should too, with new parameters inserted in the obvious positions.
• No enums for behavioural choices. Use a property map or a callable instead, and provide named makers (make_<adjective>_weight_map(g)) so the call site stays readable.
• No visitor, no optimizer, no distributed counterpart. All future PRs.
• Property maps and predicates pass by value. They are cheap handles, not the data they refer to.
• Throws only on genuinely exceptional conditions. "Did not converge in n iterations" is not exceptional, chances are the user can read the residual after the call and decide.

In Phase A, the code in godbolt can use auto everywhere it makes sense. Don't bother with concept checks or explicit return types yet. The goal at this point is just to get something that compiles against real Boost, so that feedback is grounded in code that runs:

template <typename Graph, typename WeightMap, typename SeedMap,
          typename RankMap, typename Done>
auto my_algorithm(const Graph& g,
                  WeightMap   weight,    // by value
                  SeedMap     seeds,     // by value
                  RankMap     rank,      // by value
                  Done        done)      // by value
{
    // ... iterative body ...
}

You know Phase A is done when a maintainer signs off on the signature in the issue, typically with a message like "this looks good, please open a PR."

---

Phase B Working code

The goal of Phase B is to land the agreed signature into the real source tree, in the BGL idiom, with a minimal test that proves it does the right thing. The deliverable is a PR marked as Draft.

B.1 File layout and namespaces

• Header: include/boost/graph/<algorithm>.hpp.
• Namespace: everything public goes in boost::graph::. Helpers, tag types, and implementation details go in boost::graph::<algorithm>_detail::, not in a top-level boost::graph::detail (that would collide with other algorithms' helpers).
• Public exceptions: in boost::graph::, not in the _detail namespace. If a user needs to catch it, they need to be able to spell its type.
• Tests: A minimal test/<algorithm>_test.cpp where you check the happy path, registered in test/Jamfile.v2. It should not be exhaustive at this point to facilitate review: make it short.

B.2 C++14, not C++17

Boost.Graph builds against C++14. The following are not available to you:

• if constexpr : use tag dispatch on traits instead.
• Structured bindings (auto [a, b] = ...) : use std::tie or named locals.
• std::optional : use boost::optional.
• std::variant : use boost::variant.
• Class template argument deduction : spell the template arguments.

A tag-dispatch replacement for if constexpr looks like this:

namespace my_algorithm_detail {

template <typename Graph>
auto in_degree_if_bidirectional(typename boost::graph_traits<Graph>::vertex_descriptor v, const Graph& g,  boost::bidirectional_graph_tag)
{ return in_degree(v, g); }

template <typename Graph>
auto in_degree_if_bidirectional(typename boost::graph_traits<Graph>::vertex_descriptor v, const Graph& g, boost::incidence_graph_tag)
{ return out_degree(v, g); }   // fall-back for undirected/incidence graphs

}  // namespace my_algorithm_detail

And the call site becomes:

auto d = my_algorithm_detail::in_degree_if_bidirectional(v, g, typename boost::graph_traits<Graph>::traversal_category{});

B.3 Spell out the return type

Before opening the PR, every public function must have an explicit return type in its signature. Documentation generation and the public API reference both rely on it; auto returns are not acceptable on the public boundary.

If the return type depends on a property map's value type, use property_traits:

template <typename Graph, typename WeightMap, /* ... */>
typename boost::property_traits<WeightMap>::value_type
my_algorithm(const Graph& g, WeightMap weight, /* ... */);

B.4 Write a minimal test

A minimal test is enough code in test/<algorithm>_test.cpp to exercise the algorithm on a small graph and check the expected output. It doesn't need to cover edge cases or every graph type (that's Phase C). The point is to prove the implementation behaves as designed on a clear, hand-verifiable input.

Register the new test in test/Jamfile.v2 and confirm it builds and passes with b2 from inside the test/ directory.

You know Phase B is done when CI is green on a draft PR (or your fork branch), the test passes, and the implementation matches the signature agreed in Phase A.

---

Phase C Magic Polish ✨

Phase C is everything that turns a working implementation into something we can confidently merge and maintain. None of these steps require new design decisions: they're about coverage, safety, and discoverability.

C.1 Add concept checks

BOOST_CONCEPT_ASSERT for every template parameter, at the top of the function body. This is what catches a caller who passes a VertexListGraph where you needed an IncidenceGraph, with a readable diagnostic instead of a 200-line template instantiation error.

template <typename Graph, typename WeightMap, typename SeedMap, typename RankMap, typename Done>
typename boost::property_traits<RankMap>::value_type
my_algorithm(const Graph& g, WeightMap weight, SeedMap seeds, RankMap rank, Done done)
{
    using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;
    using Edge   = typename boost::graph_traits<Graph>::edge_descriptor;

    BOOST_CONCEPT_ASSERT(( boost::IncidenceGraphConcept<Graph> ));
    BOOST_CONCEPT_ASSERT(( boost::VertexListGraphConcept<Graph> ));
    BOOST_CONCEPT_ASSERT(( boost::ReadablePropertyMapConcept<WeightMap, Edge> ));
    BOOST_CONCEPT_ASSERT(( boost::ReadablePropertyMapConcept<SeedMap,   Vertex> ));
    BOOST_CONCEPT_ASSERT(( boost::ReadWritePropertyMapConcept<RankMap,  Vertex> ));

    // ... body ...
}

Adding concepts last (rather than first) is deliberate: you don't yet know exactly which graph and map concepts you need until the body is written.

C.2 Expand test coverage

Phase B asserted the happy path on one small graph. Phase C broadens that:

• Edge cases. Empty graph, single vertex, disconnected components, graphs with self-loops or parallel edges (if your algorithm supports them).
• Different graph types. At minimum, both directed and undirected variants of adjacency_list. If the algorithm has meaningful behaviour on compressed_sparse_row_graph or other graph types, test those too.
• Different property-map kinds. iterator_property_map, function_property_map, and bundled properties if relevant, to make sure the algorithm really is property-map-generic and not accidentally specialised.
• Numerical robustness if the algorithm computes floating-point values: known reference outputs from a sibling implementation, or analytical results on small graphs where the answer can be computed by hand.

C.3 Documentation

• Add doc/<algorithm>.adoc following the AsciiDoc layout established in PR Doc migration #491.
• The page should mirror the structure of an existing algorithm's docs:
  • doc/templates/algorithm.adoc should get you started
  • keep in mind a sibling algorithm makes a good template too.

C.4 Performance benchmarks (when relevant)

Performance benchmarks aren't required for every algorithm, but for algorithms with non-trivial complexity or competing implementation strategies they make review much easier.

A benchmark doesn't need to be elaborate to be worthy:

• a few graph sizes,
• a couple of comparison points (a sibling BGL algorithm, or an external reference implementation),
• and an end-to-end runtime measurement

If your algorithm is essentially O(V + E) with no interesting hidden constants, you can skip this and say so in the PR description.

The boost-graph-benchmarks repository collects these until we agree on a long-term infrastructure. If you need your benchmark collected, ping @Becheler.

C.5 Mark the PR ready for review

Your draft PR has been open since Phase B. At this point, the action is to mark it as Ready for review (the green button at the bottom of the PR page).
Before you click it, a quick pass over the Phase C items:

• Concept checks added (C.1).
• Test coverage broadened (C.2).
• Documentation page added under doc/ (C.3).
• Benchmark added, or explicitly skipped in the PR description (C.4).
• CI is still green.

CODEOWNERS will auto-assign @jeremy-murphy and @Becheler as reviewers, no need to ping them separately. This is the point where @jeremy-murphy joins the conversation if he has not before.

---

Appendix A worked example

Issue #493 (personalized PageRank) is a good worked example of this workflow that shows a full design loop: pseudo-code in the issue, reviewer pushes back on enums and visitor design, contributor narrows scope, parties agree on a minimum viable signature, then the implementation gets a Compiler Explorer link before any PR is opened.

Reading it end-to-end is the single best preparation for your own first algorithm contribution.

Good luck! 🍀