Boost.Graph Workshop Paris | May 6th, 2026 #466
Replies: 9 comments 19 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 arnaud.becheler@gmail.com ? 😄 |
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.
-
|
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.
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 arnaud.becheler@gmail.com .
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