K-ary Trees

Table of Contents

• Introduction
• Implementations

Introduction

Coalescence k-ary Trees classes are similar to Binary Trees, but provide an interface guaranteeing that each vertex \(v\) has exactly

• \(0\) successor (the vertex is a leaf)
• \(k \geq 2\) successors (the vertex is an internal node)

The graph structure is bidirectional and allows to model a forest of disconnected trees. That is, if a vertex has no predecessor, then it's either a root (if it has 2 or more successors) or an isolated vertex (if it has no successor).

Users will encounter this type of tree when returning from coalescence multiple mergers, or if they simply want to build and manipulate graphs that do not make strong assumptions on the tree structure.

Implementations

Coalescence K-ary Trees can store an additional arbitrary type of information (called a Property Class) along their vertices or edges: if the user decides to do so, the tree class interface adapts to offer ways to manipulate this information.

There are logically 4 different classes (equivalently interfaces) resulting from this:

• A class to represent a simple topology with no additional information (no property):
  quetzal::coalescence::k_ary_tree< no_property, no_property >
• A class to embed a user-defined class VertexProperty on each vertex:
  quetzal::coalescence::k_ary_tree< VertexProperty, no_property >
• A class to embed a user-defined class EdgeProperty on each edge:
  quetzal::coalescence::k_ary_tree< boost::no_property, EdgeProperty >
• A class to embed both VertexProperty and EdgeProperty information :
  quetzal::coalescence::k_ary_tree< VertexProperty, EdgeProperty >

Usage examples are described in their respective class documentation.