Documentation
¶
Overview ¶
Package traverse provides basic graph traversal primitives.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BreadthFirst ¶
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 (*BreadthFirst) Reset ¶
func (b *BreadthFirst) Reset()
Reset resets the state of the traverser for reuse.
func (*BreadthFirst) Visited ¶
func (b *BreadthFirst) Visited(n graph.Node) bool
Visited returned whether the node n was visited during a traverse.
func (*BreadthFirst) Walk ¶
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 (*BreadthFirst) WalkAll ¶
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 ¶
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 (*DepthFirst) Reset ¶
func (d *DepthFirst) Reset()
Reset resets the state of the traverser for reuse.
func (*DepthFirst) Visited ¶
func (d *DepthFirst) Visited(n graph.Node) bool
Visited returned whether the node n was visited during a traverse.
func (*DepthFirst) Walk ¶
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 (*DepthFirst) WalkAll ¶
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 ¶
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.
Source Files