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_Depth_First< GT, Itor, SA > Class Template Reference
Graphs

Busca en profundidad un camino entre un par de nodos. More...

#include <tpl_find_path.H>

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

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)
 Invoca a la búsqueda de camino en profundidad.
 
Path< GT > operator() (const GT &g, typename GT::Node *start, typename GT::Node *end)
 Invoca a la búsqueda de camino en profundidad.
 
template<class Op >
Path< GT > operator() (const GT &g, typename GT::Node *start, Op &op)
 Invoca a la búsqueda de camino en profundidad.
 
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<class GT, template< class, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Find_Path_Depth_First< GT, Itor, SA >

Busca en profundidad un camino entre un par de nodos.

Find_Path_Depth_First busca en profundidad un camino entre start_node y end_node, a la vez que va construyendo un camino equivalente a la profundidad recursiva de la búsqueda. Si el 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_breadth_first()
dijkstra_min_spanning_tree() dijkstra_min_path()
bellman_ford_min_spanning_tree() q_bellman_ford_min_spanning_tree()

Definition at line 94 of file tpl_find_path.H.

Constructor & Destructor Documentation

◆ Find_Path_Depth_First() [1/2]

template<class GT , template< class, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
Aleph::Find_Path_Depth_First< GT, Itor, SA >::Find_Path_Depth_First ( SA &&  __sa = SA())
inline

Definition at line 173 of file tpl_find_path.H.

◆ Find_Path_Depth_First() [2/2]

template<class GT , template< class, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
Aleph::Find_Path_Depth_First< GT, Itor, SA >::Find_Path_Depth_First ( SA &  __sa)
inline

Definition at line 178 of file tpl_find_path.H.

Member Function Documentation

◆ find() [1/2]

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

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

◆ find() [2/2]

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

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

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

References Aleph::maps().

◆ operator()() [2/4]

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

Invoca a la búsqueda de camino en profundidad.

Parameters
[in]gel grafo sobre el cual se desea buscar el camino.
[in]startpuntero al nodo inicio del camino.
[in]opfunctor que implementa el criterio de búsqueda. El functor ecibe como parámetro el nodo y debe retornar true si el nodo satisface el criterio false de lo contrario.
Returns
path el camino visto durante la búsqueda en profundidad; si no existe tal camino entonces el camino es va
Exceptions
bad_allocsi no hay memoria para continuar construyendo el camino

Definition at line 231 of file tpl_find_path.H.

References Aleph::maps().

◆ operator()() [3/4]

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

Invoca a la búsqueda de camino en profundidad.

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 reaching end if this one was found; false otherwise
Exceptions
bad_allocsi no hay memoria para continuar construyendo el camino

Definition at line 209 of file tpl_find_path.H.

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

◆ operator()() [4/4]

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

Invoca a la búsqueda de camino en profundidad.

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 profundidad; sólo tiene sentido si el valor de retorno es true.
Exceptions
bad_allocsi no hay memoria para continuar construyendo el camino

Definition at line 193 of file tpl_find_path.H.

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

Member Data Documentation

◆ g_ptr

template<class GT , template< class, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
GT* Aleph::Find_Path_Depth_First< GT, Itor, SA >::g_ptr = nullptr
private

Definition at line 97 of file tpl_find_path.H.

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

◆ sa

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

Definition at line 96 of file tpl_find_path.H.

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

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