dijkstra

README

dijkstra

Fast golang Dijkstra's shortest (and longest) path finder

Documentation

godoc

How to

Install

go get github.com/RyanCarrier/dijkstra/v2

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;

data, _ := os.ReadFile("path/to/file")
graph, err := dijkstra.Import(string(data))

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 (using ImportStringMapped instead.

Creating a graph

package main

import "github.com/RyanCarrier/dijkstra/v2"

func main(){
  graph := dijkstra.NewGraph()
  //Add the 3 verticies
  graph.AddEmptyVertex(0)
  graph.AddEmptyVertex(1)
  graph.AddEmptyVertex(2)
  //Add the arcs
  graph.AddArc(0, 1, 1)
  graph.AddArc(0, 2, 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 is", best.Distance, "following path ", best.Path)

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

Finding multiple paths

graph := dijkstra.NewGraph()
//Add the 3 verticies
graph.AddVertexAndArcs(0, map[int]uint64{1: 1, 2: 1})
graph.AddVertexAndArcs(1, map[int]uint64{3: 1})
graph.AddVertexAndArcs(2, map[int]uint64{3: 1})
graph.AddVertexAndArcs(3, map[int]uint64{4: 1})

best, err := graph.ShortestAll(0, 4)
if err != nil {
  fmt.Println(graph)
  log.Fatal(err)
}
fmt.Println("Shortest distances are", best.Distance, "with paths; ", best.Paths)

best, err = graph.LongestAll(0, 4)
if err != nil {
  log.Fatal(err)
}
fmt.Println("Longest distances are", best.Distance, "following path ", best.Paths)

Documentation

Index

• Variables
• type BestPath
• type BestPaths
  • func (bps BestPaths[T]) SmallestPath() BestPath[T]
• type Graph
  • func Generate(verticies int) Graph
  • func Import(data string) (g Graph, err error)
  • func NewGraph() Graph
  • func (g *Graph) AddArc(src, dest int, distance uint64) error
  • func (g *Graph) AddEmptyVertex(index int) error
  • func (g *Graph) AddNewEmptyVertex() (index int)
  • func (g *Graph) AddVertex(index int, vertexArcs map[int]uint64) error
  • func (g *Graph) AddVertexAndArcs(index int, vertexArcs map[int]uint64) error
  • func (g Graph) Export() (string, error)
  • func (g Graph) GetArc(src, dest int) (uint64, error)
  • func (g Graph) GetVertexArcs(index int) (map[int]uint64, error)
  • func (g Graph) Longest(src, dest int) (BestPath[int], error)
  • func (g Graph) LongestAll(src, dest int) (BestPaths[int], error)
  • func (g *Graph) RemoveArc(src, dest int) error
  • func (g *Graph) RemoveVertex(index int) error
  • func (g *Graph) RemoveVertexAndArcs(index int) error
  • func (g Graph) Shortest(src, dest int) (BestPath[int], error)
  • func (g Graph) ShortestAll(src, dest int) (BestPaths[int], error)
• type MappedGraph
  • func ImportStringMapped(data string) (mg MappedGraph[string], err error)
  • func NewMappedGraph[T comparable]() MappedGraph[T]
  • func (mg *MappedGraph[T]) AddArc(src, dest T, distance uint64) error
  • func (mg *MappedGraph[T]) AddEmptyVertex(item T) error
  • func (mg *MappedGraph[T]) AddVertex(item T, vertexArcs map[T]uint64) error
  • func (mg *MappedGraph[T]) AddVertexAndArcs(item T, vertexArcs map[T]uint64) error
  • func (mg MappedGraph[T]) Export() (string, error)
  • func (mg MappedGraph[T]) GetArc(src, dest T) (uint64, error)
  • func (mg *MappedGraph[T]) GetVertexArcs(item T) (map[T]uint64, error)
  • func (mg MappedGraph[T]) Longest(src, dest T) (BestPath[T], error)
  • func (mg MappedGraph[T]) LongestAll(src, dest T) (BestPaths[T], error)
  • func (mg *MappedGraph[T]) RemoveArc(src, dest T) error
  • func (mg *MappedGraph[T]) RemoveVertex(item T) error
  • func (mg *MappedGraph[T]) RemoveVertexAndArcs(item T) error
  • func (mg MappedGraph[T]) Shortest(src, dest T) (BestPath[T], error)
  • func (mg MappedGraph[T]) ShortestAll(src, dest T) (BestPaths[T], error)

Variables

var ErrArcHanging = errors.New("arc will be left hanging")

var ErrArcNotFound = errors.New("arc not found")

var ErrGraphNotValid = errors.New("graph is not valid")

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

var ErrMapNotFound = errors.New("mapping error, can not find mapped vertex")

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

var ErrVertexAlreadyExists = errors.New("vertex already exists")

var ErrVertexNegative = errors.New("vertex is negative")

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

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

Types

type BestPath

type BestPath[T any] struct {
	Distance uint64
	Path     []T
}

BestPath contains the solution of the most optimal path

type BestPaths

type BestPaths[T any] struct {
	Distance uint64
	Paths    [][]T
}

func (BestPaths[T]) SmallestPath

func (bps BestPaths[T]) SmallestPath() BestPath[T]

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph contains all the graph details (verticies and arcs)

func Generate

func Generate(verticies int) Graph

Generate generates a graph with a moderate amount of connections with semi random weights

func Import

func Import(data 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(src, dest int, distance uint64) error

AddArc adds an arc from src to dest with the specified distance will error if the arc already exists (remove then add)

func (*Graph) AddEmptyVertex

func (g *Graph) AddEmptyVertex(index int) error

AddVertex adds a single vertex at the specified index

func (*Graph) AddNewEmptyVertex

func (g *Graph) AddNewEmptyVertex() (index int)

AddNewVertex adds a new vertex at the next available index

func (*Graph) AddVertex

func (g *Graph) AddVertex(index int, vertexArcs map[int]uint64) error

AddVertex adds or overwrites a vertex with specified arcs, if the destination of an arc does not exist, it will error. If arc destinations should be added, use AddVertexAndArcs instead

func (*Graph) AddVertexAndArcs

func (g *Graph) AddVertexAndArcs(index int, vertexArcs map[int]uint64) error

AddVertexAndArcs adds or overwrites a vertex with specified arcs, if the destination of an arc does not exist, it will be added.

func (Graph) Export

func (g Graph) Export() (string, error)

func (Graph) GetArc

func (g Graph) GetArc(src, dest int) (uint64, error)

GetArc gets the arc distance from src to dest

func (Graph) GetVertexArcs

func (g Graph) GetVertexArcs(index int) (map[int]uint64, error)

GetVertexArcs gets all the arcs from vertex index

func (Graph) Longest

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

Longest calculates the longest path from src to dest

func (Graph) LongestAll

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

LongestAll calculates all of the longest paths from src to dest

func (*Graph) RemoveArc

func (g *Graph) RemoveArc(src, dest int) error

RemoveArc removes the arc from src to dest

func (*Graph) RemoveVertex

func (g *Graph) RemoveVertex(index int) error

RemoveVertex removes the vertex at index, fails if there are still arcs pointing to the vertex. To remove all arcs also, use RemoveVertexAndArcs

func (*Graph) RemoveVertexAndArcs

func (g *Graph) RemoveVertexAndArcs(index int) error

RemoveVertexAndArcs removes the vertex at index and all arcs pointing to it

func (Graph) Shortest

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

Shortest calculates the shortest path from src to dest

func (Graph) ShortestAll

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

ShortestAll calculates all of the longest paths from src to dest

type MappedGraph

type MappedGraph[T comparable] struct {
	// contains filtered or unexported fields
}

func ImportStringMapped

func ImportStringMapped(data string) (mg MappedGraph[string], err error)

func NewMappedGraph

func NewMappedGraph[T comparable]() MappedGraph[T]

NewMappedGraph creates a new empty mapped graph

func (*MappedGraph[T]) AddArc

func (mg *MappedGraph[T]) AddArc(src, dest T, distance uint64) error

AddArc adds an arc between two vertices

func (*MappedGraph[T]) AddEmptyVertex

func (mg *MappedGraph[T]) AddEmptyVertex(item T) error

AddEmptyVertex adds a single empty vertex

func (*MappedGraph[T]) AddVertex

func (mg *MappedGraph[T]) AddVertex(item T, vertexArcs map[T]uint64) error

AddVertex adds a vertex with specified arcs, if the destination of an arc does not exist, it will error. If arc destinations should be added, use AddVertexAndArcs instead

func (*MappedGraph[T]) AddVertexAndArcs

func (mg *MappedGraph[T]) AddVertexAndArcs(item T, vertexArcs map[T]uint64) error

AddVertexAndArcs adds a vertex with specified arcs, if the destination of an arc does not exist, it will be added.

func (MappedGraph[T]) Export

func (mg MappedGraph[T]) Export() (string, error)

func (MappedGraph[T]) GetArc

func (mg MappedGraph[T]) GetArc(src, dest T) (uint64, error)

GetArc gets the distance from src to dest

func (*MappedGraph[T]) GetVertexArcs

func (mg *MappedGraph[T]) GetVertexArcs(item T) (map[T]uint64, error)

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

func (MappedGraph[T]) Longest

func (mg MappedGraph[T]) Longest(src, dest T) (BestPath[T], error)

func (MappedGraph[T]) LongestAll

func (mg MappedGraph[T]) LongestAll(src, dest T) (BestPaths[T], error)

func (*MappedGraph[T]) RemoveArc

func (mg *MappedGraph[T]) RemoveArc(src, dest T) error

RemoveArc removes the arc between two vertices

func (*MappedGraph[T]) RemoveVertex

func (mg *MappedGraph[T]) RemoveVertex(item T) error

func (*MappedGraph[T]) RemoveVertexAndArcs

func (mg *MappedGraph[T]) RemoveVertexAndArcs(item T) error

func (MappedGraph[T]) Shortest

func (mg MappedGraph[T]) Shortest(src, dest T) (BestPath[T], error)

func (MappedGraph[T]) ShortestAll

func (mg MappedGraph[T]) ShortestAll(src, dest T) (BestPaths[T], error)