dag

Documentation

Index

• Variables
• func ShortestPath[edge E, length L](g Graph[edge, length], n int) ([]edge, error)
• func ShortestPathDyn[vertex Beforer[vertex], edge E, length L](g DynamicGraph[vertex, edge, length], start, end vertex) ([]edge, error)
• type Beforer
• type DynamicGraph
• type E
• type Graph
• type L

Variables

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

Functions

func ShortestPath

func ShortestPath[edge E, length L](g Graph[edge, length], n int) ([]edge, error)

ShortestPath returns the shortest path from 0 to n. ErrNoPath is returned if there is no path from start to a vertex >= end. Otherwise, the path is returned as a slice of edges.

func ShortestPathDyn

func ShortestPathDyn[vertex Beforer[vertex], edge E, length L](g DynamicGraph[vertex, edge, length], start, end vertex) ([]edge, error)

ShortestPathDyn returns the shortest path from start to a vertex >= end. ErrNoPath is returned if there is no path from start to a vertex >= end. Otherwise, the path is returned as a slice of edges.

Types

type Beforer

type Beforer[T any] interface {
	Before(T) bool
}

type DynamicGraph

type DynamicGraph[vertex Beforer[vertex], edge E, length L] interface {
	// AppendEdges appends the outgoing edges of the given vertex to a slice.
	// All edges must lead to vertices with index strictly greater than v.
	AppendEdges(ee []edge, v vertex) []edge

	// Length returns the length of edge e starting at vertex v.
	Length(v vertex, e edge) length

	// To returns the endpoint of an edge e starting at vertex v.
	To(v vertex, e edge) vertex
}

Graph represents a directed acyclic graph.

type E

type E any

E describes the possible edge types.

type Graph

type Graph[edge E, length L] interface {
	// AppendEdges appends the outgoing edges of the given vertex to a slice.
	// All edges must lead to vertices with index strictly greater than v.
	AppendEdges(ee []edge, v int) []edge

	// Length returns the length of edge e starting at vertex v.
	Length(v int, e edge) length

	// To returns the endpoint of an edge e starting at vertex v.
	To(v int, e edge) int
}

Graph represents a directed acyclic graph.

type L

type L interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 |
		~float32 | ~float64
}

L describes the possible types for edge lengths.