Simple app to test the graph shortest path for gonum and yourbasic/graph

graph.go

package main 

import (
	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/simple"
	"gonum.org/v1/gonum/graph/traverse"
)

var (
	wdg *LightWeightedGraph

	_ graph.Graph             = wdg
	_ graph.Weighted          = wdg
	_ graph.Directed          = wdg
	_ graph.WeightedEdgeAdder = wdg
	_ traverse.Graph          = wdg
)

type NodeIterator struct {
	len     int
	current int
}

func NewNodeIterator(len int) *NodeIterator {
	return &NodeIterator{
		len:     len,
		current: -1,
	}
}

func (i *NodeIterator) Next() bool {
	if i.current >= i.len-1 {
		return false
	}
	i.current++
	return true
}

func (i *NodeIterator) Len() int {
	return i.len - i.current
}

func (i *NodeIterator) Reset() {
	i.current = -1
}

func (i *NodeIterator) Node() graph.Node {
	return simple.Node(i.current)
}

type LightWeightedGraph struct {
	edges []map[int64]float64
}

func NewLightWeightedGraph(n int) *LightWeightedGraph {
	return &LightWeightedGraph{
		edges: make([]map[int64]float64, n),
	}
}

func (wg LightWeightedGraph) Node(id int64) graph.Node {
	return simple.Node(id)
}

func (wg LightWeightedGraph) Nodes() graph.Nodes {
	return NewNodeIterator(len(wg.edges))
}

func (wg LightWeightedGraph) From(id int64) graph.Nodes {
	from := wg.edges[id]
	return NewNodes(from)
}

func (wg LightWeightedGraph) HasEdgeBetween(xid, yid int64) bool {
	panic("not implemented")
}

func (wg LightWeightedGraph) Edge(uid, vid int64) graph.Edge {
	panic("not implemented")
}

func (wg LightWeightedGraph) WeightedEdge(uid, vid int64) graph.WeightedEdge {
	panic("not implemented")
}

func (wg LightWeightedGraph) Weight(xid, yid int64) (w float64, ok bool) {
	if xid == yid {
		return 0, true
	}
	if e, ok := wg.edges[xid][yid]; ok {
		return e, true
	}
	return 0, false
}

func (wg LightWeightedGraph) HasEdgeFromTo(uid, vid int64) bool {
	panic("not implemented")
}

func (wg LightWeightedGraph) To(id int64) graph.Nodes {
	panic("not implemented")
}

func (wg LightWeightedGraph) NewWeightedEdge(from, to graph.Node, weight float64) graph.WeightedEdge {
	panic("not implemented")
}

func (g LightWeightedGraph) SetWeightedEdge(e graph.WeightedEdge) {
	var (
		from = e.From()
		fid  = from.ID()
		to   = e.To()
		tid  = to.ID()
	)
	if fid == tid {
		panic("simple: adding self edge")
	}

	if g.edges[fid] == nil {
		g.edges[fid] = make(map[int64]float64, 1)
	}
	g.edges[fid][tid] = e.Weight()
}

graph_test.go

package main

import (
	"fmt"
	"math"
	"math/rand"
	"runtime"
	"testing"
	"time"

	basicgraph "github.com/yourbasic/graph"
	"gonum.org/v1/gonum/graph/path"
	"gonum.org/v1/gonum/graph/simple"
)

func createYourBasicGraph(noOfNodes int) *basicgraph.Mutable {
	rand.Seed(time.Now().UnixNano())
	g := basicgraph.New(noOfNodes)
	for i := 0; i < noOfNodes; i++ {
		for j := 0; j < noOfNodes; j++ {
			if j != i {
				g.AddCost(i, j, int64(rand.Intn(195)+5))
			}
		}
	}
	return g
}

func createGonumGraph(noOfNodes int) *simple.WeightedDirectedGraph {
	rand.Seed(time.Now().UnixNano())
	g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
	for i := 0; i < noOfNodes; i++ {
		for j := 0; j < noOfNodes; j++ {
			if j != i {
				e := simple.WeightedEdge{F: simple.Node(i), T: simple.Node(j), W: float64(rand.Intn(195) + 5)}
				g.SetWeightedEdge(&e)
			}
		}
	}
	return g
}

