#include <quetzal/coalescence/graph/detail/cardinal_k_ary_tree.hpp>

Detailed Description

template<typename Vertex>
class boost::binary_tree< true, Vertex >

Bidirectional Binary Tree.

Template Parameters

Vertex

Classes
class	traversal_category
	The ways in which the vertices in the graph can be traversed. More...

Public Types
using	directed_category = bidirectional_tag
	Directed, undirected or bidirectional.

using	edge_descriptor = typename super_t::edge_descriptor
	The type for the objects used to identify edges in the graph.

using	vertex_descriptor = typename super_t::vertex_descriptor
	The type for the objects used to identify vertices in the graph.

using	degree_size_type = typename super_t::degree_size_type
	The integer type for vertex degree.

using	edge_parallel_category = typename super_t::edge_parallel_category

typedef std::size_t	vertices_size_type

Public Member Functions
void	clear_childrens_predecessor (vertex_descriptor u)
	Clears the children's predecessor.

BOOST_STATIC_CONSTEXPR vertex_descriptor	null_vertex ()

std::size_t	num_vertices () const

detail::binary_tree_bidirectional_node< binary_tree< true, Vertex > > const &	operator[] (vertex_descriptor u) const

bool	has_successor (vertex_descriptor u) const

void	clear ()

void	shrink_to_fit ()

Protected Member Functions
vertex_descriptor	add_vertex ()

bool	add_vertex (vertex_descriptor u)

void	remove_vertex (vertex_descriptor u)

std::pair< edge_descriptor, bool >	add_edge (vertex_descriptor u, vertex_descriptor v)

std::pair< edge_descriptor, bool >	add_edge_strict (vertex_descriptor u, vertex_descriptor v)

void	remove_edge (vertex_descriptor u, vertex_descriptor v)

void	clear_vertex (vertex_descriptor u)

edge_descriptor	add_left_edge (vertex_descriptor parent, vertex_descriptor child)

edge_descriptor	add_right_edge (vertex_descriptor parent, vertex_descriptor child)

Protected Attributes
std::vector< detail::binary_tree_bidirectional_node< binary_tree< true, Vertex > > >	nodes

std::vector< Vertex >	free_list

Friends
edge_descriptor	add_left_edge (vertex_descriptor parent, vertex_descriptor child, binary_tree &g)
	Add a left edge to the parent vertex.

edge_descriptor	add_right_edge (vertex_descriptor parent, vertex_descriptor child, binary_tree &g)
	Add a right edge to the parent vertex.

vertex_descriptor	root (vertex_descriptor u, binary_tree const &g)
	Finds the root of the tree graph starting from a vertex u.

bool	is_left_successor (vertex_descriptor u, binary_tree const &g)
	Evaluate if a vertex is a left successor (child)

bool	is_right_successor (vertex_descriptor u, binary_tree const &g)
	Evaluate if a vertex is a right successor (child)

bool	has_predecessor (vertex_descriptor u, binary_tree const &g)
	Evaluates if the vertex has a predecessor (parent)

vertex_descriptor	predecessor (vertex_descriptor u, binary_tree const &g)
	The predecessor of a given vertex.

MutableGraph interface
std::pair< edge_descriptor, bool >	add_edge (vertex_descriptor u, vertex_descriptor v, binary_tree &g)
	Inserts the edge (u,v) into the graph.

void	remove_edge (vertex_descriptor u, vertex_descriptor v, binary_tree &g)
	Remove the edge (u,v) from the graph.

void	remove_edge (edge_descriptor e, binary_tree &g)
	Remove the edge e from the graph.

void	clear_vertex (vertex_descriptor u, binary_tree &g)
	Remove all edges to and from vertex u from the graph.

void	remove_vertex (vertex_descriptor u, binary_tree &g)
	Remove u from the vertex set of the graph.

BidirectionalGraph interface
using	in_edge_iterator = transform_iterator< make_in_edge_descriptor, vertex_descriptor const *, edge_descriptor >
	Iterate through the in-edges.

degree_size_type	in_degree (vertex_descriptor u, binary_tree const &g)
	Returns the number of in-edges of vertex v in graph g.

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

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

Member Function Documentation

◆ clear_childrens_predecessor()

template<typename Vertex >

void boost::binary_tree< true, Vertex >::clear_childrens_predecessor ( vertex_descriptor u )

inline

Clears the children's predecessor.

Parameters

u

Friends And Related Symbol Documentation

◆ add_edge

template<typename Vertex >

std::pair< edge_descriptor, bool > add_edge	(	vertex_descriptor	u,
		vertex_descriptor	v,
		binary_tree< true, Vertex > &	g
	)

