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

#include <tpl_find_path.H>

Public Member Functions
	Find_Path_Breadth_First (SA &_sa)

	Find_Path_Breadth_First (SA &&_sa=SA())

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

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

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

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

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

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

Private Attributes
SA &	sa

Detailed Description

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

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

Find_Path_Breadth_First searches breadth-first for a path between start_node and end_node, building a path toward the destination node 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_depth_first(); dijkstra_min_spanning_tree() dijkstra_min_path(); bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definition at line 275 of file tpl_find_path.H.

Constructor & Destructor Documentation

◆ Find_Path_Breadth_First() [1/2]

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

Aleph::Find_Path_Breadth_First< GT, Itor, SA >::Find_Path_Breadth_First ( SA & _sa )

inline

Definition at line 359 of file tpl_find_path.H.

◆ Find_Path_Breadth_First() [2/2]

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

Aleph::Find_Path_Breadth_First< GT, Itor, SA >::Find_Path_Breadth_First ( SA && _sa = SA() )

inline

Definition at line 364 of file tpl_find_path.H.

Member Function Documentation

◆ find_path() [1/2]

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

template<class Op >

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

inlineprivate

Definition at line 352 of file tpl_find_path.H.

References Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path().

◆ find_path() [2/2]

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

template<class Op >

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

inlineprivate

Definition at line 280 of file tpl_find_path.H.

References ah_invalid_argument_if, Aleph::and, ARC_BITS, Aleph::blossom_maximum_cardinality_matching(), Aleph::Path< GT >::empty(), Aleph::DynListQueue< T >::empty(), Aleph::Find_Path, Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Path< GT >::insert(), Aleph::Path< GT >::inside_graph(), IS_ARC_VISITED, Aleph::DynListQueue< T >::is_empty(), IS_NODE_VISITED, NODE_BITS, NODE_COOKIE, Aleph::DynListQueue< T >::put(), GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), and Aleph::Find_Path_Breadth_First< GT, Itor, SA >::sa.

Referenced by Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::operator()(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::operator()(), Aleph::Find_Path_Breadth_First< GT, Itor, SA >::operator()(), and Aleph::Find_Path_Breadth_First< GT, Itor, SA >::operator()().

◆ operator()() [1/4]

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

template<class Op >

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

inline

Definition at line 387 of file tpl_find_path.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path().

◆ operator()() [2/4]

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

template<class Op >

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

inline

Invokes the breadth-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	the end-of-search criterion on the visited node

Returns: the path seen during the breadth-first search

Exceptions

bad_alloc if there is not enough memory to keep building the path or for the breadth-first traversal's internal queue.

Definition at line 379 of file tpl_find_path.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path().

◆ operator()() [3/4]

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

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

inline

Invokes the breadth-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 the path seen during the breadth-first search

Exceptions

bad_alloc if there is not enough memory to keep building the path or for the breadth-first traversal's internal queue.

Definition at line 419 of file tpl_find_path.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Find_Path_Breadth_First< GT, Itor, SA >::find_path().

◆ operator()() [4/4]

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

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

inline

Invokes the breadth-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 breadth-first search; only meaningful if the return value is true.