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

Detailed Description

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

A k-ary tree class with information attached to vertices.

Template Parameters

VertexProperty	The type of information to store at each vertex.
EdgeProperty	The type of information to store at each edge.

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 and edges embed additional information as user-defined types. 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 \(n \geq 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 = std::vector<int>;
    using tree_type = quetzal::coalescence::k_ary_tree<vertex_info, edge_info>;
 
    /*
     *              a
     *            /   \
     *           /     c
     *          /    / | \
     *         b    d  e  f
     */
 
    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{});
    auto f = tree.add_vertex(vertex_info{});
 
    // Attaches information to the edges from the root
    auto first_edges = tree.add_edges(a, {{b, edge_info{1, 2, 3}}, {c, edge_info{4, 5, 6}}});
 
    // Other edges have default values
    auto other_edges = tree.add_edges(c, {{d, edge_info{}}, {e, edge_info{}}, {f, edge_info{}}});
 
    assert(tree.degree(c) == 4);
    assert(tree.in_degree(c) == 1);
    assert(tree.out_degree(c) == 3);
    std::cout << "Degree of inner vertex c is " << tree.degree(c) << std::endl;
 
    auto root = tree.find_root_from(e);
 
    assert(root == a && !tree.has_predecessor(root));
    assert(tree.has_predecessor(root) == false);
    assert(tree.predecessor(c) == root);
    assert(tree.has_successors(root) == true);
    assert(std::ranges::none_of(tree.successors(c), [&](const auto &v) { return tree.has_successors(v); }));
 
    // Retrieve root vertex information
    std::cout << "Root first field is:\t" << tree[a].field1 << std::endl;
    std::cout << "Root other field is:\t" << tree[a].field2 << std::endl;
 
    // Retrieve edges information
    std::cout << "Edge (a->b) values are:\t";
    std::copy(tree[first_edges[0]].cbegin(), tree[first_edges[0]].cend(), std::ostream_iterator<int>(std::cout, " "));
 
    std::cout << "\nEdge (a->c) values are:\t";
    std::copy(tree[first_edges[1]].cbegin(), tree[first_edges[1]].cend(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
 
    // Other edges values were left default initialized
    assert(tree[other_edges[0]].size() == 0);
}

Output

2
3
Degree of inner vertex c is 4
Root first field is:    Im Root
Root other field is:    47
Edge (a->b) values are: 1 2 3 
Edge (a->c) values are: 4 5 6 

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

using	vertex_descriptor = typename base::vertex_descriptor
	Vertex descriptor.

using	vertex_property = VertexProperty
	Vertex information.

using	edge_property = EdgeProperty
	Edge information.

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	out_edge_iterator = typename base::out_edge_iterator
	Iterate through the out-edges.

using	edge_parallel_category = typename base::edge_parallel_category

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

	k_ary_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::vector< edge_descriptor >	add_edges (vertex_descriptor parent, std::vector< std::tuple< vertex_descriptor, EdgeProperty > > children)
	Add edges from the parent vertex (source) to the children (target)

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.

const EdgeProperty &	operator[] (const edge_descriptor &edge) const
	Read only access to the edge property.

EdgeProperty &	operator[] (const edge_descriptor &edge)
	Read and write access to the edge property.

Topology Lookup
bool	is_isomorphic (k_ary_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\).

std::optional< edge_descriptor >	edge (vertex_descriptor u, vertex_descriptor v) const
	Returns the edge between two vertices of the graph if the edge exists.

vertex_descriptor	source (edge_descriptor e) const
	Returns the source vertex of a directed edge.

vertex_descriptor	target (edge_descriptor e) const
	Returns the target vertex of a directed edge.

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 start, DFSTreeVisitor &vis)
	Performs a read-and-write depth-first traversal of the vertices starting at vertex \(s\).

void	depth_first_search (vertex_descriptor start, 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 ()
	Null vertex identifier.

static std::tuple< k_ary_tree< no_property, EdgeProperty >, vertex_descriptor >	make_random_tree (int n_leaves, int k_max, Generator &rng)

Protected Attributes
base	_graph

Member Function Documentation

◆ degree()

degree_size_type quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::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::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::depth_first_search	(	vertex_descriptor	start,
		DFSTreeVisitor &	vis
	)

inlineinherited

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

Template Parameters

DFSTreeVisitor

Parameters

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

◆ depth_first_search() [2/2]

void quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::depth_first_search	(	vertex_descriptor	start,
		DFSTreeVisitor &	vis
	)		const

inlineinherited

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

Template Parameters

DFSTreeVisitor

Parameters

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

◆ edge()

std::optional< edge_descriptor > quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::edge	(	vertex_descriptor	u,
		vertex_descriptor	v
	)		const

inlineinherited

Returns the edge between two vertices of the graph if the edge exists.

Parameters

u	The first vertex
u	The second vertex

Returns: An optional edge descriptor \(e\).

◆ find_root_from()

vertex_descriptor quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::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::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::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::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::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::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::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::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::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::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::is_isomorphic ( k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > > 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 k-ary tree graph.

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

◆ null_vertex()

static constexpr vertex_descriptor quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::null_vertex ( )

inlinestaticconstexprinherited

Null vertex identifier.

Returns: A null vertex

◆ predecessor()

vertex_descriptor quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::predecessor ( vertex_descriptor u ) const

inlineinherited

The predecessor of vertex \(u\).

Parameters

u	The vertex

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

◆ source()

vertex_descriptor quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::source ( edge_descriptor e ) const

inlineinherited

Returns the source vertex of a directed edge.

Parameters

e The edge

Returns: The source vertex of the edge \(e\).

◆ successors()

auto quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::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\).

◆ target()

vertex_descriptor quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, k_ary_tree< no_property, EdgeProperty > >::target ( edge_descriptor e ) const

inlineinherited

Returns the target vertex of a directed edge.

Parameters

e The edge

Returns: The target vertex of the edge \(e\).

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

/home/runner/work/quetzal-CoaTL/quetzal-CoaTL/src/include/quetzal/coalescence/graph/k_ary_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]

◆ edge()

◆ find_root_from()

◆ has_predecessor()

◆ has_successors()

◆ in_degree()

◆ in_edges()

◆ is_isomorphic()

◆ null_vertex()

◆ predecessor()

◆ source()

◆ successors()

◆ target()