gt

Documentation

Overview

Graph theory algorithms written in the Go programming language. Implements Shortest Path, Quadratic Assignment Problem, ...

Index

• Constants
• Variables
• func Dijkstra(G *Matrix, i int64) (p []int64)
• func Hungarian(g *Matrix) (xy, yx []int64)
• func Load(in *os.File) (int64, *Matrix, *Matrix)
• func Perm(p Vector)
• func QAP_SolveFANT(a *Matrix, b *Matrix, p Vector, r, m int64) int64
• func QAP_SolveSA(a *Matrix, b *Matrix, p Vector, m int64) int64
• func QAP_SolveTS(a, b *Matrix, p Vector, opt, tabu_duration, aspiration, nr_iterations int64) int64
• type Matrix
  • func NewMatrix(n int64) (m *Matrix)
  • func (m Matrix) Get(i int64, j int64) int64
  • func (m *Matrix) Print()
  • func (m Matrix) Set(i int64, j int64, v int64)
  • func (G *Matrix) ShortestPath(src, tar int64, N *Matrix) (p *list.List)
  • func (G *Matrix) TransitiveClosure(N *Matrix)
• type Vector
  • func (v Vector) Copy(w Vector)
  • func (v Vector) Len() int64
  • func (v Vector) Print()
  • func (p Vector) Swap(i int64, j int64)

Constants

const Inf int64 = math.MaxInt64

Variables

var Verbose bool

Functions

func Dijkstra

func Dijkstra(G *Matrix, i int64) (p []int64)

Dijkstra implements the Dijkstra's Algorithm for the shortest path.

func Hungarian

func Hungarian(g *Matrix) (xy, yx []int64)

Hungarian uses the Hungarian algorithm to solve the assigment problem.

func Load

func Load(in *os.File) (int64, *Matrix, *Matrix)

func Perm

func Perm(p Vector)

generate a random permutation p

func QAP_SolveFANT

func QAP_SolveFANT(a *Matrix, b *Matrix, p Vector, r, m int64) int64

QAP_SolveFANT solves the Quadratic Assignment Problem using Fast Ant System.

func QAP_SolveSA

func QAP_SolveSA(a *Matrix, b *Matrix, p Vector, m int64) int64

QAP_SolveSA solves the Quadratic Assignment Problem using Simulated Annealing.

func QAP_SolveTS

func QAP_SolveTS(a, b *Matrix, p Vector, opt, tabu_duration, aspiration, nr_iterations int64) int64

QAP_SolveTS solves the Quadratic Assignment Problem using the Robust Taboo Search.

Types

type Matrix

type Matrix struct {
	N int64
	A []int64
}

func NewMatrix

func NewMatrix(n int64) (m *Matrix)

func (Matrix) Get

func (m Matrix) Get(i int64, j int64) int64

func (*Matrix) Print

func (m *Matrix) Print()

func (Matrix) Set

func (m Matrix) Set(i int64, j int64, v int64)

func (*Matrix) ShortestPath

func (G *Matrix) ShortestPath(src, tar int64, N *Matrix) (p *list.List)

ShortestPath implements the algorithm for the shortest path.

func (*Matrix) TransitiveClosure

func (G *Matrix) TransitiveClosure(N *Matrix)

TransitiveClosure of a given graph G connects vertices u and v iff there is a path in G from u to v. Thus the transitive closure of any connected graph is complete.

type Vector

type Vector []int64

func (Vector) Copy

func (v Vector) Copy(w Vector)

func (Vector) Len

func (v Vector) Len() int64

func (Vector) Print

func (v Vector) Print()

func (Vector) Swap

func (p Vector) Swap(i int64, j int64)