Public Types
using	vertex_descriptor = typename base::vertex_descriptor
	Vertex descriptor ("node ID" in other words).

using	edge_descriptor = typename base::edge_descriptor
	Edge 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
	k_ary_tree_common ()
	Default constructor.

	k_ary_tree_common (size_t n)
	Constructs a tree with \(n\) vertices.

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

template<typename DFSTreeVisitor >
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.

template<typename Generator >
static std::tuple< CRTP, vertex_descriptor >	make_random_tree (int n_leaves, int k_max, Generator &rng)

Protected Types
using	base = tree_traits::model< tree_traits::out_edge_list_type, tree_traits::vertex_list_type, tree_traits::directed_type, VertexProperty, EdgeProperty >
	The type of graph hold by the tree class.

Protected Attributes
base	_graph

Member Function Documentation

◆ degree()

template<class VertexProperty , class EdgeProperty , class CRTP >

degree_size_type quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::degree ( vertex_descriptor u ) const

inline

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]

template<class VertexProperty , class EdgeProperty , class CRTP >

template<typename DFSTreeVisitor >

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

inline

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]

template<class VertexProperty , class EdgeProperty , class CRTP >

template<typename DFSTreeVisitor >

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

inline

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()

template<class VertexProperty , class EdgeProperty , class CRTP >

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

inline

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()

template<class VertexProperty , class EdgeProperty , class CRTP >

vertex_descriptor quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::find_root_from ( vertex_descriptor u ) const

inline

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()

template<class VertexProperty , class EdgeProperty , class CRTP >

bool quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::has_predecessor ( vertex_descriptor u ) const

inline

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

Parameters

u	The vertex to evaluate

Returns: True if u has a predecessor, false otherwise

◆ has_successors()

template<class VertexProperty , class EdgeProperty , class CRTP >

bool quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::has_successors ( vertex_descriptor u ) const

inline

Evaluates if vertex \(u\) has successors.

Parameters

u	The vertex to evaluate

Returns: True if u has successors, false otherwise

◆ in_degree()

template<class VertexProperty , class EdgeProperty , class CRTP >

degree_size_type quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::in_degree ( vertex_descriptor u ) const

inline

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

Parameters

u	The vertex \(u\)

Returns: The number of in-edges.

◆ in_edges()

template<class VertexProperty , class EdgeProperty , class CRTP >

std::pair< in_edge_iterator, in_edge_iterator > quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::in_edges ( vertex_descriptor u ) const

inline

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

Parameters

u	The vertex \(u\).

Returns: A pair of iterators.

◆ is_isomorphic()

template<class VertexProperty , class EdgeProperty , class CRTP >

bool quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::is_isomorphic ( k_ary_tree_common< VertexProperty, EdgeProperty, CRTP > const & other ) const

inline

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()

template<class VertexProperty , class EdgeProperty , class CRTP >

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

inlinestaticconstexpr

Null vertex identifier.

Returns: A null vertex

◆ predecessor()

template<class VertexProperty , class EdgeProperty , class CRTP >

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

inline

The predecessor of vertex \(u\).

Parameters

u	The vertex

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

◆ source()

template<class VertexProperty , class EdgeProperty , class CRTP >

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

inline

Returns the source vertex of a directed edge.

Parameters

e The edge

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

◆ successors()

template<class VertexProperty , class EdgeProperty , class CRTP >

auto quetzal::coalescence::detail::k_ary_tree_common< VertexProperty, EdgeProperty, CRTP >::successors ( vertex_descriptor u ) const

inline

The successors of vertex \(u\).

Parameters

u	The vertex

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

◆ target()

template<class VertexProperty , class EdgeProperty , class CRTP >

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

inline

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

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

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()