Description

  Mathematical trees that use underlying graphs.

See also: Basic graphs support

Author: Juan-Antonio Fernandez-Madrigal. http://jafma.net

Date: 2018

Copyright: Copyright (c), Individual contributors, see AUTHORS file. This program is free for non-commercial uses. For the rest, contact the AUTHORS. Please include a mention in your programs to the main developer and the web page of the library.

Collaboration diagram for Trees:

Classes
class	elementa::adts::Tree< Vertex, Edge >
	This class is the base for any tree implementation. More...

class	elementa::adts::Szer_TreeText< Vertex, Edge >
	Serializer of any tree as a text with a tree-like structure. More...

Functions
void	elementa::adts::Szer_TreeText< Vertex, Edge >::ser (elementa::base::OutSerCh &chout, const TreeType &tree)
	Serialize. More...

Consulting methods
BGraph::viterator	elementa::adts::Tree< Vertex, Edge >::root (void) const
	Return an iterator to the root of the tree or to end() if empty. More...

graphs::size_edge	elementa::adts::Tree< Vertex, Edge >::depth (const typename BGraph::viterator &n) const
	Return the depth of the given node in the tree (0 for root). More...

Modification methods
BGraph::viterator	elementa::adts::Tree< Vertex, Edge >::setRoot (const Vertex &v)
	If the tree has a root, changes its value by V; otherwise, add V as root. More...

BGraph::viterator	elementa::adts::Tree< Vertex, Edge >::addChild (const typename BGraph::viterator &parent, const Vertex &v, const Edge &e)
	Add a new child to a given node, as the last child of the node. More...

void	elementa::adts::Tree< Vertex, Edge >::eraseNode (const typename BGraph::viterator &node)
	Erase a node and all its descendants. More...

void	elementa::adts::Tree< Vertex, Edge >::splice (Tree &oth, const Edge &edgeval)
	Move OTH to this tree, connecting its root to this root, and clearing it. More...

Class Documentation

◆ elementa::adts::Tree

class elementa::adts::Tree

template<class Vertex, class Edge>
class elementa::adts::Tree< Vertex, Edge >

This class is the base for any tree implementation.

The particular graph implementation that is used for supporting the tree is provided in the constructors, not becoming part of the tree type.

\code
using MyTree = Tree< char, double>;

MyTree tree{SparseGraph<MyTree::BGraph::VertexType,
                        MyTree::BGraph::EdgeType>{}};
\endcode

Definition at line 64 of file trees.h.

Public Types
Types, consts, etc.
using	BGraph = graphs::Graph< Vertex, Edge >
	Base Graph class of any particular graph implementation used in the tree. More...

using	Ptr = std::shared_ptr< Tree >
	Pointer to a tree. More...

using	Forest = std::vector< Ptr >
	A forest is a set of pointers to trees. More...

Public Member Functions
Constructors
	Tree (const BGraph &exemplar)
	Constructor. More...

	Tree (const Tree &oth)
	Copy constructor. More...

	Tree (Tree &&oth)
	Move constructor. More...

Tree &	operator= (const Tree &oth)
	Copy assignment. More...

Tree &	operator= (Tree &&oth)
	Move assignment. More...

virtual	~Tree (void)
	Virtual destructor. More...

Consulting methods
bool	empty (void) const
	Return TRUE if the tree is empty. More...

BGraph &	graph (void) const
	return a reference to the internal graph. More...

BGraph::viterator	root (void) const
	Return an iterator to the root of the tree or to end() if empty. More...

graphs::size_edge	depth (const typename BGraph::viterator &n) const
	Return the depth of the given node in the tree (0 for root). More...

Modification methods
void	clear (void)
	Clear the tree. More...

BGraph::viterator	setRoot (const Vertex &v)
	If the tree has a root, changes its value by V; otherwise, add V as root. More...

BGraph::viterator	addChild (const typename BGraph::viterator &parent, const Vertex &v, const Edge &e)
	Add a new child to a given node, as the last child of the node. More...

void	eraseNode (const typename BGraph::viterator &node)
	Erase a node and all its descendants. More...

void	splice (Tree &oth, const Edge &edgeval)
	Move OTH to this tree, connecting its root to this root, and clearing it. More...

Member Typedef Documentation

◆ BGraph

template<class Vertex , class Edge >

using elementa::adts::Tree< Vertex, Edge >::BGraph = graphs::Graph<Vertex,Edge>

