Performs a depth-first search for a path between a pair of nodes. More...

#include <tpl_find_path.H>

Collaboration diagram for Aleph::Find_Path_Depth_First< GT, Itor, SA >:

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

	Find_Path_Depth_First (SA &__sa)

bool	operator() (const GT &g, typename GT::Node start, typename GT::Node end, Path< GT > &path)
	Invokes the depth-first path search.

Path< GT >	operator() (const GT &g, typename GT::Node start, typename GT::Node end)
	Invokes the depth-first path search.

template<class Op >
Path< GT >	operator() (const GT &g, typename GT::Node *start, Op &op)
	Invokes the depth-first path search.

template<class Op = Dft_Goal_Node<GT>>
Path< GT >	operator() (const GT &g, typename GT::Node *start, Op &&op)

Private Member Functions
template<class Op >
bool	find_path (typename GT::Node curr, typename GT::Arc arc, Path< GT > &path, Op &op)

template<class Op >
bool	find (const GT &g, typename GT::Node *start, Path< GT > &path, Op &op)

template<class Op >
bool	find (const GT &g, typename GT::Node *start, Path< GT > &path, Op &&op)

Private Attributes
SA &	sa

GT *	g_ptr = nullptr

Detailed Description

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
class Aleph::Find_Path_Depth_First< GT, Itor, SA >

Performs a depth-first search for a path between a pair of nodes.

Find_Path_Depth_First searches depth-first for a path between start_node and end_node, building a path equivalent to the recursive depth of the search as it goes. If a path is found, the method returns true and the path parameter holds the path in question; otherwise, the function returns false and the path's value is indeterminate.

The class takes two type parameters:

GT: the graph type, which must be derived from List_Graph
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

See also: find_path_breadth_first(); dijkstra_min_spanning_tree() dijkstra_min_path(); bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definition at line 96 of file tpl_find_path.H.

Constructor & Destructor Documentation

◆ Find_Path_Depth_First() [1/2]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

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

inline

Definition at line 175 of file tpl_find_path.H.

◆ Find_Path_Depth_First() [2/2]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Aleph::Find_Path_Depth_First< GT, Itor, SA >::Find_Path_Depth_First ( SA & __sa )

inline

Definition at line 180 of file tpl_find_path.H.

Member Function Documentation

◆ find() [1/2]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class Op >

bool Aleph::Find_Path_Depth_First< GT, Itor, SA >::find	(	const GT &	g,
		typename GT::Node *	start,
		Path< GT > &	path,
		Op &&	op
	)

inlineprivate

Definition at line 169 of file tpl_find_path.H.

References Aleph::Find_Path_Depth_First< GT, Itor, SA >::find().

◆ find() [2/2]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class Op >

bool Aleph::Find_Path_Depth_First< GT, Itor, SA >::find	(	const GT &	g,
		typename GT::Node *	start,
		Path< GT > &	path,
		Op &	op
	)

inlineprivate

Definition at line 136 of file tpl_find_path.H.

References ARC_BITS, Aleph::blossom_maximum_cardinality_matching(), Aleph::Find_Path, Aleph::Find_Path_Depth_First< GT, Itor, SA >::find_path(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::g_ptr, GraphCommon< GT, Node, Arc >::get_connected_node(), IS_NODE_VISITED, NODE_BITS, Aleph::Path< GT >::remove_last_node(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::sa, and Aleph::Path< GT >::set_graph().

Referenced by Aleph::Find_Path_Depth_First< GT, Itor, SA >::find(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::operator()(), and Aleph::Find_Path_Depth_First< GT, Itor, SA >::operator()().

◆ find_path()

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class Op >

bool Aleph::Find_Path_Depth_First< GT, Itor, SA >::find_path	(	typename GT::Node *	curr,
		typename GT::Arc *	arc,
		Path< GT > &	path,
		Op &	op
	)

inlineprivate

Definition at line 102 of file tpl_find_path.H.

References Aleph::Path< GT >::append(), ARC_BITS, Aleph::blossom_maximum_cardinality_matching(), Aleph::Find_Path, Aleph::Find_Path_Depth_First< GT, Itor, SA >::find_path(), Aleph::Find_Path_Depth_First< GT, Itor, SA >::g_ptr, GraphCommon< GT, Node, Arc >::get_connected_node(), IS_ARC_VISITED, IS_NODE_VISITED, NODE_BITS, Aleph::Path< GT >::remove_last_node(), and Aleph::Find_Path_Depth_First< GT, Itor, SA >::sa.

Referenced by Aleph::Find_Path_Depth_First< GT, Itor, SA >::find(), and Aleph::Find_Path_Depth_First< GT, Itor, SA >::find_path().

◆ operator()() [1/4]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class Op = Dft_Goal_Node<GT>>

Path< GT > Aleph::Find_Path_Depth_First< GT, Itor, SA >::operator()	(	const GT &	g,
		typename GT::Node *	start,
		Op &&	op
	)

inline

Definition at line 241 of file tpl_find_path.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()() [2/4]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

template<class Op >

Path< GT > Aleph::Find_Path_Depth_First< GT, Itor, SA >::operator()	(	const GT &	g,
		typename GT::Node *	start,
		Op &	op
	)

inline

Invokes the depth-first path search.

Parameters

[in]	g	the graph on which the path is to be searched.
[in]	start	pointer to the path's starting node.
[in]	op	functor that implements the search criterion. The functor receives the node as a parameter and must return `true` if the node satisfies the criterion, `false` otherwise.

Returns: path the path seen during the depth-first search; if no such path exists then the path is empty

Exceptions

bad_alloc if there is not enough memory to keep building the path

Definition at line 233 of file tpl_find_path.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()() [3/4]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Find_Path_Depth_First< GT, Itor, SA >::operator()	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end
	)

inline

Invokes the depth-first path search.

Parameters

[in]	g	the graph on which the path is to be searched.
[in]	start	pointer to the path's starting node.
[in]	end	pointer to the path's destination node.

Returns: path reaching end if this one was found; false otherwise

Exceptions

bad_alloc if there is not enough memory to keep building the path

Definition at line 211 of file tpl_find_path.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Find_Path_Depth_First< GT, Itor, SA >::find().

◆ operator()() [4/4]

template<AlephGraph GT, template< class, class > class Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>

bool Aleph::Find_Path_Depth_First< GT, Itor, SA >::operator()	(	const GT &	g,
		typename GT::Node *	start,
		typename GT::Node *	end,
		Path< GT > &	path
	)

inline

Invokes the depth-first path search.

Parameters

[in]	g	the graph on which the path is to be searched.
[in]	start	pointer to the path's starting node.
[in]	end	pointer to the path's destination node.
[out]	path	the path seen during the depth-first search; only meaningful if the return value is true.