mutable.go

// Copyright ©2014 The gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package concrete

import (
	"github.com/gonum/graph"
)

// A simple int alias.
type Node int

func (n Node) ID() int {
	return int(n)
}

// Just a collection of two nodes
type Edge struct {
	H, T graph.Node
}

func (e Edge) Head() graph.Node {
	return e.H
}

func (e Edge) Tail() graph.Node {
	return e.T
}

type WeightedEdge struct {
	graph.Edge
	Cost float64
}

// A GonumGraph is a very generalized graph that can handle an arbitrary number of vertices and
// edges -- as well as act as either directed or undirected.
//
// Internally, it uses a map of successors AND predecessors, to speed up some operations (such as
// getting all successors/predecessors). It also speeds up things like adding edges (assuming both
// edges exist).
//
// However, its generality is also its weakness (and partially a flaw in needing to satisfy
// MutableGraph). For most purposes, creating your own graph is probably better. For instance,
// see TileGraph for an example of an immutable 2D grid of tiles that also implements the Graph
// interface, but would be more suitable if all you needed was a simple undirected 2D grid.
type Graph struct {
	neighbors map[int]map[int]WeightedEdge
	nodeMap   map[int]graph.Node

	// Node add/remove convenience vars
	maxID   int
	freeMap map[int]struct{}
}

func NewGraph() *Graph {
	return &Graph{
		neighbors: make(map[int]map[int]WeightedEdge),
		nodeMap:   make(map[int]graph.Node),
		maxID:     0,
		freeMap:   make(map[int]struct{}),
	}
}

/* Mutable implementation */

func (g *Graph) NewNode() graph.Node {
	if g.maxID != maxInt {
		g.maxID++
		g.AddNode(Node(g.maxID))
		return Node(g.maxID)
	}

	// Implicitly checks if len(g.freeMap) == 0
	for id := range g.freeMap {
		g.AddNode(Node(id))
		return Node(id)
	}

	// I cannot foresee this ever happening, but just in case, we check.
	if len(g.nodeMap) == maxInt {
		panic("cannot allocate node: graph too large")
	}

	for i := 0; i < maxInt; i++ {
		if _, ok := g.nodeMap[i]; !ok {
			g.AddNode(Node(i))
			return Node(i)
		}
	}

	// Should not happen.
	panic("cannot allocate node id: no free id found")
}

func (g *Graph) AddNode(n graph.Node) {
	g.nodeMap[n.ID()] = n
	g.neighbors[n.ID()] = make(map[int]WeightedEdge)

	delete(g.freeMap, n.ID())
	g.maxID = max(g.maxID, n.ID())
}

func (g *Graph) AddUndirectedEdge(e graph.Edge, cost float64) {
	head, tail := e.Head(), e.Tail()
	if !g.NodeExists(head) {
		g.AddNode(head)
	}

	if !g.NodeExists(tail) {
		g.AddNode(tail)
	}

	hid, tid := head.ID(), tail.ID()
	if hid > tid {
		hid, tid = tid, hid
	}
	g.neighbors[hid][tid] = WeightedEdge{Edge: e, Cost: cost}
}

func (g *Graph) RemoveNode(n graph.Node) {
	nid := n.ID()
	if _, ok := g.nodeMap[nid]; !ok {
		return
	}
	delete(g.nodeMap, nid)

	for neigh := range g.neighbors[nid] {
		delete(g.neighbors[neigh], nid)
	}
	delete(g.neighbors, nid)

	if g.maxID != 0 && nid == g.maxID {
		g.maxID--
	}
	g.freeMap[nid] = struct{}{}
}

func (g *Graph) RemoveUndirectedEdge(e graph.Edge) {
	hid, tid := e.Head().ID(), e.Tail().ID()
	if _, ok := g.nodeMap[hid]; !ok {
		return
	}
	if _, ok := g.nodeMap[tid]; !ok {
		return
	}

	if hid > tid {
		hid, tid = tid, hid
	}
	delete(g.neighbors[hid], tid)
}

func (g *Graph) EmptyGraph() {
	g.neighbors = make(map[int]map[int]WeightedEdge)
	g.nodeMap = make(map[int]graph.Node)
}

/* Graph implementation */

func (g *Graph) Neighbors(n graph.Node) []graph.Node {
	nid := n.ID()

	nl := g.neighbors[nid]
	neighbors := make([]graph.Node, 0, len(nl))
	for pid := range nl {
		neighbors = append(neighbors, g.nodeMap[pid])
	}
	for id, nl := range g.neighbors {
		if _, ok := nl[nid]; ok {
			neighbors = append(neighbors, g.nodeMap[id])
		}
	}

	return neighbors
}

func (g *Graph) EdgeBetween(n, neigh graph.Node) graph.Edge {
	hid, tid := n.ID(), neigh.ID()
	if hid > tid {
		hid, tid = tid, hid
	}

	return g.neighbors[hid][tid]
}

