Determines whether a graph contains cycles. More...

#include <tpl_test_acyclique.H>

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

	Has_Cycle (SA &__sa)

bool	operator() (GT &g) const
	Invokes the cycle-existence test.

bool	operator() (GT &g, size_t num_arcs) const
	Invokes the cycle-existence test.

Private Attributes
SA &	sa

Detailed Description

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

Determines whether a graph contains cycles.

Has_Cycle performs a depth-first search on graph g, starting from a node, and checks whether the graph contains a cycle.

The class takes two template parameters:

GT: the graph type, which must be derived from List_Graph.
SA: a class responsible for selecting/showing arcs. Internally, the function uses the filtered iterator Node_Arc_Iterator (based on Filter_Iterator) to traverse each node's arcs. SA is the class that decides whether an arc is included in the traversal.

The class uses the Test_Cycle bit and resets it at the beginning of the algorithm to mark already visited nodes and arcs.

Definition at line 190 of file tpl_test_acyclique.H.

Constructor & Destructor Documentation

◆ Has_Cycle() [1/2]

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

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

inline

Definition at line 195 of file tpl_test_acyclique.H.

◆ Has_Cycle() [2/2]

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

Aleph::Has_Cycle< GT, SA >::Has_Cycle ( SA & __sa )

inline

Definition at line 199 of file tpl_test_acyclique.H.

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

Invokes the cycle-existence test.

If g is an undirected graph (not a digraph), then the algorithm compares the number of arcs with the number of nodes. If the graph has as many arcs as nodes (or more), then it is concluded that the graph contains cycles. Consequently, this technique does not work for multigraphs.

Parameters

[in] g the graph to test.

Returns: true if the graph contains at least one cycle; false otherwise.

Note: Because of the initial arc-count check, this routine can be preferable to test_for_cycle(), even if you know the graph is connected, since the latter routine always performs a depth-first search, while is_graph_acyclique() may not.

Definition at line 218 of file tpl_test_acyclique.H.

References Aleph::maps(), and Aleph::Has_Cycle< GT, SA >::sa.

◆ operator()() [2/2]

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

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

inline

Invokes the cycle-existence test.

If g is an undirected graph (not a digraph), then the algorithm compares the number of arcs with the number of nodes. If the graph has as many arcs as nodes (or more), then it is concluded that the graph contains cycles. Consequently, this technique does not work for multigraphs.

Parameters

[in]	g	the graph to test.
[in]	num_arcs	number of arcs in the graph (for optimization).

Returns: true if the graph contains at least one cycle; false otherwise.

Note: Because of the initial arc-count check, this routine can be preferable to test_for_cycle(), even if you know the graph is connected, since the latter routine always performs a depth-first search, while is_graph_acyclique() may not.

Definition at line 239 of file tpl_test_acyclique.H.

References Aleph::maps(), and Aleph::Has_Cycle< GT, SA >::sa.