#include <quetzal/coalescence/graph/binary_tree.hpp>

Detailed Description

template<class VertexProperty>
requires (!std::is_same_v<VertexProperty, no_property>)
class quetzal::coalescence::binary_tree< VertexProperty, no_property >

A binary tree class with information attached to vertices.

Template Parameters

VertexProperty The type of information to store at each vertex.

This class can be used as a simple way to describe the kind of topology and mutational process that emerge from evolutionary relationships between a sample of sequences for a non-recombining locus. Vertices embed a user-defined type of information. Edges embed no additional information. This graph structure is bidirected and allows to model a forest of disconnected trees and isolated vertices.

Invariant: Guarantees that each vertex \(v\) has exactly 0 or 2 successors, never 1.; Guarantees that each vertex \(v\) has exactly 0 or 1 predecessor.; Guarantees that if \((u,v)\) is an edge of the graph, then \((v,u)\) is also an edge.

Remarks: As it would be too costly to enforce non-cyclicity, it is left to the user responsability not to introduce any cycle.

Example

#include "quetzal/coalescence.hpp"
#include <cassert>
 
struct vertex_info
{
    std::string field1;
    int field2;
};
 
int main()
{
    using edge_info = boost::no_property;
    using tree_type = quetzal::coalescence::binary_tree<vertex_info, edge_info>;
 
    /*
     *             a
     *           /   \
     *          /     c
     *         /     / \
     *        b     d   e
     */
 
    tree_type tree;
 
    // Let's attach information to the root vertex
    auto a = tree.add_vertex(vertex_info{"Im Root", 47});
 
    // Other vertices have default values
    auto b = tree.add_vertex(vertex_info{});
    auto c = tree.add_vertex(vertex_info{});
    auto d = tree.add_vertex(vertex_info{});
    auto e = tree.add_vertex(vertex_info{});
 
    // No information are attached to edges
    auto [ab_edge, ac_edge] = tree.add_edges(a, b, c);
    auto [cd_edge, ce_edge] = tree.add_edges(c, d, e);
 
    auto root = tree.find_root_from(e);
 
    assert(root == a && !tree.has_predecessor(root));
    assert(tree.degree(c) == 3);
    assert(tree.in_degree(c) == 1);
    assert(tree.out_degree(c) == 2);
    assert(tree.has_predecessor(root) == false);
    assert(tree.predecessor(c) == root);
    assert(tree.has_successors(root) == true);
    for (auto v : tree.successors(c)) {
        assert(! tree.has_successors(v));
    }
    std::cout << "Degree of inner vertex c is " << tree.degree(c) << std::endl;
 
    // Root vertex field values were assigned
    std::cout << "Root first field is:\t" << tree[a].field1 << std::endl;
    std::cout << "Root other field is:\t" << tree[a].field2 << std::endl;
 
    // Other vertices fields values were left default initialized
    assert(tree[b].field1.size() == tree[b].field2);
}

Output

Degree of inner vertex c is 3
Root first field is:    Im Root
Root other field is:    47

Public Types
using	edge_descriptor = typename base::edge_descriptor
	Edge descriptor.

using	vertex_descriptor = typename base::vertex_descriptor
	Vertex descriptor.

using	degree_size_type = typename base::degree_size_type
	Degree size type.

using	traversal_category = typename base::traversal_category
	The ways in which the vertices in the graph can be traversed.

using	directed_category = typename base::directed_category
	The graph is bidirected.

using	in_edge_iterator = typename base::in_edge_iterator
	Iterate through the in-edges.

using	edge_parallel_category = typename base::edge_parallel_category

Public Member Functions
Constructors
	binary_tree ()
	Default constructor. Initializes a graph with 0 vertices.

	binary_tree (size_t n)
	Construct graph with \(n\) vertices.

Topology Modifiers
vertex_descriptor	add_vertex (const VertexProperty &p)
	Add a vertex and its properties to the graph.

std::pair< edge_descriptor, edge_descriptor >	add_edges (vertex_descriptor parent, vertex_descriptor left, vertex_descriptor right)
	Add edges between the parent vertex and the two children.

Property Lookup
const VertexProperty &	operator[] (vertex_descriptor v) const
	Read only access to the vertex property.

VertexProperty &	operator[] (vertex_descriptor v)
	Read and write access to the vertex property.

Topology Lookup
bool	is_isomorphic (binary_tree_common const &other) const
	Detects if there is a 1-to-1 mapping of the vertices in one graph to the vertices of another graph such that adjacency is preserved.

vertex_descriptor	find_root_from (vertex_descriptor u) const
	Finds the root of the tree graph starting from a vertex \(u\).

degree_size_type	degree (vertex_descriptor u) const
	Returns the number of in-edges plus out-edges.

degree_size_type	in_degree (vertex_descriptor u) const
	Returns the number of in-edges of vertex \(u\).

degree_size_type	out_degree (vertex_descriptor v) const
	Returns the number of out-edges of vertex \(v\).

bool	has_predecessor (vertex_descriptor u) const
	Evaluates if vertex \(u\) has a predecessor.

vertex_descriptor	predecessor (vertex_descriptor u) const
	The predecessor of vertex \(u\).

bool	has_successors (vertex_descriptor u) const
	Evaluates if vertex \(u\) has successors.

auto	successors (vertex_descriptor u) const
	The successors of vertex \(u\).

