Graphs in Quetzal

Table of Contents

• Invariants Guarantee
• Edge and Vertices descriptors
• Edge and Vertices Information (Property Classes)
• Depth First Search (DFS) Algorithms
• DFS on trees

Although graphs are ubiquitous in phylogeography and coalescence frameworks, they can represent quite different objects depending on the exact context. Consequently Quetzal had to make a number of design choices in their implementation.

Invariants Guarantee

As geneticists, we expect from a simple Kingman coalescent tree to exhibit certain characteristics (for example the guarantee of having either 0 or 2 children but never only 1) that we don't expect from a phylogenetic network (that would in contrast exhibit cycles and hybrid nodes).

In programming jargon, these expectations are called class invariants.

Rather than exposing a 1-fit-all type of graph and be prone to programming mistakes, Quetzal comes with more specialized classes that maintain their invariants.

Edge and Vertices descriptors

A point common to all class of graphs is that vertices and edges have unique identifiers.

This identifier is implementation-dependent and not always of type int. It is instead referred by a type nested in each graph class: vertex_descriptor and edge_descriptor.

Methods of a class that receive or return specific edges/vertices will manipulate objects of this type.

Edge and Vertices Information (Property Classes)

The quality of information attached to the vertices and edges of a graph also varies depending on the user problem.

For example, a spatial coalescent tree may need a way to store the geographic location of the visited locations, whereas a Kingman coalescent tree does not need to allocated storage for this. Similarly, Phylogenetic Networks will surely embed completely different types of information, like \(\gamma\), the inheritance probability.

To reflect this variability in the type of information, graphs can embed arbitrary information along edges and vertices through small user-defined classes called property classes.

The type of information a graph class embeds is referred by a nested type: vertex_property and edge_property.

Depth First Search (DFS) Algorithms

DFS is a form of graph traversal referering to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once.

DFS on trees

When the graph has the structure of a tree, there are only three operations that are worth worrying about:

• pre-order,
• in-order,
• post-order.
  

When you perform a DFS on a tree with Quetzal you need to pass to the DFS method a starting vertex (probably the root of the tree) and a visitor object: you would write tree.depth_first_search(start, visitor). This visitor must be a cheap-to-copy instance of a class that implements the details of the DFS operations as decided by the user, for example:

template <typename Order, typename Vertex>
struct tree_visitor
{
  void operator()(Order stage, Vertex v)
  {
    switch(stage) {
      case boost::visit::pre :
        // this line can be whatever the user sees fit
        std::cout << "Pre " << v << std::endl;
        break;
      case boost::visit::in:
        std::cout << "In " << v << std::endl; // same
        break;
      case boost::visit::post:
        std::cout << "Post " << v << std::endl; // same
        break;
      default:
        throw std::invalid_argument( "received invalid DFS order" );
    }
  }
};

You could also capture a reference to the tree graph instance if you need it:

template <typename Graph, typename Order>
struct tree_visitor
{
  Graph& _tree;
 
  void operator()(Order stage, Vertex v)
  {
    switch(stage) {
      case boost::visit::pre :
        // this line can be whatever the user sees fit
        std::cout << "Pre " << _tree[v] << std::endl;
        break;
      case boost::visit::in:
        std::cout << "In " <<_tree[v] << std::endl; // same
        break;
      case boost::visit::post:
        std::cout << "Post " << _tree[v] << std::endl; // same
        break;
      default:
        throw std::invalid_argument( "received invalid DFS order" );
    }
  }
};