`import "gonum.org/v1/gonum/graph/traverse"`

Package traverse provides basic graph traversal primitives.

- type BreadthFirst
- func (b *BreadthFirst) Reset()
- func (b *BreadthFirst) Visited(n graph.Node) bool
- func (b *BreadthFirst) Walk(g Graph, from graph.Node, until func(n graph.Node, d int) bool) graph.Node
- func (b *BreadthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node))
- type DepthFirst
- func (d *DepthFirst) Reset()
- func (d *DepthFirst) Visited(n graph.Node) bool
- func (d *DepthFirst) Walk(g Graph, from graph.Node, until func(graph.Node) bool) graph.Node
- func (d *DepthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node))
- type Graph

❖

type BreadthFirst struct { // Visit is called on all nodes on their first visit. Visit func(graph.Node) // Traverse is called on all edges that may be traversed // during the walk. This includes edges that would hop to // an already visited node. // // The value returned by Traverse determines whether // an edge can be traversed during the walk. Traverse func(graph.Edge) bool // contains filtered or unexported fields }

BreadthFirst implements stateful breadth-first graph traversal.

❖

func (b *BreadthFirst) Reset()

Reset resets the state of the traverser for reuse.

❖

func (b *BreadthFirst) Visited(n graph.Node) bool

Visited returned whether the node n was visited during a traverse.

❖

func (b *BreadthFirst) Walk(g Graph, from graph.Node, until func(n graph.Node, d int) bool) graph.Node

Walk performs a breadth-first traversal of the graph g starting from the given node, depending on the Traverse field and the until parameter if they are non-nil. The traversal follows edges for which Traverse(edge) is true and returns the first node for which until(node, depth) is true. During the traversal, if the Visit field is non-nil, it is called with each node the first time it is visited.

❖

func (b *BreadthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node))

WalkAll calls Walk for each unvisited node of the graph g using edges independent of their direction. The functions before and after are called prior to commencing and after completing each walk if they are non-nil respectively. The function during is called on each node as it is traversed.

❖

type DepthFirst struct { // Visit is called on all nodes on their first visit. Visit func(graph.Node) // Traverse is called on all edges that may be traversed // during the walk. This includes edges that would hop to // an already visited node. // // The value returned by Traverse determines whether an // edge can be traversed during the walk. Traverse func(graph.Edge) bool // contains filtered or unexported fields }

DepthFirst implements stateful depth-first graph traversal.

❖

func (d *DepthFirst) Reset()

Reset resets the state of the traverser for reuse.

❖

func (d *DepthFirst) Visited(n graph.Node) bool

Visited returned whether the node n was visited during a traverse.

Walk performs a depth-first traversal of the graph g starting from the given node, depending on the Traverse field and the until parameter if they are non-nil. The traversal follows edges for which Traverse(edge) is true and returns the first node for which until(node) is true. During the traversal, if the Visit field is non-nil, it is called with each node the first time it is visited.

❖

func (d *DepthFirst) WalkAll(g graph.Undirected, before, after func(), during func(graph.Node))

WalkAll calls Walk for each unvisited node of the graph g using edges independent of their direction. The functions before and after are called prior to commencing and after completing each walk if they are non-nil respectively. The function during is called on each node as it is traversed.

❖

type Graph interface { // From returns all nodes that can be reached directly // from the node with the given ID. From(id int64) graph.Nodes // Edge returns the edge from u to v, with IDs uid and vid, // if such an edge exists and nil otherwise. The node v // must be directly reachable from u as defined by // the From method. Edge(uid, vid int64) graph.Edge }

Graph is the subset of graph.Graph necessary for graph traversal.

Package traverse imports 3 packages (graph) and is imported by 7 packages. Updated 2019-09-16. Refresh now. Tools for package owners.