Determines whether a graph is acyclic (contains no cycles). More...

#include <tpl_test_acyclique.H>

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

	Is_Graph_Acyclique (SA &__sa)

bool	operator() (GT &g, size_t num_arcs)
	Invokes the acyclicity test.

bool	operator() (GT &g)
	Invokes the acyclicity test.

Private Member Functions
bool	is_acyclique (typename GT::Node *curr)

bool	is_acyclique (GT &g, size_t num_arcs)

Private Attributes
SA &	sa

Detailed Description

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

Determines whether a graph is acyclic (contains no cycles).

Is_Graph_Acyclique performs a depth-first search on graph g, starting from a node, and checks whether the graph is acyclic; i.e., that it contains no 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 66 of file tpl_test_acyclique.H.

Constructor & Destructor Documentation

◆ Is_Graph_Acyclique() [1/2]

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

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

inline

Definition at line 119 of file tpl_test_acyclique.H.

◆ Is_Graph_Acyclique() [2/2]

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

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

inline

Definition at line 123 of file tpl_test_acyclique.H.

Member Function Documentation

◆ is_acyclique() [1/2]

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

bool Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique	(	GT &	g,
		size_t	num_arcs
	)

inlineprivate

Definition at line 94 of file tpl_test_acyclique.H.

References ah_domain_error_if, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), GraphCommon< GT, Node, Arc >::is_digraph(), IS_NODE_VISITED, Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), and Aleph::Test_Cycle.

◆ is_acyclique() [2/2]

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

bool Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique ( typename GT::Node * curr )

inlineprivate

Definition at line 70 of file tpl_test_acyclique.H.

References ARC_BITS, Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, Aleph::Is_Graph_Acyclique< GT, SA >::sa, and Aleph::Test_Cycle.

Referenced by Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique(), Aleph::Is_Graph_Acyclique< GT, SA >::operator()(), and Aleph::Is_Graph_Acyclique< GT, SA >::operator()().

◆ operator()() [1/2]

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

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

inline

Invokes the acyclicity 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 is not acyclic. Consequently, this technique does not work for multigraphs.

Parameters

[in] g the graph to test.

Returns: true if the graph contains no 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 166 of file tpl_test_acyclique.H.

References GraphCommon< GT, Node, Arc >::get_num_arcs(), and Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique().

◆ operator()() [2/2]

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

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

inline

Invokes the acyclicity 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 is not acyclic. Consequently, this technique does not work for multigraphs.

Parameters

[in]	g	the graph to test.
	num_arcs	number of arcs in g. Use this value if you are using filtered iterators over marked arcs, or arcs interpreted according to a given criterion. This way, the routine knows how many arcs satisfy the criterion.

Returns: true if the graph contains no 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 146 of file tpl_test_acyclique.H.

References Aleph::Is_Graph_Acyclique< GT, SA >::is_acyclique().