Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CombinationsExceed ¶
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.
Types ¶
type Iterator ¶
type Iterator interface {
// Next returns the next element in the iteration order,
// or nil if there is no such an element
Next() *TreeVertex
}
Iterator defines an iterator that can be used to traverse vertices of a graph
type Tree ¶
type Tree struct {
Root *TreeVertex
}
Tree defines a Tree of vertices of type TreeVertex
func (*Tree) BFS ¶
BFS returns an iterator that iterates the vertices in a Breadth-First-Search order
func (*Tree) Permute ¶
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.
type TreeVertex ¶
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
}
TreeVertex defines a vertex of a tree
func NewTreeVertex ¶
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 (*TreeVertex) AddDescendant ¶
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 (*TreeVertex) Clone ¶
func (v *TreeVertex) Clone() *TreeVertex
Clone clones the tree who's root vertex is the current vertex.
func (*TreeVertex) Exists ¶
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 (*TreeVertex) Find ¶
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 (*TreeVertex) IsLeaf ¶
func (v *TreeVertex) IsLeaf() bool
IsLeaf returns whether the given vertex is a leaf
func (*TreeVertex) ToTree ¶
func (v *TreeVertex) ToTree() *Tree
ToTree creates a Tree who's root vertex is the current vertex
type Vertex ¶
type Vertex struct {
Id string
Data interface{}
// contains filtered or unexported fields
}
Vertex defines a vertex of a graph
func (*Vertex) AddNeighbor ¶
AddNeighbor adds the given vertex as a neighbor of the vertex
func (*Vertex) NeighborById ¶
NeighborById returns a neighbor vertex with the given id, or nil if no vertex with such an id is a neighbor
Source Files