5 ms·

As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times.

As someone who did a lot of work with graphs, "why don't programming languages have a built-in graph data type?" is a question I’ve been asked a million times. 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.

jjice 3y ago
I used to think that since graphs are such a broad data structure that can be represented in different ways depending on requirements that it just made more sense to implement them at a domain-ish level (the article mentions this in the "There are too many implementation choices" section). 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. [0] https://github.com/petgraph/petgraph https://github.com/petgraph/petgraph
- nickpsecurity 3y ago
  You might say graphs are an abstract concept, solving our problems requires specialized graphs, and so we just use or build the kind we need.
  - sanderjd 3y ago
    Yeah this is exactly how I think of it. I think "graphs" are just at a different level of the abstraction hierarchy than the data structures they're often grouped together with. 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.
    - eru 3y ago
      Well, the original article actually describes that relations are great way to model graphs, and suggests that your language (or its standard library) should ship with a good datastructure for relations. You would get most of a what you need for a simple relation database this way.
- TachyonicBytes 3y ago
  Why wouldn't an abstract `Graph` type and specific implementations of that work? Like Java has for `Set` and various implementations?
  - gryn 3y ago
    even at that level of abstraction there are many flavors of "graphs". what some people call graph are actually hypergraphs, or attributed graphs.
  - skybrian 3y ago
    For importing and exporting data, it often makes more sense to use something like a table or a tree rather than a graph. (Like a CSV file or a JSON file.) 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.
    - nyrikki 3y ago
      To add to this, recursively enumerable is the same as semi-decidable, and that only gets you to finite time. 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.
      - deleted 3y ago
        [deleted]
      - eru 3y ago
        Btw, solving practical instance of NP problems is often not all that bad in practice. Even solving them to optimality. 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 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.
somat 3y ago
This is a super naive take. but I would consider the pointer the be the native graph type. What is wanted is not a graph type but the tooling to traverse graphs.
- alanbernstein 3y ago
  Maybe a pointer is better described as equivalent to a half-edge?
  - andyferris 3y ago
    I think this might be kinda right. 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.
- nine_k 3y ago
  It's a bit like saying that a byte is a native number type, providing comparison to zero and addition as the only operations, and asking to figure the rest yourself. I mean, it's technically sufficient, but I'd not call it proper support on a language level.
- cwillu 3y ago
  Period should probably be a comma; I read this comment a couple times before it made sense, rather than calling the grand parent super naive.
- boothby 3y ago
  I actually brought this hot take up in my conversation with Hillel -- something along the lines of "void * * is the canonical native graph representation in C."
- computerdork 3y ago
  Hmm, think you're taking the title of the article a little too literally, and focusing on just the "data type" aspect. Yeah, the article itself indirectly agrees with you that pointers are often how graphs are implemented: "Graphs are a generalization of linked lists, binary trees, and hash tables," which are data-structures often implemented by pointers. 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??
