graph

package
v0.1.4 Latest Latest
Warning

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

 Go to latest Published: Nov 26, 2024 License: BSD-3-Clause Imports: 13 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AStar 

func AStar[V comparable, N constraints.Number](
	g Graph[V, N],
	start V,
	h heuristic[V, N],
	options ...option[V],
) iter.Seq[tuples.Edge[V, N]]

AStar performs an A* search on the graph g starting from the vertex start and ending at the vertex end. The algorithm will return an iter.Seq[tuples.Edge[V, N]] that represents the path from the start vertex to the destination vertex. If no path exists, an empty sequence is returned. The algorithm can be configured with the following options:

  • BaseCaseOption: return true if searching should stop, false otherwise.
  • UnvisitedFilter: return true if unvisited vertex should be considered, false otherwise.
  • EarlyReturnOption: return true if the search should stop after visiting a certain vertex, false otherwise
  • PreVisitOption: execute a process with src and dst prior to visiting an unvisited vertex.
  • PostVisitOpton: execute a process with src and dst after visiting a vertex.
  • DeferredOption: execute a process with a source vertex if it does not satisfy the base case.

func BFS 

func BFS[V comparable, N constraints.Number](
	g Graph[V, N],
	start V,
	options ...option[V],
) iter.Seq[tuples.Edge[V, N]]

BFS performs a breadth-first search on the graph g starting from the vertex start. The algorithm will return an iter.Seq[tuples.Edge[V, N]] that represents the path from the start vertex to the destination vertex which needs to be defined in a base case option. If no baseCase is given, BFS will return all of the vertices reachable from the starting vertex. The algorithm can be configured with the following options:

  • BaseCaseOption: return true if searching should stop, false otherwise.
  • UnvisitedFilter: return true if unvisited vertex should be considered, false otherwise.
  • EarlyReturnOption: return true if the search should stop after visiting a certain vertex, false otherwise
  • PreVisitOption: execute a process with src and dst prior to visiting an unvisited vertex.
  • PostVisitOpton: execute a process with src and dst after visiting a vertex.
  • DeferredOption: execute a process with a source vertex if it does not satisfy the base case.
  • WithDeferred: execute a process with a source vertex if it does not satisfy the base case.

func BaseCaseOption 

func BaseCaseOption[V comparable](predicate func(src V) bool) option[V]

BaseCaseOption returns an option that sets the base case for the path finding algorithms. If the predicate returns true, the algorithms will stop and return the path.

func DFS 

func DFS[V comparable, N constraints.Number](
	g Graph[V, N],
	start V,
	options ...option[V],
) iter.Seq[tuples.Edge[V, N]]

DFS performs a depth-first search on the graph g starting from the vertex start. The algorithm returns an iter.Seq[tuples.Edge[V, N]] that represents the path from the start vertex to the destination vertex which needs to be defined in a base case option. If no baseCase is given, DFS will return an empty sequence. The algorithm can be configured with the following options:

  • BaseCaseOption: return true if searching should stop, false otherwise.
  • UnvisitedFilter: return true if unvisited vertex should be considered, false otherwise.
  • EarlyReturnOption: return true if the search should stop after visiting a certain vertex, false otherwise
  • PreVisitOption: execute a process with src and dst prior to visiting an unvisited vertex.
  • PostVisitOpton: execute a process with src and dst after visiting a vertex.
  • DeferredOption: execute a process with a source vertex if it does not satisfy the base case.

func DeferredOption 

func DeferredOption[V comparable](process func(src V)) option[V]

DeferredOption returns an option that allows for a process to be executed after every neighbor of the source vertex has been visited. The process is executed only if the source vertex does not satisfy the base case.

func Dijkstra 

func Dijkstra[V comparable, N constraints.Number](
	g Graph[V, N],
	start V,
	options ...option[V],
) iter.Seq[tuples.Edge[V, N]]

