AStar.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
#ifndef ASTAR_H
#define ASTAR_H
 
# include <cmath>
# include <iostream>
# include <ahFunction.H>
# include <ah-errors.H>
# include <archeap.H>
# include <tpl_find_path.H>
# include <tpl_agraph.H>
# include <shortest_path_common.H>
 
namespace Aleph
{
 
template <class GT, class Distance = Dft_Dist<GT>>
struct Zero_Heuristic
{
  using Distance_Type = typename Distance::Distance_Type;
 
  Distance_Type operator()(typename GT::Node*, typename GT::Node*) const
  {
    return Distance_Type(0);
  }
};
 
template <class GT,
          class Distance = Dft_Dist<GT>,
          class Heuristic = Zero_Heuristic<GT, Distance>,
          template <typename, class> class Itor = Node_Arc_Iterator,
          class SA = Dft_Show_Arc<GT>,
          template <class, class, class> class HeapT = ArcHeap>
class AStar_Min_Path
  : public Shortest_Path_Base<GT, Distance, Itor, SA, HeapT>
{
  using Base = Shortest_Path_Base<GT, Distance, Itor, SA, HeapT>;
 
  // Import types from base class
  using typename Base::Node_Info;
  using typename Base::Tree_Node_Info;
  using typename Base::Arc_Info;
  using typename Base::Tree_Arc_Info;
  using typename Base::Initialize_Node;
  using typename Base::Initialize_Arc;
  using typename Base::Initialize_Tree_Node;
  using typename Base::Initialize_Tree_Arc;
  using typename Base::Destroy_Node;
  using typename Base::Destroy_Arc;
  using typename Base::Destroy_Tree_Node;
  using typename Base::Destroy_Tree_Arc;
 
  // Local cookie access macros
#define ANassert(p) (static_cast<Node_Info*>(NODE_COOKIE(p)))
#define ATREENODE(p) (static_cast<Tree_Node_Info*>(NODE_COOKIE(p))->tree_node)
#define AACC(p) (ANassert(p)->dist)
#define AHEAPNODE(p) (ANassert(p)->heap_node)
#define APARENT(p) (ANassert(p)->ret_node)
#define AAassert(p) (static_cast<Arc_Info*>(ARC_COOKIE(p)))
#define AARC_DIST(p) (Distance()(p))
#define ATREEARC(p) (static_cast<Tree_Arc_Info*>(ARC_COOKIE(p))->tree_arc)
#define APOT(p) (AAassert(p)->pot)
 
  // Import member variables from base
  using Base::sa;
  using Base::heap;
  using Base::painted;
  using Base::ptr_g;
  using Base::s;
 
  // A* specific: heuristic functor
  Heuristic heuristic;
 
#ifndef NDEBUG
  // Debug mode: track heuristic validation
  bool validate_heuristic = true;
 
  void check_heuristic_admissibility(typename GT::Node* node,
                                     typename GT::Node* goal,
                                     const typename Distance::Distance_Type& actual_cost)
  {
    if (!validate_heuristic)
      return;
 
    auto h_estimate = heuristic(node, goal);
    if (h_estimate > actual_cost)
      {
        std::cerr << "WARNING: Inadmissible heuristic detected!\n";
        std::cerr << "  Heuristic estimate h(" << node << ") = " << h_estimate << "\n";
        std::cerr << "  Actual remaining cost = " << actual_cost << "\n";
        std::cerr << "  Heuristic overestimates by " << (h_estimate - actual_cost) << "\n";
        std::cerr << "  A* may return suboptimal paths.\n";
      }
  }
#endif
 
public:
  AStar_Min_Path(Distance dist = Distance(),
                 Heuristic __heuristic = Heuristic(),
                 SA __sa = SA())
    : Base(dist, __sa), heuristic(__heuristic)
  {
    // empty
  }
 
  // Import public methods from base
  using Base::has_computation;
  using Base::is_painted;
  using Base::get_start_node;
  using Base::get_graph;
  using Base::get_distance;
  using Base::get_min_path;
  using Base::copy_painted_min_paths_tree;
 
  // =========================================================================
  // Methods WITH Heuristic (A* specific)
  // =========================================================================
 
  typename GT::Node*
  compute_partial_path(const GT& g,
                       typename GT::Node* start,
                       typename GT::Node* end,
                       GT& tree)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
    ah_domain_error_if(end == nullptr) << "end node cannot be null";
    ah_domain_error_if(g.get_num_nodes() == 0) << "graph is empty";
 
    this->template init<Initialize_Tree_Node, Initialize_Tree_Arc>(g, start);
    clear_graph(tree);
 
    // Handle trivial case: start == end
    if (start == end)
      {
        NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
        AACC(start) = 0;
        auto tree_node = tree.insert_node(start->get_info());
        ATREENODE(start) = tree_node;
        NODE_COOKIE(tree_node) = start;
        this->template uninit<Destroy_Tree_Node, Destroy_Tree_Arc>();
        return tree_node;
      }
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    AACC(start) = 0;
    ATREENODE(start) = tree.insert_node(start->get_info());
    NODE_COOKIE(ATREENODE(start)) = start;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        auto tgt = it.get_tgt_node();
        auto g_cost = AARC_DIST(arc);
        auto h_cost = heuristic(tgt, end);
        APOT(arc) = this->checked_add(g_cost, h_cost);
        heap.put_arc(arc, tgt);
      }
 
