wgraph

package
v0.0.0-...-e5e7391 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 4, 2024 License: BSD-3-Clause Imports: 7 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrConnExists                 = errors.New("node connection already exists")
	ErrDijkstraNegativeWeightEdge = errors.New("a Dijkstra edge's weight must not be negative")
)

Functions

This section is empty.

Types

type DijstraShortestPath 

type DijstraShortestPath[W WeightDijkstra] struct {
	From  NodeDijkstra[W]
	Paths map[NodeDijkstra[W]]NodeDijkstra[W]
}

This type is the Dijkstra shortest path answer. It has 2 fields, (1) `From` the 'from' node, and (2) `Paths`. DijkstraShortestPath.Paths is a hash map where the key is a node, and the value is the previous node with the lowest cost to that key node. Because each instance holds all best route to every reachable node from From node, you can reconstruct the shortest path from any nodes in that Paths map with ReconstructPathTo

func (*DijstraShortestPath[T]) ReconstructPathTo 

func (d *DijstraShortestPath[T]) ReconstructPathTo(to NodeDijkstra[T]) []NodeDijkstra[T]

ReconstructPathTo reconstructs shortest path as slice of nodes, from `d.from` to `to` using DijkstraShortestPathReconstruct

type EdgeWeighted 

type EdgeWeighted[T Weight, N NodeWeighted[T]] interface {
	ToNode() (to N)
	GetWeight() T
}

EdgeWeighted represents what a weighted edge should be able to do.

type EdgeWeightedImpl 

type EdgeWeightedImpl[T Weight, N NodeWeighted[T]] struct {
	// contains filtered or unexported fields
}

func (*EdgeWeightedImpl[T, N]) GetWeight 

func (e *EdgeWeightedImpl[T, N]) GetWeight() T

func (*EdgeWeightedImpl[T, N]) ToNode 

func (e *EdgeWeightedImpl[T, N]) ToNode() N

If E is an edge from nodes A to B, then E.GetToNode() returns B.

type GraphDijkstra 

type GraphDijkstra[W WeightDijkstra] interface {
	GraphWeighted[NodeDijkstra[W], EdgeWeighted[W, NodeDijkstra[W]], W]
	DijkstraShortestPathFrom(startNode NodeDijkstra[W]) *DijstraShortestPath[W]
}

func NewDijkstraGraph 

func NewDijkstraGraph[T WeightDijkstra](directed bool) GraphDijkstra[T]

NewDikstraGraph calls NewGraphWeighted[T], and return the wrapped graph. Alternatively, you can create your own implementation of GraphWeighted[T].

func NewDijkstraGraphUnsafe 

func NewDijkstraGraphUnsafe[W WeightDijkstra](
	directed bool,
) GraphDijkstra[W]

NewDikstraGraph calls NewGraphWeightedUnsafe[T], and return the wrapped graph. Alternatively, you can create your own implementation of GraphWeighted[T].

type GraphDijkstraImpl 

type GraphDijkstraImpl[T WeightDijkstra] struct {
	// contains filtered or unexported fields
}

GraphDijkstraImpl[T] wraps GraphWeightedImpl[T], where T is generic type numeric types and S is ~string. It uses HashMapGraphWeighted as the underlying data structure.

func (*GraphDijkstraImpl[T]) AddEdge 

func (g *GraphDijkstraImpl[T]) AddEdge(n1, n2 NodeDijkstra[T], edge EdgeWeighted[T, NodeDijkstra[T]]) error

func (*GraphDijkstraImpl[T]) AddEdgeWeightOrDistance 

func (g *GraphDijkstraImpl[T]) AddEdgeWeightOrDistance(n1, n2 NodeDijkstra[T], weight T) error

func (*GraphDijkstraImpl[T]) AddNode 

func (g *GraphDijkstraImpl[T]) AddNode(node NodeDijkstra[T])

