Dial.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 DIAL_H
# define DIAL_H
 
# include <ah-graph-concepts.H>
 
# include <limits>
# include <type_traits>
# include <tpl_array.H>
# include <tpl_graph_utils.H>
# include <ah-errors.H>
 
namespace Aleph
{
  template <AlephGraph GT,
            ArcDistance<GT> Distance = Dft_Dist<GT>,
            template <typename, class> class Itor = Node_Arc_Iterator,
            ArcFilter<GT> SA = Dft_Show_Arc<GT>>
  class Dial_Min_Paths
  {
  public:
    using Distance_Type = typename Distance::Distance_Type;
    using Node = typename GT::Node;
    using Arc = typename GT::Arc;
 
    static_assert(std::is_integral_v<Distance_Type>,
                  "Dial's algorithm requires integral distance type");
 
  private:
    SA sa;
    Distance distance;
    bool painted = false;
    GT *ptr_g = nullptr;
    Node *s = nullptr;
    static constexpr size_t Max_Sane_Buckets = 16u * 1024u * 1024u;
 
    static constexpr Distance_Type Inf =
        std::numeric_limits<Distance_Type>::max();
 
    struct Node_Info
    {
      Distance_Type dist;
      Node *parent;
      Arc *parent_arc;
 
      Node_Info() noexcept : dist(Inf), parent(nullptr), parent_arc(nullptr) {}
    };
 
#define DIAL_INFO(p)   (static_cast<Node_Info *>(NODE_COOKIE(p)))
#define DIAL_DIST(p)   (DIAL_INFO(p)->dist)
#define DIAL_PARENT(p) (DIAL_INFO(p)->parent)
#define DIAL_PARC(p)   (DIAL_INFO(p)->parent_arc)
 
    void reset_state_after_failure() noexcept
    {
      painted = false;
      ptr_g = nullptr;
      s = nullptr;
    }
 
    class Dial_Init_Guard
    {
      Dial_Min_Paths * owner = nullptr;
      const GT * g = nullptr;
      bool committed = false;
 
    public:
      Dial_Init_Guard(Dial_Min_Paths & __owner, const GT & __g) noexcept
        : owner(&__owner), g(&__g)
      {
        // empty
      }
 
      Dial_Init_Guard(const Dial_Init_Guard &) = delete;
      Dial_Init_Guard & operator = (const Dial_Init_Guard &) = delete;
      Dial_Init_Guard(Dial_Init_Guard &&) = delete;
      Dial_Init_Guard & operator = (Dial_Init_Guard &&) = delete;
 
      void commit() noexcept { committed = true; }
 
      ~Dial_Init_Guard() noexcept
      {
        if (not committed)
          {
            owner->uninit_discard();
            owner->reset_state_after_failure();
          }
      }
    };
 
    void init(const GT & g)
    {
      ptr_g = &const_cast<GT &>(g);
      for (typename GT::Node_Iterator it(g); it.has_curr(); it.next())
        {
          auto p = it.get_curr();
          g.reset_bit(p, Aleph::Spanning_Tree);
          NODE_COOKIE(p) = nullptr;
        }
      for (typename GT::Arc_Iterator it(g); it.has_curr(); it.next())
        g.reset_bit(it.get_curr(), Aleph::Spanning_Tree);
 
      try
        {
          for (typename GT::Node_Iterator it(g); it.has_curr(); it.next())
            NODE_COOKIE(it.get_curr()) = new Node_Info;
        }
      catch (...)
        {
          uninit_discard();
          reset_state_after_failure();
          throw;
        }
    }
 
    void uninit_paint()
    {
      for (typename GT::Node_Iterator it(*ptr_g); it.has_curr(); it.next())
        {
          auto p = it.get_curr();
          auto info = DIAL_INFO(p);
          auto parent = info->parent;
          delete info;
          NODE_COOKIE(p) = parent;
        }
    }
 
    void uninit_discard()
    {
      if (ptr_g == nullptr)
        return;
 
      for (typename GT::Node_Iterator it(*ptr_g); it.has_curr(); it.next())
        {
          auto p = it.get_curr();
          auto info = DIAL_INFO(p);
          if (info != nullptr)
            delete info;
          NODE_COOKIE(p) = nullptr;
          ptr_g->reset_bit(p, Aleph::Spanning_Tree);
        }
 
      for (typename GT::Arc_Iterator it(*ptr_g); it.has_curr(); it.next())
        ptr_g->reset_bit(it.get_curr(), Aleph::Spanning_Tree);
    }
 
