Aleph::Graph_To_Tree_Node< GT, Key, Convert, SA > Class Template Reference

#include <graph_to_tree.H>

Public Member Functions
	Graph_To_Tree_Node (SA __sa=SA())
Tree_Node< Key > *	operator() (GT &g, typename GT::Node *groot, Convert &&conv=Convert())
Tree_Node< Key > *	operator() (GT &g, typename GT::Node *groot, Convert &conv)

Detailed Description

template<class GT, typename Key, class Convert, class SA = Dft_Show_Arc<GT>>
class Aleph::Graph_To_Tree_Node< GT, Key, Convert, SA >

Convierte un árbol representado en una representación de grafo a un árbol Tree_Node.

graph_to_tree_node() toma un árbol representado mediante algún tipo de grafo representado con listas de adyacencia y un nodo groot que se asume raíz del árbol y lo convierte a un árbol representado con el tipo Tree_Node<Key>.

El interés de esta rutina es obtener una representación del árbol en la cual se puedan aplicar otras técnicas, clases y algoritmos. Un ejemplo representativo es el dibujado de árboles inherentes a los grafos; en la ocurrencia, árboles abarcadores.

El procedimiento utiliza el bit spanning_tree para marcar los nodos y arcos ya visitados.

Como medio de representación, el tipo Tree_Node<Key> es menos versátil que cualquier tipo basado en un grafo representado con listas de adyacencia; por ejemplo, List_graph. Note, por instancia, que List_Graph<Node,Arc> estipula un tipo para los arcos, mientras que no ocurre lo mismo para Tree_Node<Key>. En este sentido, como representación, Tree_Node<Key> no tiene ningún medio para guardar los datos asociados a los arcos. Consecuentemente, sólo se podría manejar los datos contenidos en los nodos. Por otra parte, el tipo guardado en GT::Node puede ser de índole distinta al guardado en Tree_Node<Key>.

A menudo (ese es el caso típico del dibujado), el tipo de dato a guardar en Tree_Node<Key> es de índole distinta al guardado en GT::Node. Otras veces, lo que se desea guardar en cada Tree_Node<Key> es un subconjunto de lo que está guardado en GT::Node. Puesto que es imposible generizar todos los casos posibles, la escritura de cada Tree_Node<Key> se delega a una clase cuyo operador ()() es invocado por la rutina de conversión para cada nodo del grafo. La clase en cuestión es el parámetro tipo Convert.

La clase Convert se invoca de la siguiente manera:

void Convert::operator () (gnode, tnode)

donde:
-# gnode es de tipo GT::Node
-# tnode de tipo Tree_Node<Key>

La rutina hace una prueba de aciclicidad sobre g mediante la función is_graph_acyclique(), lo que no afecta la complejidad algorítmica de pero que toma tiempo adicional.

El procedimiento maneja los siguientes tipos parametrizados:

1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
2. Key: el tipo de dato que albergará el árbol en su representación Tree_Node<Key>.
3. Convert: clase de conversión de GT::Node a Key, cuyo operador ()(gnode,tnode) es invocado por cada nodo de g cuando se realiza la conversión a uno Tree_Node.
4. SA: el filtro de arcos.

See also

Tree_Node is_graph_acyclique()

Member Function Documentation

operator()()

template<class GT , typename Key , class Convert , class SA = Dft_Show_Arc<GT>>

Tree_Node<Key>* Aleph::Graph_To_Tree_Node< GT, Key, Convert, SA >::operator() ( GT &  g, typename GT::Node *  groot, Convert &&  conv = Convert()  )

inline

Invoca a la conversión de grafo hacia árbol abarcador.

Parameters

[in]	g	el árbol de tipo GT (derivado de List_Graph) que se desea convertir.
[in]	groot	el nodo de g que se considera raíz del árbol.
[in]	conv	clase de conversión.

Returns

la raíz de un árbol de tipo Tree_Node<Key> correspondiente a la conversión

Exceptions

bad_alloc

si no hay memoria para apartar el árbol de tipo Tree_Node<Key>

---

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

• graph_to_tree.H