diff options
Diffstat (limited to 'vendor/github.com/mattermost/rsc/rosetta/graph')
-rw-r--r-- | vendor/github.com/mattermost/rsc/rosetta/graph/Makefile | 7 | ||||
-rw-r--r-- | vendor/github.com/mattermost/rsc/rosetta/graph/graph.go | 133 |
2 files changed, 140 insertions, 0 deletions
diff --git a/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile b/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile new file mode 100644 index 000000000..1cb49f788 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/rosetta/graph/Makefile @@ -0,0 +1,7 @@ +include $(GOROOT)/src/Make.inc + +TARG=rsc.googlecode.com/hg/rosetta/graph +GOFILES=\ + graph.go\ + +include $(GOROOT)/src/Make.pkg diff --git a/vendor/github.com/mattermost/rsc/rosetta/graph/graph.go b/vendor/github.com/mattermost/rsc/rosetta/graph/graph.go new file mode 100644 index 000000000..359617d41 --- /dev/null +++ b/vendor/github.com/mattermost/rsc/rosetta/graph/graph.go @@ -0,0 +1,133 @@ +// Copyright 2011 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Simple demonstration of a graph interface and +// Dijkstra's algorithm built on top of that interface, +// without using inheritance. + +package graph + +import "container/heap" + +// A Graph is the interface implemented by graphs that +// this package can run algorithms on. +type Graph interface { + // NumVertex returns the number of vertices in the graph. + NumVertex() int + + // VertexID returns a vertex ID, 0 <= ID < NumVertex(), for v. + VertexID(v Vertex) int + + // Neighbors returns a slice of vertices that are adjacent + // to v in the graph. + Neighbors(v Vertex) []Vertex +} + +type Vertex interface { + String() string +} + +// ShortestPath uses Dijkstra's algorithm to find the shortest +// path from start to end in g. It returns the path as a slice of +// vertices, with start first and end last. If there is no path, +// ShortestPath returns nil. +func ShortestPath(g Graph, start, end Vertex) []Vertex { + d := newDijkstra(g) + + d.visit(start, 1, nil) + for !d.empty() { + p := d.next() + if g.VertexID(p.v) == g.VertexID(end) { + break + } + for _, v := range g.Neighbors(p.v) { + d.visit(v, p.depth+1, p) + } + } + + p := d.pos(end) + if p.depth == 0 { + // unvisited - no path + return nil + } + path := make([]Vertex, p.depth) + for ; p != nil; p = p.parent { + path[p.depth-1] = p.v + } + return path +} + +// A dpos is a position in the Dijkstra traversal. +type dpos struct { + depth int + heapIndex int + v Vertex + parent *dpos +} + +// A dijkstra is the Dijkstra traversal's work state. +// It contains the heap queue and per-vertex information. +type dijkstra struct { + g Graph + q []*dpos + byID []dpos +} + +func newDijkstra(g Graph) *dijkstra { + d := &dijkstra{g: g} + d.byID = make([]dpos, g.NumVertex()) + return d +} + +func (d *dijkstra) pos(v Vertex) *dpos { + p := &d.byID[d.g.VertexID(v)] + p.v = v // in case this is the first time we've seen it + return p +} + +func (d *dijkstra) visit(v Vertex, depth int, parent *dpos) { + p := d.pos(v) + if p.depth == 0 { + p.parent = parent + p.depth = depth + heap.Push(d, p) + } +} + +func (d *dijkstra) empty() bool { + return len(d.q) == 0 +} + +func (d *dijkstra) next() *dpos { + return heap.Pop(d).(*dpos) +} + +// Implementation of heap.Interface +func (d *dijkstra) Len() int { + return len(d.q) +} + +func (d *dijkstra) Less(i, j int) bool { + return d.q[i].depth < d.q[j].depth +} + +func (d *dijkstra) Swap(i, j int) { + d.q[i], d.q[j] = d.q[j], d.q[i] + d.q[i].heapIndex = i + d.q[j].heapIndex = j +} + +func (d *dijkstra) Push(x interface{}) { + p := x.(*dpos) + p.heapIndex = len(d.q) + d.q = append(d.q, p) +} + +func (d *dijkstra) Pop() interface{} { + n := len(d.q) + x := d.q[n-1] + d.q = d.q[:n-1] + x.heapIndex = -1 + return x +} |