tree

Documentation

Overview

Package tree provides search algorithms on trees.

For better performance, all functions in this package are unsafe for concurrency unless otherwise specified.

Index

• func BFS[Node any](itf AccessNode[Node], initArgs ...any) (nodeFound Node, found bool)
• func BFSPath[Node any](itf AccessPath[Node], initArgs ...any) []Node
• func DFS[Node any](itf AccessNode[Node], initArgs ...any) (nodeFound Node, found bool)
• func DFSPath[Node any](itf AccessPath[Node], initArgs ...any) []Node
• func DLS[Node any](itf AccessNode[Node], limit int, initArgs ...any) (nodeFound Node, found, more bool)
• func DLSPath[Node any](itf AccessPath[Node], limit int, initArgs ...any) (pathFound []Node, more bool)
• func IDS[Node any](itf AccessNode[Node], initLimit int, initArgs ...any) (nodeFound Node, found bool)
• func IDSPath[Node any](itf AccessPath[Node], initLimit int, initArgs ...any) []Node
• type AccessNode
• type AccessPath
• type Common

Functions

func BFS

func BFS[Node any](itf AccessNode[Node], initArgs ...any) (nodeFound Node, found bool)

BFS finds a node in itf using breadth-first search algorithm and returns that node.

It also returns an indicator found to report whether the node has been found.

initArgs are the arguments to initialize itf.

func BFSPath

func BFSPath[Node any](itf AccessPath[Node], initArgs ...any) []Node

BFSPath is similar to function BFS, except that it returns the path from the root of itf to the node found instead of only the node.

It returns nil if the node is not found.

func DFS

func DFS[Node any](itf AccessNode[Node], initArgs ...any) (nodeFound Node, found bool)

DFS finds a node in itf using depth-first search algorithm and returns that node.

It also returns an indicator found to report whether the node has been found.

initArgs are the arguments to initialize itf.

func DFSPath

func DFSPath[Node any](itf AccessPath[Node], initArgs ...any) []Node

DFSPath is similar to function DFS, except that it returns the path from the root of itf to the node found instead of only the node.

It returns nil if the node is not found.

func DLS

func DLS[Node any](itf AccessNode[Node], limit int, initArgs ...any) (nodeFound Node, found, more bool)

DLS finds a node in itf using depth-limited depth-first search algorithm.

limit is the maximum depth during this search. The depth of the root is 0, of children of the root is 1, and so on.

initArgs are the arguments to initialize itf.

It returns the node found and two indicators:

found - to report whether the node has been found;
more - to report whether there is any undiscovered node because of the depth limit.

The indicator more makes sense only when the node is not found. When more is false, all the nodes must have been discovered; when more is true, there must be at least one undiscovered node.

func DLSPath

func DLSPath[Node any](itf AccessPath[Node], limit int, initArgs ...any) (pathFound []Node, more bool)

DLSPath is similar to function DLS, except that it returns the path from the root of itf to the node found instead of only the node.

It returns nil for the path if the node is not found.

func IDS

func IDS[Node any](itf AccessNode[Node], initLimit int, initArgs ...any) (nodeFound Node, found bool)

IDS finds a node in itf using iterative deepening depth-first search algorithm and returns that node.

It also returns an indicator found to report whether the node has been found.

initLimit is the depth limit used in the first iteration. The depth of the root is 0, of children of the root is 1, and so on. If initLimit < 1, the depth limit in the first iteration is 1.

initArgs are the arguments to initialize itf.

If the client needs to reset any search state at the beginning of each iteration, just add the method ResetSearchState to itf. This method will be called before each iteration except for the first one.

The method signature should be

ResetSearchState()

And the client should define this method like

func (m MyInterface) ResetSearchState() {
	// Reset your search state.
}

func IDSPath

func IDSPath[Node any](itf AccessPath[Node], initLimit int, initArgs ...any) []Node

IDSPath is similar to function IDS, except that it returns the path from the root of itf to the node found instead of only the node.

It returns nil if the node is not found.

Same as function IDS, if the client needs to reset any search state at the beginning of each iteration, just add the method ResetSearchState to itf. This method will be called before each iteration except for the first one.

The method signature should be

ResetSearchState()

And the client should define this method like

func (m MyInterface) ResetSearchState() {
	// Reset your search state.
}

Types

type AccessNode

type AccessNode[Node any] interface {
	Common[Node]

	// AccessNode examines the specified node.
	//
	// It has two parameters:
	//   node - the node to examine;
	//   depth - the search depth from the root to the node.
	//
	// It returns two indicators:
	//   found - to report whether the specified node is the search goal;
	//   cont - to report whether to continue searching.
	//
	// The search algorithm should exit immediately if cont is false.
	// In this case, the search result may be invalid.
	//
	// Sometimes it is also referred to as "visit".
	AccessNode(node Node, depth int) (found, cont bool)
}

AccessNode represents a tree used in the tree search algorithm.

Its method AccessNode examines the current node.

type AccessPath

type AccessPath[Node any] interface {
	Common[Node]

	// AccessPath examines the path from the search root to the current node.
	//
	// Its parameter is the path from the search root to
	// the current node to examine.
	// path must be non-empty.
	//
	// It returns two indicators:
	//   found - to report whether the specified node is the search goal;
	//   cont - to report whether to continue searching.
	//
	// The search algorithm should exit immediately if cont is false.
	// In this case, the search result may be invalid.
	//
	// Sometimes it is also referred to as "visit".
	AccessPath(path []Node) (found, cont bool)
}

AccessPath represents a tree used in the tree search algorithm.

Its method AccessPath examines the path from the search root to the current node.

type Common

type Common[Node any] interface {
	// Init initializes all states for a new search
	// with the specified arguments args (e.g., set the search goal).
	//
	// It will be called once at the beginning of the search functions.
	Init(args ...any)

	// Root returns the node of the tree where the search algorithm start.
	Root() Node

	// FirstChild returns the first child of the specified node
	// and an indicator ok to report whether the node has a child.
	FirstChild(node Node) (fc Node, ok bool)

	// NextSibling returns the next sibling of the specified node
	// (i.e., the next child of the parent of the specified node)
	// and an indicator ok to report whether the node has the next sibling.
	// (If the node is the root or the last child of its parent, ok is false.)
	NextSibling(node Node) (ns Node, ok bool)
}

Common is the interface common to AccessNode and AccessPath. It represents a tree used in the tree search algorithm.