func (*GraphDijkstraImpl[T]) DijkstraShortestPathFrom 

func (g *GraphDijkstraImpl[T]) DijkstraShortestPathFrom(startNode NodeDijkstra[T]) *DijstraShortestPath[T]

DjisktraFrom takes a *NodeImpl[T] startNode, and finds the shortest path from startNode to all other nodes. This implementation uses PriorityQueue[T], so the nodes' values must satisfy constraints.Ordered.

func (*GraphDijkstraImpl[T]) GetEdges 

func (g *GraphDijkstraImpl[T]) GetEdges() []EdgeWeighted[T, NodeDijkstra[T]]

func (*GraphDijkstraImpl[T]) GetNodeEdges 

func (g *GraphDijkstraImpl[T]) GetNodeEdges(node NodeDijkstra[T]) []EdgeWeighted[T, NodeDijkstra[T]]

func (*GraphDijkstraImpl[T]) GetNodeNeighbors 

func (g *GraphDijkstraImpl[T]) GetNodeNeighbors(node NodeDijkstra[T]) []NodeDijkstra[T]

func (*GraphDijkstraImpl[T]) GetNodes 

func (g *GraphDijkstraImpl[T]) GetNodes() []NodeDijkstra[T]

func (*GraphDijkstraImpl[T]) IsDirected 

func (g *GraphDijkstraImpl[T]) IsDirected() bool

func (*GraphDijkstraImpl[T]) SetDirection 

func (g *GraphDijkstraImpl[T]) SetDirection(directed bool)

type GraphWeighted 

type GraphWeighted[N NodeWeighted[T], E EdgeWeighted[T, N], T Weight] graph.Graph[N, E, T]

GraphWeighted has T as node values and edge weight.

func NewGraphWeighted 

func NewGraphWeighted[
	N NodeWeighted[W],
	E EdgeWeighted[W, N],
	W Weight,
](directed bool,
) GraphWeighted[N, E, W]

NewGraphWeighted[T] returns the default implementation of GraphWeighted[T] with the concurrency safety wrapper.

func NewGraphWeightedUnsafe 

func NewGraphWeightedUnsafe[
	N NodeWeighted[W],
	E EdgeWeighted[W, N],
	W Weight,
](directed bool,
) GraphWeighted[N, E, W]

NewGraphWeightedUnsafe[T] returns the default implementation of GraphWeighted[T] without the concurrency wrapper. If your code is concurrent, use NewGraphWeighted[T] instead

func WrapSafeGraphWeighted 

func WrapSafeGraphWeighted[
	N NodeWeighted[W],
	E EdgeWeighted[W, N],
	W Weight,
](g GraphWeighted[N, E, W],
) GraphWeighted[N, E, W]

WrapSafeGraphWeighted wraps any graph g that implements GraphWeighted[T] with graph.SafeGraph[N, E, M, W].

type HashMapGraphWeightedImpl 

type HashMapGraphWeightedImpl[
	N NodeWeighted[W],
	E EdgeWeighted[W, N],
	W Weight,
] struct {
	Directed bool
	Nodes    []N
	Edges    map[NodeWeighted[W]]map[NodeWeighted[W]]EdgeWeighted[W, N]
}

HashMapGraphWeightedImpl[W, N] is the default implementation of GraphWeighted[N, EdgeWeighted[W], W].

func (*HashMapGraphWeightedImpl[N, E, W]) AddEdge 

func (g *HashMapGraphWeightedImpl[N, E, W]) AddEdge(n1, n2 N, edge E) error

AddEdge adds edge from n1 to n2

func (*HashMapGraphWeightedImpl[N, E, W]) AddEdgeWeightOrDistance 

func (g *HashMapGraphWeightedImpl[N, E, W]) AddEdgeWeightOrDistance(n1, n2 N, weight W) error

func (*HashMapGraphWeightedImpl[N, E, W]) AddNode 

