graph: Consider how to help with dynamically created graph implementations
Created by: Zaerei
I do a lot with what I'd call "dynamic graphs". This is a graph where a state generates its successors, rather than having its entire representation preconstructed. I implemented a toy problem with our interface yesterday night just to test it for my use case.
The problem is that a lot of methods end up being incompletely implemented. Many times in these implementations it's intractable to generate Predecessors (meaning that it's also intractable to generate Neighbors). In fact, it's computationally expensive to determine if an edge even exists between two nodes in some cases. You have to compute the successors of each and check if one happens to be equivalent to one of the successors of the other. For combinatorically large numbers of successors to generate, this gets expensive quickly.
Numeric IDs are a problem too, but you can sneak around that by having a map[string]int in the graph and implementing a String() method on the node type, so every time you generate a node you check if g.idMap[n.String()] exists and if not request a new ID and store it. It's ugly, but acceptable.
Other things that are impossible to implement would be NodeList, EdgeList, and by extension Order (#18 (closed)), as well as Degree (which has been removed but worth considering in the future). In fact, these graphs may or may not be infinite.
Obviously this means that using these types of graphs with certain algorithms is impossible. I can use A*, but not FloydWarshall, for instance. That's acceptable since, well, it's a logical fact that if you can't implement certain methods you can't use them. However, it does lead to a lot of dead methods to implement.
The problem I have is fragmenting graph into increasingly small interfaces. It seems messy to have an individual interface for every conceivable method. Any ideas on how to handle this?