3 ms·

> or modelling the problem in some completely different way that lets you skip the problems of ownership semantics for the given domain Maybe that's an interes

> or modelling the problem in some completely different way that lets you skip the problems of ownership semantics for the given domain Maybe that's an interesting way to think about the article too. The obvious way to think about a graph using ownership is to start with a root node, then to say that nodes own other nodes through their edges. But that model won't generalise to disjoint graphs (eg, social network with separate friend groups) and it isn't always clear which node is the "root" node.

trumpeta 6y ago
Graphs are usually persisted as a list of nodes and a list of vertices. The ML approaches usually use tuples or triplets of nodes to represent connectivity and model neighborhood. I wonder if that can not be used to model a graph in a linear system?
- DougBTX 6y ago
  Yes, that makes a lot of sense. The ownership would be linear: struct Graph { nodes: Vec<Node>, edges: Vec<Edge>, } but the associations between nodes would have an arbitrary structure. The article suggests that handles are better than references anyway (I'd tend to agree in this case) so Edge would be a pair of handles. That seems totally fine, so maybe the "fatal flaw" is overstated...
chrismorgan 6y ago
Fundamentally, this most obvious way of representing a graph (each node has a list of adjacent nodes, which are references to the actual nodes) can only work in an ownership-oriented language for directed acyclic graphs. Blockchains, Git commits, directory trees not supporting links, that sort of thing. (Mind you, for practical reasons many systems will still prefer to invert the tree and probably even traverse from leaf to root; this most obvious way is not actually a good fit for computers a lot of the time, even if it’s conceptually beautiful.) But if your graph is not directed, then ownership is not clear (A → B means A owns B, but with A ↔ B you can’t have both A owning B and B owning A), and if it can be cyclic, single ownership definitely falls apart.
- chrismorgan 6y ago
  Correction: tree, not directed acyclic graph. Multiple paths to a single node is verboten for single ownership. Note that DAGs may still be useful in single-ownership languages: recursive traversal will never touch a visited node, so if you exclusively borrow the whole graph, then you can safely exclusively borrow any node you traverse (which you couldn’t do if the graph was cyclic; in Rust terms, you’d have to check it at runtime).

trumpeta 6y ago

Graphs are usually persisted as a list of nodes and a list of vertices. The ML approaches usually use tuples or triplets of nodes to represent connectivity and model neighborhood. I wonder if that can not be used to model a graph in a linear system?

DougBTX 6y ago
Yes, that makes a lot of sense. The ownership would be linear: struct Graph { nodes: Vec<Node>, edges: Vec<Edge>, } but the associations between nodes would have an arbitrary structure. The article suggests that handles are better than references anyway (I'd tend to agree in this case) so Edge would be a pair of handles. That seems totally fine, so maybe the "fatal flaw" is overstated...

chrismorgan 6y ago

Fundamentally, this most obvious way of representing a graph (each node has a list of adjacent nodes, which are references to the actual nodes) can only work in an ownership-oriented language for directed acyclic graphs. Blockchains, Git commits, directory trees not supporting links, that sort of thing. (Mind you, for practical reasons many systems will still prefer to invert the tree and probably even traverse from leaf to root; this most obvious way is not actually a good fit for computers a lot of the time, even if it’s conceptually beautiful.) But if your graph is not directed, then ownership is not clear (A → B means A owns B, but with A ↔ B you can’t have both A owning B and B owning A), and if it can be cyclic, single ownership definitely falls apart.

chrismorgan 6y ago
Correction: tree, not directed acyclic graph. Multiple paths to a single node is verboten for single ownership. Note that DAGs may still be useful in single-ownership languages: recursive traversal will never touch a visited node, so if you exclusively borrow the whole graph, then you can safely exclusively borrow any node you traverse (which you couldn’t do if the graph was cyclic; in Rust terms, you’d have to check it at runtime).