func (g *Graph) NodeExists(n graph.Node) bool {
	_, ok := g.nodeMap[n.ID()]

	return ok
}

func (g *Graph) NodeList() []graph.Node {
	nodes := make([]graph.Node, len(g.nodeMap))
	i := 0
	for _, n := range g.nodeMap {
		nodes[i] = n
		i++
	}

	return nodes
}

func (g *Graph) Cost(e graph.Edge) float64 {
	hid, tid := e.Head().ID(), e.Tail().ID()
	if hid > tid {
		hid, tid = tid, hid
	}
	if n, ok := g.neighbors[hid]; ok {
		if we, ok := n[tid]; ok {
			return we.Cost
		}
	}
	return inf
}

func (g *Graph) EdgeList() []graph.Edge {
	m := make(map[WeightedEdge]struct{})
	toReturn := make([]graph.Edge, 0)

	for _, neighs := range g.neighbors {
		for _, we := range neighs {
			if _, ok := m[we]; !ok {
				m[we] = struct{}{}
				toReturn = append(toReturn, we.Edge)
			}
		}
	}

	return toReturn
}

func (g *Graph) Degree(n graph.Node) int {
	nid := n.ID()
	var d int
	for id, n := range g.neighbors {
		if id == nid {
			d += len(n)
		} else if _, ok := n[nid]; ok {
			d++
		}
	}

	return d
}

mutable_test.go

package concrete_test

import (
	"math/rand"
	"testing"

	"github.com/gonum/graph"
	. "github.com/gonum/graph/concrete"
)

func edgarGilbert(n int, rnd func() float64, alpha float64) *Graph {
	g := NewGraph()
	for i := 0; i < n; i++ {
		g.AddNode(Node(i))
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if rnd() < alpha {
				g.AddUndirectedEdge(Edge{Node(i), Node(j)}, 1)
			}
		}
	}
	return g
}

var (
	neighbors []graph.Node
	edge      graph.Edge
)

func benchmarkNeighbors(b *testing.B, n int, rnd func() float64, alpha float64) {
	g := edgarGilbert(n, rnd, alpha)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		neighbors = g.Neighbors(Node(0))
	}
}

func BenchmarkNeighbours1e4div1e2(b *testing.B) {
	benchmarkNeighbors(b, 1e4, rand.Float64, 0.01)
}
func BenchmarkNeighbours1e2div1e1(b *testing.B) {
	benchmarkNeighbors(b, 1e2, rand.Float64, 0.1)
}
func BenchmarkNeighbours1e3div1e1(b *testing.B) {
	benchmarkNeighbors(b, 1e3, rand.Float64, 0.1)
}
func BenchmarkNeighbours1e4div1e1(b *testing.B) {
	benchmarkNeighbors(b, 1e4, rand.Float64, 0.1)
}
func BenchmarkNeighbours1e2div5e1(b *testing.B) {
	benchmarkNeighbors(b, 1e2, rand.Float64, 0.5)
}
func BenchmarkNeighbours1e3div5e1(b *testing.B) {
	benchmarkNeighbors(b, 1e3, rand.Float64, 0.5)
}
func BenchmarkNeighbours1e4div5e1(b *testing.B) {
	benchmarkNeighbors(b, 1e4, rand.Float64, 0.5)
}

func benchmarkEdgeBetween(b *testing.B, n int, rnd func() float64, alpha float64) {
	g := edgarGilbert(n, rnd, alpha)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		u := Node(rand.Intn(n))
		v := Node(rand.Intn(n))
		edge = g.EdgeBetween(u, v)
	}
}

func BenchmarkEdgeBetween1e4div1e2(b *testing.B) {
	benchmarkEdgeBetween(b, 1e4, rand.Float64, 0.01)
}
func BenchmarkEdgeBetween1e2div1e1(b *testing.B) {
	benchmarkEdgeBetween(b, 1e2, rand.Float64, 0.1)
}
func BenchmarkEdgeBetween1e3div1e1(b *testing.B) {
	benchmarkEdgeBetween(b, 1e3, rand.Float64, 0.1)
}
func BenchmarkEdgeBetween1e4div1e1(b *testing.B) {
	benchmarkEdgeBetween(b, 1e4, rand.Float64, 0.1)
}
func BenchmarkEdgeBetween1e2div5e1(b *testing.B) {
	benchmarkEdgeBetween(b, 1e2, rand.Float64, 0.5)
}
func BenchmarkEdgeBetween1e3div5e1(b *testing.B) {
	benchmarkEdgeBetween(b, 1e3, rand.Float64, 0.5)
}
func BenchmarkEdgeBetween1e4div5e1(b *testing.B) {
	benchmarkEdgeBetween(b, 1e4, rand.Float64, 0.5)
}