graph: Atomize interfaces
Closed this issue · 2 comments
At the moment, we've been operating under the conceit that directed/undirected graphs are special cases of one another. We started with the idea that an undirected graph was essentially a directed graph that was symmetric. Later, we inverted this due to necessity (for reasons I don't quite recall), and decided that a directed graph was more or less an undirected graph with edges with an ordered head and tail.
This caused its own problems, for instance, a graph cannot safely implement both directed and undirected mutability, which is a bit silly given that directed graph is a sub-interface of graph.
In addition, Graph dictates that all graphs can provide a slice of all nodes and edges, but this isn't always a fair assumption.
I propose splitting interfaces far more atomically, and having functions only use interfaces specifying which methods they need. For instance, search only requires knowing outgoing edges given a node; a 1 method interface (pro: implemented correctly this means A* can now effortlessly handle multigraphs). Kruskal's requires an undirected edge list.
This will reduce or eliminate the weird smart-switching between interface methods at the beginning of most algorithms, but may increase implementation burden on users who want to build more general graphs. HOWEVER, it will also make it easier to write graphs if you only need a small part of the functionality (like A*).
Yay. This is essentially along the lines of what I was thinking.
We have ended up with part of this. I think we have stabilised.