    typename GT::Node* result = nullptr;
 
    while (not heap.is_empty())
      {
        auto garc = heap.get_min_arc();
        if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
          continue;
 
        auto gsrc = g.get_src_node(garc);
        auto gtgt = g.get_tgt_node(garc);
 
        if (IS_NODE_VISITED(gsrc, Aleph::Spanning_Tree) and
            IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
          continue;
 
        ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);
 
        if (IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
          std::swap(gsrc, gtgt);
 
        NODE_BITS(gtgt).set_bit(Aleph::Spanning_Tree, true);
 
        auto ttgt = tree.insert_node(gtgt->get_info());
        ATREENODE(gtgt) = ttgt;
        auto tsrc = ATREENODE(gsrc);
 
        auto tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
        ATREEARC(garc) = tarc;
 
        AACC(gtgt) = this->checked_add(AACC(gsrc), AARC_DIST(garc));
 
        if (gtgt == end)
          {
            result = ttgt;
            break;
          }
 
        const auto& g_cost = AACC(gtgt);
 
        for (Itor<GT, SA> it(gtgt, sa); it.has_curr(); it.next_ne())
          {
            auto arc = it.get_current_arc_ne();
            if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
              continue;
 
            auto tgt = it.get_tgt_node();
            if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
              continue;
 
            auto new_g = this->checked_add(g_cost, AARC_DIST(arc));
            auto h = heuristic(tgt, end);
            APOT(arc) = this->checked_add(new_g, h);
            heap.put_arc(arc, tgt);
          }
      }
 
    this->template uninit<Destroy_Tree_Node, Destroy_Tree_Arc>();
 
    return result;
  }
 
  bool paint_partial_path(const GT& g,
                          typename GT::Node* start,
                          typename GT::Node* end)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
    ah_domain_error_if(end == nullptr) << "end node cannot be null";
    ah_domain_error_if(g.get_num_nodes() == 0) << "graph is empty";
 
    this->template init<Initialize_Node, Initialize_Arc>(g, start);
 
