graph/{multi,simple,testgraph}: add support for ID-specified node addition
MODIFY
graph/graph.go
graph/graph.go
@@ -146,6 +146,18 @@ type NodeAdder interface {
AddNode(Node)
}
+// NodeWithIDer is a graph that can return potentially new nodes with
+// a defined ID.
+type NodeWithIDer interface {
+ // NodeWithID returns a Node with the given ID if possible.
+ // A nil Node will be returned if no Node exists or
+ // can be created.
+ // If a non-nil Node is returned that is not already in the
+ // graph NodeWithID will return true for new and the Node
+ // must be added to the graph before use.
+ NodeWithID(id int64) (n Node, new bool)
+}
+
// NodeRemover is an interface for removing nodes from a graph.
type NodeRemover interface {
// RemoveNode removes the node with the given ID

MODIFY
graph/multi/directed.go
graph/multi/directed.go
@@ -187,6 +187,17 @@ func (g *DirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *DirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveLine removes the line with the given end point and line IDs from the graph, leaving
// the terminal nodes. If the line does not exist it is a no-op.
func (g *DirectedGraph) RemoveLine(fid, tid, id int64) {

MODIFY
graph/multi/undirected.go
graph/multi/undirected.go
@@ -196,6 +196,17 @@ func (g *UndirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *UndirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveLine removes the line with the given end point and line Ids from the graph, leaving
// the terminal nodes. If the line does not exist it is a no-op.
func (g *UndirectedGraph) RemoveLine(fid, tid, id int64) {

MODIFY
graph/multi/weighted_directed.go
graph/multi/weighted_directed.go
@@ -195,6 +195,17 @@ func (g *WeightedDirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *WeightedDirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveLine removes the line with the given end point and line IDs from the graph,
// leaving the terminal nodes. If the line does not exist it is a no-op.
func (g *WeightedDirectedGraph) RemoveLine(fid, tid, id int64) {

MODIFY
graph/multi/weighted_undirected.go
graph/multi/weighted_undirected.go
@@ -202,6 +202,17 @@ func (g *WeightedUndirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *WeightedUndirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveLine removes the line with the given end point and line IDs from the graph,
// leaving the terminal nodes. If the line does not exist it is a no-op.
func (g *WeightedUndirectedGraph) RemoveLine(fid, tid, id int64) {

MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -139,6 +139,17 @@ func (g *DirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *DirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
// nodes. If the edge does not exist it is a no-op.
func (g *DirectedGraph) RemoveEdge(fid, tid int64) {

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -144,6 +144,17 @@ func (g *UndirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *UndirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveEdge removes the edge with the given end IDs from the graph, leaving the terminal nodes.
// If the edge does not exist it is a no-op.
func (g *UndirectedGraph) RemoveEdge(fid, tid int64) {

MODIFY
graph/simple/weighted_directed.go
graph/simple/weighted_directed.go
@@ -143,6 +143,17 @@ func (g *WeightedDirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *WeightedDirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
// nodes. If the edge does not exist it is a no-op.
func (g *WeightedDirectedGraph) RemoveEdge(fid, tid int64) {

MODIFY
graph/simple/weighted_undirected.go
graph/simple/weighted_undirected.go
@@ -142,6 +142,17 @@ func (g *WeightedUndirectedGraph) Nodes() graph.Nodes {
return iterator.NewNodes(g.nodes)
}
+// NodeWithID returns a Node with the given ID if possible. If a graph.Node
+// is returned that is not already in the graph NodeWithID will return true
+// for new and the graph.Node must be added to the graph before use.
+func (g *WeightedUndirectedGraph) NodeWithID(id int64) (n graph.Node, new bool) {
+ n, ok := g.nodes[id]
+ if ok {
+ return n, false
+ }
+ return Node(id), true
+}
+
// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
// nodes. If the edge does not exist it is a no-op.
func (g *WeightedUndirectedGraph) RemoveEdge(fid, tid int64) {

MODIFY
graph/testgraph/testgraph.go
graph/testgraph/testgraph.go
@@ -1376,6 +1376,9 @@ type NodeAdder interface {
// AddNodes gets a new node from g and adds it to the graph, repeating this pair
// of operations n times. The existence of added nodes is confirmed in the graph.
// AddNodes also checks that re-adding each of the added nodes causes a panic.
+// If g satisfies NodeWithIDer, the NodeWithID method is tested for an additional
+// n rounds of node addition using NodeWithID to create new nodes as well as
+// confirming that NodeWithID returns existing nodes.
func AddNodes(t *testing.T, g NodeAdder, n int) {
defer func() {
r := recover()
@@ -1426,6 +1429,34 @@ func AddNodes(t *testing.T, g NodeAdder, n int) {
t.Fatalf("expected panic adding existing node: %v", it.Node())
}
}
+
+ if gwi, ok := g.(graph.NodeWithIDer); ok {
+ // Test existing nodes.
+ it := g.Nodes()
+ for it.Next() {
+ id := it.Node().ID()
+ n, new := gwi.NodeWithID(id)
+ if n == nil {
+ t.Errorf("unexpected nil node for existing node with ID=%d", id)
+ }
+ if new {
+ t.Errorf("unexpected new node for existing node with ID=%d", id)
+ }
+ }
+ // Run n rounds of ID-specified node addition.
+ for i := 0; i < n; i++ {
+ id := g.NewNode().ID() // Get a guaranteed non-existing node.
+ n, new := gwi.NodeWithID(id)
+ if n == nil {
+ // Could not create a node, valid behaviour.
+ continue
+ }
+ if !new {
+ t.Errorf("unexpected old node for non-existing node with ID=%d", id)
+ }
+ g.AddNode(n) // Use the node to advance to a new non-existing node.
+ }
+ }
}
// AddArbitraryNodes tests whether g correctly implements the AddNode method. Not all

graph/{multi,simple,testgraph}: add support for ID-specified node addition