I'm thrilled I'll be able to point folks to a much more in-depth analysis like the one here, instead of saying some variation of "it's really hard to do it well" and having them just take my word for it.
What I find a little funny about that question is that people miss the fact that there isn't even a tree data structure in most languages. Most languages have static arrays, dynamic arrays, linked lists, and... that's it as far as structural types go. Everything else (BSTs, hashtables, etc.) is some semantic abstraction that hides some capabilities of the underlying structure, not a purely structural representation.
However, algebraic data types really make your life easier, and more languages should have them.
Then I saw Petgraph [0] which is the first time I had really looked at a generic graph library. It's very interesting, but I still have implemented graphs at a domain level.
This is even further up the abstraction hierarchy, but to illustrate the point, nobody really wonders why languages don't ship with a built-in database implementation. And it's the same basic reason as with graphs; one size doesn't fit most.
You would get most of a what you need for a simple relation database this way.
So it's not clear what the interface would do. What methods should there be? Again, there are too many choices, and a Graph interface often isn't the best way to represent a view of some subset of a graph.
One of the big reasons to fight to make dependencies DAG like is because exhaustive search gets you to exponential time.
NP-complete, NP-hard are easy to run into with graphs.
Graph k-colorability, finding Hamiltonian cycles, max cliques, max independent sets, and vertex cover on (n)vertex graphs aren't just NP, they have no sub-exponential time algorithms.
Finding those subgraphs is often impractical.
But you need to move away from writing your own solvers. Instead you use a library that lets you describe your problem, and then throws off-the-shelf solvers at them. See eg https://developers.google.com/optimization
That's a good approach even for problems that are in P, because minor changes in the business logic requirements often only translate into minor changes in the programmatic problem description, but would translate to major changes in the a bespoke, custom algorithm to solve them, even if everything stays in P.
It also separates the description of the problem from the solution. In the real world, the business logic requirements are seldom written down explicitly somewhere, and are only available implicitly as described by the code. So without this separation, it can be hard to disentangle what's a real requirement, and what's just something your custom heuristic algorithm happens to spit out.
SETH has a sub quadratic lower bound and several other graph problems have cubic lower bounds.
Many real systems are often saved because it is actually hard to write code that aren't primitive recursive functions.
Cycles often are what destroy that, as considering WHILE and GOTO being the difference between primitive and general recursive functions helps show.
If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help.
A graph data type wouldn't have those heuristics.
Those are lower bounds on worst case instances. Not lower bounds on solving typical, practical instances.
> If you consider NP as second-order queries where the second-order quantifiers are only existantials, That will help explain why heuristics (educated guesses) help.
> A graph data type wouldn't have those heuristics.
Sounds like your heuristic for why heuristics help with many NP problems is less than helpful here.
In practice, you can encode many graph problems as eg SAT or integer programming or SMT etc and get good performance.
Even biggish instances of eg the traveling salesman problem are often solved well in practice.
I'm not sure why you bring up primitive recursive functions? Primitive recursion is able to express all of NP (and much more), so it's not much of a constraint in this discussion? (I agree that you have to try hard in practice to go beyond primitive recursion but stay finite.)
https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
More importantly, there are a lot of tradeoffs.
Virtually every language offers a hash map. You can roll your own to outperform in an individual circumstance, the default works pretty well.
You can't really do that with a graph. Maybe if you offered a bunch of graph types.
---
PS. Bit of trivia: Java's HashMap is a bit different from almost every other language in that it lets you tune the load factor.
I'm not sure that's particularly unusual. For example, C++ supports this too:
https://en.cppreference.com/w/cpp/container/unordered_map/ma...
(And Java doesn't let you change after construction.)
And so why isn't this the solution?
Most languages support both hash map (fast lookup) and balanced tree (ordered entries) primitives, even though they both implement the "associative map" container type.
Can't we have 2, 3, 5, or even 8 different graph types?
That’s what graph libraries do, look at petgraph. You’ve got a bunch of graph implementations, and a bunch of algorithms over them.
Why not? Relations model graphs really well, and you could have a relation datastructure in your language (or its standard library).
Take rust. Tree edges use Box, and DAG edges use Arc or Rc. Rust doesn’t really help with building non-DAG graphs as native data types - you can drop back to using “handles” for more generic graphs.
And I actually think that is kinda fair. Languages and standard libraries should support trees and DAGs out of the box. Perhaps Hillel is right that more complex graphs should be in a user-space library or something.
I mean, it's technically sufficient, but I'd not call it proper support on a language level.
Yeah, the article is really saying what you're saying, that building a graph library ("tooling") is very complicated.
But, maybe I'm misunderstanding what you're saying??
Other graphs, that are partly or wholly computed or recomputed as needed from other relationships, could be considered "implicit" graphs and can be implemented many other ways.
The fact that graphs can be any combinations of literally or dependently defined, static or dynamic defined, would add even more complexity to any truly general graph library.
You are right that the data representation itself is only one small part of a data structure, the operations on that representation are also really important.
I guess it is just that there are many problems that can be solved incredibly well without graphs and not that many where graphs outshine everything else so clearly that people would use them.
That being said, convince me of the opposite and I am happy.
Some of those interpretations can involve graphs, but that's not necessarily intrinsic to the problem nor solution.
Even if you work with pure webdev - the least CS-requiring field of all programming, if you work with DOM, it's a tree/graph structure, or if you work with a sitemap - it's a graph.
From my experience working with non-cs programmers, they tend to struggle with finding solutions to problems that would be solved instantly with graph structures. Or they write suboptimal code because they end up doing BFS, where they should DFS, or brute force when they could use a specific graph algorithm.