tpl_find_path.H

/* Aleph-w

     / \  | | ___ _ __ | |__      __      __
    / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
   / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
  /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                 |_|         

  This file is part of Aleph-w library

  Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program. If not, see <https://www.gnu.org/licenses/>.
*/

# ifndef TPL_FIND_PATH_H
# define TPL_FIND_PATH_H

# include <tpl_dynListStack.H>
# include <tpl_dynListQueue.H>
# include <tpl_graph_utils.H>

namespace Aleph {

  template <class GT>
struct Dft_Goal_Node
{
  bool operator () (typename GT::Node *) const noexcept { return false; } 
};

    template <class GT, 
              template <class, class> class Itor = Node_Arc_Iterator,
              class SA = Dft_Show_Arc<GT>> 
class Find_Path_Depth_First
{
  SA & sa;
  GT * g_ptr = nullptr;

  template <class Op>
  bool find_path(typename GT::Node * curr, typename GT::Arc * arc, 
                 Path<GT> & path, Op & op)
  {
    if (op(curr)) // goal node reached?
      {
        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 (Itor<GT, SA> i(curr, sa); i.has_curr(); i.next())
      {
        auto next_arc = i.get_curr();
        if (IS_ARC_VISITED(next_arc, Find_Path)) 
          continue;

        ARC_BITS(next_arc).set_bit(Find_Path, true); 
        auto next_node = g_ptr->get_connected_node(next_arc, curr);
        if (find_path(next_node, next_arc, path, op))
          return true; // se encontró camino
      }

    path.remove_last_node(); 

    return false;
  }

  template <class Op>
  bool find(const GT & g, typename GT::Node * start, Path<GT> & path, Op & op)
  {
    g_ptr = const_cast<GT*>(&g);
    path.set_graph(g, start);

    if (op(start))
      return true;

    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
    for (Itor<GT, SA> i(start, sa); i.has_curr(); i.next())
    {
      auto arc = i.get_curr();
      ARC_BITS(arc).set_bit(Find_Path, true); 

      auto next_node = g.get_connected_node(arc, start);
      if (IS_NODE_VISITED(next_node, Find_Path)) 
        continue; 

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

    path.remove_last_node();

    return false;
  }

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

public:

  Find_Path_Depth_First(SA && __sa = SA()) 
  noexcept(std::is_nothrow_constructible<SA>::value and
           std::is_nothrow_copy_assignable<SA>::value)
    : sa(__sa) { /* empty */ }

  Find_Path_Depth_First(SA & __sa) 
  noexcept(std::is_nothrow_copy_assignable<SA>::value)
    : sa(__sa) { /* empty */ }

  bool operator () (const GT & g, 
                    typename GT::Node * start, typename GT::Node * end, 
                    Path<GT> & path) 
  {
    return find(g, start, path, [end] (auto p) { return p == end; });
  }

  Path<GT> operator () (const GT & g, 
                        typename GT::Node * start,
                        typename GT::Node * end) 
  {
    Path<GT> ret(g);
    find(g, start, ret, [end] (auto p) { return p == end; });
    return ret;
  }

  template <class Op>
  Path<GT> operator () (const GT & g, typename GT::Node * start, Op & op)
  {
    Path<GT> ret(g);
    find<Op>(g, start, ret, op);
    return ret;
  }

  template <class Op = Dft_Goal_Node<GT>>
  Path<GT> operator () (const GT & g, typename GT::Node * start, Op && op)
  {
    Path<GT> ret(g);
    find<Op>(g, start, ret, op);
    return ret;
  }
};


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

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

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

    for (Itor<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

    typename GT::Node * end = nullptr;

    while (not q.is_empty()) // mientras queden arcos por visitar
      {
        auto arc = q.get(); 
        auto src = g.get_src_node(arc); 
        auto 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 (op(tgt)) // ¿se encontró un camino que satisfaga op?
          { 
            end = tgt;
            break;
          }

        for (Itor<GT,SA> i(tgt); i.has_curr(); i.next())
          {
            auto 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 end)
      return false;

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

    return true;
  }

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

public:

  Find_Path_Breadth_First(SA & _sa) 
  noexcept(std::is_nothrow_copy_assignable<SA>::value)
    : sa(_sa) { /* Empty */ }

  Find_Path_Breadth_First(SA && _sa = SA()) 
  noexcept(std::is_nothrow_constructible<SA>::value and
           std::is_nothrow_copy_assignable<SA>::value)
    : sa(_sa) { /* Empty */ }
 
  template <class Op>
  Path<GT> operator () (const GT & g, typename GT::Node * start, Op & op)
  {
    Path<GT> ret(g);
    find_path(g, start, ret, op);
    return ret;
  }

  template <class Op>
  Path<GT>  operator () (const GT & g, typename GT::Node * start, Op && op)
  {
    Path<GT> ret(g);
    find_path(g, start, ret, op);
    return ret;
  }

  bool operator () (const GT & g, typename GT::Node * start, 
                    typename GT::Node * end, Path<GT> & path) 
  {
    return find_path(g, start, path, [end] (auto p) { return p == end; });
  }

  Path<GT> operator () (const GT & g, 
                        typename GT::Node * start, typename GT::Node * end)
  {
    Path<GT> ret(g);
    find_path(g, start, ret, [end] (auto p) { return p == end; });
    return ret;
  }
};

  template <class GT,
            template <typename, class> class Itor = Out_Iterator,
            class SA = Dft_Show_Arc<GT>>
class Directed_Find_Path
{
  const GT & g;
  SA & sa;

  template <template <typename T> class Q, class Op>
  Path<GT> find(typename GT::Node * start, Op & op)
  {
    g.reset_nodes();
    g.reset_arcs();

    start->set_state(Processed);

    Q<typename GT::Arc*> q;
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next())
      {
        auto a = it.get_curr();
        it.get_node(a)->set_state(Processing);
        a->set_state(Processing);
        q.put(a);
      }

    typename GT::Node * end = nullptr, * curr = nullptr;
    while (not q.is_empty())
      {
        auto arc = q.get();
        assert(arc->state() == Processing);
        arc->set_state(Processed);

        curr = g.get_tgt_node(arc);
        if (curr->state() == Processed)
          continue;

        curr->set_state(Processed);
        NODE_COOKIE(curr) = g.get_src_node(arc);

        if (op(curr))
          {
            end = curr;
            break;
          }

        for (Itor<GT, SA> it(curr, sa); it.has_curr(); it.next()) 
          {
            auto a  = it.get_curr();
            a->set_state(Processing);

            auto tgt = it.get_node(a);
            if (tgt->state() == Processed)
              continue;

            if (tgt->state() != Processed)
            {
              q.put(a);
              tgt->set_state(Processing);
            }
          else
            a->set_state(Processed);
        }
      } // end while

    Path<GT> ret(g);
    if (not end)
      return ret;

    assert(curr == end);

    while (curr != start)
      {
        ret.insert(curr);
        curr = (typename GT::Node*) NODE_COOKIE(curr);
      }
    ret.insert(start);

    return ret;
  }

public:

  Directed_Find_Path(const GT & __g, SA & __sa) : g(__g), sa(__sa) {}

  Directed_Find_Path(const GT & __g, SA && __sa = SA()) : g(__g), sa(__sa) {}

  template <class Op> 
  Path<GT> dfs(typename GT::Node * start, Op & op) 
  {
    return find<DynListStack, Op>(start, op);
  }

  template <class Op> 
  Path<GT> dfs(typename GT::Node * start, Op && op) 
  {
    return find<DynListStack, Op>(start, op);
  }

  template <class Op> 
  Path<GT> bfs(typename GT::Node * start, Op & op) 
  {
    return find<DynListQueue, Op>(start, op);
  }

  template <class Op> 
  Path<GT> bfs(typename GT::Node * start, Op && op) 
  {
    return find<DynListQueue, Op>(start, op);
  }

  Path<GT> dfs(typename GT::Node * start, typename GT::Node * end) 
  {
    return dfs(start, [end] (auto p) { return p == end; });
  }

  Path<GT> bfs(typename GT::Node * start, typename GT::Node * end) 
  {
    return bfs(start, [end] (auto p) { return p == end; });
  }
};




} // namespace Aleph

# endif // TPL_FIND_PATH_H