func CombinationsExceed(n, k, threshold int) bool
CombinationsExceed computes the number of combinations of choosing K elements from N elements, and returns whether the number of combinations exceeds a given threshold. If n < k then it returns false.
Iterator defines an iterator that can be used to traverse vertices of a graph
type Iterator interface {
// Next returns the next element in the iteration order,
// or nil if there is no such an element
Next() *TreeVertex
}
Tree defines a Tree of vertices of type TreeVertex
type Tree struct {
Root *TreeVertex
}
func (t *Tree) BFS() Iterator
BFS returns an iterator that iterates the vertices in a Breadth-First-Search order
func (t *Tree) Permute(combinationUpperBound int) []*Tree
Permute returns Trees that their vertices and edges all exist in the original tree. The permutations are calculated according to the thresholds of all vertices. The combinationUpperBound is an upper bound of possible combinations of direct descendants of a vertex. If the vertex has a threshold and descendants that result a number of combinations that exceeds the given combinationUpperBound, the descendants are pruned until the number of combinations is lower than the combinationUpperBound. This is done in order to cap the memory usage of the computed result.
TreeVertex defines a vertex of a tree
type TreeVertex struct {
Id string // id identifies uniquely the TreeVertex in the Tree
Data interface{} // data holds arbitrary data, to be used by the user of the package
Descendants []*TreeVertex // descendants are the vertices that this TreeVertex is their parent in the tree
Threshold int // threshold symbols the count of sub-trees / leaves to pick when creating tree permutations
}
func NewTreeVertex(id string, data interface{}, descendants ...*TreeVertex) *TreeVertex
NewTreeVertex creates a new vertex with a given unique id and a given arbitrary data
func (v *TreeVertex) AddDescendant(u *TreeVertex) *TreeVertex
AddDescendant creates a new vertex who's parent is the invoker vertex, with a given id and data. Returns the new vertex
func (v *TreeVertex) Clone() *TreeVertex
Clone clones the tree who's root vertex is the current vertex.
func (v *TreeVertex) Exists(id string) bool
Exists searches for a vertex who's id is the given id, and returns whether such a vertex was found or not.
func (v *TreeVertex) Find(id string) *TreeVertex
Find searches for a vertex who's id is the given id. Returns the first vertex it finds with such an Id, or nil if not found
func (v *TreeVertex) IsLeaf() bool
IsLeaf returns whether the given vertex is a leaf
func (v *TreeVertex) ToTree() *Tree
ToTree creates a Tree who's root vertex is the current vertex
Vertex defines a vertex of a graph
type Vertex struct {
Id string
Data interface{}
// contains filtered or unexported fields
}
func NewVertex(id string, data interface{}) *Vertex
NewVertex creates a new vertex with given id and data
func (v *Vertex) AddNeighbor(u *Vertex)
AddNeighbor adds the given vertex as a neighbor of the vertex
func (v *Vertex) NeighborById(id string) *Vertex
NeighborById returns a neighbor vertex with the given id, or nil if no vertex with such an id is a neighbor
func (v *Vertex) Neighbors() []*Vertex
Neighbors returns the neighbors of the vertex