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

func (d *DepthFirst) Walk(g 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 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