Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BFS ¶
type BFS struct {
// contains filtered or unexported fields
}
BFS provides a breadth-first search strategy. It always selects one of the earliest paths added to the frontier.
func NewBreadthFirstSearch ¶
func NewBreadthFirstSearch() *BFS
NewBreadthFirstSearch returns a breadth-first search strategy.
type DFS ¶
type DFS struct {
// contains filtered or unexported fields
}
DFS provides a depth-first search strategy. It always selects the last path added to the frontier.
func NewDepthFirstSearch ¶
func NewDepthFirstSearch() *DFS
NewDepthFirstSearch returns a depth-first search strategy.
type Graph ¶
type Graph struct { // V contains a set of vertices, also called nodes. V []vertex.Vertexer // E contains a set of edges, also called links. E []edge.Edger // Frontier provides the paths that have been, or may yet to be expanded. // The way in which the frontier returns paths is known as the search // strategy. Frontier Strategizer // StartingVertices contain the vertices to start solving the graph search // from. StartingVertices []vertex.Vertexer // Goal contains the algorithm to check if a given vertex satisfies the // goal state. Goal GoalFunc // contains filtered or unexported fields }
Graph provides the data structure for a Graph. G = (V, E)
type Grapher ¶
Grapher is the interface that wraps the graph search algorithms.
Search traverses a graph in order to find a solution. If no solution is found, nil will be returned. Search should be implemented in such a way that multiple calls to search can continue to find other solutions from where it left off.
type LCFS ¶
type LCFS struct {
// contains filtered or unexported fields
}
LCFS provides a lowest-cost-first search strategy. It always selects a path from the frontier with teh lowest cost. It is a priority queue ordered by path cost. When path costs are equal, it performs a breadth-first search.
func NewLowestCostFirstSearch ¶
func NewLowestCostFirstSearch() *LCFS
NewLowestCostFirstSearch returns a lowest-cost-first search strategy.
type Option ¶
type Option func(g *Graph)
Option provides variadic options when creating a new Graph.
func WithGoalFunc ¶
WithGoalFunc provides a way to supply your own algorithm in order to satisfy the graph search.
func WithSearchStrategy ¶
func WithSearchStrategy(strategy Strategizer) Option
WithSearchStrategy provides a way to inject a search strategy, that is, the way in which a frontier is expanded in order to find the goal state.
func WithStartingVertices ¶
WithStartingVertices provides a way to inject vertices to start with.
func WithTraceLogging ¶
func WithTraceLogging() Option
WithTraceLogging provides a way to enable algorithm trace logging.
func WithVertices ¶
WithVertices provides a way to supply your own vertices when creating a new graph.
type Strategizer ¶
type Strategizer interface { // Len returns the current number of paths stored in the frontier. Len() int // Add stores an expanded path into the frontier. Add(path path.Pather) // Next returns the next path in the frontier to process, or nil if there // are no more paths to expand. Next() path.Pather }
Strategizer provides a search strategy. A search strategy defines the way in which the underlying frontier is expanded and traversed.