    Distance_Type find_max_weight(const GT & g)
    {
      Distance_Type max_w = 0;
      for (typename GT::Arc_Iterator it(g); it.has_curr(); it.next())
        {
          auto w = distance(it.get_curr());
          ah_domain_error_if(w < 0) << "Dial: negative weight " << w << " not allowed";
          if (w > max_w)
            max_w = w;
        }
      return max_w;
    }
 
    void run_dial(const GT & g, Node *start, Node *end = nullptr)
    {
      auto max_w = find_max_weight(g);
 
      if (max_w == 0)
        {
          // All edges have weight 0: simple BFS
          DIAL_DIST(start) = 0;
          NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
 
          DynList<Node *> queue;
          queue.append(start);
 
          while (not queue.is_empty())
            {
              auto curr = queue.remove_first();
 
              if (end != nullptr and curr == end)
                break;
 
              for (Itor<GT, SA> it(curr, sa); it.has_curr(); it.next())
                {
                  auto arc = it.get_current_arc();
                  auto tgt = g.get_connected_node(arc, curr);
 
                  if (DIAL_DIST(tgt) > 0)
                    {
                      DIAL_DIST(tgt) = 0;
                      DIAL_PARENT(tgt) = curr;
                      DIAL_PARC(tgt) = arc;
                      NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
                      ARC_BITS(arc).set_bit(Aleph::Spanning_Tree, true);
                      queue.append(tgt);
                    }
                }
            }
          return;
        }
 
      auto num_nodes = g.get_num_nodes();
      const size_t path_edge_bound = num_nodes > 0 ? num_nodes - 1 : 0;
      const size_t max_w_size = static_cast<size_t>(max_w);
 
      // Maximum possible shortest-path distance in this graph:
      // (|V|-1) * max_w. Compute it with checked size_t arithmetic.
      ah_overflow_error_if(max_w_size != 0 and
                           path_edge_bound > std::numeric_limits<size_t>::max() / max_w_size)
        << "Dial: overflow computing max_dist = (|V|-1) * max_w with |V|="
        << num_nodes << " and max_w=" << max_w;
 
      const size_t max_dist_size = path_edge_bound * max_w_size;
      ah_overflow_error_if(max_dist_size > static_cast<size_t>(std::numeric_limits<Distance_Type>::max()))
        << "Dial: max_dist " << max_dist_size
        << " exceeds Distance_Type range; use a wider type or Dijkstra";
      ah_overflow_error_if(max_dist_size == std::numeric_limits<size_t>::max())
        << "Dial: overflow computing number of buckets";
 
      const Distance_Type max_dist = static_cast<Distance_Type>(max_dist_size);
      const size_t num_buckets = max_dist_size + 1;
      ah_runtime_error_if(num_buckets > Max_Sane_Buckets)
        << "Dial: bucket count " << num_buckets
        << " exceeds safety limit " << Max_Sane_Buckets
        << "; use Dijkstra_Min_Paths for large weight ranges";
 
      Array<DynList<Node *>> buckets(num_buckets, DynList<Node *>());
 
      DIAL_DIST(start) = 0;
      NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
      buckets[0].append(start);
 
      size_t processed = 0;
 
      for (size_t idx = 0; idx < num_buckets and processed < num_nodes; ++idx)
        {
          while (not buckets[idx].is_empty())
            {
              auto curr = buckets[idx].remove_first();
              auto curr_dist = DIAL_DIST(curr);
 
              // Skip if this entry is stale (node was already relaxed to
              // a shorter distance)
              if (static_cast<size_t>(curr_dist) != idx)
                continue;
 
              ++processed;
 
              if (end != nullptr and curr == end)
                return;
 
              for (Itor<GT, SA> it(curr, sa); it.has_curr(); it.next())
                {
                  auto arc = it.get_current_arc();
                  auto tgt = g.get_connected_node(arc, curr);
                  auto w = distance(arc);
                  ah_domain_error_if(w < 0) << "Dial: negative weight " << w
                                            << " not allowed";
                  ah_overflow_error_if(curr_dist > std::numeric_limits<Distance_Type>::max() - w)
                    << "Dial: overflow computing new_dist = curr_dist + w";
                  auto new_dist = curr_dist + w;
 
                  // Distances above the computed bound are not representable in buckets.
                  if (new_dist > max_dist)
                    continue;
 
                  if (new_dist < DIAL_DIST(tgt))
                    {
                      // Clear previous Spanning_Tree mark for tgt's parent arc
                      // to correctly handle multi-edges and avoid stale marks.
                      if (DIAL_PARC(tgt) != nullptr)
                        ARC_BITS(DIAL_PARC(tgt)).set_bit(Aleph::Spanning_Tree, false);
 
                      DIAL_DIST(tgt) = new_dist;
                      DIAL_PARENT(tgt) = curr;
                      DIAL_PARC(tgt) = arc;
                      NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
                      ARC_BITS(arc).set_bit(Aleph::Spanning_Tree, true);
                      buckets[static_cast<size_t>(new_dist)].append(tgt);
                    }
                }
            }
        }
    }
 