    // Handle trivial case: start == end
    if (start == end)
      {
        NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
        AACC(start) = 0;
        this->template uninit<Destroy_Node, Destroy_Arc>();
        painted = true;
        return true;
      }
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    AACC(start) = 0;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        auto tgt = it.get_tgt_node();
        auto g_cost = AARC_DIST(arc);
        auto h_cost = heuristic(tgt, end);
        APOT(arc) = this->checked_add(g_cost, h_cost);
        heap.put_arc(arc, tgt);
      }
 
    bool found = false;
 
    while (not heap.is_empty())
      {
        auto garc = heap.get_min_arc();
        if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
          continue;
 
        auto src = g.get_src_node(garc);
        auto tgt = g.get_tgt_node(garc);
 
        if (IS_NODE_VISITED(src, Aleph::Spanning_Tree) and
            IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
          continue;
 
        ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);
 
        if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
          std::swap(src, tgt);
 
        NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
        APARENT(tgt) = src;
 
        if (tgt == end)
          {
            found = true;
            break;
          }
 
        AACC(tgt) = this->checked_add(AACC(src), AARC_DIST(garc));
        const auto& g_cost = AACC(tgt);
 
        for (Itor<GT, SA> it(tgt, sa); it.has_curr(); it.next_ne())
          {
            auto arc = it.get_current_arc_ne();
            if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
              continue;
 
            auto t = it.get_tgt_node();
            if (IS_NODE_VISITED(t, Aleph::Spanning_Tree))
              continue;
 
            auto new_g = this->checked_add(g_cost, AARC_DIST(arc));
            auto h = heuristic(t, end);
            APOT(arc) = this->checked_add(new_g, h);
            heap.put_arc(arc, t);
          }
      }
 
    this->template uninit<Destroy_Node, Destroy_Arc>();
    painted = true;
 
    return found;
  }
 
  typename Distance::Distance_Type
  find_path(const GT& g,
            typename GT::Node* start,
            typename GT::Node* end,
            Path<GT>& path)
  {
    path.empty();
    if (paint_partial_path(g, start, end))
      return this->get_min_path(end, path);
 
    return std::numeric_limits<typename Distance::Distance_Type>::max();
  }
 
  // =========================================================================
  // Backward Compatibility Aliases
  // =========================================================================
 
  typename GT::Node*
  compute_path(const GT& g, typename GT::Node* start,
               typename GT::Node* end, GT& tree)
  {
    return compute_partial_path(g, start, end, tree);
  }
 
  bool paint_path(const GT& g, typename GT::Node* start, typename GT::Node* end)
  {
    return paint_partial_path(g, start, end);
  }
 
  // =========================================================================
  // Methods WITHOUT Heuristic (Dijkstra-compatible)
  // =========================================================================
 
  typename GT::Node*
  compute_min_paths_tree(const GT& g, typename GT::Node* start, GT& tree)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
    ah_domain_error_if(g.get_num_nodes() == 0) << "graph is empty";
 
    this->template init<Initialize_Tree_Node, Initialize_Tree_Arc>(g, start);
 
    clear_graph(tree);
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    AACC(start) = 0;
    auto ret = ATREENODE(start) = tree.insert_node(start->get_info());
    NODE_COOKIE(ATREENODE(start)) = start;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        APOT(arc) = AARC_DIST(arc);  // No heuristic: pot = g only
        heap.put_arc(arc, it.get_tgt_node());
      }
 
    const auto& n = g.get_num_nodes();
 
    while (tree.get_num_nodes() < n and not heap.is_empty())
      {
        auto garc = heap.get_min_arc();
        if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
          continue;
 
        auto gsrc = g.get_src_node(garc);
        auto gtgt = g.get_tgt_node(garc);
 
        if (IS_NODE_VISITED(gsrc, Aleph::Spanning_Tree) and
            IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
          continue;
 
        ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);
 
        if (IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
          std::swap(gsrc, gtgt);
 
        NODE_BITS(gtgt).set_bit(Aleph::Spanning_Tree, true);
 
        auto ttgt = tree.insert_node(gtgt->get_info());
        ATREENODE(gtgt) = ttgt;
        auto tsrc = ATREENODE(gsrc);
 
        auto tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
        ATREEARC(garc) = tarc;
 
        AACC(gtgt) = this->checked_add(AACC(gsrc), AARC_DIST(garc));
        const auto& acc = AACC(gtgt);
 
        for (Itor<GT, SA> it(gtgt, sa); it.has_curr(); it.next_ne())
          {
            auto arc = it.get_current_arc_ne();
            if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
              continue;
 
            auto tgt = it.get_tgt_node();
            if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
              continue;
 
            APOT(arc) = this->checked_add(acc, AARC_DIST(arc));
            heap.put_arc(arc, tgt);
          }
      }
 
    this->template uninit<Destroy_Tree_Node, Destroy_Tree_Arc>();
 
    return ret;
  }
 
  void compute_partial_min_paths_tree(const GT& g,
                                      typename GT::Node* start,
                                      typename GT::Node* end,
                                      GT& tree)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
    ah_domain_error_if(end == nullptr) << "end node cannot be null";
    ah_domain_error_if(g.get_num_nodes() == 0) << "graph is empty";
 
    this->template init<Initialize_Tree_Node, Initialize_Tree_Arc>(g, start);
    clear_graph(tree);
 
    // Handle trivial case: start == end
    if (start == end)
      {
        NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
        AACC(start) = 0;
        auto tree_node = tree.insert_node(start->get_info());
        ATREENODE(start) = tree_node;
        NODE_COOKIE(tree_node) = start;
        this->template uninit<Destroy_Tree_Node, Destroy_Tree_Arc>();
        return;
      }
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    AACC(start) = 0;
    ATREENODE(start) = tree.insert_node(start->get_info());
    NODE_COOKIE(ATREENODE(start)) = start;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        APOT(arc) = AARC_DIST(arc);
        heap.put_arc(arc, it.get_tgt_node());
      }
 
    const auto& n = g.get_num_nodes();
 
    while (tree.get_num_nodes() < n and not heap.is_empty())
      {
        auto garc = heap.get_min_arc();
        if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
          continue;
 
        auto gsrc = g.get_src_node(garc);
        auto gtgt = g.get_tgt_node(garc);
 
        if (IS_NODE_VISITED(gsrc, Aleph::Spanning_Tree) and
            IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
          continue;
 
        ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);
 
        if (IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
          std::swap(gsrc, gtgt);
 
        NODE_BITS(gtgt).set_bit(Aleph::Spanning_Tree, true);
 
        auto ttgt = tree.insert_node(gtgt->get_info());
        ATREENODE(gtgt) = ttgt;
 
        auto tarc = tree.insert_arc(ATREENODE(gsrc), ATREENODE(gtgt), garc->get_info());
        ATREEARC(garc) = tarc;
 
        AACC(gtgt) = this->checked_add(AACC(gsrc), AARC_DIST(garc));
 
        if (gtgt == end)
          break;
        const auto& acc = AACC(gtgt);
 
        for (Itor<GT, SA> it(gtgt, sa); it.has_curr(); it.next_ne())
          {
            auto arc = it.get_current_arc_ne();
            if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
              continue;
 
            auto tgt = it.get_tgt_node();
            if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
              continue;
 
            APOT(arc) = this->checked_add(acc, AARC_DIST(arc));
            heap.put_arc(arc, tgt);
          }
      }
 
    this->template uninit<Destroy_Tree_Node, Destroy_Tree_Arc>();
  }
 
  bool paint_partial_min_paths_tree(const GT& g,
                                    typename GT::Node* start,
                                    typename GT::Node* end)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
    ah_domain_error_if(end == nullptr) << "end node cannot be null";
    ah_domain_error_if(g.get_num_nodes() == 0) << "graph is empty";
 
    this->template init<Initialize_Node, Initialize_Arc>(g, start);
 
    // Handle trivial case: start == end
    if (start == end)
      {
        NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
        AACC(start) = 0;
        this->template uninit<Destroy_Node, Destroy_Arc>();
        painted = true;
        return true;
      }
 
    bool ret_val = false;
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    AACC(start) = 0;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        APOT(arc) = AARC_DIST(arc);
        heap.put_arc(arc, it.get_tgt_node());
      }
 
    const auto& n = g.get_num_nodes();
    size_t tn = 1;
 
    while (tn < n and not heap.is_empty())
      {
        auto garc = heap.get_min_arc();
        if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
          continue;
 
        auto src = g.get_src_node(garc);
        auto tgt = g.get_tgt_node(garc);
 
        if (IS_NODE_VISITED(src, Aleph::Spanning_Tree) and
            IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
          continue;
 
        ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);
 
        if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
          std::swap(src, tgt);
 
        NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
        APARENT(tgt) = src;
 
        ++tn;
 
        if (tgt == end)
          {
            ret_val = true;
            break;
          }
 
        AACC(tgt) = this->checked_add(AACC(src), AARC_DIST(garc));
        const auto& acc = AACC(tgt);
 
        for (Itor<GT, SA> it(tgt, sa); it.has_curr(); it.next_ne())
          {
            auto a = it.get_current_arc_ne();
            if (IS_ARC_VISITED(a, Aleph::Spanning_Tree))
              continue;
 
            auto t = it.get_tgt_node();
            if (IS_NODE_VISITED(t, Aleph::Spanning_Tree))
              continue;
 
            APOT(a) = this->checked_add(acc, AARC_DIST(a));
            heap.put_arc(a, t);
          }
      }
 
    this->template uninit<Destroy_Node, Destroy_Arc>();
    painted = true;
 
    return ret_val;
  }
 
  void paint_min_paths_tree(const GT& g, typename GT::Node* start)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
    ah_domain_error_if(g.get_num_nodes() == 0) << "graph is empty";
 
    this->template init<Initialize_Node, Initialize_Arc>(g, start);
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    AACC(start) = 0;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        APOT(arc) = AARC_DIST(arc);
        heap.put_arc(arc, it.get_tgt_node());
      }
 
    const auto& n = g.get_num_nodes();
    size_t tn = 1;
 
    while (tn < n and not heap.is_empty())
      {
        auto garc = heap.get_min_arc();
        if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
          continue;
 
        auto src = g.get_src_node(garc);
        auto tgt = g.get_tgt_node(garc);
 
        if (IS_NODE_VISITED(src, Aleph::Spanning_Tree) and
            IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
          continue;
 
        ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);
 
        if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
          std::swap(src, tgt);
 
        NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
        APARENT(tgt) = src;
 
        ++tn;
 
        AACC(tgt) = this->checked_add(AACC(src), AARC_DIST(garc));
        const auto& acc = AACC(tgt);
 
        for (Itor<GT, SA> it(tgt, sa); it.has_curr(); it.next_ne())
          {
            auto a = it.get_current_arc_ne();
            if (IS_ARC_VISITED(a, Aleph::Spanning_Tree))
              continue;
 
            auto t = it.get_tgt_node();
            if (IS_NODE_VISITED(t, Aleph::Spanning_Tree))
              continue;
 
            APOT(a) = this->checked_add(acc, AARC_DIST(a));
            heap.put_arc(a, t);
          }
      }
 
    this->template uninit<Destroy_Node, Destroy_Arc>();
    painted = true;
  }
 
  typename Distance::Distance_Type
  find_min_path(const GT& g,
                typename GT::Node* start,
                typename GT::Node* end,
                Path<GT>& min_path)
  {
    min_path.empty();
    if (paint_partial_min_paths_tree(g, start, end))
      return this->get_min_path(end, min_path);
 
    return std::numeric_limits<typename Distance::Distance_Type>::max();
  }
 
  // =========================================================================
  // Operator Interfaces
  // =========================================================================
 
  void operator()(const GT& g, typename GT::Node* s, GT& tree)
  {
    compute_min_paths_tree(g, s, tree);
  }
 
  typename Distance::Distance_Type operator()(const GT& g,
                                              typename GT::Node* s,
                                              typename GT::Node* e,
                                              Path<GT>& path)
  {
    return find_path(g, s, e, path);
  }
 
#undef ANassert
#undef APARENT
#undef ATREENODE
#undef AACC
#undef AHEAPNODE
#undef AAassert
#undef AARC_DIST
#undef ATREEARC
#undef APOT
};
 
template <class GT, class Distance = Dft_Dist<GT>>
struct Euclidean_Heuristic
{
  using Distance_Type = typename Distance::Distance_Type;
 
  Distance_Type operator()(typename GT::Node* from, typename GT::Node* to) const
  {
    auto& f = from->get_info();
    auto& t = to->get_info();
    auto dx = f.x - t.x;
    auto dy = f.y - t.y;
    return static_cast<Distance_Type>(std::sqrt(dx * dx + dy * dy));
  }
};
 
template <class GT, class Distance = Dft_Dist<GT>>
struct Manhattan_Heuristic
{
  using Distance_Type = typename Distance::Distance_Type;
 
  Distance_Type operator()(typename GT::Node* from, typename GT::Node* to) const
  {
    auto& f = from->get_info();
    auto& t = to->get_info();
    return static_cast<Distance_Type>(std::abs(f.x - t.x) + std::abs(f.y - t.y));
  }
};
 
} // end namespace Aleph
 
#endif // ASTAR_H