traverse

package
v1.1.0 Latest Latest
Warning

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

Go to latest
Published: Mar 14, 2022 License: Apache-2.0, BSD-3-Clause Imports: 3 Imported by: 0

Documentation

Overview

Package traverse provides basic graph traversal primitives.

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 {
	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.

Jump to

Keyboard shortcuts

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