Boost.Graph Workshop Paris | May 6th, 2026 #466
Replies: 11 comments 28 replies
-
|
@andrea-cassioli-maersk @andreacassioli would you be interested joining us ? |
Beta Was this translation helpful? Give feedback.
-
|
@Becheler yes! |
Beta Was this translation helpful? Give feedback.
-
|
but I am not sure I can travel to Paris, so most likely online for me |
Beta Was this translation helpful? Give feedback.
-
|
Amazing 👍🏽 Very happy to get you onboard with us 😄 |
Beta Was this translation helpful? Give feedback.
-
|
@andrea-cassioli-maersk For organization purpose, would you mind reaching out to me on [email protected] ? 😄 |
Beta Was this translation helpful? Give feedback.
-
|
I am from the CGAL Open Source project. Technically, CGAL does not depend on algorithms of the BGL, but we fully embraced the design idea of external adaption, that is making the representation of the graph independent from the graph algorithms. In the first step, we provided what it needs for CGAL data structures like polygonal meshes to become models of BGL Graph concepts (meshes have vertices and edges between them). Edges then may have weights associated, which can be the Euclidean distance between the points, which can be seen as a vertex property, This done it is possible to run any algorithm of the BGL on CGAL polygonal meshes. In the second step, we extended the hierarchy of graph concepts, introducing concepts such as At some point we thought about contributing this to the BGL, but didn’t bring up the necessary energy, and also felt that the BGL had reached a point of stability. We could revive this idea. Ideally there would be an industrial or institutional sponsor who finances this community effort. Concerning needs, in one of CGAL algorithms, we do have a dependency on a BGL algorithm, namely for the max flow (which is at the same time a min cut) So, we are definitively interested in participating in a BGL Workshop. |
Beta Was this translation helpful? Give feedback.
-
|
Thank you Andrea ! It's very exciting to get to meet CGAL people. I am not aware of anyone else who extended the BGL to this level 😍 Thanks a lot for the detailed description of usage and needs. I will look into the max flow fast implementation and open an issue. This is good material for the workshop! |
Beta Was this translation helpful? Give feedback.
-
|
Hi all, I have been using boost.graph on and off for many years since my master thesis in 2005! Now I am working for Maersk, a large Danish logistic company and regularly use boost.graph as core component in optimization algorithms. Our focus is mostly on path finding algorithms, but we might also need other (recently I use max-flow for instance). On a personal level, I have made two small contributions, and helped a bit triage old issues or PR in order to familiarize more with the project. This renewed push to modernize and revitalize boost.graph is very welcome and I hope I can contribute somehow. |
Beta Was this translation helpful? Give feedback.
-
|
Hi @andreacassioli ! Thank you for this description ! What was your master thesis about and how did you end up in Maersk ? Had you heard about the max flow implementation mentioned by @afabri ? Have you had concerns about the performance of the current max flow algorithm implemented in BGL ? |
Beta Was this translation helpful? Give feedback.
-
|
Hi Graphlings! I am a C++ software engineer and researcher working since January 2026 with the C++ Alliance on revitalizing the Boost Graph Library. My first instinct was to connect with same-minded people and have all of us sitting in same room, hence this workshop 😂 I am a mixed bag of sciences. I hold a PhD in computational genetics from Université Paris-Saclay, where my research focused on spatially explicit models of gene genealogies and ecological modeling/inference of population graphs. I authored Quetzal-CoaTL, a published open-source C++ template library for building geospatial population genetics simulators, designed around reusable generic components and the same generic programming philosophy that underpins Boost (and would need some revitalizing too after I'm done with BGL ahaha 🥲) I am hoping to get researchers and C++ graph people in the same room, have an honest conversation about what is missing, what is painful, and what Boost.Graph could realistically become. If that sounds like your kind of day, I would love to have you there ❤️ |
Beta Was this translation helpful? Give feedback.
-
|
This upcoming workshop looks terrific! Not sure if it belongs in the agenda, but one thing I'd be curious to know is how much of a pain the rather complex interface of BGL is for newcomers and seasoned practitioners. Some random notes on API improvement ideas I'd like to discuss, here or elsewhere:
dijkstra_shortest_paths(
g, vertex(0, g),
predecessor_map(make_iterator_property_map(
p.begin(), get(vertex_index, g))).
distance_map(make_iterator_property_map(
d.begin(), get(vertex_index, g))));Something more intuitive could be devised along these lines: dijkstra_shortest_paths(
g, vertex(0, g),
predecessor_map(g >> vertex_index >> p).
distance_map(g >> vertex_index >> d));(Crude proof of concept at https://godbolt.org/z/as6rxW6M8; C++20 concepts used, but this surely can be backported to C++14).
|
Beta Was this translation helpful? Give feedback.
-
|
Wahoo palate-wise those are delicious suggestions 😋 I particularly love the idea of the >> composing operator for property maps. Because as amazing as they are for genericity, I indeed hate them at the call site. Thank you so much for those proposals (not me adding more work to the backlog ahaha) 😂 @jeremy-murphy was it on your radar ? |
Beta Was this translation helpful? Give feedback.
-
|
Sadly, I won't be flying in for the workshop. One thing that should be considered for future developments is CUDA support. The CUDA API is very well industry standard, not particularly difficult to retrofit onto existing libraries, and brings with it massive parallelism. If you need assistance with this endeavor let me know. I have added at least partial CUDA support to 3 boost libraries so far, and the upcoming boost.multi has it. |
Beta Was this translation helpful? Give feedback.
-
|
My plan is to to deprecate graph_parallel in favour of function overloads like the standard library does, which is what I think Arnaud is misremembering as using |
Beta Was this translation helpful? Give feedback.
-
|
Woooops ! My bad ahaha 😅 |
Beta Was this translation helpful? Give feedback.
-
|
Don't worry, it's really not your fault! I probably made a very vague reference to the idea without explaining it properly. What I mean is, similar to how the standard algorithms have extensions for parallelism, we can do the same for graph algorithms. I don't know the CUDA space at all, but my very quick search tells me that using that strategy means that simply using NVC++ can automatically do some GPU offloading, as it knows how to handle the parallel execution policies. In that case, would we actually need to write any CUDA-specific code, @mborland ? |
Beta Was this translation helpful? Give feedback.
-
|
That is generally correct. In most cases all you will need to do is add macro definition to your config that allows detection and insertion of CUDA's There's a few things you'll have to work around such as if you have things in static memory that need to be referenced such as lookup tables. In general though once functions have been annotated as such you can launch them into the CUDA kernel which is written like sequential code, but is automatically parallelized: https://github.com/boostorg/math/blob/develop/test/github_issue_1383.cu#L38. In the case of say divide and conquer type algorithms we will also have to do special handling and/or post-processing as the results are returned back from each of the individual threads. |
Beta Was this translation helpful? Give feedback.
-
|
In the case of execution policies, we have also rolled our own implementations of parallelism that are enabled when a parallel execution policy is passed. You can find those: https://github.com/boostorg/math/blob/develop/include/boost/math/statistics/detail/single_pass.hpp and the driver functions are in: https://github.com/boostorg/math/blob/develop/include/boost/math/statistics/univariate_statistics.hpp. This method allowed us to offer far more parallelism than you can from just the STL, and also offer dual support for language standards prior to C++17 |
Beta Was this translation helpful? Give feedback.
-
|
Hi there! I find this discussion very interesting, and as a previous Boost.Graph user that, unfortunately, had to move to a self-implemented graph after having worked with Boost.Graph for about two years on my project, I think this is the first and best opportunity to explain my reasons behind this. First, I want to say thank you to Boost.Graph, because it gave me the possibility to initially try out my project and get it to work. I am doing high performance (in terms of accuracy and computational speed) offline map matching. For offline map matching, a road network (i.e., OpenStreetMap) needs to be imported in advance of mapping a GNSS-recorded track (i.e., GPS-track) to the road network. As such, I started to import huge road networks into graphs. When it is not known beforehand where a GPS-track is located, a large road network has to be made available so that the spatial extents of the GPS-tracks and the road network fit together, which is essential for map matching. I first used Boost.Graph for implementing my approach, but I encountered a few major issues along the way that required me to completely abandon Boost.Graph in favor of an own graph implementation. To this date, I keep an eye on the development of Boost.Graph, but for my personal project, it is very unlikely that I can revert. My own implementation is so specifically tuned towards my use-case that a general-purpose graph library probably won't improve the performance for me any further. However, future researchers may benefit from my points, which is the reason why I write this comment. What were the reasons that I had to abandon Boost.Graph:
These were the two major issues that I had with Boost.Graph and I could only solve them with an own implementation, unfortunately. I will not be able to attend the meeting and I know my use-case is special, but maybe my point of view and the reasons why I had to abandon Boost.Graph can help in the discussion. Thank you for listening! |
Beta Was this translation helpful? Give feedback.
-
|
Dear @addy90 , thank you so much for this fantastic feedback. That is what is called giving back to the community ! 🫶 I am sorry you had to leave BGL, and also very happy you could build something that works so well for your use case ! You gave me so much to think about it took me the all day to answer ahaha 😄 If I can summarize your feedback, you should probably be able to see if I misunderstood your points: Dijkstra needs a kind of generic termination criterionIn terms of API, the only way to terminate Dijkstra early is to throw an exception from a visitor hook: it's undocumented but a known workaround, and you are saying it is too expensive: struct my_visitor : dijkstra_visitor<> {
template<class V, class G>
void examine_vertex(V u, const G& g) {
if (distance[u] > max_radius || found_all_goals())
throw goal_reached{}; // unwinds entire stack: aouch !
}
};
try { dijkstra_shortest_paths(g, src, visitor(my_vis)); }
catch (goal_reached&) { /* done but ugly and slow */ }I believe the reason they used exception is linked to the choice to make all visitors hook return struct local_dijkstra_visitor : dijkstra_visitor<> {
bool should_continue(auto u, auto distanceMap, const auto &g) {
if (get(distanceMap, u) > max_distance) return false;
if (goals.count(u)) {
settled_goals.insert(u);
if (settled_goals.size() == goals.size()) return false;
}
return true;
}
};
// and then find where in dijkstra that criterion should be checked outI encountered a similar issue in my Louvain clustering implementation (PR #443 ), in the sense that many researchers out-there tune their algorithm to terminate for a variety or reasons (marginal gains hit 0, or 10-6, or a user-defined threshold, or a decaying threshold, and I suspect one could try to estimate remaining potential gain based on the pattern of gain decay ...). I think the idea of a stateful termination criterion could be good, it is just not clear to me what is the information context worth passing to the decision criterion. In the case of generic Louvain that seems to be almost the entire algorithm state 😓 In any case, adding For your other issue, are you aware of the Graph Data Structures need AllocatorsThat one sounds really hard ahahah From what I understand BGL predates standard mental model of allocators so it's not surprising the implementation is naive. Also (and just like Dijkstra) I guess there were not so many large graphs at the time. Unless I'm mistaken that sounds like implementing new graph data structures, not new algorithms. This is good news because rewriting algorithms is pretty much a no-go. But all algorithms are implemented against concepts, not concrete data structures, so they should still work with new stateful allocators-aware graph data structures respecting those concepts. We can expect CSR to be reasonably easy since "it's just" two vectors. We can probably ask our friends at CGAL if they encountered similar issues. There are discussions about how to handle namespaces and new APIs. Currently, BGL puts everything into a boost::adjacency_list<vecS, vecsS> ; // not allocator aware, no memory mapping
boost::graph::adjacency_list<vecS, vecS, ..., Alloc> // ding !But that would require very careful documentation so users don't get mistaken. I tried to be synthetic but sorry if I rambled or misunderstood your explanations. Feel absolutely free to correct me 😸 |
Beta Was this translation helpful? Give feedback.
-
|
I've run into this naive allocator issue as well when dealing with large graphs. It seems counterintuitive to load the entire graph into memory at all times. It really slows down algorithms that are 'local' in nature and do not require full graph visibility. |
Beta Was this translation helpful? Give feedback.
-
|
Dear @Becheler, thank you for your thorough reply and your thoughts about my statements! I hope that I can help with your understanding with some more explanations from my side. DijkstraConcerning the Exception-throwing part, my old code from 4-5 years ago was similar to this: void examine_vertex(vertex_descriptor &vertex, const graph_type &_graph) {
if (_goals.contains(vertex)) {
_goals_found.emplace(vertex);
}
if (_goals_found.size() >= _goals.size()) {
throw goals_found_exception();
}
}So I threw the exception when I found all goals that I passed to the custom visitor in advance. That exception was caught when calling Dijkstra's algorithm, so that I could then walk through the predecessor_map for extracting all paths to all goals. In my newest code, I am calling a if (_goals_found.size() >= _goals.size()) {
this->stop();
}That simply sets a bool flag to true, which can be checked by the [[nodiscard]] constexpr bool stopped() const {
return _stop;
}
void stop() {
_stop = true;
}And that method is called in the while (not Q.empty() and not visitor.stopped()) {
...
}This way, the algorithm naturally stopped after examining the current vertex before proceeding with the next one, without a stack-unwielding. Of course this contradicts the idea that the visitor simply observes, but throwing an exception to forcefully stop Dijkstra's algorithm does the same, and is necessary in my approach. I did another small benchmark with exception-throwing vs. graceful stopping and the exception-throwing was slower, but not much, only by a few samples. The reason behind this is, however, that I make use of heavy caching mechanisms that prevent most recurring routing calls, so the impact is not as big anymore in my case. Iirc, the impact for me was bigger back then, but I made many other optimization improvements in the last years, so I am not surprised that the impact is smaller today. Concerning the early-stopping with the distance, I made it differently. I did not throw an exception here. My visitor received a calculated max-distance, depending on the current area size of the routing queries, and an additional safety factor that could be set at run-time. In the void examine_edge(edge_descriptor edge, const graph_type &_graph) {
if (_max_distance_factor < 0.0) {
// effectively disable this method if the max-distance-factor is disabled
return;
}
const vertex_descriptor source = boost::source(edge, _graph);
const auto distance_source = boost::get(_distance_map, source);
const auto weight = boost::get(_weight_map, edge);
const auto distance_target = distance_source + weight;
if (distance_target > _max_distance_factor * _max_distance) {
// disable target
const vertex_descriptor target = boost::target(edge, _graph);
_vertices.emplace_back(target); // explained later down
boost::put(_color_map, target, boost::black_color);
}
}This concept worked great and I kept the idea in my newest code with my custom graph and shortest path algorithms. This also contradicts that the visitor should only observe, but this idea already worked great with the BGL Dijkstra's algorithm, so it already is possible to intervene from the visitor. Maybe this lowers the ideologic entrance level of the visitor being able to manipulate the routing algorithm, because it already can. 😄 The issue with This is the final call method and it initializes a vertex_property_map_generator on that it calls the build method.And this build method creates an array in the size of the number of vertices: And when your graph is very large, this takes a tremendous amount of time. For this reason, in practice, I reimplemented this final void discover_vertex(vertex_descriptor &vertex, const graph_type &_graph) {
_vertices.emplace_back(vertex);
}Then, I could clean and reuse the data structures instead of reallocating them every time I called Dijkstra's algorithm (including the still initialized array in the no_init method, I mean, that I initialized in my re-built "no_init" method myself): for (const auto &vertex: vertices) {
boost::put(predecessor_map, vertex, vertex);
boost::put(distance_map, vertex, std::numeric_limits<length_type>::infinity());
boost::put(color_map, vertex, boost::white_color);
boost::put(heap_index_map, vertex, 0);
}
vertices.clear();This saved a lot of time because I only had to allocate the data structures one time and then cleaned them after every use in those positions where they have been changed. Still, they had to be allocated in the size of the number of vertices once. But in my current version, and with additional benchmarks that I made during development, using flat_maps was even faster the larger the road network graph became, simply because the flat_maps never need to have the size of the number of vertices due to the distance-limit, and clearing the flat_maps leaves the memory allocated, so that it can be reused without additional bookkeeping. I hope this explains some of my thoughts on Dijkstra's shortest path algorithm. The key circumstance in my map-matching use-case is that I called the routing algorithm very, very often and needed very quick results for spatially very small extents to feed the routing lengths into a stochastic optimizer for determining the best route in comparison to a track segment. Without extensive optimization in the routing algorithm, this can easily take over 90 % of the complete run-time, and I was able to reduce it down to around 20-40 % of the run-time. Stateful AllocatorsThere are some additional caveats with this. First, Boost.Interprocess currently has some bugs in the Windows memory-mapping implementation that prevents it from using sparse-files and files over 4 GB. I have, unfortunately, not found the time to make bug reports for these issues, but I implemented workarounds in my own map-matching application for the Windows path so that I can use sparse-files and files over 4 GB both on Windows and Linux. So for anyone trying to work with Boost.Interprocess and graphs larger than 4 GB, this only works natively on Linux right now and Windows needs workarounds. For example, on Linux, a sparse file is created with the // set sparse file: https://learn.microsoft.com/en-us/windows/win32/api/winioctl/ni-winioctl-fsctl_set_sparse
DWORD bytesReturned;
if (not DeviceIoControl(hFile, FSCTL_SET_SPARSE, NULL, 0, NULL, 0, &bytesReturned, NULL)) {
CloseHandle(hFile);
// marking as sparse did not work
}However, when creating the file in Boost.Interprocess on Windows, this method is not called, which means that the file is not a sparse-file in Windows: https://github.com/boostorg/interprocess/blob/87d8c1059e513621cd4da71567ec127ff5ea38a0/include/boost/interprocess/detail/win32_api.hpp#L831 Furthermore, the 4 GB limit on Windows on growing a file (which calles the truncate method on both platforms) comes from the fact that in Boost.Interprocess, within the truncate method, a static cast to an Second, when using memory-mapped files, there is the issue that the file needs to be closed, grown, and reopened when the size limit is reached. It would be possible to create a sparse file with some TB of size in advance and simply grow, but when someone sees this file-size, I am not sure whether this would frighten them. So I created a way of "doubling" the file size whenever it reaches its file limit. The issue with this approach is that when I add an edge into a bidirectional graph, for example, and I get the This is a general issue with stateful allocators: They may throw an exception because they cannot allocate, for example, due to resource exhaustion, i.e., file size limit reached. The file size cannot be easily computed in advance, because in my case, I filter the OpenStreetMap data based on tags during import, so I don't know how much I will import eventually. Furthermore, the bookkeeping of the allocators state, i.e., the positions of the data in the file in an index, also need space that is difficult to estimate in advance. Therefore, making a data structure robust for stateful allocators means that every function that allocated data needs a transaction concept that allows it to revert the changes back to the initial, stable state. Only then, it is possible to handle the exception without having a corrupt data structure beneath. It's possible, but quite challenging to implement. My data structures can grow multiple times per run without any corruption, but it took quite some effort to make this happen. Currently, BGL uses or edge properties: These were the major issues for me that made it hard to use BGL with stateful allocators, since I needed the entire graph in the memory-mapped file, so that I could reopen it on the next application run. So yes, maybe a different API is necessary here for modernized versions, if using default template arguments does not work as expected. I know these topics are very deep, but I had to work on them for many months in succession. I don't know how many use-cases there are for these high-performance huge graph topics, but I can at least tell that I had these issues, personally. Thank you sincerely for your interest in my topics! I hope I could shed some more light into the details and challenges around them. |
Beta Was this translation helpful? Give feedback.
-
|
Hi, I'm a developer working in CAD / CAE (mostly with computational geometry & meshing). Recently we had to implement a lot of graph functionality and Boost.Graph was heavily considered for the use case, however in the end we went with a custom implementation. Below I will outline the use case, why it didn't fit Boost.Graph and how it was solved. Algorithms of interest
Problem assumptions
Architectural preferences
Why BGL is desirableIt provides a very general "common language" for working with graph structures. Currently there is a lot of wheel re-invention - everyone implements their own graph structures and as a result their algorithms become non-reusable. Why we didn't go with BGLThe main reason is its lack of community finding & graph clustering algorithms, if those we present right off the bat other issues would likely be worked around just avoid having to manually implement them. Second significant reason is API complexity, although this is motivated by generality (which is understandable) and age (also understandable) it oftentimes results in algorithms being unwieldy and arcane. It feels like API could be significantly more convenient if it made use of C++20 concepts, ranges and better Custom indexations and allocator support were also somewhat awkward to not have, which further motivated going towards custom path. What internal solution ended up looking likeInternally I implemented a data structure based on a pair of dense slotmaps (one for verts and one for edges) with "keys" corresponding to columns of an AoS table storing interior vert / edge properties, also a few modifications to allow insertion / erasure at arbitrary indices. This resulted in a very cache-friendly representation with O(1) lookups, O(1) insertion / erasure (assuming a sparse graph) and pretty much entirely contiguous iteration: // Define graph
using weighted_oriented_multigraph = network_type<
type_list<>, // data attached to every vert
type_list<weight>, // data attached to every edge
network_policy::oriented_multigraph // topological policy
>;
auto graph = weighted_oriented_multigraph::with_slots(48, 36);
// Insert at specific indices
graph.insert_verts({ 3, 7, 12, 23, 47 });
graph.insert_edges({ 12, 23, 33, 35 }, { { 3, 7 }, { 7, 12 }, { 7, 23 }, { 7, 23 } });
// Iterate ranges
vert_id vert_0 = 23;
edge_id edge_0 = 12;
for (const auto vert : graph.verts()) {} // [contiguous] all verts
for (const auto edge : graph.edges()) {} // [contiguous] all edges
for (const auto vert : graph.verts(edge_0)) {} // [contiguous] verts of edge
for (const auto vert : graph.incoming_verts(vert_0)) {} // [random_access] adjacent verts
for (const auto edge : graph.incoming_edges(vert_0)) {} // [random_access] adjacent edges
for (const auto vert : graph.outgoing_edges(vert_0)) {} // [random_access] adjacent verts
for (const auto edge : graph.outgoing_verts(vert_0)) {} // [random_access] adjacent edges
for (const auto [root, edge] : graph.incoming_links(vert_0)) {} // [contiguous] adjacent verts & corresponding edges
for (const auto [dest, edge] : graph.outgoing_links(vert_0)) {} // [contiguous] adjacent verts & corresponding edges
for (const auto weight : graph.edge<weight>()) {} // [contiguous] all edge weights
for (const auto edge : graph.find_edges(3, 7)) {} // [random_access] all edges from vert 3 to vert 7
// Undirected graphs provide additional ranges
// for (const auto vert : graph.verts(vert_0)) {} // [random_access] adjacent verts
// for (const auto edge : graph.edges(vert_0)) {} // [random_access] adjacent edges
// for (const auto [root, edge] : graph.links(vert_0)) {} // [contiguous] adjacent verts & corresponding edgesNot aware of any C++ libraries doing the same, but the result ended up being rather convenient and performance-wise there's been no complaints, should probably do a few benchmarks against more traditional adjacency list representations some day. General allocator awareness was also attempted, however it ended up being too unwieldy to be practical so I went with a What would be nice to see in BGLBGL is already very good at solving general problems, but it could use some improvements in getting the usage across. I think it would greatly benefit from a documentation update like in Boost.Unordered so we can have an "easier on the eyes" navigation with sidebar T.O.C. and codeblock highlighting. It would also benefit from modernizing a lot of examples (e.g. prefer Lack of community detection / clustering is a big thing so its good to see it addressed in current priorities. SBM would be particularly great to see (especially the weighted version) as currently there doesn't seem to be any implementations in C++. In community finding there are generally 3 main approaches: spectral (k-means, recursive bisection), agglomerative (Louvain, Leiden and all the other partition -> aggregate schemes) and inference-based (SBM, WSBM and multiple others). They all have different quirks and trade-offs so the seemingly sensible choice would be to implement 1-2 "solid classics" from every approach. |
Beta Was this translation helpful? Give feedback.
-
|
Thank you @DmitriBogdanov for this carefully written feedback.
Yes, this is what makes me so happy to work on BGL. Writing generic algorithms against graph concepts is hard, but so worth to see the polymorphism we get in return.
Amazing, back in January I identified this methodological gap as being the most serious/urgent to cover, I am glad to see it was relevant. I have a first PR #453 about to be merged for Louvain, my goal is to refine it progressively and continue with Leiden, then SBM.
This is very relevant. Related to Louvain, do you have any use of:
I began to work on solidfying the broken
Yes the index mapping is so cumbersome. It's at the same time very "logical" implementation-wise to not assume descriptors are indices, and also very counter-intuitive. I wonder to what extend that could be "fixed" with some API/syntactic sugar following @joaquintides ideas. Definitely a pain point for anyone starting with BGL.
I completely empathize with this. Recently @jeremy-murphy bumped from C++03 to C++14, which is quite consequent. I am not sure it would be worth to move up to C++20 (although if we could we would).
Absolutely. I began to work on a local version of the documentation. My main priorities have been to:
Yes, yes and yes 🫶 Would you be able to give priority numbers to those reclamations ? 😄 What feels most urgent to you for your own needs ? |
Beta Was this translation helpful? Give feedback.
-
Didn't have to deal with non-modularity variations yet, but with modularity my experience is that Louvain / Leiden cost tends to be very front-loaded — most of the work is done in the first node-moving pass after which the algorithm converges quite quickly so there is little gain to be had from granular stopping criteria, simply limiting iterations to a certain limit e.g. 10-20 tends to be enough, some Python libraries even go as low as stopping after 3 iterations by default. Directed Louvain is also a rather exotic thing, not sure about its use cases, but as far as I understand it should be it shouldn't be terribly different from the undirected version.
No experience with them, realized that it's not gonna be easy and decided to not research much further.
I'd say "unwieldy" comes mostly from a lot of avoidable boilerplate diluting the algorithms. E.g. something as simple as iterating all indices in the "canonical" example becomes an entire code block, while the actual idea could easily fit into a 1-2 liner: // [Boost.Graph] Iterate vert indices
// (unmodified example from https://www.boost.org/doc/libs/latest/libs/graph/doc/quick_tour.html)
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
Vertex v = *vp.first;
some_func(index[v]);
}
// [Custom] Iterate vert indices
for (const auto vert : graph.verts()) some_func(graph.packed_index(vert));
// vert ~ potentially sparse ID of the vertex => [0, n_vert_slots)
// graph.packed_index(vert) ~ dense index in the underlying std::vector<vert_id> => [0, n_verts )A lot of the algorithms can also feel "heavy" due to requiring a custom visitor / handler struct in places where most common use cases could be serviceable by a lambda, through this is quite difficult to avoid due to the generality of such adaptors. I'd say a lot of "busywork" could be simplified by making better use of ranges and type deduction, e.g. below is a snippet of code from the Louvain PR: // [Boost.graph] (unmodified code from PR)
template <typename Graph>
auto get_vertex_vector(const Graph& g) {
using vertex_descriptor = typename graph_traits<Graph>::vertex_descriptor;
using vertex_iterator = typename graph_traits<Graph>::vertex_iterator;
std::vector<vertex_descriptor> vertices_vec;
vertices_vec.reserve(num_vertices(g));
vertex_iterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
vertices_vec.push_back(*vi);
}
return vertices_vec;
}
// [Boost.graph] (same code refactored with ranges)
template <typename Graph>
auto get_vertex_vector(const Graph& g) {
const auto [begin, end] = vertices(g);
return std::vector(std::from_range, std::ranges::subrange(begin, end));
}
// [Custom] (same code with a custom graph structure)
template <concepts::graph Graph>
auto get_vertex_vector(const Graph& graph) { return std::vector(std::from_range, graph.verts()); }Going straight to C++20 / C++23 is, of course, unlikely in practice due to Boost's compatibility requirements, but a lot of the ideas can be adopted even without explicit std support (e.g. snippet above could be just as easily written in terms of external It seems like a lot of things could also be improved by introducing helper templates for things that are done frequently e.g.: // Current
using vertex_descriptor = typename graph_traits<Graph>::vertex_descriptor;
// With a helper template
using vertex_descriptor = boost::vertex_descriptor_t<Graph>;
Great work! WIP looks good and easy to navigate, with syntax highlighting and a search bar should end up rather nice. I've had a really great experience setting up documentation with Markdown-based MkDocs (e.g. DmitriBogdanov/UTL), quite powerful for how trivial it is to work with, might be worth looking into. Some Boost libs are also migrating to Mr.Docs (e.g. Boost.URL), no experience working with it, but the results seem rather nice.
|
Beta Was this translation helpful? Give feedback.
-
|
heya! won't be able to make it to the workshop but here's some feedback! https://ossia.io has relied extensively on boost.graph for its dataflow pipeline for audio / video / media arts. It's been used in shows and art installations around the world since 2015 :)
In general, what would be absolutely incredible would be to have complete control over memory allocations and container implementations throughout the library. Maybe with an explicit allocator, maybe with std::pmr (although it can murder performance on frequent resizes), maybe with explicit container selection as template arguments through for instance a per-algorithm configuration struct... Having more low-level control over the containers and allocators would really allow the library to go places where no one can go today. Likewise there's lots of places using, say, std::map and such where today incredibly faster containers exist. Just swapping one for the other can yield double-digit performance improvements in some use cases.
Most common algorithms I reach for are very classic.
But there's been lot of state-of-the-art improvement to things such as transitive closure since the library was released. My use cases are generally pretty small graphs, on the order of hundreds, at most a few thousand of nodes ; at this scale, algorithmic complexity can be as influent as implementation quality when the best performance is needed, since I have always very small time budgets due to the nature of the software which allows live manipulation of graphs by the user : operations must be instant, with strict deadlines on the order of milliseconds (max 16 ms for something such as "indicating to the user that he cannot create this connection because this would create a cycle, max 2 ms for computing a transitive closure for instance). this has some good discussion on the tradeoffs: https://drops.dagstuhl.de/storage/00lipics/lipics-vol160-sea2020/LIPIcs.SEA.2020.14/LIPIcs.SEA.2020.14.pdf |
Beta Was this translation helpful? Give feedback.
-
|
Again I am so impressed and grateful for the care you all put in describing precisely your needs and painpoints. There are now so many gold mines to dig in this discussion @jcelerier 🙏🏽 🫶 What is fantastic to me is that your space problem seems opposite to others like @DmitriBogdanov and @addy90 . Where they need large graphs and at scale allocators, you need small graph but very hard runtime walls, with no malloc allowed in the audio thread. If I understood correctly (correct me if not), hidden allocations by the BGL are not a scalability issue for you but a correctness issue, that will lead to glitches or missed frames. If I can summarize, you would want to see:
I ranked them by feasibility. Fixing implementation details, adding algorithms, extending some feature coverage are all in the "doable but takes time" category. Rewriting existing algorithms or bumping C++ versions are much more risky. Ergonomics improvements like structured bindings only require C++17, which may be a reasonable minimum target although that's a conversation to have with @jeremy-murphy . My hope is that we could add a tiny modern layer (for example with the config struct you need for allocation) in a separate namespace and dispatch to existing algorithms and interfaces. Maybe ? This sounds tricky though. Here are a few questions for you @jcelerier if you dont mind:
|
Beta Was this translation helpful? Give feedback.
-
|
heya!
aha, to be honest I know my needs are specific, but definitely the n°1 thing is having access to memory allocations / containers used. Everything else can be worked around or is a matter of ergonomics, but this is a core thing that cannot be worked around without rewriting.
yes, i'll try do a complete overview with boost 1.90
absolutely, thanks for your interest! I can be flexible time-wise |
Beta Was this translation helpful? Give feedback.
-
|
Amazing thank you ! |
Beta Was this translation helpful? Give feedback.
-
|
Arno, thank you for making us aware of this. We feel your work on Boost.Graph and this event are the perfect Act 3 to our Boost Documentary Film we have been shooting since last summer and will be premiering in September (location TBA)! Hopefully the folks attending are not camera shy, as we plan to document / film your important event from top to bottom using our pro level camera and cinematographers. How exciting! |
Beta Was this translation helpful? Give feedback.
-
|
Oh, a sample of a prior film I produced, about Johnny Cash, on Netflix: https://www.netflix.com/title/80191051 |
Beta Was this translation helpful? Give feedback.
-
|
Ahaha you are amazing as always guys ! Thanks again for accepting to cover our workshop 😄 I still have fond memory of my (shy) interview moments back at CPPCon25 😆 |
Beta Was this translation helpful? Give feedback.
-
|
This is incredible news, I'm so excited! |
Beta Was this translation helpful? Give feedback.
-
|
Hi everyone, I am the (principal/most active) maintainer of the BGL. I am so grateful to Arnaud for his interest and passion in the BGL, without which this workshop would not happen. I took over the reins a couple of years ago because I believe in the Boost community and value of the BGL. Some of the more ambitious ideas for the library are mine, so please don't hesitate to contact me about them. I first used the BGL roughly ten years ago in a tool that designed and optimized fibre optic networks, and I guess I fell in love immediately. 😆 I want to revitalize the BGL both technically and culturally, so please join us! |
Beta Was this translation helpful? Give feedback.
-
|
I am really looking forward to your talk about the maintainer experience ! |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Boost.Graph Modernization Workshop – May 6th, 2026
Hi everyone,
I am organizing a small workshop in Paris, France on May 6th, 2026 focused on the future of Boost.Graph, and I wanted to open a discussion here so the broader community can follow along, contribute ideas, and join if interested.
Context
I have been working with the C++ Alliance on modernizing Boost.Graph: improving documentation, expanding algorithm coverage, and making the library more accessible to researchers and industrial users working with large-scale graphs. One concrete area of current work is community detection (Louvain, Leiden, SBM), but a broader question I share with @jeremy-murphy is what Boost.Graph should look like in 2026 and beyond.
What the workshop is about
The goal is to bring together a small group (~10-15 people) of researchers, open-source implementers, and industrial users for a focused day of honest conversation. Three questions will anchor the discussions:
The format is a mix of short lightning talks in the morning and structured discussions in the afternoon, ending with a concrete prioritized roadmap.
Agenda (draft)
Morning
Afternoon
Logistics
Who should attend
This workshop is aimed at anyone working at the intersection of graph algorithms and software:
How to get involved
If you are interested in attending, or if you have thoughts on what Boost.Graph should prioritize, please reply to this thread. You can also reach me directly at [email protected] .
Even if you cannot attend on May 6th, this thread is a good place to share your use cases, algorithm wishlist, or feedback on the current state of BGL. All input will feed into the roadmap.
Looking forward to the conversation!
Arnaud Becheler, PhD
C++ Alliance / Boost.Graph
Beta Was this translation helpful? Give feedback.
All reactions