The Hunt for the Missing Data Type (discussion on Hacker News) is an article exploring why are graph implementations so rare while graph problems are so common:
I see graphs everywhere and use them to analyze all sorts of systems. At the same time, I dread actually using graphs in my code. There is almost no graph support in any mainstream language. None have it as a built-in type, very few have them in the standard library, and many don’t have a robust third-party library in the ecosystem. Most of the time, I have to roll graphs from scratch. There’s a gap between how often software engineers could use graphs and how little our programming ecosystems support them. Where are all the graph types?
They have interviewed multiple experts, and they all gave the same answer: graphs are just hard.
- There are many different kinds of graphs
- There are many different representations of each kind of graph
- There are many different graph algorithms
- Graph algorithm performance is very sensitive to graph representation and implementation details
- People run very expensive algorithms on very big graphs.
This explains why languages don’t support graphs in their standard libraries: too many design decisions, too many tradeoffs, and too much maintenance burden. It explains why programmers might avoid third party graph libraries, because they’re either too limited or too slow. And it explains why programmers might not want to think about things in terms of graphs except in extreme circumstances: it’s just too hard to work with them.
For what it’s worth, this matches my experience: graphs are really nice and elegant in theory, but in practice they are too hard and too messy. As one commenter on HN put it:
Ya, the central obstacle is that:
for simple and small graph problems, a simple vector-of-vectors adjacency list is easy enough to code up.
For complex and huge graph problems, the only way to get performant solutions is to tailor the graph implementation to the specific details of the problem to be solved.