Test_Connectivity< GT, SA > Class Template Reference

Determines if a graph g is connected. More...

#include <tpl_test_connectivity.H>

Public Member Functions
bool	operator() (GT &g, SA &&sa=SA()) const
	Invokes the connectivity test.
bool	operator() (GT &g, SA &sa) const
	Invokes the connectivity test.

Detailed Description

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

Determines if a graph g is connected.

This class performs a connectivity test on graph g. The test uses a depth-first traversal.

The class verifies the number of arcs. If this number is less than the number of nodes minus one, then the graph is considered disconnected.

The function takes two type parameters:

1. GT: the graph type, which must be derived from List_Graph.
2. SA: class responsible for showing the arc. Internally, the function uses the filtered iterator Node_Arc_Iterator (based on Filter_Iterator) to traverse the arcs of each node. SA is the class that determines whether the arc should be shown during traversal.

See also

depth_first_traversal() is_reachable()

Definition at line 67 of file tpl_test_connectivity.H.

Member Function Documentation

operator()() [1/2]

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

bool Test_Connectivity< GT, SA >::operator() ( GT &  g, SA &&  sa = SA()  ) const

inline

Invokes the connectivity test.

This version is used when the arc filter needs to maintain state.

Parameters

g	the graph or digraph to verify
sa	the arc filter for the graph (rvalue reference, default: Dft_Show_Arc<GT>)

Returns

true if the graph is connected; false otherwise.

Note

Due to the test with the number of arcs, this function is incorrect for multigraphs.

Exceptions

domain_error

if the routine is invoked on a digraph.

Definition at line 82 of file tpl_test_connectivity.H.

References ah_domain_error_if, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), and Aleph::maps().

operator()() [2/2]

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

bool Test_Connectivity< GT, SA >::operator() ( GT &  g, SA &  sa  ) const

inline

Invokes the connectivity test.

This version is used when the arc filter needs to maintain state.

Parameters

g	the graph or digraph to verify
sa	the arc filter for the graph (lvalue reference)

Returns

true if the graph is connected; false otherwise.

Note

Due to the test with the number of arcs, this function is incorrect for multigraphs.

Exceptions

domain_error

if the routine is invoked on a digraph.

Definition at line 106 of file tpl_test_connectivity.H.

References ah_domain_error_if, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), and Aleph::maps().

---

The documentation for this class was generated from the following file:

• tpl_test_connectivity.H