Aleph::Test_For_Path< GT, SA > Class Template Reference

Checks whether a path exists between two nodes. More...

#include <tpl_test_path.H>

Public Member Functions
	Test_For_Path (SA __sa=SA())
bool	operator() (const GT &g, typename GT::Node *start_node, typename GT::Node *end_node)
	Invokes the test for a path's existence between two nodes.

Private Member Functions
bool	test_path (typename GT::Node *curr)
bool	test_path (const GT &g, typename GT::Node *src, typename GT::Node *dest)

Private Attributes
SA	sa
GT::Node *	tgt = nullptr

Detailed Description

template<AlephGraph GT, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Test_For_Path< GT, SA >

Checks whether a path exists between two nodes.

Test_For_Path explores graph g depth-first starting from a start node, searching for a path that leads to a destination one.

The class takes two type parameters:

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

The test_path bit is used to mark the nodes and arcs visited during the search.

See also

find_path_depth_first() find_path_breadth_first()

Definition at line 69 of file tpl_test_path.H.

Constructor & Destructor Documentation

Test_For_Path()

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

Aleph::Test_For_Path< GT, SA >::Test_For_Path ( SA  __sa = SA() )

inline

Definition at line 127 of file tpl_test_path.H.

Member Function Documentation

operator()()

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

bool Aleph::Test_For_Path< GT, SA >::operator() ( const GT &  g, typename GT::Node *  start_node, typename GT::Node *  end_node  )

inline

Invokes the test for a path's existence between two nodes.

Parameters

[in]	g	the graph to search a path in.
[in]	start_node	pointer to the path's source node.
[in]	end_node	pointer to the path's destination node.

Returns

true if a path exists between start_node and end_node.

Definition at line 136 of file tpl_test_path.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Test_For_Path< GT, SA >::test_path().

test_path() [1/2]

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

bool Aleph::Test_For_Path< GT, SA >::test_path ( const GT &  g, typename GT::Node *  src, typename GT::Node *  dest  )

inlineprivate

Definition at line 101 of file tpl_test_path.H.

References Aleph::and, ARC_BITS, Aleph::blossom_maximum_cardinality_matching(), Aleph::Find_Path, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), Aleph::Test_For_Path< GT, SA >::sa, Aleph::Test_For_Path< GT, SA >::test_path(), and Aleph::Test_For_Path< GT, SA >::tgt.

test_path() [2/2]

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

bool Aleph::Test_For_Path< GT, SA >::test_path ( typename GT::Node *  curr )

inlineprivate

Definition at line 74 of file tpl_test_path.H.

References ARC_BITS, Aleph::Find_Path, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_BITS, Aleph::Test_For_Path< GT, SA >::sa, Aleph::Test_For_Path< GT, SA >::test_path(), and Aleph::Test_For_Path< GT, SA >::tgt.

Referenced by Aleph::Test_For_Path< GT, SA >::operator()(), Aleph::Test_For_Path< GT, SA >::test_path(), and Aleph::Test_For_Path< GT, SA >::test_path().

Member Data Documentation

sa

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

SA Aleph::Test_For_Path< GT, SA >::sa

private

Definition at line 71 of file tpl_test_path.H.

Referenced by Aleph::Test_For_Path< GT, SA >::test_path(), and Aleph::Test_For_Path< GT, SA >::test_path().

tgt

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

GT::Node* Aleph::Test_For_Path< GT, SA >::tgt = nullptr

private

Definition at line 72 of file tpl_test_path.H.

Referenced by Aleph::Test_For_Path< GT, SA >::test_path(), and Aleph::Test_For_Path< GT, SA >::test_path().

---

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

• tpl_test_path.H