Base Graph class of any particular graph implementation used in the tree.

Definition at line 72 of file trees.h.

◆ Ptr

template<class Vertex , class Edge >

using elementa::adts::Tree< Vertex, Edge >::Ptr = std::shared_ptr<Tree>

Pointer to a tree.

Definition at line 75 of file trees.h.

◆ Forest

template<class Vertex , class Edge >

using elementa::adts::Tree< Vertex, Edge >::Forest = std::vector<Ptr>

A forest is a set of pointers to trees.

Definition at line 78 of file trees.h.

Constructor & Destructor Documentation

◆ Tree() [1/3]

template<class Vertex , class Edge >

elementa::adts::Tree< Vertex, Edge >::Tree ( const BGraph & exemplar )

inline

Constructor.

Parameters

exemplar is just used to get an empty clone of a particular supporting graph type.

Note: - This could also be made with a templated constructor that admits the type of the supporting graph, but templated constructors, specially default ones, are problematic due to the way they are called from derived classes. For instance: https://stackoverflow.com/questions/2786946/c-invoke-explicit-template-constructor

Definition at line 96 of file trees.h.

◆ Tree() [2/3]

template<class Vertex , class Edge >

elementa::adts::Tree< Vertex, Edge >::Tree ( const Tree< Vertex, Edge > & oth )

inline

Copy constructor.

Definition at line 100 of file trees.h.

◆ Tree() [3/3]

template<class Vertex , class Edge >

elementa::adts::Tree< Vertex, Edge >::Tree ( Tree< Vertex, Edge > && oth )

inline

Move constructor.

Definition at line 104 of file trees.h.

◆ ~Tree()

template<class Vertex , class Edge >

virtual elementa::adts::Tree< Vertex, Edge >::~Tree ( void )

inlinevirtual

Virtual destructor.

Definition at line 116 of file trees.h.

Member Function Documentation

◆ operator=() [1/2]

template<class Vertex , class Edge >

Tree & elementa::adts::Tree< Vertex, Edge >::operator= ( const Tree< Vertex, Edge > & oth )

inline

Copy assignment.

Definition at line 108 of file trees.h.

◆ operator=() [2/2]

template<class Vertex , class Edge >

Tree & elementa::adts::Tree< Vertex, Edge >::operator= ( Tree< Vertex, Edge > && oth )

inline

Move assignment.

Definition at line 112 of file trees.h.

◆ empty()

template<class Vertex , class Edge >

bool elementa::adts::Tree< Vertex, Edge >::empty ( void ) const

inline

Return TRUE if the tree is empty.

Definition at line 126 of file trees.h.

References ELE_CODE_TRACE_OFF, and elementa::base::to_number().

Referenced by elementa::adts::Szer_TreeText< Vertex, Edge >::ser(), and elementa::adts::Tree< Vertex, Edge >::splice().

◆ graph()

template<class Vertex , class Edge >

BGraph & elementa::adts::Tree< Vertex, Edge >::graph ( void ) const

inline

return a reference to the internal graph.

Definition at line 132 of file trees.h.

Referenced by elementa::adts::Szer_TreeText< Vertex, Edge >::ser().

◆ clear()

template<class Vertex , class Edge >

void elementa::adts::Tree< Vertex, Edge >::clear ( void )

inline

Clear the tree.

Definition at line 148 of file trees.h.

Referenced by elementa::adts::Tree< Vertex, Edge >::splice().

◆ elementa::adts::Szer_TreeText

class elementa::adts::Szer_TreeText

template<class Vertex, class Edge>
class elementa::adts::Szer_TreeText< Vertex, Edge >

Serializer of any tree as a text with a tree-like structure.

Mainly useful for visualization.

Definition at line 195 of file trees.h.

Inheritance diagram for elementa::adts::Szer_TreeText< Vertex, Edge >:

[legend]

Collaboration diagram for elementa::adts::Szer_TreeText< Vertex, Edge >:

[legend]

Public Types
using	TreeType = Tree< Vertex, Edge >

using	SType = Tree< Vertex, Edge >
	To access the Sble type parameter of this type. More...

using	RDeserType = Tree< Vertex, Edge >
	To access the ReturnDeserType type parameter of this type. More...

using	RSerType = Tree< Vertex, Edge >
	To access the ReturnSerType type parameter of this type. More...

Public Member Functions
	Szer_TreeText (elementa::base::Serializer< Vertex > &szerv, elementa::base::Serializer< Edge > &szere)
	Constructor: configure the serializer. More...

