#include <tpl_test_acyclique.H>

Métodos públicos
	Has_Cycle (SA &&__sa=SA())

	Has_Cycle (SA &__sa)

bool	operator() (GT &g) const

bool	operator() (GT &g, size_t num_arcs) const

Descripción detallada

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

Determina si un grafo contiene o no ciclos.

Has_Cycle explora en profundidad en grafo g, a partir de un nodo y verifica si el grafo es acíclico; es decir, que no contenga ningún ciclo.

La clase toma dos parámetros tipo:

GT: el tipo de grafo, el cual debe ser derivado de List_Graph.
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.

La clase usa el bit is_acyclique y lo reinicia al principio del algoritmo para marcar los nodos y arcos ya visitados.

Documentación de las funciones miembro

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

bool Aleph::Has_Cycle< GT, SA >::operator() ( GT & g ) const

inline

Invoca la prueba de existencia de ciclos.

Si g es un grafo (no un digrafo) entonces el algoritmo compara la cantidad de arcos con la de nodos. Si el grafo tiene igual o más arcos que nodos, entonces se concluye que el grafo tiene ciclos. Consecuentemente, esta técnica no opera para multigrafos.

Parámetros

[in] g el grafo a probar.

Devuelve: true si el grafo no contiene ningún ciclo; false de lo contrario.

Nota: Debido a la prueba inicial con la cantidad de arcos, esta rutina es preferible que test_for_cycle(), aún bajo el conocimiento de que el grafo es conexo, pues esta última rutina siempre realiza la exploración en profundidad, mientras que is_graph_acyclique() no.