func byteCountIEC(b uint64) string {
	const unit = 1024
	if b < unit {
		return fmt.Sprintf("%d B", b)
	}
	div, exp := int64(unit), 0
	for n := b / unit; n >= unit; n /= unit {
		div *= unit
		exp++
	}
	return fmt.Sprintf("%.1f %ciB",
		float64(b)/float64(div), "KMGTPE"[exp])
}

func BenchmarkYourBasicGraph1000(b *testing.B) {
	g := createYourBasicGraph(1000)
	var from, to int64
	from = int64(rand.Intn(195) + 5)
	for {
		to := int64(rand.Intn(195) + 5)
		if from != to {
			break
		}
	}
	for n := 0; n < b.N; n++ {
		_, _ = basicgraph.ShortestPath(g, int(from), int(to))
	}
}

func TestYourBasicGraphMemory(t *testing.T) {
	var m, m2 runtime.MemStats
	runtime.GC()
	runtime.ReadMemStats(&m)
	createYourBasicGraph(1000)
	runtime.ReadMemStats(&m2)
	totalBytes := m2.Alloc - m.Alloc
	t.Logf("Memory usage %s, %s, %s", byteCountIEC(m.Alloc), byteCountIEC(m2.Alloc), byteCountIEC(totalBytes))
}

func BenchmarkGonumGraph1000(b *testing.B) {
	g := createGonumGraph(1000)
	var from, to int64
	from = int64(rand.Intn(195) + 5)
	for {
		to := int64(rand.Intn(195) + 5)
		if from != to {
			break
		}
	}
	for n := 0; n < b.N; n++ {
		pth := path.DijkstraFrom(simple.Node(from), g)
		_, _ = pth.To(to)
	}
}

func TestGonumGraphMemory(t *testing.T) {
	var m, m2 runtime.MemStats
	runtime.GC()
	runtime.ReadMemStats(&m)
	createGonumGraph(1000)
	runtime.ReadMemStats(&m2)
	totalBytes := m2.Alloc - m.Alloc
	t.Logf("Memory usage %s, %s, %s", byteCountIEC(m.Alloc), byteCountIEC(m2.Alloc), byteCountIEC(totalBytes))
}

main.go

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"

	basicgraph "github.com/yourbasic/graph"
	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/path"
	"gonum.org/v1/gonum/graph/simple"
)

func main() {
	fmt.Print("Begin graph test\n")
	rand.Seed(time.Now().UnixNano())
	noOfNodes := 1000
	fmt.Print("Creating the ping times table...")
	pingTimes := createPingTimes(noOfNodes)
	fmt.Print("Done.\n")

	from, to := int64(rand.Intn(noOfNodes)), int64(rand.Intn(noOfNodes))

	fmt.Print("=== basic graph ===\nBuilding graph...")
	sg := yourBasicGraphBuild(pingTimes)
	fmt.Print("Done.\nTesting shortest path...\n")
	yourBasicGraphPath(sg, from, to)
	fmt.Print("Done.\n")
	fmt.Print("=== gonum graph ===\nBuilding graph...")
	gg := gonumGraphBuild(pingTimes)
	fmt.Print("Done.\nTesting shortest path...\n")
	gonumGraphPath(gg, from, to)
	fmt.Print("Done.\n")
}

func createPingTimes(noOfNodes int) [][]int64 {
	pingTimes := make([][]int64, noOfNodes)
	for i := 0; i < noOfNodes; i++ {
		pingTimes[i] = make([]int64, noOfNodes)
		for j := 0; j < noOfNodes; j++ {
			pingTimes[i][j] = int64(rand.Intn(195) + 5)
		}
	}
	return pingTimes
}

func gonumGraphPath(g graph.Graph, from, to int64) {
	startTime := time.Now()
	pth := path.DijkstraFrom(simple.Node(from), g)
	shpath, distance := pth.To(to)
	duration := time.Since(startTime)
	fmt.Printf("time: %f ms,from %d, to %d, path %v, distance: %d\n",
		float64(duration.Nanoseconds())/float64(time.Millisecond),
		from, to, shpath, int64(distance))
}