bool	is_left_successor (vertex_descriptor u) const
	Evaluate if vertex \(u\) is a left successor.

bool	is_right_successor (vertex_descriptor u) const
	Evaluate if vertex \(u\) is a right successor.

Iterators
std::pair< in_edge_iterator, in_edge_iterator >	in_edges (vertex_descriptor u) const
	Provides iterators to iterate over the in-going edges of vertex \(u\).

Algorithms
void	depth_first_search (vertex_descriptor s, DFSTreeVisitor &vis)
	Performs a read-and-write depth-first traversal of the vertices starting at vertex \(s\).

void	depth_first_search (vertex_descriptor s, DFSTreeVisitor &vis) const
	Performs a read-only depth-first traversal of the vertices starting at vertex \(s\).

Input/Output
void	to_graphviz (std::ostream &out) const
	Print the tree to the graphviz format.

Static Public Member Functions
static constexpr vertex_descriptor	null_vertex ()

Protected Attributes
base	_graph

Member Function Documentation

◆ degree()

degree_size_type quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::degree ( vertex_descriptor u ) const

inlineinherited

Returns the number of in-edges plus out-edges.

Parameters

u	The vertex \(u\)

Returns: Returns the number of in-edges plus out-edges.

◆ depth_first_search() [1/2]

void quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::depth_first_search	(	vertex_descriptor	s,
		DFSTreeVisitor &	vis
	)

inlineinherited

Performs a read-and-write depth-first traversal of the vertices starting at vertex \(s\).

Template Parameters

DFSTreeVisitor

Parameters

s	The vertex to start from.
vis	The visitor to apply.

◆ depth_first_search() [2/2]

void quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::depth_first_search	(	vertex_descriptor	s,
		DFSTreeVisitor &	vis
	)		const

inlineinherited

Performs a read-only depth-first traversal of the vertices starting at vertex \(s\).

Template Parameters

DFSTreeVisitor

Parameters

s	The vertex to start from.
vis	The visitor to apply.

◆ find_root_from()

vertex_descriptor quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::find_root_from ( vertex_descriptor u ) const

inlineinherited

Finds the root of the tree graph starting from a vertex \(u\).

Parameters

u	The vertex to start from.

Remarks: This function will be an infinite loop if called on a recurrent tree (which is not a tree any more).

◆ has_predecessor()

bool quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::has_predecessor ( vertex_descriptor u ) const

inlineinherited

Evaluates if vertex \(u\) has a predecessor.

Parameters

u	The vertex to evaluate

Returns: True if u has a predecessor, false otherwise

◆ has_successors()

bool quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::has_successors ( vertex_descriptor u ) const

inlineinherited

Evaluates if vertex \(u\) has successors.

Parameters

u	The vertex to evaluate

Returns: True if u has successors, false otherwise

◆ in_degree()

degree_size_type quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::in_degree ( vertex_descriptor u ) const

inlineinherited

Returns the number of in-edges of vertex \(u\).

Parameters

u	The vertex \(u\)

Returns: The number of in-edges.

◆ in_edges()

std::pair< in_edge_iterator, in_edge_iterator > quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::in_edges ( vertex_descriptor u ) const

inlineinherited

Provides iterators to iterate over the in-going edges of vertex \(u\).

Parameters

u	The vertex \(u\).

Returns: A pair of iterators.

◆ is_isomorphic()

bool quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::is_isomorphic ( binary_tree_common< VertexProperty, no_property > const & other ) const

inlineinherited

Detects if there is a 1-to-1 mapping of the vertices in one graph to the vertices of another graph such that adjacency is preserved.

Parameters

other A binary tree graph.

Returns: true if there exists an isomorphism between the two graphs and false otherwise

◆ is_left_successor()

bool quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::is_left_successor ( vertex_descriptor u ) const

inlineinherited

Evaluate if vertex \(u\) is a left successor.

Parameters

u	The vertex to be evaluated

Returns: True if u is a left successoir, false otherwise.

◆ is_right_successor()

bool quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::is_right_successor ( vertex_descriptor u ) const

inlineinherited

Evaluate if vertex \(u\) is a right successor.

Parameters

u	The vertex to be evaluated

Returns: True if u is a right successoir, false otherwise.

◆ predecessor()

vertex_descriptor quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::predecessor ( vertex_descriptor u ) const

inlineinherited

The predecessor of vertex \(u\).

Parameters

u	The vertex

Returns: The vertex that is the predecessor of \(u\).

◆ successors()

auto quetzal::coalescence::detail::binary_tree_common< VertexProperty, no_property >::successors ( vertex_descriptor u ) const

inlineinherited

The successors of vertex \(u\).

Parameters

u	The vertex

Returns: A pair of iterators on the vertices that are the successors of \(u\).

The documentation for this class was generated from the following file:

/home/runner/work/quetzal-CoaTL/quetzal-CoaTL/src/include/quetzal/coalescence/graph/binary_tree.hpp

Detailed Description

Example

Output

Public Types

Public Member Functions

Static Public Member Functions

Protected Attributes

Member Function Documentation

◆ degree()

◆ depth_first_search() [1/2]

◆ depth_first_search() [2/2]

◆ find_root_from()

◆ has_predecessor()

◆ has_successors()

◆ in_degree()

◆ in_edges()

◆ is_isomorphic()

◆ is_left_successor()

◆ is_right_successor()

◆ predecessor()

◆ successors()