void	ser (elementa::base::OutSerCh &chout, const TreeType &tree)
	Serialize. More...

virtual void	ser (OutSerCh &chout, const Tree< Vertex, Edge > &obj)
	Serializes an object, writing the resulting chars into CHOUT. More...

virtual void	deser (InSerCh &chin, Tree< Vertex, Edge > &obj)
	Deserializes an object from a sequence of chars in CHIN. More...

Member Typedef Documentation

◆ TreeType

template<class Vertex , class Edge >

using elementa::adts::Szer_TreeText< Vertex, Edge >::TreeType = Tree<Vertex,Edge>

Definition at line 199 of file trees.h.

◆ SType

using elementa::base::Serializer< Tree< Vertex, Edge > , void , void >::SType = Tree< Vertex, Edge >

inherited

To access the Sble type parameter of this type.

Definition at line 193 of file serializers.h.

◆ RDeserType

using elementa::base::Serializer< Tree< Vertex, Edge > , void , void >::RDeserType = Tree< Vertex, Edge >

inherited

To access the ReturnDeserType type parameter of this type.

Definition at line 196 of file serializers.h.

◆ RSerType

using elementa::base::Serializer< Tree< Vertex, Edge > , void , void >::RSerType = Tree< Vertex, Edge >

inherited

To access the ReturnSerType type parameter of this type.

Definition at line 199 of file serializers.h.

Constructor & Destructor Documentation

◆ Szer_TreeText()

template<class Vertex , class Edge >

elementa::adts::Szer_TreeText< Vertex, Edge >::Szer_TreeText	(	elementa::base::Serializer< Vertex > &	szerv,
		elementa::base::Serializer< Edge > &	szere
	)

inline

Constructor: configure the serializer.

SZERV will be used to serialize the Vertex class, and SZERE for the Edge class. Both serializers must exist beyond this serializer, since this method just take their references and do not copy them.

Definition at line 205 of file trees.h.

Member Function Documentation

◆ ser()

virtual void elementa::base::Serializer< Tree< Vertex, Edge > , void , void >::ser	(	OutSerCh &	chout,
		const Tree< Vertex, Edge > &	obj
	)

inlinevirtualinherited

Serializes an object, writing the resulting chars into CHOUT.

Must throw if any error during serialization, including channel errors (in that case, the channel can be left in the state it was when the error occurred).

Definition at line 206 of file serializers.h.

◆ deser()

virtual void elementa::base::Serializer< Tree< Vertex, Edge > , void , void >::deser	(	InSerCh &	chin,
		Tree< Vertex, Edge > &	obj
	)

inlinevirtualinherited

Deserializes an object from a sequence of chars in CHIN.

Must change the content of OBJ with the result. Throw if any error during serialization, including channel errors (in that case, the channel and the object are left in the state they were at the moment of the error).

Definition at line 214 of file serializers.h.

Function Documentation

◆ root()

template<class Vertex , class Edge >

Tree< Vertex, Edge >::BGraph::viterator elementa::adts::Tree< Vertex, Edge >::root ( void ) const

#include <elementa/adts/trees.h>

Return an iterator to the root of the tree or to end() if empty.

Definition at line 242 of file trees.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::begin(), elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::end(), elementa::adts::graphs::Graph< Vertex, Edge >::size_vertices(), and elementa::adts::graphs::Graph< Vertex, Edge >::vrangeAll().

Referenced by elementa::adts::Szer_TreeText< Vertex, Edge >::ser(), and elementa::adts::Tree< Vertex, Edge >::splice().

◆ depth()

template<class Vertex , class Edge >

graphs::size_edge elementa::adts::Tree< Vertex, Edge >::depth ( const typename BGraph::viterator & n ) const

#include <elementa/adts/trees.h>

Return the depth of the given node in the tree (0 for root).

This method has to traverse all parents of N to calculate the depth.

Definition at line 249 of file trees.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_Entering::begin(), elementa::adts::graphs::Graph< Vertex, Edge >::erangeEntering(), elementa::base::MultIterator< Data, BIDIR >::isEnd(), and elementa::adts::graphs::Graph< Vertex, Edge >::origin().

Referenced by elementa::adts::Szer_TreeText< Vertex, Edge >::ser().

◆ setRoot()

template<class Vertex , class Edge >

Tree< Vertex, Edge >::BGraph::viterator elementa::adts::Tree< Vertex, Edge >::setRoot ( const Vertex & v )