paulddraper 3y ago
> "it's really hard to do it well" 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.
- sltkr 3y ago
  > 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/max_load_factor https://en.cppreference.com/w/cpp/container/unordered_map/ma...
  - paulddraper 3y ago
    til thanks. (And Java doesn't let you change after construction.)
- adastra22 3y ago
  > You can't really do that with a graph. Maybe if you offered a bunch of graph types. 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?
  - masklinn 3y ago
    > 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.
- karmakaze 3y ago
  It's also different in that each hash bucket can use a Red-Black tree when there's many entries.
sayrer 3y ago
I think it's because you have to think it through when they get too big for one machine. A lot of those so-called "NoSQL" databases are really meant to represent graph databases (think DynamoDB) in an adjacency list. I've had success with Gremlin and JanusGraph, but it's a really messy space. It's not a programming language problem in my opinion, but a distributed systems one.
dataflow 3y ago
> "why don't programming languages have a built-in graph data type?" 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.
- maxiepoo 3y ago
  Typed functional languages like Haskell (data)/ML (type) do have a built-in way to define new tree types, and so does Rust (enum). It's one of the biggest things I miss when I'm not using these languages, especially when combined with some metaprogramming (deriving/derive) to get some functions defined for these new types very quickly.
  - dataflow 3y ago
    I think we might be speaking past each other? How is enum in Rust a tree type? You might be able to use it to create a tree type, but that's no different from using struct to make struct Tree : std::vector<Tree> {}; in C++. That wouldn't mean C++ has a tree type, it just means it's not hard to create your own. Whereas std::list is actually a linked list type that's already there.
    - eru 3y ago
      Well, std::list is something you can create with C++ code (and likely is in most implementations of C++?), it doesn't need any special support. So I can see why someone might not treat std::list as any more special than a tree datastructure supplied by a different library? However, algebraic data types really make your life easier, and more languages should have them.
bloaf 3y ago
I had an opposite experience. I was doing some new-to-me graph work in tcl and had just assumed the tcl standard library wouldn't have any graph algorithms. Come to find out I was wrong, and ended up saving myself a bunch of time not having to re-invent the wheel: https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tcllib/files/modules/struct/graphops.md https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
atoav 3y ago
Puthon has one, as mentioned, but as a non CS-person I never encountered any problem in my programming-life that so fundamentally called for graphs that I needed one, not did I had so much fascination for graphs that it was a tool I wanted to force onto my problems. 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.
- eru 3y ago
  Two people can look at the same solution to the same problem, and interpret and analyse it differently. Some of those interpretations can involve graphs, but that's not necessarily intrinsic to the problem nor solution.
- kolinko 3y ago
  What kinds of projects did you build? I'd risk saying that it's more likely you just didn't spot where graphs could be useful, or you implemented a graph not recognising it as such. 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.

jjice 3y ago

I used to think that since graphs are such a broad data structure that can be represented in different ways depending on requirements that it just made more sense to implement them at a domain-ish level (the article mentions this in the "There are too many implementation choices" section). 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. [0] https://github.com/petgraph/petgraph https://github.com/petgraph/petgraph

nickpsecurity 3y ago
You might say graphs are an abstract concept, solving our problems requires specialized graphs, and so we just use or build the kind we need.
- sanderjd 3y ago
  Yeah this is exactly how I think of it. I think "graphs" are just at a different level of the abstraction hierarchy than the data structures they're often grouped together with. 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.
  - eru 3y ago
    Well, the original article actually describes that relations are great way to model graphs, and suggests that your language (or its standard library) should ship with a good datastructure for relations. You would get most of a what you need for a simple relation database this way.
TachyonicBytes 3y ago
Why wouldn't an abstract `Graph` type and specific implementations of that work? Like Java has for `Set` and various implementations?
- gryn 3y ago
  even at that level of abstraction there are many flavors of "graphs". what some people call graph are actually hypergraphs, or attributed graphs.
- skybrian 3y ago
  For importing and exporting data, it often makes more sense to use something like a table or a tree rather than a graph. (Like a CSV file or a JSON file.) 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.
  - nyrikki 3y ago
    To add to this, recursively enumerable is the same as semi-decidable, and that only gets you to finite time. 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.
    - deleted 3y ago
      [deleted]
    - eru 3y ago
      Btw, solving practical instance of NP problems is often not all that bad in practice. Even solving them to optimality. 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 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.

somat 3y ago

This is a super naive take. but I would consider the pointer the be the native graph type. What is wanted is not a graph type but the tooling to traverse graphs.

alanbernstein 3y ago
Maybe a pointer is better described as equivalent to a half-edge?
- andyferris 3y ago
  I think this might be kinda right. 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.
nine_k 3y ago
It's a bit like saying that a byte is a native number type, providing comparison to zero and addition as the only operations, and asking to figure the rest yourself. I mean, it's technically sufficient, but I'd not call it proper support on a language level.
cwillu 3y ago
Period should probably be a comma; I read this comment a couple times before it made sense, rather than calling the grand parent super naive.
boothby 3y ago
I actually brought this hot take up in my conversation with Hillel -- something along the lines of "void * * is the canonical native graph representation in C."
computerdork 3y ago
Hmm, think you're taking the title of the article a little too literally, and focusing on just the "data type" aspect. Yeah, the article itself indirectly agrees with you that pointers are often how graphs are implemented: "Graphs are a generalization of linked lists, binary trees, and hash tables," which are data-structures often implemented by pointers. 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??

paulddraper 3y ago

> "it's really hard to do it well" 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.

sltkr 3y ago
> 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/max_load_factor https://en.cppreference.com/w/cpp/container/unordered_map/ma...
- paulddraper 3y ago
  til thanks. (And Java doesn't let you change after construction.)
adastra22 3y ago
> You can't really do that with a graph. Maybe if you offered a bunch of graph types. 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?
- masklinn 3y ago
  > 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.
karmakaze 3y ago
It's also different in that each hash bucket can use a Red-Black tree when there's many entries.

sayrer 3y ago

I think it's because you have to think it through when they get too big for one machine. A lot of those so-called "NoSQL" databases are really meant to represent graph databases (think DynamoDB) in an adjacency list. I've had success with Gremlin and JanusGraph, but it's a really messy space. It's not a programming language problem in my opinion, but a distributed systems one.

dataflow 3y ago

> "why don't programming languages have a built-in graph data type?" 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.

maxiepoo 3y ago
Typed functional languages like Haskell (data)/ML (type) do have a built-in way to define new tree types, and so does Rust (enum). It's one of the biggest things I miss when I'm not using these languages, especially when combined with some metaprogramming (deriving/derive) to get some functions defined for these new types very quickly.
- dataflow 3y ago
  I think we might be speaking past each other? How is enum in Rust a tree type? You might be able to use it to create a tree type, but that's no different from using struct to make struct Tree : std::vector<Tree> {}; in C++. That wouldn't mean C++ has a tree type, it just means it's not hard to create your own. Whereas std::list is actually a linked list type that's already there.
  - eru 3y ago
    Well, std::list is something you can create with C++ code (and likely is in most implementations of C++?), it doesn't need any special support. So I can see why someone might not treat std::list as any more special than a tree datastructure supplied by a different library? However, algebraic data types really make your life easier, and more languages should have them.

bloaf 3y ago

I had an opposite experience. I was doing some new-to-me graph work in tcl and had just assumed the tcl standard library wouldn't have any graph algorithms. Come to find out I was wrong, and ended up saving myself a bunch of time not having to re-invent the wheel: https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tcllib/files/modules/struct/graphops.md https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...

atoav 3y ago

Puthon has one, as mentioned, but as a non CS-person I never encountered any problem in my programming-life that so fundamentally called for graphs that I needed one, not did I had so much fascination for graphs that it was a tool I wanted to force onto my problems. 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.

eru 3y ago
Two people can look at the same solution to the same problem, and interpret and analyse it differently. Some of those interpretations can involve graphs, but that's not necessarily intrinsic to the problem nor solution.
kolinko 3y ago
What kinds of projects did you build? I'd risk saying that it's more likely you just didn't spot where graphs could be useful, or you implemented a graph not recognising it as such. 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.