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(itf Interface, goal interface{}) interface{}
- func BfsPath(itf Interface, goal interface{}) []interface{}
- func Dfs(itf Interface, goal interface{}) interface{}
- func DfsPath(itf Interface, goal interface{}) []interface{}
- func Dls(itf Interface, goal interface{}, limit int) (nodeFound interface{}, more bool)
- func DlsPath(itf Interface, goal interface{}, limit int) (pathFound []interface{}, more bool)
- func Ids(itf Interface, goal interface{}, initLimit int) interface{}
- func IdsPath(itf Interface, goal interface{}, initLimit int) []interface{}
- type Interface
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Bfs ¶
func Bfs(itf Interface, goal interface{}) interface{}
Bfs finds goal in itf using breadth-first search algorithm, and returns the goal node found.
It returns nil if goal is not found.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of Interface, and set goal to an arbitrary value, such as nil.
func BfsPath ¶
func BfsPath(itf Interface, goal interface{}) []interface{}
BfsPath is similar to function Bfs, except that it returns the path from the root of itf to the goal node found, instead of only the goal node.
It returns nil if goal is not found.
func Dfs ¶
func Dfs(itf Interface, goal interface{}) interface{}
Dfs finds goal in itf using depth-first search algorithm, and returns the goal node found.
It returns nil if goal is not found.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of Interface, and set goal to an arbitrary value, such as nil.
func DfsPath ¶
func DfsPath(itf Interface, goal interface{}) []interface{}
DfsPath is similar to function Dfs, except that it returns the path from the root of itf to the goal node found, instead of only the goal node.
It returns nil if goal is not found.
func Dls ¶ added in v0.3.1
Dls finds goal 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.
It returns the goal node found (nil if goal is not found) and an indicator more to report whether there is any undiscovered nodes because of the depth limit. This indicator makes sense only when the goal 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.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of Interface, and set goal to an arbitrary value, such as nil.
func DlsPath ¶ added in v0.3.1
DlsPath is similar to function Dls, except that it returns the path from the root of itf to the goal node found, instead of only the goal node.
It returns nil for the path if goal is not found.
func Ids ¶ added in v0.3.1
Ids finds goal in itf using iterative deepening depth-first search algorithm, and returns the goal node 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 will be 1.
It returns nil if goal is not found.
goal is only used to call the method SetGoal of itf. It's OK to handle goal in your implementation of Interface, and set goal to an arbitrary value, such as nil.
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 ¶ added in v0.3.1
IdsPath is similar to function Ids, except that it returns the path from the root of itf to the goal node found, instead of only the goal node.
It returns nil if goal 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 Interface ¶
type Interface interface {
// Root returns the root of the tree.
Root() interface{}
// FirstChild returns the first child of the specified node.
//
// If the node has no child, FirstChild returns nil.
FirstChild(node interface{}) interface{}
// NextSibling returns the next sibling of the specified node,
// i.e., the next child of the parent of the specified node.
//
// If the node is the root or the last child of its parent,
// NextSibling returns nil.
NextSibling(node interface{}) interface{}
// SetGoal sets the search goal.
//
// It will be called once at the beginning of the search functions.
//
// Its implementation can do initialization for each search in this method.
SetGoal(goal interface{})
// Access examines the specified node.
//
// It returns an indicator found to reports whether the specified node
// is the search goal.
//
// Sometimes it is also referred to as "visit".
Access(node interface{}) (found bool)
}
Interface represents a tree used in the tree search algorithm.
Source Files