package traverse

import "k8s.io/kubernetes/third_party/forked/gonum/graph/traverse"

Package traverse provides basic graph traversal primitives.

Package traverse provides basic graph traversal primitives.

Index ¶

• type BreadthFirst
• func (b *BreadthFirst) Reset()
• func (b *BreadthFirst) Visited(n graph.Node) bool
• func (b *BreadthFirst) Walk(g graph.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.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 VisitableGraph
• type VisitingDepthFirst
• func (d *VisitingDepthFirst) Reset()
• func (d *VisitingDepthFirst) Visited(n graph.Node) bool
• func (d *VisitingDepthFirst) Walk(g VisitableGraph, from graph.Node, until func(graph.Node) bool) graph.Node

Types ¶

type BreadthFirst ¶

type BreadthFirst struct {
	EdgeFilter func(graph.Edge) bool
	Visit      func(u, v graph.Node)
	// 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.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 EdgeFilter field and the until parameter if they are non-nil. The traversal follows edges for which EdgeFilter(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 the nodes joined by each followed edge.

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 {
	EdgeFilter func(graph.Edge) bool
	Visit      func(u, v graph.Node)
	// 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 ¶

func (d *DepthFirst) Walk(g graph.Graph, from graph.Node, until func(graph.Node) bool) graph.Node

Walk performs a depth-first traversal of the graph g starting from the given node, depending on the EdgeFilter field and the until parameter if they are non-nil. The traversal follows edges for which EdgeFilter(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 the nodes joined by each followed edge.

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 VisitableGraph ¶

type VisitableGraph interface {
	graph.Graph

	// VisitFrom invokes visitor with all nodes that can be reached directly from the given node.
	// If visitor returns false, visiting is short-circuited.
	VisitFrom(from graph.Node, visitor func(graph.Node) (shouldContinue bool))
}

VisitableGraph

type VisitingDepthFirst ¶

type VisitingDepthFirst struct {
	EdgeFilter func(graph.Edge) bool
	Visit      func(u, v graph.Node)
	// contains filtered or unexported fields
}

VisitingDepthFirst implements stateful depth-first graph traversal on a visitable graph.

func (*VisitingDepthFirst) Reset ¶

func (d *VisitingDepthFirst) Reset()

Reset resets the state of the traverser for reuse.

func (*VisitingDepthFirst) Visited ¶

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

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

func (*VisitingDepthFirst) Walk ¶

func (d *VisitingDepthFirst) Walk(g VisitableGraph, from graph.Node, until func(graph.Node) bool) graph.Node

Walk performs a depth-first traversal of the graph g starting from the given node, depending on the EdgeFilter field and the until parameter if they are non-nil. The traversal follows edges for which EdgeFilter(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 the nodes joined by each followed edge.

Source Files ¶

traverse.go visit_depth_first.go