func (g *HashMapGraphWeightedImpl[N, E, W]) AddNode(node N)

func (*HashMapGraphWeightedImpl[N, E, W]) GetEdges 

func (g *HashMapGraphWeightedImpl[N, E, W]) GetEdges() []E

func (*HashMapGraphWeightedImpl[N, E, W]) GetNodeEdges 

func (g *HashMapGraphWeightedImpl[N, E, W]) GetNodeEdges(node N) []E

func (*HashMapGraphWeightedImpl[N, E, W]) GetNodeNeighbors 

func (g *HashMapGraphWeightedImpl[N, E, W]) GetNodeNeighbors(node N) []N

func (*HashMapGraphWeightedImpl[N, E, W]) GetNodes 

func (g *HashMapGraphWeightedImpl[N, E, W]) GetNodes() []N

func (*HashMapGraphWeightedImpl[N, E, W]) IsDirected 

func (g *HashMapGraphWeightedImpl[N, E, W]) IsDirected() bool

func (*HashMapGraphWeightedImpl[N, E, W]) SetDirection 

func (g *HashMapGraphWeightedImpl[N, E, W]) SetDirection(directed bool)

type NodeDijkstra 

type NodeDijkstra[W WeightDijkstra] interface {
	NodeWeighted[W]

	GetPrevious() NodeDijkstra[W]     // When using with Dijkstra code, gets the previous (prior node) from a Dijkstra walk.
	SetPrevious(prev NodeDijkstra[W]) // In Dijkstra code, set a node's previous node value
}

func DijkstraShortestPathReconstruct 

func DijkstraShortestPathReconstruct[T WeightDijkstra](
	shortestPaths map[NodeDijkstra[T]]NodeDijkstra[T],
	src NodeDijkstra[T],
	dst NodeDijkstra[T],
) []NodeDijkstra[T]

DijkstraShortestPathReconstruct reconstructs a path as an array of nodes from dst back until it found nil, that is, the first node after the start node. For example, if you have a shortestPaths map lile this: 

dubai: nil
helsinki: dubai
budapest: helsinki

Then, the returned slice will be [budapest, helsinki, dubai], and the returned length will be 3 (inclusive). The path reconstruct from this function starts from the destination and goes all the way back to the source.

type NodeDijkstraImpl 

type NodeDijkstraImpl[T WeightDijkstra] struct {
	NodeWeightedImpl[T]
	Previous NodeDijkstra[T]
}

func (*NodeDijkstraImpl[T]) GetPrevious 

func (n *NodeDijkstraImpl[T]) GetPrevious() NodeDijkstra[T]

func (*NodeDijkstraImpl[T]) SetPrevious 

func (n *NodeDijkstraImpl[T]) SetPrevious(prev NodeDijkstra[T])

type NodeWeighted 

type NodeWeighted[T Weight] interface {
	// Inherit some from unweighted graphs
	graph.Node[T]

	GetKey() string         // Get the node's key, names, IDs
	SetValueOrCost(value T) // Save cost or value to the node
}

NodeWeighted should be able to put in a priority queue, just in case topological sort is needed.

type NodeWeightedImpl 

type NodeWeightedImpl[T Weight] struct {
	Name        string
	ValueOrCost T
}

func (*NodeWeightedImpl[T]) GetKey 

func (n *NodeWeightedImpl[T]) GetKey() string

func (*NodeWeightedImpl[T]) GetValue 

func (n *NodeWeightedImpl[T]) GetValue() T

Implements data.Valuer[T]

func (*NodeWeightedImpl[T]) SetValueOrCost 

func (n *NodeWeightedImpl[T]) SetValueOrCost(value T)

type Weight 

type Weight constraints.Ordered

type WeightDijkstra 

type WeightDijkstra interface {
	constraints.Integer | constraints.Float
}

WeightDijkstra represents the allowed types for edge weights and node costs. TODO: integrate more comparable types, like big.Int and big.Float

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.