README
¶
graph
'jus playing with graph theory really..
Check out the _examples folder for the interesting bits.
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.
Source Files
Directories