Dijkstra performs a Dijkstra search on the graph g starting from the vertex start. The algorithm will return an iter.Seq[tuples.Edge[V, N]] that represents the path from the start vertex to the destination vertex. If no path exists, an empty sequence is returned. The algorithm can be configured with the following options:

  • BaseCaseOption: return true if searching should stop, false otherwise.
  • UnvisitedFilter: return true if unvisited vertex should be considered, false otherwise.
  • EarlyReturnOption: return true if the search should stop after visiting a certain vertex, false otherwise
  • PreVisitOption: execute a process with src and dst prior to visiting an unvisited vertex.
  • PostVisitOpton: execute a process with src and dst after visiting a vertex.
  • DeferredOption: execute a process with a source vertex if it does not satisfy the base case.

func EarlyReturnOption 

func EarlyReturnOption[V comparable](predicate func(src, dst V) bool) option[V]

EarlyReturnOption returns an option that sets an early return for the path finding algorithms. It is only called on visited vertices. If predicate returns true, the algorithm will stop and return the path.

func Edmonds 

func Edmonds[V comparable, N constraints.Number](g Graph[V, N], r V) iter.Seq[tuples.Edge[V, N]]

Note: Needs more testing Edmonds returns the minimum arborescence of the graph g rooted at the vertex root.

func EuclideanHeuristic 

func EuclideanHeuristic[P ituples.Point2d[N], N constraints.Number](end P) heuristic[P, float64]

EuclideanHeuristic returns a heuristic function that calculates the Euclidean distance between two points in a 2D plane.

func HasCycle 

func HasCycle[V comparable, N constraints.Number](g Graph[V, N]) bool

HasCycle returns true if the graph has a cycle and false otherwise. The algorithm used is depth-first search.

func HasPath 

func HasPath[V comparable, N constraints.Number](g Graph[V, N], src, dst V) bool

HasPath returns true if there is a path between two vertices and false otherwise. The algorithm used is depth-first search.

func IsConnected 

func IsConnected[V comparable, N constraints.Number](g Graph[V, N], start ...V) bool

IsConnected returns true if the graph is connected and false otherwise. The algorithm used is breadth-first search.

func Kruskal 

func Kruskal[V comparable, N constraints.Number](g Graph[V, N]) iter.Seq[tuples.Edge[V, N]]

Kruskal returns the minimum spanning tree of the graph g. The algorithm will returns an iter.Seq[tuples.Edge[V, N]] that represents the minimum spanning tree of the graph.

func Path 

func Path[V comparable, N constraints.Number](g Graph[V, N], src, dst V) iter.Seq[tuples.Edge[V, N]]

Path returns the a path between two vertices. The path is returned as a iter.Seq[tuples.Edge[V, N]] If no path exists, an empty sequence is returned. The algorithm used is depth-first search.

func PreVisitOption 

func PreVisitOption[V comparable](process func(src, dst V)) option[V]

PreVisitOption returns an option that allows for a process to be executed before the algorithm visits the vertex. This option cannot modify the current path. User may pass in an UnvisitedFilterOption() if they wish to modify the path with an unvisited vertex.

func ShortesPath 

func ShortesPath[V comparable, N constraints.Number](g Graph[V, N], src, dst V) iter.Seq[tuples.Edge[V, N]]

ShortestPath returns the shortest path between two vertices. The path is returned as a iter.Seq[tuples.Edges[V, N]]. If no path exists, an empty sequence is returned. The algorithm used is breadth-first search. For a faster algorithm, use Dijkstra or AStar.

func VertexFilterOption 

func VertexFilterOption[V comparable](predicate func(src, dst V) bool) option[V]

VertexFilterOption returns an option that sets the vertex filter for the path finding algorithms. If the predicate returns false, the algorithm will not visit the vertex.

func Weight 

func Weight[V comparable, N constraints.Number](g Graph[V, N]) N

Weight returns the total weight of all the edges in the graph.

Types

type Graph 

type Graph[V comparable, N constraints.Number] interface {
	IsDirected() bool
	Edges() iter.Seq[tuples.Edge[V, N]]
	VertexCount() int
	Vertices() iter.Seq[V]
	Neighbors(V) iter.Seq2[V, N]
}

Graph is an interface that defines the methods that a graph must implement to be used by the algorithms in this package

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.