dijkstra

README

dijkstra

Golangs fastest Dijkstra's shortest (and longest) path calculator

Documentation

godoc

How to

Generate a graph

Importing from file

The package can import dijkstra files in the format:

0 1,1 2,1
1 0,1 2,2
2

using;

graph, err := dijkstra.Import("path/to/file")

i.e. node then each arc and it's weight. The default is to use nodes with numbers starting from 0, but the package will map string appropriately.

Creating a graph

package main

func main(){
  graph:=dijkstra.NewGraph()
  //Add the 3 verticies
  graph.AddVertex(0)
  graph.AddVertex(1)
  graph.AddVertex(2)
  //Add the arcs
  graph.AddArc(0,1,1)
  graph.AddArc(0,2,1)
  graph.AddArc(1,0,1)
  graph.AddArc(1,2,2)
}

Finding paths

Once the graph is created, shortest or longest paths between two points can be generated.

best, err := graph.Shortest(0, 2)
if err!=nil{
  log.Fatal(err)
}
fmt.Println("Shortest distance ", best.Distance, " following path ", best.Path)

best, err := graph.Longest(0, 2)
if err!=nil{
  log.Fatal(err)
}
fmt.Println("Longest distance ", best.Distance, " following path ", best.Path)

best, err := graph.ShortestSafe(0, 2)
if err!=nil{
  log.Fatal(err)
}
fmt.Println("Shortest distance with thread safety", best.Distance, " following path ", best.Path)

Documentation

Index

• Variables
• type BestPath
• type BestPaths
• type Graph
  • func Generate(nodes int) Graph
  • func GenerateWorstCase(nodes int) Graph
  • func Import(filename string) (g Graph, err error)
  • func NewGraph() *Graph
  • func (g *Graph) AddArc(Source, Destination int, Distance int64) error
  • func (g *Graph) AddMappedArc(Source, Destination string, Distance int64) error
  • func (g *Graph) AddMappedVertex(ID string) int
  • func (g *Graph) AddNewVertex() *Vertex
  • func (g *Graph) AddVertex(ID int) *Vertex
  • func (g *Graph) AddVerticies(verticies ...Vertex)
  • func (g Graph) ExportToFile(filename string) error
  • func (g *Graph) GetMapped(a int) (string, error)
  • func (g *Graph) GetMapping(a string) (int, error)
  • func (g *Graph) GetVertex(ID int) (*Vertex, error)
  • func (g *Graph) Longest(src, dest int) (BestPath, error)
  • func (g *Graph) LongestAll(src, dest int) (BestPaths, error)
  • func (g *Graph) LongestSafe(src, dest int) (BestPath, error)
  • func (g *Graph) RemoveArc(Source, Destination int) error
  • func (g *Graph) Shortest(src, dest int) (BestPath, error)
  • func (g *Graph) ShortestAll(src, dest int) (BestPaths, error)
  • func (g *Graph) ShortestSafe(src, dest int) (BestPath, error)
• type Vertex
  • func NewVertex(ID int) *Vertex
  • func (v *Vertex) AddArc(Destination int, Distance int64)
  • func (v *Vertex) GetArc(Destination int) (distance int64, ok bool)
  • func (v *Vertex) RemoveArc(Destination int)

Variables

var ErrAlreadyCalculating = errors.New("already calculating")

ErrAlreadyCalculating is thrown when the algorithm is already running

var ErrLoopDetected = errors.New("infinite loop detected")

ErrLoopDetected is thrown when a loop is detected, causing the distance to go to inf (or -inf), or just generally loop forever

var ErrMixMapping = errors.New("potential mixing of integer and string node ID's :" + ErrWrongFormat.Error())

ErrMixMapping is thrown when there is a mixture of integers and strings in the input file

var ErrNoMap = errors.New("map is not being used/initialised")

ErrNoMap is thrown when the map is not being used but is being requested/accessed

var ErrNoPath = errors.New("no path found")

ErrNoPath is thrown when there is no path from src to dest

var ErrNodeNotFound = errors.New("node not found")

ErrNodeNotFound is thrown when a node is not found in the graph when it is being requested/used

var ErrVertexNotFound = errors.New("vertex not found")

ErrAlreadyCalculating is thrown when the algorithm is already running

var ErrWrongFormat = errors.New("wrong source format")

ErrWrongFormat is thrown when the source file input is in an incorrect format

Types

type BestPath

type BestPath struct {
	Distance int64
	Path     []int
}

BestPath contains the solution of the most optimal path

type BestPaths

type BestPaths []BestPath

BestPaths contains the list of best solutions

type Graph

type Graph struct {

	//slice of all verticies available
	Verticies []Vertex
	// contains filtered or unexported fields
}

