Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Public Member Functions | Private Member Functions | Private Attributes | List of all members
Aleph::Find_Path_Breadth_First< GT, Itor, SA > Class Template Reference
Graphs

Busca en amplitud un camino entre un par de nodos. 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)
 Invoca a la búsqueda de camino en amplitud.
 
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)
 Invoca a la búsqueda de camino en amplitud.
 
Path< GT > operator() (const GT &g, typename GT::Node *start, typename GT::Node *end)
 Invoca a la búsqueda de camino en amplitud.
 

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<class GT, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Find_Path_Breadth_First< GT, Itor, SA >

Busca en amplitud un camino entre un par de nodos.

Find_Path_Breadth_First busca en amplitud un camino entre start_node y end_node, a la vez que va construyendo un camino hacia el nodo destino. Si se encuentra un camino, entonces el método retorna true y el parámetro path alberga el camino en cuestión; de lo contrario, la función retorna false y valor del camino es indeterminado.

La clase toma dos parámetros tipo:

  1. GT: el tipo de grafo, el cual debe ser derivado de List_Graph
  2. SA: clase que se encarga de mostrar el arco. Internamente, la función emplea el iterador filtro Node_Arc_Iterator (basado en Filter_Iterator) para recorrer los arcos de cada nodo. SA es el la clase que determina si el arco debe o no mostrarse al recorrido
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 274 of file tpl_find_path.H.

Constructor & Destructor Documentation

◆ Find_Path_Breadth_First() [1/2]

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
Aleph::Find_Path_Breadth_First< GT, Itor, SA >::Find_Path_Breadth_First ( SA &  _sa)
inline

Definition at line 358 of file tpl_find_path.H.

◆ Find_Path_Breadth_First() [2/2]

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
Aleph::Find_Path_Breadth_First< GT, Itor, SA >::Find_Path_Breadth_First ( SA &&  _sa = SA())
inline

Definition at line 363 of file tpl_find_path.H.

Member Function Documentation

◆ find_path() [1/2]

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class 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 351 of file tpl_find_path.H.

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

◆ find_path() [2/2]

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class 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 279 of file tpl_find_path.H.

References ah_invalid_argument_if, ARC_BITS, 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, Aleph::maps(), 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<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class 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 386 of file tpl_find_path.H.

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

◆ operator()() [2/4]

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class 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

Invoca a la búsqueda de camino en amplitud.

Parameters
[in]gel grafo sobre el cual se desea buscar el camino.
[in]startpuntero al nodo inicio del camino.
[in]opcriterio de fin de búsqueda sobre el nodo visitado
Returns
el camino visto durante la búsqueda en amplitud
Exceptions
bad_allocsi no hay memoria para continuar construyendo el camino o para la cola interna del recorrido en amplitud.

Definition at line 378 of file tpl_find_path.H.

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

◆ operator()() [3/4]

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class 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

Invoca a la búsqueda de camino en amplitud.

Parameters
[in]gel grafo sobre el cual se desea buscar el camino.
[in]startpuntero al nodo inicio del camino.
[in]endpuntero al nodo destino del camino.
Returns
path el camino visto durante la búsqueda en amplitud
Exceptions
bad_allocsi no hay memoria para continuar construyendo el camino o para la cola interna del recorrido en amplitud.

Definition at line 418 of file tpl_find_path.H.

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

◆ operator()() [4/4]

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class 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

Invoca a la búsqueda de camino en amplitud.

Parameters
[in]gel grafo sobre el cual se desea buscar el camino.
[in]startpuntero al nodo inicio del camino.
[in]endpuntero al nodo destino del camino.
[out]pathel camino visto durante la búsqueda en amplitud; sólo tiene sentido si el valor de retorno es true.
Exceptions
bad_allocsi no hay memoria para continuar construyendo el camino o para la cola interna del recorrido en amplitud.

Definition at line 403 of file tpl_find_path.H.

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

Member Data Documentation

◆ sa

template<class GT , template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
SA& Aleph::Find_Path_Breadth_First< GT, Itor, SA >::sa
private

Definition at line 276 of file tpl_find_path.H.

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

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