Repository: gonum/gonum
Pull request #1584 (2021-03-15 02:18:25)

graph/{multi,simple,testgraph}: add support for ID-specified node addition
I'm not sure about the placement of the `NodeWithIDer` interface. Given that we need to have it in testgraph, I'm thinking that maybe it *should* just go in graph.

Please take a look.

Updates #1582.

/cc @mattConn 

<!--
Checklist:

- API changes have been discussed
- code is goformated correctly (goimports)
- packages with generated code have had code generation run
- tests pass locally
- linked to relevant issues

Please make sure your commit message summary line and pull request
title match the Go convention; a one-line summary of the change,
prefixed by the primary affected package that should complete the
sentence, "This change modifies Gonum to _____."
-->


codecov-io: # [Codecov](https://codecov.io/gh/gonum/gonum/pull/1584?src=pr&el=h1) Report
> Merging [#1584](https://codecov.io/gh/gonum/gonum/pull/1584?src=pr&el=desc) (380f515) into [master](https://codecov.io/gh/gonum/gonum/commit/14aa307d4904274505b229b9b9be86495136ef9d?el=desc) (14aa307) will **increase** coverage by `0.01%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/gonum/gonum/pull/1584/graphs/tree.svg?width=650&height=150&src=pr&token=B7qHnqSPNL)](https://codecov.io/gh/gonum/gonum/pull/1584?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master    #1584      +/-   ##
==========================================
+ Coverage   72.67%   72.68%   +0.01%     
==========================================
  Files         481      481              
  Lines       57936    57968      +32     
==========================================
+ Hits        42105    42136      +31     
  Misses      13430    13430              
- Partials     2401     2402       +1     
```


| [Impacted Files](https://codecov.io/gh/gonum/gonum/pull/1584?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [graph/multi/directed.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvbXVsdGkvZGlyZWN0ZWQuZ28=) | `92.30% <100.00%> (+0.24%)` | :arrow_up: |
| [graph/multi/undirected.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvbXVsdGkvdW5kaXJlY3RlZC5nbw==) | `91.30% <100.00%> (+0.25%)` | :arrow_up: |
| [graph/multi/weighted\_directed.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvbXVsdGkvd2VpZ2h0ZWRfZGlyZWN0ZWQuZ28=) | `94.96% <100.00%> (+0.12%)` | :arrow_up: |
| [graph/multi/weighted\_undirected.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvbXVsdGkvd2VpZ2h0ZWRfdW5kaXJlY3RlZC5nbw==) | `93.10% <100.00%> (+0.16%)` | :arrow_up: |
| [graph/simple/directed.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvc2ltcGxlL2RpcmVjdGVkLmdv) | `90.36% <100.00%> (+0.48%)` | :arrow_up: |
| [graph/simple/undirected.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvc2ltcGxlL3VuZGlyZWN0ZWQuZ28=) | `88.09% <100.00%> (+0.59%)` | :arrow_up: |
| [graph/simple/weighted\_directed.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvc2ltcGxlL3dlaWdodGVkX2RpcmVjdGVkLmdv) | `91.75% <100.00%> (+0.35%)` | :arrow_up: |
| [graph/simple/weighted\_undirected.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvc2ltcGxlL3dlaWdodGVkX3VuZGlyZWN0ZWQuZ28=) | `90.56% <100.00%> (+0.36%)` | :arrow_up: |
| [graph/flow/control\_flow\_lt.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-Z3JhcGgvZmxvdy9jb250cm9sX2Zsb3dfbHQuZ28=) | `87.50% <0.00%> (-8.93%)` | :arrow_down: |
| [optimize/listsearch.go](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree#diff-b3B0aW1pemUvbGlzdHNlYXJjaC5nbw==) | `72.22% <0.00%> (-1.86%)` | :arrow_down: |
| ... and [1 more](https://codecov.io/gh/gonum/gonum/pull/1584/diff?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/gonum/gonum/pull/1584?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/gonum/gonum/pull/1584?src=pr&el=footer). Last update [14aa307...380f515](https://codecov.io/gh/gonum/gonum/pull/1584?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

kortschak: What do you think about placing interface in graph? As it is, it needs to be defined in at least one more place (the use package) since referring to testgraph feels very wrong.
mewmew: > What do you think about placing interface in graph? As it is, it needs to be defined in at least one more place (the use package) since referring to testgraph feels very wrong.

I'm fine with placing the interface in the graph package.
kortschak: PTAL

Patch:
diff --git a/graph/graph.go b/graph/graph.go
index 4d570778..3302c5e4 100644
--- a/graph/graph.go
+++ b/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
diff --git a/graph/multi/directed.go b/graph/multi/directed.go
index 83e78369..46d64481 100644
--- a/graph/multi/directed.go
+++ b/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) {
diff --git a/graph/multi/undirected.go b/graph/multi/undirected.go
index 8540547a..4e41fbee 100644
--- a/graph/multi/undirected.go
+++ b/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) {
diff --git a/graph/multi/weighted_directed.go b/graph/multi/weighted_directed.go
index 2a02fda6..348b2058 100644
--- a/graph/multi/weighted_directed.go
+++ b/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) {
diff --git a/graph/multi/weighted_undirected.go b/graph/multi/weighted_undirected.go
index a2a29445..9347166e 100644
--- a/graph/multi/weighted_undirected.go
+++ b/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) {
diff --git a/graph/simple/directed.go b/graph/simple/directed.go
index e71b93b1..feb4b043 100644
--- a/graph/simple/directed.go
+++ b/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) {
diff --git a/graph/simple/undirected.go b/graph/simple/undirected.go
index 2adef6a1..16e9e37a 100644
--- a/graph/simple/undirected.go
+++ b/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) {
diff --git a/graph/simple/weighted_directed.go b/graph/simple/weighted_directed.go
index 4ba005e8..e529174e 100644
--- a/graph/simple/weighted_directed.go
+++ b/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) {
diff --git a/graph/simple/weighted_undirected.go b/graph/simple/weighted_undirected.go
index 915aabd7..4c36ea53 100644
--- a/graph/simple/weighted_undirected.go
+++ b/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) {


Test patch:
diff --git a/graph/testgraph/testgraph.go b/graph/testgraph/testgraph.go
index 3f0e80fc..b7c541c0 100644
--- a/graph/testgraph/testgraph.go
+++ b/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