func gonumGraphBuild(pingTimes [][]int64) graph.Graph {
	g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
	for i := 0; i < len(pingTimes); i++ {
		for j := 0; j < len(pingTimes[i]); j++ {
			if j != i {
				e := simple.WeightedEdge{F: simple.Node(i), T: simple.Node(j), W: float64(pingTimes[i][j])}
				g.SetWeightedEdge(e)
			}
		}
	}
	return g
}

func yourBasicGraphPath(g *basicgraph.Mutable, from, to int64) {
	startTime := time.Now()
	path, distance := basicgraph.ShortestPath(g, int(from), int(to))
	duration := time.Since(startTime)
	fmt.Printf("time: %f ms,from %d, to %d, path %v, distance: %d\n",
		float64(duration.Nanoseconds())/float64(time.Millisecond),
		from, to, path, distance)
}

func yourBasicGraphBuild(pingTimes [][]int64) *basicgraph.Mutable {
	rand.Seed(time.Now().UnixNano())
	g := basicgraph.New(len(pingTimes))
	for i := 0; i < len(pingTimes); i++ {
		for j := 0; j < len(pingTimes[i]); j++ {
			if j != i {
				g.AddCost(i, j, pingTimes[i][j])
			}
		}
	}
	return g
}

main_after.go

package main

import (
	"fmt"
	"math/rand"
	"time"

	basicgraph "github.com/yourbasic/graph"
	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/path"
	"gonum.org/v1/gonum/graph/simple"
)

func main() {
	fmt.Print("Begin graph test\n")
	rand.Seed(time.Now().UnixNano())
	noOfNodes := 1000
	fmt.Print("Creating the ping times table...")
	pingTimes := createPingTimes(noOfNodes)
	fmt.Print("Done.\n")

	from, to := int64(rand.Intn(noOfNodes)), int64(rand.Intn(noOfNodes))

	fmt.Print("=== basic graph ===\nBuilding graph...")
	sg := yourBasicGraphBuild(pingTimes)
	fmt.Print("Done.\nTesting shortest path...\n")
	yourBasicGraphPath(sg, from, to)
	fmt.Print("Done.\n")
	fmt.Print("=== gonum graph ===\nBuilding graph...")
	gg := gonumGraphBuild(pingTimes)
	fmt.Print("Done.\nTesting shortest path...\n")
	gonumGraphPath(gg, from, to)
	fmt.Print("Done.\n")
}

func createPingTimes(noOfNodes int) [][]int64 {
	pingTimes := make([][]int64, noOfNodes)
	for i := 0; i < noOfNodes; i++ {
		pingTimes[i] = make([]int64, noOfNodes)
		for j := 0; j < noOfNodes; j++ {
			pingTimes[i][j] = int64(rand.Intn(195) + 5)
		}
	}
	return pingTimes
}

func gonumGraphPath(g graph.Graph, from, to int64) {
	startTime := time.Now()
	pth := path.DijkstraFrom(simple.Node(from), g)
	shpath, distance := pth.To(to)
	duration := time.Since(startTime)
	fmt.Printf("time: %f ms,from %d, to %d, path %v, distance: %d\n",
		float64(duration.Nanoseconds())/float64(time.Millisecond),
		from, to, shpath, int64(distance))
}

func gonumGraphBuild(pingTimes [][]int64) graph.Graph {
	g := NewLightWeightedGraph(len(pingTimes))
	for i := 0; i < len(pingTimes); i++ {
		for j := 0; j < len(pingTimes[i]); j++ {
			if j != i {
				e := simple.WeightedEdge{F: simple.Node(i), T: simple.Node(j), W: float64(pingTimes[i][j])}
				g.SetWeightedEdge(&e)
			}
		}
	}
	return g
}

