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

Member Function Documentation

operator()() [1/2]

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

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

operator()() [2/2]

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

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

---

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

• tpl_test_connectivity.H