#include <tpl_test_acyclique.H>

Public Member Functions
	Has_Cycle (SA &&__sa=SA())

	Has_Cycle (SA &__sa)

bool	operator() (GT &g) const

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

Detailed Description

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.

Member Function Documentation

◆ operator()() [1/2]

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.

Parameters

[in] g el grafo a probar.

Returns: true si el grafo no contiene ningÃºn ciclo; false de lo contrario.

Note: 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.

◆ operator()() [2/2]