The highest tagged major version is
README
¶
dijkstra
Golangs fastest Dijkstra's shortest (and longest) path calculator
Documentation
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 (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 Item
- type Vertex
Constants ¶
This section is empty.
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 ErrWrongFormat = errors.New("wrong source format")
ErrWrongFormat is thrown when the source file input is in an incorrect format
Functions ¶
This section is empty.
Types ¶
type Graph ¶
type Graph struct {
//slice of all verticies available
Verticies []Vertex
// contains filtered or unexported fields
}
Graph contains all the graph details
func GenerateWorstCase ¶ added in v1.2.0
GenerateWorstCase generates a graph with the worst case scenario for Dijkstra's algorithm, has to hit every node on the way
func Import ¶
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 (*Graph) AddArc ¶
AddArc is the default method for adding an arc from a Source Vertex to a Destination Vertex
func (*Graph) AddMappedArc ¶
AddMappedArc adds a new Arc from Source to Destination, for when verticies are referenced by strings.
func (*Graph) AddMappedVertex ¶
AddMappedVertex adds a new Vertex with a mapped ID (or returns the index if ID already exists).
func (*Graph) AddNewVertex ¶
AddNewVertex adds a new vertex at the next available index
func (*Graph) AddVerticies ¶
AddVerticies adds the listed verticies to the graph, overwrites any existing Vertex with the same ID.
func (Graph) ExportToFile ¶
ExportToFile exports the verticies to file currently does not take into account mappings (from string to int)
func (*Graph) GetMapping ¶
GetMapping gets the index associated with the specified key
func (*Graph) GetVertex ¶
GetVertex gets the reference of the specified vertex. An error is thrown if there is no vertex with that index/ID.
func (*Graph) LongestAll ¶
LongestAll calculates all the longest paths from src to dest
func (*Graph) LongestSafe ¶ added in v1.3.0
LongestSafe calculates the longest path from src to dest with thread safety
(slightly slower than regular Longest)
func (*Graph) RemoveArc ¶ added in v1.1.0
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) ShortestAll ¶
ShortestAll calculates all of the shortest paths from src to dest
type Item ¶
type Item struct {
// contains filtered or unexported fields
}
An Item is something we manage in a priority queue.
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 (*Vertex) AddArc ¶
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.
Source Files