The C++ Standard Template Library is now 29 years old. It doesn't have a graph (or generic B-tree) data structure. That says it all for me. In my too many years of programming, I have only needed to program a graph structure once or twice. Yes, the are "ubiquitous in software engineering", but still incredibly rare in most enterprise programming projects.
How many times you had to program recursion with detection and special-casing of cycles? How many times the tree thing you wrote was artificially constraining the domain due to not allowing multiple parents? Those are the cases where graph is the right mental model, and graph structure ought to be considered (you may still hack the solution from special-cased recursion on lists, for engineering reasons).
Also, how much does the control flow jump between objects in your code? There's nothing more core to enterprise programming (at least of C++/Java school of thought) than the object graph. Which is what it says on the tin: a runtime directed graph of objects connected by pointers/references. A lot of enterprise code is, in a way, graph algorithms, just inlined and so smeared out that people don't recognize them for what they are.
Also, how many times the domain model you were using was plain broken, because whoever designed it didn't understand that most things in life don't arrange well into hierarchy - they tend to form directed graphs.
Boost does have the BGL (which, following the STL, abstracts graph algorithms from graph implementations). But I don't think it has seen significant updates in more than two decades.
