graph

package
v2.1.1+incompatible Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 1, 2020 License: Apache-2.0 Imports: 3 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CombinationsExceed

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.

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

func (t *Tree) BFS() Iterator

BFS returns an iterator that iterates the vertices in a Breadth-First-Search order

func (*Tree) Permute

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.

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 NewVertex

func NewVertex(id string, data interface{}) *Vertex

NewVertex creates a new vertex with given id and data

func (*Vertex) AddNeighbor

func (v *Vertex) AddNeighbor(u *Vertex)

AddNeighbor adds the given vertex as a neighbor of the vertex

func (*Vertex) NeighborById

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 (*Vertex) Neighbors

func (v *Vertex) Neighbors() []*Vertex

Neighbors returns the neighbors of the vertex

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL