graph

package module
v0.0.0-...-5a28473 Latest Latest
Warning

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

Go to latest
Published: Oct 6, 2019 License: GPL-3.0 Imports: 6 Imported by: 0

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.

func (*BFS) Add

func (b *BFS) Add(newPath path.Pather)

Add enqueues a path to the end of the queue.

func (BFS) Len

func (b BFS) Len() int

Len returns the current number of paths stored in the queue.

func (*BFS) Next

func (b *BFS) Next() (nextPath path.Pather)

Next dequeues a path from the front of the queue.

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.

func (*DFS) Add

func (d *DFS) Add(newPath path.Pather)

Add pushes a path on to the top of the stack.

func (DFS) Len

func (d DFS) Len() int

Len returns the current number of paths stored in the stack.

func (*DFS) Next

func (d *DFS) Next() (nextPath path.Pather)

Next pops the path that is sitting on top of the stack.

type GoalFunc

type GoalFunc func(vertex vertex.Vertexer) bool

GoalFunc provides the algorithm to check if the provided vertex satisfies the goal.

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)

func New

func New(options ...Option) *Graph

New creates a new graph that to solve a graph search.

func (Graph) PrintInfo

func (g Graph) PrintInfo()

PrintInfo prints information about the graphs directionality, parents and children.

func (*Graph) Search

func (g *Graph) Search() (goalPath path.Pather)

Search implements a generic search algorithm: given a graph, starting vertices and a goal, incrementally explore edges from the start vertices.

type Grapher

type Grapher interface {
	Search() (goalPath path.Pather)
}

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.

func (*LCFS) Add

func (l *LCFS) Add(newPath path.Pather)

Add enqueues a path to the end of the queue.

func (LCFS) Len

func (l LCFS) Len() int

Len returns the current number of paths stored in the queue.

func (*LCFS) Next

func (l *LCFS) Next() (nextPath path.Pather)

Next dequeues a path from the front of the queue.

type Option

type Option func(g *Graph)

Option provides variadic options when creating a new Graph.

func WithEdges

func WithEdges(edges []edge.Edger) Option

WithEdges provides a way to supply your own edges when creating a new graph.

func WithGoalFunc

func WithGoalFunc(f GoalFunc) Option

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

func WithStartingVertices(vertices ...vertex.Vertexer) Option

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

func WithVertices(vertices []vertex.Vertexer) Option

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.

Directories

Path Synopsis
_examples
TODO: Document module
TODO: Document module

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL