tpl_find_path.H

# ifndef TPL_FIND_PATH_H
# define TPL_FIND_PATH_H

# include <tpl_graph_utils.H>

namespace Aleph {

    template <class GT, class SA = Dft_Show_Arc<GT> > 
class Find_Path_Depth_First
{
  SA & sa;
  typename GT::Node * end;
  Path<GT> * path;
  
  bool find_path(typename GT::Node * curr, typename GT::Arc * arc)
  {
    if (curr == end) // ¿se alcanzó nodo final?
      {     // sí, terminar añadir el arco y terminar
        path->append(arc);

        return true;
      }

    if (IS_NODE_VISITED(curr, Find_Path)) // ¿ha sido visitado?
      return false; // sí ==> desde él no hay camino

    path->append(arc); // añadir curr_arc al camino
    NODE_BITS(curr).set_bit(Find_Path, true); 

      // buscar recursivamente a través de arcos de curr_node
    for (Node_Arc_Iterator<GT, SA> i(curr, sa); i.has_curr(); i.next())
      {
        typename GT::Arc * next_arc = i.get_current_arc();
        if (IS_ARC_VISITED(next_arc, Find_Path)) 
          continue;

        ARC_BITS(next_arc).set_bit(Find_Path, true); 
        typename GT::Node * next_node = i.get_tgt_node(); 
        if (find_path(next_node, next_arc))
          {
            I(path->get_last_node() == end);
            
            return true; // se encontró camino
          }
      }

    path->remove_last_node(); 

    return false;
  }

  bool find_path(GT & g, typename GT::Node * start, 
                 typename GT::Node * end_node, Path<GT> & p)
  {
    if (not p.inside_graph(g))
      throw std::invalid_argument("Path does not belong to graph");

    end  = end_node;
    path = &p;

    path->clear_path();         
    path->init(start); 

    g.reset_bit_nodes(Find_Path);
    g.reset_bit_arcs(Find_Path); 

    NODE_BITS(start).set_bit(Find_Path, true);

      // explorar recursivamente cada arco de start_node
    for (Node_Arc_Iterator<GT, SA> i(start, sa); i.has_curr(); i.next())
    {
      typename GT::Arc * arc = i.get_current_arc();
      ARC_BITS(arc).set_bit(Find_Path, true); 

      typename GT::Node * next_node = i.get_tgt_node();
      if (IS_NODE_VISITED(next_node, Find_Path)) 
        continue; 

      if (find_path(next_node, arc)) 
        return true;
    }

    return false;
  }

public:

  Find_Path_Depth_First(SA && __sa = SA()) : sa(__sa) { /* empty */ }

  Find_Path_Depth_First(SA & __sa) : sa(__sa) { /* empty */ }

  bool operator () (GT & g, typename GT::Node * start_node, 
                    typename GT::Node * end_node, Path<GT> & path) 
  {
    return find_path(g, start_node, end_node, path);
  }
};


      template <class GT, class SA = Dft_Show_Arc<GT> > 
class Find_Path_Breadth_First
{
  SA & sa;

  bool find_path(GT & g, typename GT::Node * start, 
                 typename GT::Node * end, Path<GT> & path)
  {
    if (not path.inside_graph(g))
      throw std::invalid_argument("Path does not belong to graph");

    path.clear_path(); // limpiamos cualquier cosa que esté en path
    g.reset_nodes();
    g.reset_arcs(); 
  
    DynListQueue<typename GT::Arc*> q; 

    for (Node_Arc_Iterator<GT, SA> i(start, sa); i.has_curr(); i.next())
      q.put(i.get_current_arc());
        
    NODE_BITS(start).set_bit(Find_Path, true); // márquelo visitado

    bool path_found = false;

    while (not q.is_empty()) // mientras queden arcos por visitar
      {
        typename GT::Arc * arc = q.get(); 
        typename GT::Node * src = g.get_src_node(arc); 
        typename GT::Node * tgt = g.get_tgt_node(arc);

        if (IS_NODE_VISITED(src, Find_Path) and IS_NODE_VISITED(tgt, Find_Path))
          continue;
      
        if (IS_NODE_VISITED(tgt, Find_Path))
          std::swap(src, tgt);

        ARC_BITS(arc).set_bit(Find_Path, true); 
        NODE_BITS(tgt).set_bit(Find_Path, true);
        NODE_COOKIE(tgt) = src;

        if (tgt == end) // ¿se encontró un camino?
          { 
            path_found = true;
            break;
          }

        for (Node_Arc_Iterator<GT,SA> i(tgt); i.has_curr(); i.next())
          {
            typename GT::Arc * a = i.get_current_arc();
            if (IS_ARC_VISITED(a, Find_Path)) // ¿arco visitado?
              continue; // sí ==> avanzar al siguiente 

            // revise nodos del arco para ver si han sido visitados
            if (IS_NODE_VISITED(g.get_src_node(a), Find_Path) and 
                IS_NODE_VISITED(g.get_tgt_node(a), Find_Path))
              continue; // nodos ya visitados ==> no  meter arco

            q.put(a);
          }
      }

    if (not path_found)
      return false;

    q.empty();
    path.insert(end);
    typename GT::Node * p = end;
    while (p != start)
      {
        p = (typename GT::Node *) NODE_COOKIE(p);
        path.insert(p);
      }

    return true;
  }

public:

  Find_Path_Breadth_First(SA & _sa) : sa(_sa) { /* Empty */ }

  Find_Path_Breadth_First(SA && _sa = SA()) : sa(_sa) { /* Empty */ }
 
  bool operator () (GT & g, typename GT::Node * start, 
                    typename GT::Node * end, Path<GT> & path) 
  {
    return find_path(g, start, end, path);
  }
};


} // namespace Aleph

# endif // TPL_FIND_PATH_H