func yourBasicGraphPath(g *basicgraph.Mutable, from, to int64) {
	startTime := time.Now()
	path, distance := basicgraph.ShortestPath(g, int(from), int(to))
	duration := time.Since(startTime)
	fmt.Printf("time: %f ms,from %d, to %d, path %v, distance: %d\n",
		float64(duration.Nanoseconds())/float64(time.Millisecond),
		from, to, path, distance)
}

func yourBasicGraphBuild(pingTimes [][]int64) *basicgraph.Mutable {
	rand.Seed(time.Now().UnixNano())
	g := basicgraph.New(len(pingTimes))
	for i := 0; i < len(pingTimes); i++ {
		for j := 0; j < len(pingTimes[i]); j++ {
			if j != i {
				g.AddCost(i, j, pingTimes[i][j])
			}
		}
	}
	return g
}

map.go

package main

import (
	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/simple"
	"unsafe"
)

type Nodes struct {
	nodes int
	iter  *mapIter
	pos   int
	curr  graph.Node
}

func NewNodes(nodes map[int64]float64) *Nodes {
	return &Nodes{nodes: len(nodes), iter: newMapIterNodes(nodes)}
}

// Len returns the remaining number of nodes to be iterated over.
func (n *Nodes) Len() int {
	return n.nodes - n.pos
}

// Next returns whether the next call of Node will return a valid node.
func (n *Nodes) Next() bool {
	if n.pos >= n.nodes {
		return false
	}
	ok := n.iter.next()
	if ok {
		n.pos++
		n.curr = simple.Node(n.iter.node()) 
	}
	return ok
}

// Node returns the current node of the iterator. Next must have been
// called prior to a call to Node.
func (n *Nodes) Node() graph.Node {
	return n.curr
}

// Reset returns the iterator to its initial state.
func (n *Nodes) Reset() {
	n.curr = nil
	n.pos = 0
	n.iter.it = nil
}


// A mapIter is an iterator for ranging over a map.
type mapIter struct {
	m  *emptyInterface
	it unsafe.Pointer
}

type emptyInterface struct {
	typ, word unsafe.Pointer
}

// newMapIterNodes returns a range iterator for a map of nodes.
func newMapIterNodes(m map[int64]float64) *mapIter {
	return &mapIter{m: eface(m)}
}


// id returns the key of the iterator's current map entry.
func (it *mapIter) id() int64 {
	if it.it == nil {
		panic("mapIter.id called before Next")
	}
	if mapiterkey(it.it) == nil {
		panic("mapIter.id called on exhausted iterator")
	}
	return *(*int64)(mapiterkey(it.it))
}

// node returns the value of the iterator's current map entry.
func (it *mapIter) node() int64 {
	if it.it == nil {
		panic("mapIter.node called before next")
	}
	if mapiterkey(it.it) == nil {
		panic("mapIter.node called on exhausted iterator")
	}
	return *(*int64)(mapiterkey(it.it))
}

// next advances the map iterator and reports whether there is another
// entry. It returns false when the iterator is exhausted; subsequent
// calls to Key, Value, or next will panic.
func (it *mapIter) next() bool {
	if it.it == nil {
		it.it = mapiterinit(it.m.typ, it.m.word)
	} else {
		if mapiterkey(it.it) == nil {
			panic("mapIter.next called on exhausted iterator")
		}
		mapiternext(it.it)
	}
	return mapiterkey(it.it) != nil
}

func eface(i interface{}) *emptyInterface {
	return (*emptyInterface)(unsafe.Pointer(&i))
}

// m escapes into the return value, but the caller of mapiterinit
// doesn't let the return value escape.
//go:linkname mapiterinit reflect.mapiterinit
//go:noescape
func mapiterinit(t, m unsafe.Pointer) unsafe.Pointer

//go:linkname mapiterkey reflect.mapiterkey
//go:noescape
func mapiterkey(it unsafe.Pointer) (key unsafe.Pointer)

//go:linkname mapiterelem reflect.mapiterelem
//go:noescape
func mapiterelem(it unsafe.Pointer) (elem unsafe.Pointer)

//go:linkname mapiternext reflect.mapiternext
//go:noescape
func mapiternext(it unsafe.Pointer)