graph: [proposal] use node ID for retrieval operations and graph.Node for creation
Created by: mewmew
Background discussion: https://github.com/gonum/graph/issues/87#issuecomment-299039592
The intention of this proposal is to refine the graph API to mitigate subtle issues related to node retrieval from edges (original issue reported in gonum/graph#87), and to clearly communicate intent through the API; specifically that retrieval operations should only require access to a node ID, while creation operations require the entire data structure implementing the graph.Node
interface.
Since this is an extensive update of the API, we should take the opportunity to simultaneously update the return type of NodeID
from int
to int64
, to allow for future uses in huge graphs.
A rough sketch of the intended API changes is presented below. Please feel free to discuss and further improve upon it.
// Node is a graph node.
type Node interface {
// ID returns a graph-unique integer ID of the graph node.
- ID() int
+ ID() int64
}
// Graph is a generalized graph.
type Graph interface {
// Has reports whether the given node ID exists within the graph.
- Has(Node) bool
+ Has(id int64) bool
// Nodes returns all the nodes in the graph.
Nodes() []Node
// From returns all nodes that can be reached directly
// from the given node ID.
- From(Node) []Node
+ From(id int64) []Node
// HasEdgeBeteen reports whether an edge exists between the
// node IDs xid and yid without considering direction.
- HasEdgeBetween(x, y Node) bool
+ HasEdgeBetween(xid, yid int64) bool
// Edge returns the edge from the node ID uid to vid if such an
// edge exists and nil otherwise. The node ID vid must be directly
// reachable from node ID uid as defined by the From method.
- Edge(u, v Node) Edge
+ Edge(uid, vid int64) Edge
}
// Undirected is an undirected graph.
type Undirected interface {
Graph
// EdgeBetween returns the edge between the node IDs xid and yid.
- EdgeBetween(x, y Node) Edge
+ EdgeBetween(xid, yid int64) Edge
}
// Directed is a directed graph.
type Directed interface {
Graph
// HasEdgeFromTo reports whether an edge exists
// in the graph from node ID uid to vid.
- HasEdgeFromTo(u, v Node) bool
+ HasEdgeFromTo(uid, vid int64) bool
// To returns all nodes that can reach directly
// to the given node ID.
- To(Node) []Node
+ To(id int64) []Node
}
// NodeAdder is an interface for adding arbitrary nodes to a graph.
type NodeAdder interface {
// NewNodeID returns a new unique arbitrary node ID.
- NewNodeID() int
+ NewNodeID() int64
// Adds a node to the graph. AddNode panics if
// the added node ID matches an existing node ID.
AddNode(Node)
}
// NodeRemover is an interface for removing nodes from a graph.
type NodeRemover interface {
// RemoveNode removes a node with the given node ID from the graph,
// as well as any edges attached to it. If the node is not in the
// graph it is a no-op.
- RemoveNode(Node)
+ RemoveNode(id int64)
}
Any and all feedback is welcome.
Edit: updated based on feedback in https://github.com/gonum/gonum/issues/31#issuecomment-304740719