  public:
    Dial_Min_Paths(Distance dist = Distance(), SA __sa = SA())
      : sa(__sa), distance(dist)
    {
      // empty
    }
 
    [[nodiscard]] bool is_painted() const noexcept { return painted; }
 
    [[nodiscard]] Node * get_start_node() const noexcept { return s; }
 
    [[nodiscard]] GT * get_graph() const noexcept { return ptr_g; }
 
    void paint_min_paths_tree(const GT & g, 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";
 
      painted = false;
      s = nullptr;
 
      init(g);
      Dial_Init_Guard guard(*this, g);
      s = start;
      run_dial(g, start);
      uninit_paint();
      guard.commit();
      painted = true;
    }
 
    [[nodiscard]] Distance_Type get_distance(Node *node)
    {
      ah_domain_error_if(not painted) << "Graph has not been painted";
      ah_domain_error_if(node == nullptr) << "node cannot be null";
 
      if (node == s)
        return Distance_Type(0);
 
      ah_domain_error_if(not IS_NODE_VISITED(node, Aleph::Spanning_Tree))
      << "node is not reachable from start";
 
      Distance_Type total = 0;
      for (auto curr = node; curr != s;)
        {
          auto parent = static_cast<Node *>(NODE_COOKIE(curr));
          ah_domain_error_if(parent == nullptr)
            << "Dial: path reconstruction failed (null parent)";
 
          bool found = false;
          for (Itor<GT, SA> it(parent, sa); it.has_curr(); it.next())
            {
              auto arc = it.get_current_arc();
              auto tgt = ptr_g->get_connected_node(arc, parent);
              if (tgt == curr and IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
                {
                  total += distance(arc);
                  found = true;
                  break;
                }
            }
          ah_domain_error_if(not found)
            << "Dial: path reconstruction failed (arc not found)";
 
          curr = parent;
        }
 
      return total;
    }
 
    Distance_Type get_min_path(Node *end, Path<GT> & path)
    {
      ah_domain_error_if(not painted) << "Graph has not been painted";
      ah_domain_error_if(ptr_g == nullptr) << "No computation has been done";
 
      return Aleph::get_min_path<GT, Distance>(s, end, path);
    }
 
    Distance_Type find_min_path(const GT & g, Node *start, Node *end,
                                Path<GT> & path)
    {
      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";
 
      path.empty();
 
      painted = false;
      s = nullptr;
 
      init(g);
      Dial_Init_Guard guard(*this, g);
      s = start;
      run_dial(g, start, end);
      uninit_paint();
      guard.commit();
      painted = true;
 
      if (not IS_NODE_VISITED(end, Aleph::Spanning_Tree))
        return Inf;
 
      return get_min_path(end, path);
    }
 
    Distance_Type operator()(const GT & g, Node *start, Node *end,
                             Path<GT> & path)
    {
      return find_min_path(g, start, end, path);
    }
 
#undef DIAL_INFO
#undef DIAL_DIST
#undef DIAL_PARENT
#undef DIAL_PARC
  };
} // end namespace Aleph
 
# endif // DIAL_H