4 ms·

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

by 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??
Nevermark 3y ago
Generalized pointers (RAM addresses, disk storage locations, network locations, etc.) would be the general way to implement explicit literal graphs. 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.
- thfuran 3y ago
  You could say the same of Lists.
  - Nevermark 3y ago
    Well, of course! Lists, trees, arrays, structures, etc. are specialized graphs.
eru 3y ago
You can use a pointer when building a graph data structure. You can also use numeric indices into arrays. Or you can store your graph in an entirely different way. 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.

by 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??

Nevermark 3y ago

Generalized pointers (RAM addresses, disk storage locations, network locations, etc.) would be the general way to implement explicit literal graphs. 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.

thfuran 3y ago
You could say the same of Lists.
- Nevermark 3y ago
  Well, of course! Lists, trees, arrays, structures, etc. are specialized graphs.

eru 3y ago

You can use a pointer when building a graph data structure. You can also use numeric indices into arrays. Or you can store your graph in an entirely different way. 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.