Tree

Functions

std::ostream &operator<<(std::ostream&, const Tree&)

class Tree

#include <tree.hpp>

Represents a forest of rooted trees. After the initialisation, the forest is composed of trees containing only one node. The forest is updated using setParent on a vertex. A node is the root of a tree if and only if its parent is -1. After calling setParent at least one time, updateRoots must be called to update the roots of the trees.

Public Functions

Tree(const int vertexCount = 0)

Tree(const int vertexCount, const int root)

inline int vertexCount() const

Returns the number of vertices in the forest.

inline int root() const

Returs the root of the tree. The forest must contain only one tree.

inline const std::vector<int> &roots() const

Returns the roots of the trees in the forest.

inline int parent(const int vertex) const

Returns the parent of a vertex (-1 if the vertex is a root).

inline const std::vector<int> &children(const int vertex) const

Returns the children of a vertex.

void setParent(const int vertex, const int newParent)

Sets the parent of a vertex (-1 if the vertex must become a root)

inline int treeCount() const

Returns the number of tree in the forest.

void updateRoots()

Recalculates the roots of the trees. Must be called after changing the parent of at least one vertex.

Private Members

std::vector<int> m_roots

std::vector<Vertex> m_vertices

struct Vertex

Public Members

int parent

std::vector<int> children