Dijkstra.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 DIJKSTRA_H
#define DIJKSTRA_H
 
#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>,
          template <typename, class> class Itor = Node_Arc_Iterator,
          class SA = Dft_Show_Arc<GT>,
          template <class, class, class> class HeapT = ArcHeap>
class Dijkstra_Min_Paths
  : 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 DNassert(p) (static_cast<Node_Info*>(NODE_COOKIE(p)))
#define TREENODE(p) (static_cast<Tree_Node_Info*>(NODE_COOKIE(p))->tree_node)
#define ACC(p) (DNassert(p)->dist)
#define HEAPNODE(p) (DNassert(p)->heap_node)
#define PARENT(p) (DNassert(p)->ret_node)
#define DAassert(p) (static_cast<Arc_Info*>(ARC_COOKIE(p)))
#define ARC_DIST(p) (Distance()(p))
#define TREEARC(p) (static_cast<Tree_Arc_Info*>(ARC_COOKIE(p))->tree_arc)
#define POT(p) (DAassert(p)->pot)
 
  // Import member variables from base
  using Base::sa;
  using Base::heap;
  using Base::painted;
  using Base::ptr_g;
  using Base::s;
 
public:
  Dijkstra_Min_Paths(Distance dist = Distance(), SA __sa = SA())
    : Base(dist, __sa)
  {
    // 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;
 
  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);
    ACC(start) = 0;
    auto ret = TREENODE(start) = tree.insert_node(start->get_info());
    NODE_COOKIE(TREENODE(start)) = start;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        POT(arc) = ARC_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());
        TREENODE(gtgt) = ttgt;
        auto tsrc = TREENODE(gsrc);
 
        auto tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
        TREEARC(garc) = tarc;
 
        ACC(gtgt) = this->checked_add(ACC(gsrc), ARC_DIST(garc));
        const auto& acc = ACC(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;
 
            POT(arc) = this->checked_add(acc, ARC_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);
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    ACC(start) = 0;
    TREENODE(start) = tree.insert_node(start->get_info());
    NODE_COOKIE(TREENODE(start)) = start;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        POT(arc) = ARC_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);
 
        auto ttgt = tree.insert_node(gtgt->get_info());
        TREENODE(gtgt) = ttgt;
        NODE_BITS(gtgt).set_bit(Aleph::Spanning_Tree, true);
 
        auto tarc = tree.insert_arc(TREENODE(gsrc), TREENODE(gtgt), garc->get_info());
        TREEARC(garc) = tarc;
 
        if (gtgt == end)
          break;
 
        ACC(gtgt) = this->checked_add(ACC(gsrc), ARC_DIST(garc));
        const auto& acc = ACC(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;
 
            POT(arc) = this->checked_add(acc, ARC_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";
 
    bool ret_val = false;
    this->template init<Initialize_Node, Initialize_Arc>(g, start);
 
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
    ACC(start) = 0;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        POT(arc) = ARC_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);
        PARENT(tgt) = src;
 
        ++tn;
 
        if (tgt == end)
          {
            ret_val = true;
            break;
          }
 
        ACC(tgt) = this->checked_add(ACC(src), ARC_DIST(garc));
        const auto& acc = ACC(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;
 
            POT(a) = this->checked_add(acc, ARC_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);
    ACC(start) = 0;
 
    for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_current_arc_ne();
        POT(arc) = ARC_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);
        PARENT(tgt) = src;
 
        ++tn;
 
        ACC(tgt) = this->checked_add(ACC(src), ARC_DIST(garc));
        const auto& acc = ACC(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;
 
            POT(a) = this->checked_add(acc, ARC_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();
  }
 
  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_min_path(g, s, e, path);
  }
 
#undef DNassert
#undef PARENT
#undef TREENODE
#undef ACC
#undef HEAPNODE
#undef DAassert
#undef ARC_DIST
#undef TREEARC
#undef POT
};
 
} // end namespace Aleph
 
#endif // DIJKSTRA_H