graph,graph/{encoding/dot,internal/set,topo,traverse}: remove intsets imports
MODIFY
graph/encoding/dot/decode.go
graph/encoding/dot/decode.go
@@ -7,11 +7,10 @@ package dot
import (
"fmt"
- "golang.org/x/tools/container/intsets"
-
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/formats/dot"
"gonum.org/v1/gonum/graph/formats/dot/ast"
+ "gonum.org/v1/gonum/graph/internal/set"
)
// Builder is a graph that can have user-defined nodes and edges added.
@@ -267,14 +266,14 @@ func (gen *generator) popSubgraph() []graph.Node {
// unique returns the set of unique nodes contained within ns.
func unique(ns []graph.Node) []graph.Node {
var nodes []graph.Node
- var set intsets.Sparse
+ seen := make(set.Ints)
for _, n := range ns {
id := n.ID()
- if set.Has(id) {
+ if seen.Has(id) {
// skip duplicate node
continue
}
- set.Insert(id)
+ seen.Add(id)
nodes = append(nodes, n)
}
return nodes

MODIFY
graph/encoding/dot/dot_test.go
graph/encoding/dot/dot_test.go
@@ -12,14 +12,14 @@ import (
"gonum.org/v1/gonum/graph/simple"
)
-// set is an integer set.
-type set map[int]struct{}
+// intset is an integer set.
+type intset map[int]struct{}
-func linksTo(i ...int) set {
+func linksTo(i ...int) intset {
if len(i) == 0 {
return nil
}
- s := make(set)
+ s := make(intset)
for _, v := range i {
s[v] = struct{}{}
}
@@ -29,7 +29,7 @@ func linksTo(i ...int) set {
var (
// Example graph from http://en.wikipedia.org/wiki/File:PageRanks-Example.svg 16:17, 8 July 2009
// Node identities are rewritten here to use integers from 0 to match with the DOT output.
- pageRankGraph = []set{
+ pageRankGraph = []intset{
0: nil,
1: linksTo(2),
2: linksTo(1),
@@ -44,7 +44,7 @@ var (
}
// Example graph from http://en.wikipedia.org/w/index.php?title=PageRank&oldid=659286279#Power_Method
- powerMethodGraph = []set{
+ powerMethodGraph = []intset{
0: linksTo(1, 2),
1: linksTo(3),
2: linksTo(3, 4),
@@ -53,7 +53,7 @@ var (
}
)
-func directedGraphFrom(g []set) graph.Directed {
+func directedGraphFrom(g []intset) graph.Directed {
dg := simple.NewDirectedGraph(0, math.Inf(1))
for u, e := range g {
for v := range e {
@@ -63,7 +63,7 @@ func directedGraphFrom(g []set) graph.Directed {
return dg
}
-func undirectedGraphFrom(g []set) graph.Graph {
+func undirectedGraphFrom(g []intset) graph.Graph {
dg := simple.NewUndirectedGraph(0, math.Inf(1))
for u, e := range g {
for v := range e {
@@ -83,7 +83,7 @@ type namedNode struct {
func (n namedNode) ID() int { return n.id }
func (n namedNode) DOTID() string { return n.name }
-func directedNamedIDGraphFrom(g []set) graph.Directed {
+func directedNamedIDGraphFrom(g []intset) graph.Directed {
dg := simple.NewDirectedGraph(0, math.Inf(1))
for u, e := range g {
nu := namedNode{id: u, name: alpha[u : u+1]}
@@ -95,7 +95,7 @@ func directedNamedIDGraphFrom(g []set) graph.Directed {
return dg
}
-func undirectedNamedIDGraphFrom(g []set) graph.Graph {
+func undirectedNamedIDGraphFrom(g []intset) graph.Graph {
dg := simple.NewUndirectedGraph(0, math.Inf(1))
for u, e := range g {
nu := namedNode{id: u, name: alpha[u : u+1]}
@@ -116,7 +116,7 @@ type attrNode struct {
func (n attrNode) ID() int { return n.id }
func (n attrNode) DOTAttributes() []Attribute { return n.attr }
-func directedNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Directed {
+func directedNodeAttrGraphFrom(g []intset, attr [][]Attribute) graph.Directed {
dg := simple.NewDirectedGraph(0, math.Inf(1))
for u, e := range g {
var at []Attribute
@@ -135,7 +135,7 @@ func directedNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Directed {
return dg
}
-func undirectedNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Graph {
+func undirectedNodeAttrGraphFrom(g []intset, attr [][]Attribute) graph.Graph {
dg := simple.NewUndirectedGraph(0, math.Inf(1))
for u, e := range g {
var at []Attribute
@@ -164,7 +164,7 @@ func (n namedAttrNode) ID() int { return n.id }
func (n namedAttrNode) DOTID() string { return n.name }
func (n namedAttrNode) DOTAttributes() []Attribute { return n.attr }
-func directedNamedIDNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Directed {
+func directedNamedIDNodeAttrGraphFrom(g []intset, attr [][]Attribute) graph.Directed {
dg := simple.NewDirectedGraph(0, math.Inf(1))
for u, e := range g {
var at []Attribute
@@ -183,7 +183,7 @@ func directedNamedIDNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Directe
return dg
}
-func undirectedNamedIDNodeAttrGraphFrom(g []set, attr [][]Attribute) graph.Graph {
+func undirectedNamedIDNodeAttrGraphFrom(g []intset, attr [][]Attribute) graph.Graph {
dg := simple.NewUndirectedGraph(0, math.Inf(1))
for u, e := range g {
var at []Attribute
@@ -213,7 +213,7 @@ func (e attrEdge) To() graph.Node { return e.to }
func (e attrEdge) Weight() float64 { return 0 }
func (e attrEdge) DOTAttributes() []Attribute { return e.attr }
-func directedEdgeAttrGraphFrom(g []set, attr map[edge][]Attribute) graph.Directed {
+func directedEdgeAttrGraphFrom(g []intset, attr map[edge][]Attribute) graph.Directed {
dg := simple.NewDirectedGraph(0, math.Inf(1))
for u, e := range g {
for v := range e {
@@ -223,7 +223,7 @@ func directedEdgeAttrGraphFrom(g []set, attr map[edge][]Attribute) graph.Directe
return dg
}
-func undirectedEdgeAttrGraphFrom(g []set, attr map[edge][]Attribute) graph.Graph {
+func undirectedEdgeAttrGraphFrom(g []intset, attr map[edge][]Attribute) graph.Graph {
dg := simple.NewUndirectedGraph(0, math.Inf(1))
for u, e := range g {
for v := range e {
@@ -263,7 +263,7 @@ func (e portedEdge) ToPort() (port, compass string) {
return e.toPort, e.toCompass
}
-func directedPortedAttrGraphFrom(g []set, attr [][]Attribute, ports map[edge]portedEdge) graph.Directed {
+func directedPortedAttrGraphFrom(g []intset, attr [][]Attribute, ports map[edge]portedEdge) graph.Directed {
dg := simple.NewDirectedGraph(0, math.Inf(1))
for u, e := range g {
var at []Attribute
@@ -284,7 +284,7 @@ func directedPortedAttrGraphFrom(g []set, attr [][]Attribute, ports map[edge]por
return dg
}
-func undirectedPortedAttrGraphFrom(g []set, attr [][]Attribute, ports map[edge]portedEdge) graph.Graph {
+func undirectedPortedAttrGraphFrom(g []intset, attr [][]Attribute, ports map[edge]portedEdge) graph.Graph {
dg := simple.NewUndirectedGraph(0, math.Inf(1))
for u, e := range g {
var at []Attribute
@@ -325,7 +325,7 @@ type structuredGraph struct {
sub []Graph
}
-func undirectedStructuredGraphFrom(c []edge, g ...[]set) graph.Graph {
+func undirectedStructuredGraphFrom(c []edge, g ...[]intset) graph.Graph {
s := &structuredGraph{UndirectedGraph: simple.NewUndirectedGraph(0, math.Inf(1))}
var base int
for i, sg := range g {
@@ -366,7 +366,7 @@ func (g subGraph) Subgraph() graph.Graph {
return namedGraph{id: g.id, Graph: g.Graph}
}
-func undirectedSubGraphFrom(g []set, s map[int][]set) graph.Graph {
+func undirectedSubGraphFrom(g []intset, s map[int][]intset) graph.Graph {
var base int
subs := make(map[int]subGraph)
for i, sg := range s {
@@ -1264,7 +1264,7 @@ var encodeTests = []struct {
// Handling subgraphs.
{
- g: undirectedSubGraphFrom(pageRankGraph, map[int][]set{2: powerMethodGraph}),
+ g: undirectedSubGraphFrom(pageRankGraph, map[int][]intset{2: powerMethodGraph}),
want: `graph {
// Node definitions.
@@ -1315,7 +1315,7 @@ var encodeTests = []struct {
},
{
name: "H",
- g: undirectedSubGraphFrom(pageRankGraph, map[int][]set{1: powerMethodGraph}),
+ g: undirectedSubGraphFrom(pageRankGraph, map[int][]intset{1: powerMethodGraph}),
strict: true,
want: `strict graph H {

MODIFY
graph/internal/set/same.go
graph/internal/set/same.go
@@ -16,3 +16,12 @@ import "unsafe"
func same(a, b Nodes) bool {
return *(*uintptr)(unsafe.Pointer(&a)) == *(*uintptr)(unsafe.Pointer(&b))
}
+
+// intsSame determines whether two sets are backed by the same store. In the
+// current implementation using hash maps it makes use of the fact that
+// hash maps are passed as a pointer to a runtime Hmap struct. A map is
+// not seen by the runtime as a pointer though, so we use unsafe to get
+// the maps' pointer values to compare.
+func intsSame(a, b Ints) bool {
+ return *(*uintptr)(unsafe.Pointer(&a)) == *(*uintptr)(unsafe.Pointer(&b))
+}

MODIFY
graph/internal/set/same_appengine.go
graph/internal/set/same_appengine.go
@@ -16,3 +16,12 @@ import "reflect"
func same(a, b Nodes) bool {
return reflect.ValueOf(a).Pointer() == reflect.ValueOf(b).Pointer()
}
+
+// intsSame determines whether two sets are backed by the same store. In the
+// current implementation using hash maps it makes use of the fact that
+// hash maps are passed as a pointer to a runtime Hmap struct. A map is
+// not seen by the runtime as a pointer though, so we use reflect to get
+// the maps' pointer values to compare.
+func intsSame(a, b Ints) bool {
+ return reflect.ValueOf(a).Pointer() == reflect.ValueOf(b).Pointer()
+}

MODIFY
graph/internal/set/set.go
graph/internal/set/set.go
@@ -34,6 +34,26 @@ func (s Ints) Count() int {
return len(s)
}
+// IntsEqual reports set equality between the parameters. Sets are equal if
+// and only if they have the same elements.
+func IntsEqual(a, b Ints) bool {
+ if intsSame(a, b) {
+ return true
+ }
+
+ if len(a) != len(b) {
+ return false
+ }
+
+ for e := range a {
+ if _, ok := b[e]; !ok {
+ return false
+ }
+ }
+
+ return true
+}
+
// Nodes is a set of nodes keyed in their integer identifiers.
type Nodes map[int]graph.Node

MODIFY
graph/topo/tarjan.go
graph/topo/tarjan.go
@@ -8,10 +8,9 @@ import (
"fmt"
"sort"
- "golang.org/x/tools/container/intsets"
-
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/ordered"
+ "gonum.org/v1/gonum/graph/internal/set"
)
// Unorderable is an error containing sets of unorderable graph.Nodes.
@@ -122,7 +121,7 @@ func tarjanSCCstabilized(g graph.Directed, order func([]graph.Node)) [][]graph.N
indexTable: make(map[int]int, len(nodes)),
lowLink: make(map[int]int, len(nodes)),
- onStack: &intsets.Sparse{},
+ onStack: make(set.Ints),
}
for _, v := range nodes {
if t.indexTable[v.ID()] == 0 {
@@ -143,7 +142,7 @@ type tarjan struct {
index int
indexTable map[int]int
lowLink map[int]int
- onStack *intsets.Sparse
+ onStack set.Ints
stack []graph.Node
@@ -160,7 +159,7 @@ func (t *tarjan) strongconnect(v graph.Node) {
t.indexTable[vID] = t.index
t.lowLink[vID] = t.index
t.stack = append(t.stack, v)
- t.onStack.Insert(vID)
+ t.onStack.Add(vID)
// Consider successors of v.
for _, w := range t.succ(v) {

MODIFY
graph/traverse/traverse.go
graph/traverse/traverse.go
package traverse // import "gonum.org/v1/gonum/graph/traverse"
import (
- "golang.org/x/tools/container/intsets"
-
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/linear"
+ "gonum.org/v1/gonum/graph/internal/set"
)
// BreadthFirst implements stateful breadth-first graph traversal.
@@ -17,7 +16,7 @@ type BreadthFirst struct {
EdgeFilter func(graph.Edge) bool
Visit func(u, v graph.Node)
queue linear.NodeQueue
- visited *intsets.Sparse
+ visited set.Ints
}
// Walk performs a breadth-first traversal of the graph g starting from the given node,
@@ -27,10 +26,10 @@ type BreadthFirst struct {
// non-nil, it is called with the nodes joined by each followed edge.
func (b *BreadthFirst) Walk(g graph.Graph, from graph.Node, until func(n graph.Node, d int) bool) graph.Node {
if b.visited == nil {
- b.visited = &intsets.Sparse{}
+ b.visited = make(set.Ints)
}
b.queue.Enqueue(from)
- b.visited.Insert(from.ID())
+ b.visited.Add(from.ID())
var (
depth int
@@ -52,7 +51,7 @@ func (b *BreadthFirst) Walk(g graph.Graph, from graph.Node, until func(n graph.N
if b.Visit != nil {
b.Visit(t, n)
}
- b.visited.Insert(n.ID())
+ b.visited.Add(n.ID())
children++
b.queue.Enqueue(n)
}
@@ -93,15 +92,13 @@ func (b *BreadthFirst) WalkAll(g graph.Undirected, before, after func(), during
// Visited returned whether the node n was visited during a traverse.
func (b *BreadthFirst) Visited(n graph.Node) bool {
- return b.visited != nil && b.visited.Has(n.ID())
+ return b.visited.Has(n.ID())
}
// Reset resets the state of the traverser for reuse.
func (b *BreadthFirst) Reset() {
b.queue.Reset()
- if b.visited != nil {
- b.visited.Clear()
- }
+ b.visited = nil
}
// DepthFirst implements stateful depth-first graph traversal.
@@ -109,7 +106,7 @@ type DepthFirst struct {
EdgeFilter func(graph.Edge) bool
Visit func(u, v graph.Node)
stack linear.NodeStack
- visited *intsets.Sparse
+ visited set.Ints
}
// Walk performs a depth-first traversal of the graph g starting from the given node,
@@ -119,10 +116,10 @@ type DepthFirst struct {
// is called with the nodes joined by each followed edge.
func (d *DepthFirst) Walk(g graph.Graph, from graph.Node, until func(graph.Node) bool) graph.Node {
if d.visited == nil {
- d.visited = &intsets.Sparse{}
+ d.visited = make(set.Ints)
}
d.stack.Push(from)
- d.visited.Insert(from.ID())
+ d.visited.Add(from.ID())
for d.stack.Len() > 0 {
t := d.stack.Pop()
@@ -139,7 +136,7 @@ func (d *DepthFirst) Walk(g graph.Graph, from graph.Node, until func(graph.Node)
if d.Visit != nil {
d.Visit(t, n)
}
- d.visited.Insert(n.ID())
+ d.visited.Add(n.ID())
d.stack.Push(n)
}
}
@@ -174,13 +171,11 @@ func (d *DepthFirst) WalkAll(g graph.Undirected, before, after func(), during fu
// Visited returned whether the node n was visited during a traverse.
func (d *DepthFirst) Visited(n graph.Node) bool {
- return d.visited != nil && d.visited.Has(n.ID())
+ return d.visited.Has(n.ID())
}
// Reset resets the state of the traverser for reuse.
func (d *DepthFirst) Reset() {
d.stack = d.stack[:0]
- if d.visited != nil {
- d.visited.Clear()
- }
+ d.visited = nil
}

MODIFY
graph/traverse/traverse_test.go
graph/traverse/traverse_test.go
@@ -20,7 +20,7 @@ import (
var (
// batageljZaversnikGraph is the example graph from
// figure 1 of http://arxiv.org/abs/cs/0310049v1
- batageljZaversnikGraph = []set{
+ batageljZaversnikGraph = []intset{
0: nil,
1: linksTo(2, 3),
@@ -48,7 +48,7 @@ var (
// wpBronKerboschGraph is the example given in the Bron-Kerbosch article on wikipedia (renumbered).
// http://en.wikipedia.org/w/index.php?title=Bron%E2%80%93Kerbosch_algorithm&oldid=656805858
- wpBronKerboschGraph = []set{
+ wpBronKerboschGraph = []intset{
0: linksTo(1, 4),
1: linksTo(2, 4),
2: linksTo(3),
@@ -59,7 +59,7 @@ var (
)
var breadthFirstTests = []struct {
- g []set
+ g []intset
from graph.Node
edge func(graph.Edge) bool
until func(graph.Node, int) bool
@@ -171,7 +171,7 @@ func TestBreadthFirst(t *testing.T) {
}
var depthFirstTests = []struct {
- g []set
+ g []intset
from graph.Node
edge func(graph.Edge) bool
until func(graph.Node) bool
@@ -254,7 +254,7 @@ func TestDepthFirst(t *testing.T) {
}
var walkAllTests = []struct {
- g []set
+ g []intset
edge func(graph.Edge) bool
want [][]int
}{
@@ -342,14 +342,14 @@ func TestWalkAll(t *testing.T) {
}
}
-// set is an integer set.
-type set map[int]struct{}
+// intset is an integer set.
+type intset map[int]struct{}
-func linksTo(i ...int) set {
+func linksTo(i ...int) intset {
if len(i) == 0 {
return nil
}
- s := make(set)
+ s := make(intset)
for _, v := range i {
s[v] = struct{}{}
}
@@ -378,8 +378,8 @@ func benchmarkWalkAllBreadthFirst(b *testing.B, g graph.Undirected) {
for i := 0; i < b.N; i++ {
bft.WalkAll(g, nil, nil, nil)
}
- if bft.visited.Len() != n {
- b.Fatalf("unexpected number of nodes visited: want: %d got %d", n, bft.visited.Len())
+ if len(bft.visited) != n {
+ b.Fatalf("unexpected number of nodes visited: want: %d got %d", n, len(bft.visited))
}
}
@@ -409,8 +409,8 @@ func benchmarkWalkAllDepthFirst(b *testing.B, g graph.Undirected) {
for i := 0; i < b.N; i++ {
dft.WalkAll(g, nil, nil, nil)
}
- if dft.visited.Len() != n {
- b.Fatalf("unexpected number of nodes visited: want: %d got %d", n, dft.visited.Len())
+ if len(dft.visited) != n {
+ b.Fatalf("unexpected number of nodes visited: want: %d got %d", n, len(dft.visited))
}
}

MODIFY
graph/undirect.go
graph/undirect.go
package graph
-import (
- "golang.org/x/tools/container/intsets"
-)
-
// Undirect converts a directed graph to an undirected graph, resolving
// edge weight conflicts.
type Undirect struct {
@@ -47,20 +43,18 @@ func (g Undirect) Nodes() []Node { return g.G.Nodes() }
// From returns all nodes in g that can be reached directly from u.
func (g Undirect) From(u Node) []Node {
- var (
- nodes []Node
- seen intsets.Sparse
- )
+ var nodes []Node
+ seen := make(map[int]struct{})
for _, n := range g.G.From(u) {
- seen.Insert(n.ID())
+ seen[n.ID()] = struct{}{}
nodes = append(nodes, n)
}
for _, n := range g.G.To(u) {
id := n.ID()
- if seen.Has(id) {
+ if _, ok := seen[id]; ok {
continue
}
- seen.Insert(id)
+ seen[n.ID()] = struct{}{}
nodes = append(nodes, n)
}
return nodes

graph,graph/{encoding/dot,internal/set,topo,traverse}: remove intsets imports