3 ms·
Graphs are really common data structures but there hasn’t yet been an “everything’s a graph” language Nearly all common languages like Python, JS, Java, OCaml,
by chubot 4y ago
Graphs are really common data structures but there hasn’t yet been an “everything’s a graph” language
Nearly all common languages like Python, JS, Java, OCaml, etc. let you express graphs with records / objects. Everything is a graph!
If you want a homogeneous graph, you just declare a single node type, like
class Node:
edges: List[Node] # or maybe Dict[str, Node] if you want them to be named
payload: int
- Or you can have a heterogeneous graph with many different node types.
- If you want to label the edges, you can reify them as their own type
The whole heap is graph-shaped!
It's true that many programs in these languages are more tree-like than graph-like. And sometimes imperative code to manipulate graphs is hard to visualize.
But I think there doesn’t need to be a separate language of graphs for this reason.
---
If you want to see graphs done in plain C, look at this DFA code by Russ Cox:
https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
e.g. Implementation: Compiling to NFA
(copy of lobste.rs comment)
- chickenpotpie 4y agoEverything is a graph doesn't mean you can make a graph from other data structures, it means you have to make other data structures from a graph. A graph isn't defined as a list of nodes. A list is defined as a directed graph where each node has one vertex in each direction.
- chubot 4y agoBut why? What would that make easier? A list is defined as a directed graph where each node has one vertex in each direction. That definition works equally well for existing languages, e.g. struct Node { struct Node *prev, *next; int payload; }: The types gives you some constraints on the shape of the graph.