#include <elementa/adts/trees.h>

If the tree has a root, changes its value by V; otherwise, add V as root.

Return an iterator to the new node.

Definition at line 269 of file trees.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::VRange_All::begin(), ELE_CODE_TRACE_OFF, elementa::adts::graphs::Graph< Vertex, Edge >::insert(), elementa::adts::graphs::Graph< Vertex, Edge >::size_vertices(), and elementa::adts::graphs::Graph< Vertex, Edge >::vrangeAll().

◆ addChild()

template<class Vertex , class Edge >

Tree< Vertex, Edge >::BGraph::viterator elementa::adts::Tree< Vertex, Edge >::addChild	(	const typename BGraph::viterator &	parent,
		const Vertex &	v,
		const Edge &	e
	)

#include <elementa/adts/trees.h>

Add a new child to a given node, as the last child of the node.

Return an iterator to the new child node.

Definition at line 285 of file trees.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::connect(), ELE_CODE_INVARG, ELE_CODE_TRACE_OFF, elementa::adts::graphs::Graph< Vertex, Edge >::insert(), elementa::base::MultIterator< Data, BIDIR >::isEnd(), elementa::base::MultIterator< Data, BIDIR >::to_string(), and elementa::base::MultIterator< Data, BIDIR >::valid().

◆ eraseNode()

template<class Vertex , class Edge >

void elementa::adts::Tree< Vertex, Edge >::eraseNode ( const typename BGraph::viterator & node )

#include <elementa/adts/trees.h>

Erase a node and all its descendants.

Definition at line 305 of file trees.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_DepthFirst::begin(), elementa::adts::graphs::Graph< Vertex, Edge >::connection(), ELE_CODE_TRACE_OFF, elementa::adts::graphs::Graph< Vertex, Edge >::erangeDepthFirst(), and elementa::adts::graphs::Graph< Vertex, Edge >::erase().

◆ splice()

template<class Vertex , class Edge >

void elementa::adts::Tree< Vertex, Edge >::splice	(	Tree< Vertex, Edge > &	oth,
		const Edge &	edgeval
	)

#include <elementa/adts/trees.h>

Move OTH to this tree, connecting its root to this root, and clearing it.

EDGEVAL must have the value to annotate in the edge that connects this root with OTH root.

Definition at line 327 of file trees.h.

References elementa::adts::Tree< Vertex, Edge >::clear(), elementa::adts::graphs::Graph< Vertex, Edge >::connect(), ELE_CODE_TRACE_OFF, elementa::adts::Tree< Vertex, Edge >::empty(), elementa::adts::Tree< Vertex, Edge >::root(), and elementa::adts::graphs::Graph< Vertex, Edge >::splice().

◆ ser()

template<class Vertex , class Edge >

void elementa::adts::Szer_TreeText< Vertex, Edge >::ser	(	elementa::base::OutSerCh &	chout,
		const TreeType &	tree
	)

#include <elementa/adts/trees.h>

Serialize.

Definition at line 356 of file trees.h.

References elementa::adts::Tree< Vertex, Edge >::depth(), ELE_CODE_PLACE, ELE_CODE_TRACE_OFF, elementa::adts::Tree< Vertex, Edge >::empty(), elementa::adts::Tree< Vertex, Edge >::graph(), elementa::adts::Tree< Vertex, Edge >::root(), elementa::base::serch_isgood(), and elementa::adts::graphs::Graph< Vertex, Edge >::size_edges().

Description

Classes

Functions

Consulting methods

Modification methods

Class Documentation

◆ elementa::adts::Tree

Public Types

Public Member Functions

Member Typedef Documentation

◆ BGraph

◆ Ptr

◆ Forest

Constructor & Destructor Documentation

◆ Tree() [1/3]

◆ Tree() [2/3]

◆ Tree() [3/3]

◆ ~Tree()

Member Function Documentation

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ empty()

◆ graph()

◆ clear()

◆ elementa::adts::Szer_TreeText

Public Types

Public Member Functions

Member Typedef Documentation

◆ TreeType

◆ SType

◆ RDeserType

◆ RSerType

Constructor & Destructor Documentation

◆ Szer_TreeText()

Member Function Documentation

◆ ser()

◆ deser()

Function Documentation

◆ root()

◆ depth()

◆ setRoot()

◆ addChild()

◆ eraseNode()

◆ splice()

◆ ser()