Aleph::Find_Depth_First_Spanning_Tree< GT, SA > Class Template Reference

#include <tpl_spanning_tree.H>

Public Member Functions
	Find_Depth_First_Spanning_Tree (SA __sa=SA())
GT::Node *	operator() (GT &g, GT &tree)
GT::Node *	operator() (GT &g, typename GT::Node *gnode, GT &tree)

Detailed Description

template<class GT, class SA = Dft_Show_Arc<GT>>
class Aleph::Find_Depth_First_Spanning_Tree< GT, SA >

Calcula un árbol abarcador en profundidad de un grafo.

Esta clase toma un grafo g, efectúa un recorrido en profundidad a partir de un nodo seleccionado y construye el árbol abarcador según el orden de visita dado por el recorrido.

La clase toma dos parámetros tipo:

1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido.

See also

find_breadth_first_spanning_tree() Tree_Node

graph_to_tree_node()

Member Function Documentation

operator()() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

GT::Node* Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::operator() ( GT &  g, GT &  tree  )

inline

Invoca a la construcción de árbol abarcador en profundidad.

Luego de la operación el parámetro tree contiene el árbol abarcador en cuestión con sus arcos y nodos mapeados al grafo g.

Durante la ejecución, el algoritmo marca los nodos y arcos visitados con el bit el spanning_tree.

El orden de visita del grafo no necesariamente es el mismo que el de la primitiva depth_first_traversal().

Parameters

[in]	g	el grafo sobre el cual se desea construir el árbol abarcador en profundidad.
[out]	tree	grafo donde se colocará el árbol abarcador de profundidad.

Returns

si el grafo es conexo y existe un árbol abarcador, se retorna un puntero al nodo desde donde se inicia la búsqueda en profundidad; de lo contrario se retorna nullptr.

Exceptions

bad_alloc

si no hay memoria para construir el árbol abarcador.

operator()() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

GT::Node* Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::operator() ( GT &  g, typename GT::Node *  gnode, GT &  tree  )

inline

Invoca a la construcción de árbol abarcador en profundidad a partir de un nodo dado.

Luego de la operación el parámetro tree contiene el árbol abarcador en cuestión con sus arcos y nodos mapeados al grafo g.

Durante la ejecución, el algoritmo marca los nodos y arcos visitados con el bit el spanning_tree.

El orden de visita del grafo no necesariamente es el mismo que el de la primitiva depth_first_traversal().

Parameters

[in]	g	el grafo sobre el cual se desea construir el árbol abarcador en profundidad.
[in]	gnode	nodo desde el cual se deseaq iniciar la búsqueda en profundidad.
[out]	tree	grafo donde se colocará el árbol abarcador de profundidad.

Returns

puntero al nodo desde donde se inicia la búsqueda en profundidad; de lo contrario se retorna nullptr.

Exceptions

bad_alloc

si no hay memoria para construir el árbol abarcador.

---

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

• tpl_spanning_tree.H