friend

Inserts the edge (u,v) into the graph.

Remarks: If the graph disallows parallel edges, and the edge (u,v) is already in the graph, then the bool flag returned is false and the returned edge descriptor points to the already existing edge.

Parameters

u	Vertex u
v	Vertex v
g	Binary tree graph

Returns: An edge descriptor pointing to the new edge

◆ add_left_edge

template<typename Vertex >

edge_descriptor add_left_edge	(	vertex_descriptor	parent,
		vertex_descriptor	child,
		binary_tree< true, Vertex > &	g
	)

friend

Add a left edge to the parent vertex.

Parameters

parent	The parent vertex
child	The child vertex
g	The binary tree graph

Returns: The descriptor of the edge added.

◆ add_right_edge

template<typename Vertex >

edge_descriptor add_right_edge	(	vertex_descriptor	parent,
		vertex_descriptor	child,
		binary_tree< true, Vertex > &	g
	)

friend

Add a right edge to the parent vertex.

Parameters

parent	The parent vertex
child	The child vertex
g	The binary tree graph

Returns: The descriptor of the edge added

◆ clear_vertex

template<typename Vertex >

void clear_vertex	(	vertex_descriptor	u,
		binary_tree< true, Vertex > &	g
	)

friend

Remove all edges to and from vertex u from the graph.

Parameters

u	Vertex u
g	The binary tree graph.

◆ degree

template<typename Vertex >

degree_size_type degree	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

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

Parameters

u	The vertex u
g	The binary tree graph

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

◆ has_predecessor

template<typename Vertex >

bool has_predecessor	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

Evaluates if the vertex has a predecessor (parent)

Parameters

u	The vertex to evaluate
g	The binary tree graph

Returns: True if u has a predecessor, false otherwise

◆ in_degree

template<typename Vertex >

degree_size_type in_degree	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

Returns the number of in-edges of vertex v in graph g.

Parameters

u	The vertex u
g	The binary tree graph

Returns: The number of in-edges.

◆ in_edges

template<typename Vertex >

std::pair< in_edge_iterator, in_edge_iterator > in_edges	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

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

Parameters

u	The vertex u
g	The binary tree graph

Returns: A pair of iterators

◆ is_left_successor

template<typename Vertex >

bool is_left_successor	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

Evaluate if a vertex is a left successor (child)

Parameters

u	The vertex to be evaluated
g	The binary tree graph

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

◆ is_right_successor

template<typename Vertex >

bool is_right_successor	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

Evaluate if a vertex is a right successor (child)

Parameters

u	The vertex to be evaluated
g	The binary tree graph

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

◆ predecessor

template<typename Vertex >

vertex_descriptor predecessor	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

The predecessor of a given vertex.

Parameters

u	The vertex
g	The binary tree graph.

Returns: The vertex that is the predecessor of u.

◆ remove_edge [1/2]

template<typename Vertex >

void remove_edge	(	edge_descriptor	e,
		binary_tree< true, Vertex > &	g
	)

friend

Remove the edge e from the graph.

Parameters

e	The edge to be removed
g	The binary tree graph

◆ remove_edge [2/2]

template<typename Vertex >

void remove_edge	(	vertex_descriptor	u,
		vertex_descriptor	v,
		binary_tree< true, Vertex > &	g
	)

friend

Remove the edge (u,v) from the graph.

Parameters

u	Vertex u
v	Vertex v
g	The binary tree graph

◆ remove_vertex

template<typename Vertex >

void remove_vertex	(	vertex_descriptor	u,
		binary_tree< true, Vertex > &	g
	)

friend

Remove u from the vertex set of the graph.

Note: Undefined behavior may result if there are edges remaining in the graph who's target is u. Typically the clear_vertex() function should be called first.

Parameters

u
g

◆ root

template<typename Vertex >

vertex_descriptor root	(	vertex_descriptor	u,
		binary_tree< true, Vertex > const &	g
	)

friend

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

Parameters

u	The vertex to start from.
g	The binary tree graph.

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

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

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

Detailed Description

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Friends

BidirectionalGraph interface

Member Function Documentation

◆ clear_childrens_predecessor()

Friends And Related Symbol Documentation

◆ add_edge

◆ add_left_edge

◆ add_right_edge

◆ clear_vertex

◆ degree

◆ has_predecessor

◆ in_degree

◆ in_edges

◆ is_left_successor

◆ is_right_successor

◆ predecessor

◆ remove_edge [1/2]

◆ remove_edge [2/2]

◆ remove_vertex

◆ root