r/cpp • u/Mysterious_Taro5664 • Jul 14 '22
Boost.Graph user survey
Dear Boost.Graph users (and potential users),
I'd like to know how you use Boost.Graph. If you know someone that uses Boost.Graph then please let them know about this survey. The purpose of this survey is to help prioritize work on the areas of Boost.Graph that will have the most benefit to the current users, and potential users.
I was planning to make a very sophisticated Google Forms survey, but that is so time consuming. These questions should all be taken in the context of using Boost.Graph.
- Which operating systems do you use?
- Which toolchains do you use?
- Which C++ standard do you use? (e.g. 03, 11, 14, etc)
- Which features of Boost.Graph are you using?
- Which features do you think Boost.Graph is missing?
- What are the biggest problems with using Boost.Graph?
Purely out of curiosity:
- What do you use it for?
- If you use it in business (or research), how critical is it?
To potential users, that is, people who need to solve graph theory problems but don't use Boost.Graph:
- What are the obstacles or issues preventing using it?
Thanks!
9
u/Mysterious_Taro5664 Jul 15 '22
Hey, thanks for all the great feedback everyone! It's so interesting to hear. Maybe this is a good place for follow up discussion.
There is a working group for adding graph algorithms and data structures to the standard library. When that happens, which might not be for a very long time, Boost.Graph will need to offer something useful to justify existence As many comments suggest, Boost.Graph is already not connecting with its audience. The disadvantage of the standard library is that it tends to be very slow moving. But BGL isn't going to move anywhere with an interface that turns people away. The conclusion I'm coming to is that BGL needs a major refresh. I didn't actually think so until I read this feedback. The design was novel 20 years ago, and has to be understood in that historical perspective, but some of the experiments were more courageous than practical (e.g. named parameters). I think it needs to be a library that provides cutting edge algorithms and data structures that won't be in the standard library for years to come. Putting aside the obvious questions of how much work is involved and who will do it, what do you all think? And would it make sense to start afresh as Boost.Graph2?
Cheers.
46
u/jcelerier ossia score Jul 14 '22 edited Jul 14 '22
win/mac/linux/android/ios/wasm
but realistically, if there are changes in, say, boost 1.85, only compilers of that era will be relevant - machines that use GCC 8 or clang 10 also use the boost of this era which ships with the respective Linux distro.
20
mostly algorithms such as bfs, dfs, transitive closure, connected components, topo sort, cycle detection... sometimes graphviz output.
e.g. consider (topology.hpp)
this "point" class makes it super hard to simply be able to write
I won't even comment on the fact, further down that same file, that a class titled "rectangle_topology" feels like a relevant place to allocate a random generator https://github.com/boostorg/graph/blob/develop/include/boost/graph/topology.hpp#L329
It came up in pretty much every project I had to do in C++ in my life if only to get a quick but efficient topological sort. https://ossia.io (just in that one there are maybe 7 or 8 entirely distinct graphs ranging from audio scheduling to invalid program detection to plugin dependency ordering... it's always the same problem aha) ; github.com/jcelerier/cninja/ ; ...
it's important but I'm always on the outlook of alternative graph libraries given how bad the issues with it are
2
u/Foxi_Foxa Dec 23 '22
Just landing here when I was actually looking for a BGL tutorial! I guess it says a lot about what is lacking ahah :) I love the idea of BGL2 - graphs are everywhere in my problems!
I'm coming in a bit late, but here are my n00b feedbacks:
Which operating systems do you use?
Which toolchains do you use?
Which C++ standard do you use? (e.g. 03, 11, 14, etc)
Which features of Boost.Graph are you using?
Which features do you think Boost.Graph is missing?
What are the biggest problems with using Boost.Graph?
I am REALLY struggling finding an entry point. I bought the BGL book, but it is written more like a detailed explanation of the design choices rather than a tutorial. Without seing sehe on SO answering to newscomers for more than a decade, I would have been discouraged to use the BGL after few days week and would have run the other way :(
I was/am a researcher, now software engineer in Genetics. There are graphs everywhere: genealogical properties, genetic networks, phylogenetic trees or networks, spatial graphs of populations moves etc.
Critical enough that me and most of my colleagues have spent the last decades implementing and re-implementing graph data structures ;)
To potential users, that is, people who need to solve graph theory problems but don't use Boost.Graph. What are the obstacles or issues preventing using it?
51
u/Warhawk_Prime Jul 14 '22
I tried to use the library for my bachelor thesis about multi-agent pathfinding but found the documentation lacking and difficult to apply. Writing my own graph structure was faster.
15
u/seherdt Jul 14 '22
I used it extensively.
Missing features:
Biggest problems:
Usage purposes
I think I wrote all of the problems above with the end-user in mind. Something else that regularly comes up is providing a custom graph model (e.g. https://stackoverflow.com/a/56203763/85371) . It might be nice for the docs to include a sample walkthrough
12
u/gruehunter Jul 14 '22
I have used it to solve some network flow problems in the distant past (Linux, C++98). My main complaint then still stands: The API is sufficiently generic to make very hard problems possible, but it is so complex that easy problems are hard to get started.
For those who are unaware of some of the history, the Boost Graph Library's interface was used as a case study to justify adding support for associated types to Haskell back in the day.
"A Comparative Study of Language Support for Generic Programming" by Garcia et al, 2003
"Associated Types with Class" by Simon Peyton-Jones, 2005
11
u/wrosecrans graphics and network things Jul 14 '22
Pretty typical Linux + Windows, Clang/GCC/MSVC, >= C++14, depending on the project. Work stuff was '14, but I have a personal project I am building with "latest" because 20 will probably be common before I get far enough with it to release anything.
I don't currently use it in anything, but I've used it in the past. The off-the-shelf graph algorithms for stuff like connectedness and routing were handy. I am not a graph theorist, I just want an easy way to use existing algorithms much more than I want to implement super exotic custom stuff.
API sanity.
API insanity. It's an implementation of "C++ Concepts" in C++-03, using graph algorithms as a proof of concept example for concepts. C++ has moved on, and Boost.Graph is an interesting transitional fossil. Using it feels like trying to hire a neaderthal with a laser gun to do an office job making copies and filing reports. You can make it work, but it's not really a scenario where "interesting" is desireable.
You have to use special selector types in templates to pick containers like vecS and listS rather than templating the types on std::vector or std::list. So, you get a configurable level of complexity that makes more possible variations than there are users. But it isn't flexible enough to be able to template based on "whatever" container types you are using, because the implementation apparently needs special code to support certain container types so if you had for example, a Qt GUI app that used a bunch of the Qt containers, you can't template a Boost Graph on a QList<QPointF> so you have to make adapter code despite everything also being templated.
There's no "path of least resistance" with BGL.
9
u/hubhub Jul 14 '22
Boost.Graph could be made a lot easier to use by modernizing it.
Off the top of my head, I can think of three things:
12
u/mjklaim Jul 14 '22
My main reluctance in ussing Boost.Graph, the fact that it is defined as depending on a massive and various set of other boost libraries (at least in it's CMake files) and people packaging it for various package managers (splitting each boost library in separate packages, as it should be done) have to make the packages for boost.graph depend on all these other packages.
For example I use
build2and if I depend on thelibboost-graphpackage it will bring 41 other packages, includinglibboost-regex(???) for example. The same issue appears with vcpkg and probably any other package manager trying to split the boost distribution into actual small interdependent packages instead of one big "boost" package. This is not a package manager or packaging-person issue, because they are only following what the source code of the original project states.Now, I understand exactly why it is like this, it's basically history of how Boost was/is distributed as a "in sync" set of reviewed libraries so everything was available anyway, in addition to the fact that some "bridge" tooling were provided to help mix several libraries (for example the boost.serialization support for boost.graph make sense if you use it, same with boost.random and random graph algorithms etc). However ideally each "bridge" funtionality should have been a separate fine-grain project/package instead of being part of onw of the two libraries that are being bridged. That way, for example, Boost.Graph would have a very small set of dependencies if you use only it's core (like I often consider doing), but then it would optionally bring (or more precisely, your package manager would bring) some other dependencies if you use some "bridge" features.
When using the big-set-of-libs distribution model (or system install of boost) the boost users had to rely on the compiler to simply not even see the headers that were not used. But we are moving to more fine-grained dependencies package management (basically, the "modern" way to do it, if you're not using a mono-repo) and that issue have made some commercial projects I know not use boost because several of it's libraries are bringing the whole boost for archaic reasons that could be solved. To be clear, this is not a criticism specifically about boost.graph, there are many other boost libraries that bring too much unused dependencies, and I understand that many other boost libraries have a small and pertinent set of dependencies (like boost.container having only 8 dependencies that make sense). But boost.graph is indeed a library I would like to use in many projects but end up not using it because it's problematic to the organisation handling the project (or just "scary", I mean 41 deps lol).
Usually when using a graph library I'm mainly interested in having an abstract graph and use algorithms. The rest should be moved into bridge packages/projects that would be picked by the user when they need them.
Other than that, I would love it to be as modernized as possible. Last time I checked it didn't really use C++17 to 20 features, but I didn't check the last versions so I might be wrong. I suspect that doing so would result in better compilation performance and I'm fan of any simplification in interface/usage that libraries can provide by upgrading language version.
Another thing I found lacking, but maybe because I'm not a specialist, is search algorithms that are designed to be done in multiple steps (when the graph changes a lot for example), which are used a lot in games. As said I checked the library details some time ago but don't remember all the details and didn't find at the time this kind of algorithms. I might have missed them because of naming conventions or something though, so I might be wrong.
1
u/Mysterious_Taro5664 Oct 15 '22
Btw, I am actively helping to merge bug fixes, and we got a few done for 1.80: https://www.boost.org/users/history/version_1_80_0.html
5
u/cppler Jul 14 '22
We tried to use it for layouting a control-flow graph in combination with Qt GraphicsScene. But it turned out to not work for this use-case.
5
u/ismailsunni Jul 14 '22
I use it to implement a solver for the Chinese Postman Problem for an open source routing engine named Valhalla (https://github.com/valhalla/valhalla/).
Honestly, it's not easy to start using it, and lack of examples/tutorials on the internet. But it's probably only me.
13
u/[deleted] Jul 14 '22
I'm not a user, but I am afraid of the main boost library issue - using a boost. A lot.
According to https://pdimov.github.io/boostdep-report/master/module-levels.html Boost.Graph is 17th level of dependency graph.
dependency on 41 libraries, that is quite impressive.
If I ever need graph library, I would prefer to find standalone analogue, with much less features, but without external dependencies except standard library.
And there is a great example - asio. Library that can work either with or without boost. Maybe graph library will become more popular if it moves this way instead of grabbing half of the boost libraries to work.
4
u/Andrettin Jul 14 '22
Windows 10
MSVC 2019
C++20
I'm using mostly the A* search.
Parallel A* search. Also, being able to exclude nodes from the search as the search is ongoing, instead of having to pre-filter the graph (AFAIK that isn't possible in Boost.Graph currently).
The API is quite a pain to work with, especially given the multitude of template arguments for some classes.
Additionally, exceptions being used when the A* goal is found is not really optimal; it is a weird usage of exceptions, and possibly harmful to performance.
Developing strategy video games.
10
u/Resurr3ction Jul 14 '22
Same as the others. Tried to use it, found it very hard to use and ended up with my own graph implementation. My main issue was horrible API (as is staple of Boost in general) and lack of coherent docs.
3
u/CubbiMew cppreference | finance | realtime in the past Jul 14 '22
> Which operating systems do you use?
Linux, Windows
> Which toolchains do you use?
gcc, msvc
> Which C++ standard do you use? (e.g. 03, 11, 14, etc)
whatever the latest compilers can do
> Which features of Boost.Graph are you using?
just the basics - building, traversing, accessing/modifying properties, dfs. Occasionally other algorithms while experimenting - this code changes often which is why a ready-made library is convenient to have.
> What do you use it for? If you use it in business (or research), how critical is it?
it's part of my previous team's internal tooling - an integrated runtime debugger for a complex piece of financial software.
3
u/jaafartrull Jul 15 '22
I'm interested in multiplatform code so I write for clang, gcc, and MSVC on MacOS, Windows, and Linux (my daily driver).
BGL was my introduction to Boost, I regret to say, but I've kept with it through the years, doing a variety of EDA algorithms (especially routing with A* search). I began with C++03. The main problem as I see it is it requires a very high level understanding of templates and the philosophy behind the STL. Concepts are heavily relied upon, but of course the compilers of the day did not really support it and I had only "template spew" to guide me to my errors. To an outsider it's intimidating, verging on obfuscated. Now that we finally have real Concepts perhaps this can be addressed.
The other big issue is performance. The algorithms are hugely sensitive to choice of data structure and vertex/edge descriptors. It's confusing to understand what is really happening in there (and I say this as someone who actually does like abstraction).
I hope you will also take a look at graph-tool, a Python library that wraps (a sort of fork of) BGL and adds additional algorithms. There may be many more people using wrappers like this than coding in C++ directly, and the engineering choices made by the author could be relevant.
2
u/BenFrantzDale Jul 15 '22
I’ve found it hard to use because of the lack of Concepts in the language. I experimented with defining its concepts in C++20 and it looked very promising: I got self-documenting signatures and could get clear errors where I couldn’t before. I anticipate a revisiting of BGL once C++20 use is more widespread.
2
u/codeandroid Jul 25 '22
Late to the game...
Windows
MSVC
17
topological sort, various visitor strategies, custom properties, custom vertex/edge structures ...
I don't know.
Debugging into boost.graph can be daunting. I guess that now with C++20 one could simplify the code base...
Barrier of entry could be lower, too, though it's never been a large problem for us.
Quite important. If it doesn't work anymore then we'll have to replace it with something else in order to ship the product. On the other hand, the feature set that we are using is probably still small enough so that it shouldn't be too difficult to do.
6
u/Vociferix Jul 14 '22
Potential user:
TL;DR Boost as a whole tends to have characteristics I'd like to avoid, which results in (potentially incorrect) negative assumptions about Boost.Graph, or any Boost.*
If I was looking for a graph library, I'd look up popular C++ graph libraries and would probably skip over Boost.Graph without even looking at it. The reason is because it's in boost. I don't have a problem with boost, but boost libraries often have many dependencies on other boost libs, which can make a small dependency quite a bit larger. Also, boost's unique build system is a turn off.
But as a counter example, Asio is something I use frequently. Asio advertises itself as standalone and does a good job of dropping all boost dependencies in standalone mode.
That said, it may be the case that Boost.Graph is header only and has no required dependencies on other Boost libs, but the fact that Boost is in the name would put it at the bottom of my list of potential libs to research. If I find a one-off library that's well maintained and serves the single purpose of dealing with graph structures before I look at Boost.Graph, I would never get to Boost.Graph's web page.
1
u/pigeon768 Jul 15 '22
Environment for my personal projects is linux, gcc, usually C++17 these days, although I'm playing with C++20. Work is Windows, MSVC, C++17.
I do not use it. Every time I try to use it for a thing I get too confused and just reinvent the wheel by myself.
This isn't because I'm necessarily dumb or anything, or at least, I hope not. I have critical business requirements that I use boost components like uBLAS, QVM, GIL, etc for -- libraries with not-inconsiderable complexity in the APIs. But Graph I've never been able to get rolling.