Trees generation

Jngen provides a Tree class. It offers some methods to manipulate with trees and static generators. As other Jngen objects, Tree can be printed to std::ostream. Here is a standard way to use generators:

cout << Tree::random(100).shuffled() << endl;

Generators

Note that all generators return trees with sorted edges to make tests more human-readable. More, numbering is not always random for same reason. Particularly, Tree::random(size, elongation) always returns a tree rooted at 0. You can always use tree.shuffle() to renumerate vertices and shuffle edges.

random(int size)

• Returns: a completely random tree, selected uniformly over all n^n-2 trees. Name comes from the fact that this generator exploits Prüfer sequences.

randomPrim(int size, int elongation = 0)

• Returns: a random tree with given elongation built with Prim-like process. The most classical tree generator ever.
• Description: first, vertex no. 0 is selected as a root. Next, for each vertex from 1 to n-1 its parent is selected as wnext(i, elongation). With elongation = -1000000 you will likely get a star, with elongation = 1000000 -- a bamboo (a path).

randomKruskal(int size)

• Returns: a random tree built with a Kruskal-like process.
• Description: uniformly random edges are added one by one. The edge is added if it doesn't introduce a cycle.

bamboo(int size)

• Returns: a bamboo (or a path) of a kind 0 -- 1 -- ... -- n-1.

star(int size)

• Returns: a star graph with size vertices and vertex no. 0 in the center. Central vertex is counted, i.e. there are size - 1 leaf vertices in general case.

caterpillar(int size, int length)

• Returns: a caterpillar tree with size vertices based on a path of length length.
• Description: first, a path of length length is generated. Vertices of the path are numbered in order. Next, other size - length vertices are connected to random vertices of the path.

Tree binary(int size)

• Returns: a complete binary tree with size vertices.
• Numeration: parent of vertex i is (i-1)/2, 0 is root.

Tree kary(int size, int k)

• Returns: a complete k-ary tree with size vertices.
• Numeration: parent of vertex i is (i-1)/k, 0 is root.

Tree fromPruferSequence(const Array& code)

• Returns: a tree with given Prüfer sequence. The tree contains code.size() + 2 vertices.

Tree methods

Tree& shuffle()

Tree shuffled() const

• Shuffle the tree. This means:
  • relabel vertices in random order;
  • shuffle edges;
  • randomly swap egdes' endpoints.

Tree& shuffleAllBut(const Array& except)

Tree shuffledAllBut(const Array& except)

• Same as shuffle, but vertices from except do not change their numbers.
  • Possible usecase: we may generate a rooted tree and shuffle it in such a way that root still has number 1.

t = Tree::randomPrim(n, 1000);
t.shuffleAllBut({0});

Array parents(int root) const

• Returns: array of size n, where i-th element is a parent of vertex i if the tree is rooted at root. Parent of root is -1.

Tree link(int vInThis, const Tree& other, int vInOther)

• Returns: a tree made of _this_ and other, with an extra edge between two vertices with ids vInThis and vInOther*, respectively.
• Labeling: labels of the source tree are unchanged, labels of the other tree are increased by the number of vertices in source. Edges are ordered like "source edges, other edges, new edge".

Tree glue(int vInThis, const Tree& other, int vInOther)

• Returns: a tree made of _this_ and other, where vertices vInThis and vInOther* are glued into one.
• Labeling: labels of the source tree are unchanged, vertices of the other tree are renumbered in order starting with the number of vertices in source, except for vInOther.