Referencia de la plantilla de la Clase Aleph::Depth_First_Traversal< GT, Operation, SA >

#include <tpl_graph_utils.H>

Métodos públicos
	Depth_First_Traversal (SA &&__sa=SA())
	Depth_First_Traversal (SA &__sa)
size_t	operator() (GT &g, Operation &&op=Operation())
size_t	operator() (GT &g, Operation &op)
size_t	operator() (GT &g, typename GT::Node *sn, Operation &&op=Operation())
size_t	operator() (GT &g, typename GT::Node *sn, Operation &op)

Descripción detallada

template<class GT, class Operation = Default_Visit_Op<GT>, class SA = Dft_Show_Arc<GT>>
class Aleph::Depth_First_Traversal< GT, Operation, SA >

Recorrido genérico en profundidad de un grafo.

Esta clase recorre en profundidad el grafo g. Por cada nodo visitado, se invoca a una función cuyo prototipo debe ser:

bool visitar(GT & g, typename GT::Node * p, typename GT::Arc * a)

Cuyos parámetros se describen a continuación:

1. g: el grafo.
2. p: el nodo actual que se está visitando en profundidad.
3. a: el arco que conduce al nodo actual p.

La clase toma dos parámetros tipo:

1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
2. Op: la operación de "visita" a efectuar cada vez que se vea un nuevo nodo.
3. 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. Mediante esta clase, el recorrido en profundidad se puede especializar para procese los arcos según algún criterio; arcos residuales de una red residual de flujo, por ejemplo.

La operación de visita tiene la siguiente estructura:

struct Operation
{
  bool operator () (GT & g,
                    typename GT::Node * node, 
                    typename GT::Arc * arc)
  {
    // return true si el recorrido se debe detener; 
    // false de lo contrario
  }
};

El primer parámetro g es el grafo. El segundo node es el nodo actual de visita. Finalmente, el tercero arc es el arco desde el cual se llega a node. Este valor es NULL en el caso del primer nodo que se visite.

Si la función retorna true, entonces el recorrido se detiene; es decir, no se prosigue el recorrido sobre el grafo. Si la función retorna false, entonces el recorrido en profundidad prosigue y se detendría una vez que todos los arcos del grafo hayan sido vistos.

El recorrido utiliza el bit depth_first, el cual es iniciado al principio del algoritmo.

Ver también

breadth_first_traversal() test_connectivity() Filter_Iterator

Documentación del constructor y destructor

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

Aleph::Depth_First_Traversal< GT, Operation, SA >::Depth_First_Traversal ( SA &&  __sa = SA() )

inline

Constructor de Functor Depth_First_Traversal. El parámetro es el filtro de arcos del iterador interno.

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

Aleph::Depth_First_Traversal< GT, Operation, SA >::Depth_First_Traversal ( SA &  __sa )

inline

Constructor de Functor Depth_First_Traversal. El parámetro es el filtro de arcos del iterador interno.

Documentación de las funciones miembro

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

size_t Aleph::Depth_First_Traversal< GT, Operation, SA >::operator() ( GT &  g, Operation &&  op = Operation()  )

inline

Invoca al recorrido en profundidad.

Parámetros

[in]	g	el grafo a explorar.
[in]	__op	la operación de visita.

Devuelve

el número de nodos que fueron visitados

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

size_t Aleph::Depth_First_Traversal< GT, Operation, SA >::operator() ( GT &  g, typename GT::Node *  sn, Operation &&  op = Operation()  )

inline

Invoca al recorrido en profundidad con inicio desde un nodo particular.

Parámetros

[in]	g	el grafo a explorar.
[in]	sn	el nodo por donde se inicia el recorrido.
[in]	__op	operación de visita.

Devuelve

el número de nodos que fueron visitados

---

La documentación para esta clase fue generada a partir del siguiente fichero:

• tpl_graph_utils.H