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<AlephGraph GT, ArcFilter< GT > 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 192 of file tpl_test_acyclique.H.

Constructor & Destructor Documentation

◆ Has_Cycle() [1/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inline

Definition at line 197 of file tpl_test_acyclique.H.

◆ Has_Cycle() [2/2]

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inline

Definition at line 201 of file tpl_test_acyclique.H.

Member Function Documentation

◆ operator()() [1/2]

template<AlephGraph GT, ArcFilter< GT > 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 220 of file tpl_test_acyclique.H.

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

◆ operator()() [2/2]

template<AlephGraph GT, ArcFilter< GT > 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 241 of file tpl_test_acyclique.H.

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