Graph contains all the graph details

func Generate

func Generate(nodes int) Graph

Generate generates file with the amount of nodes specified

func GenerateWorstCase

func GenerateWorstCase(nodes int) Graph

GenerateWorstCase generates a graph with the worst case scenario for Dijkstra's algorithm, has to hit every node on the way

func Import

func Import(filename string) (g Graph, err error)

Import imports a graph from the specified file returns the Graph, a map for if the nodes are not integers and an error if needed.

func NewGraph

func NewGraph() *Graph

NewGraph creates a new empty graph

func (*Graph) AddArc

func (g *Graph) AddArc(Source, Destination int, Distance int64) error

AddArc is the default method for adding an arc from a Source Vertex to a Destination Vertex

func (*Graph) AddMappedArc

func (g *Graph) AddMappedArc(Source, Destination string, Distance int64) error

AddMappedArc adds a new Arc from Source to Destination, for when verticies are referenced by strings.

func (*Graph) AddMappedVertex

func (g *Graph) AddMappedVertex(ID string) int

AddMappedVertex adds a new Vertex with a mapped ID (or returns the index if ID already exists).

func (*Graph) AddNewVertex

func (g *Graph) AddNewVertex() *Vertex

AddNewVertex adds a new vertex at the next available index

func (*Graph) AddVertex

func (g *Graph) AddVertex(ID int) *Vertex

AddVertex adds a single vertex

func (*Graph) AddVerticies

func (g *Graph) AddVerticies(verticies ...Vertex)

AddVerticies adds the listed verticies to the graph, overwrites any existing Vertex with the same ID.

func (Graph) ExportToFile

func (g Graph) ExportToFile(filename string) error

ExportToFile exports the verticies to file currently does not take into account mappings (from string to int)

func (*Graph) GetMapped

func (g *Graph) GetMapped(a int) (string, error)

GetMapped gets the key assosciated with the mapped int

func (*Graph) GetMapping

func (g *Graph) GetMapping(a string) (int, error)

GetMapping gets the index associated with the specified key

func (*Graph) GetVertex

func (g *Graph) GetVertex(ID int) (*Vertex, error)

GetVertex gets the reference of the specified vertex. An error is thrown if there is no vertex with that index/ID.

func (*Graph) Longest

func (g *Graph) Longest(src, dest int) (BestPath, error)

Longest calculates the longest path from src to dest

func (*Graph) LongestAll

func (g *Graph) LongestAll(src, dest int) (BestPaths, error)

LongestAll calculates all the longest paths from src to dest

func (*Graph) LongestSafe

func (g *Graph) LongestSafe(src, dest int) (BestPath, error)

LongestSafe calculates the longest path from src to dest with thread safety

(slightly slower than regular Longest)

func (*Graph) RemoveArc

func (g *Graph) RemoveArc(Source, Destination int) error

RemoveArc removes and arc from the Source vertex to the Destination vertex fails if either vertex doesn't exist, but will succeed if destination is not an arc of Source (as a nop)

func (*Graph) Shortest

func (g *Graph) Shortest(src, dest int) (BestPath, error)

Shortest calculates the shortest path from src to dest

func (*Graph) ShortestAll

func (g *Graph) ShortestAll(src, dest int) (BestPaths, error)

ShortestAll calculates all of the shortest paths from src to dest

func (*Graph) ShortestSafe

func (g *Graph) ShortestSafe(src, dest int) (BestPath, error)

ShortestSafe calculates the shortest path from src to dest with thread safety

(slightly slower than regular Shortest)

type Vertex

type Vertex struct {
	//ID of the Vertex
	ID int
	// contains filtered or unexported fields
}

Vertex is a single node in the network, contains it's ID, best distance (to itself from the src) and the weight to go to each other connected node (Vertex)

func NewVertex

func NewVertex(ID int) *Vertex

NewVertex creates a new vertex

func (*Vertex) AddArc

func (v *Vertex) AddArc(Destination int, Distance int64)

AddArc adds an arc to the vertex, it's up to the user to make sure this is used correctly, firstly ensuring to use before adding to graph, or to use referenced of the Vertex instead of a copy. Secondly, to ensure the destination is a valid Vertex in the graph. Note that AddArc will overwrite any existing distance set if there is already an arc set to Destination.

func (*Vertex) GetArc

func (v *Vertex) GetArc(Destination int) (distance int64, ok bool)

GetArc gets the specified arc to Destination, bool is false if no arc found

func (*Vertex) RemoveArc

func (v *Vertex) RemoveArc(Destination int)

RemoveArc completely removes the arc to Destination (if it exists), this method will not error if Destination doesn't exist, only nop