3 ms·
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
by 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 agoCorrection: 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).