shortest_path_common.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 SHORTEST_PATH_COMMON_H
#define SHORTEST_PATH_COMMON_H
 
#include <limits>
#include <type_traits>
#include <ah-errors.H>
#include <tpl_graph.H>
#include <tpl_find_path.H>
 
namespace Aleph
{
 
// =============================================================================
// Cookie Access Macros (internal use)
// =============================================================================
 
// These macros provide unified access to node/arc cookies across algorithms
 
#define SP_NODE_INFO(p) (static_cast<typename Shortest_Path_Base::Node_Info*>(NODE_COOKIE(p)))
 
#define SP_TREE_NODE_INFO(p) (static_cast<typename Shortest_Path_Base::Tree_Node_Info*>(NODE_COOKIE(p)))
 
#define SP_ACC(p) (SP_NODE_INFO(p)->dist)
 
#define SP_HEAPNODE(p) (SP_NODE_INFO(p)->heap_node)
 
#define SP_PARENT(p) (SP_NODE_INFO(p)->ret_node)
 
#define SP_TREENODE(p) (SP_TREE_NODE_INFO(p)->tree_node)
 
#define SP_ARC_INFO(p) (static_cast<typename Shortest_Path_Base::Arc_Info*>(ARC_COOKIE(p)))
 
#define SP_TREE_ARC_INFO(p) (static_cast<typename Shortest_Path_Base::Tree_Arc_Info*>(ARC_COOKIE(p)))
 
#define SP_POT(p) (SP_ARC_INFO(p)->pot)
 
#define SP_TREEARC(p) (SP_TREE_ARC_INFO(p)->tree_arc)
 
#define SP_ARC_DIST(p) (Distance()(p))
 
 
// =============================================================================
// Overflow-Checked Arithmetic
// =============================================================================
 
namespace shortest_path_detail
{
 
template <typename T>
[[nodiscard]] inline T checked_add(const T& a, const T& b)
{
  if constexpr (std::is_integral_v<T>)
    {
      ah_overflow_error_if(b > 0 and a > std::numeric_limits<T>::max() - b)
        << "Integer overflow in distance addition: " << a << " + " << b;
 
      ah_overflow_error_if(b < 0 and a < std::numeric_limits<T>::min() - b)
        << "Integer underflow in distance addition: " << a << " + " << b;
    }
 
  return a + b;
}
 
} // namespace shortest_path_detail
 
 
// =============================================================================
// Base Class for Shortest Path Algorithms
// =============================================================================
 
template <class GT,
          class Distance,
          template <typename, class> class Itor,
          class SA,
          template <class, class, class> class HeapT>
class Shortest_Path_Base
{
public:
  // =========================================================================
  // Cookie Structures
  // =========================================================================
 
  struct Arc_Info
  {
    typename Distance::Distance_Type pot = 0;  
  };
 
  struct Tree_Arc_Info : public Arc_Info
  {
    typename GT::Arc* tree_arc = nullptr;  
  };
 
  struct Node_Info
  {
    typename Distance::Distance_Type dist = 0;  
    void* heap_node = nullptr;                   
    void* ret_node = nullptr;                    
  };
 
  struct Tree_Node_Info : public Node_Info
  {
    typename GT::Node* tree_node = nullptr;  
  };
 
  // =========================================================================
  // Heap Access Functor
  // =========================================================================
 
  struct Heap_Info
  {
    void*& operator()(typename GT::Node* p) const noexcept
    {
      return SP_HEAPNODE(p);
    }
  };
 
  // =========================================================================
  // Get Potential Functor
  // =========================================================================
 
  struct Get_Potential_Arc : public Distance
  {
    Get_Potential_Arc() = default;
 
    Get_Potential_Arc(Distance& d) noexcept : Distance(d) { }
 
    typename Distance::Distance_Type
    operator()(typename GT::Arc* a) const noexcept
    {
      return SP_POT(a);
    }
  };
 
  // =========================================================================
  // Initialize Functors
  // =========================================================================
 
  struct Initialize_Node
  {
    void operator()(const GT& g, typename GT::Node* p) const
    {
      g.reset_bit(p, Aleph::Spanning_Tree);
      NODE_COOKIE(p) = new Node_Info;
    }
  };
 
  struct Initialize_Arc
  {
    void operator()(const GT& g, typename GT::Arc* a) const
    {
      g.reset_bit(a, Aleph::Spanning_Tree);
      ARC_COOKIE(a) = new Arc_Info;
      SP_POT(a) = 0;
    }
  };
 
  struct Initialize_Tree_Node
  {
    void operator()(const GT& g, typename GT::Node* p) const
    {
      g.reset_bit(p, Aleph::Spanning_Tree);
      NODE_COOKIE(p) = new Tree_Node_Info;
    }
  };
 
  struct Initialize_Tree_Arc
  {
    void operator()(const GT& g, typename GT::Arc* a) const
    {
      g.reset_bit(a, Aleph::Spanning_Tree);
      ARC_COOKIE(a) = new Tree_Arc_Info;
      SP_POT(a) = 0;
      SP_TREEARC(a) = nullptr;
    }
  };
 
  // =========================================================================
  // Destroy Functors
  // =========================================================================
 
  struct Destroy_Node
  {
    void operator()(const GT&, typename GT::Node* p) const noexcept
    {
      void* tmp = SP_PARENT(p);
      delete SP_NODE_INFO(p);
      NODE_COOKIE(p) = tmp;
    }
  };
 
  struct Destroy_Arc
  {
    void operator()(const GT&, typename GT::Arc* ga) const noexcept
    {
      delete SP_ARC_INFO(ga);
    }
  };
 
  struct Destroy_Tree_Node
  {
    void operator()(const GT&, typename GT::Node* p) const noexcept
    {
      auto aux = SP_TREE_NODE_INFO(p);
      auto tp = SP_TREENODE(p);
      if (tp != nullptr)
        {
          NODE_COOKIE(p) = NODE_COOKIE(tp) = nullptr;
          GT::map_nodes(p, tp);
        }
      else
        NODE_COOKIE(p) = nullptr;
 
      delete aux;
    }
  };
 
  struct Destroy_Tree_Arc
  {
    void operator()(const GT&, typename GT::Arc* ga) const noexcept
    {
      auto aux = SP_TREE_ARC_INFO(ga);
      typename GT::Arc* ta = SP_TREEARC(ga);
      if (ta != nullptr)
        {
          assert(IS_ARC_VISITED(ga, Aleph::Spanning_Tree));
          GT::map_arcs(ga, ta);
        }
 
      delete aux;
    }
  };
 
  // =========================================================================
  // Type Aliases
  // =========================================================================
 
  using Heap = HeapT<GT, Get_Potential_Arc, Heap_Info>;
 
protected:
  // =========================================================================
  // Member Variables
  // =========================================================================
 
  SA sa;                           
  Get_Potential_Arc get_pot;       
  Heap heap;                       
  bool painted = false;            
  GT* ptr_g = nullptr;             
  typename GT::Node* s = nullptr;  
 
  // =========================================================================
  // Protected Methods
  // =========================================================================
 
  template <class IN, class IA>
  void init(const GT& g, typename GT::Node* start)
  {
    heap.empty();
 
    ptr_g = &const_cast<GT&>(g);
    s = start;
 
    Operate_On_Nodes<GT, IN>()(g);
    (Operate_On_Arcs<GT, IA>(sa))(g);
  }
 
  template <class DN, class DA>
  void uninit()
  {
    // Clear heap first to avoid use-after-free when heap destructor
    // tries to compare arcs whose cookies have been freed
    heap.empty();
 
    Operate_On_Nodes<GT, DN>()(*ptr_g);
    (Operate_On_Arcs<GT, DA, SA>(sa))(*ptr_g);
  }
 
  typename Distance::Distance_Type
  checked_add(const typename Distance::Distance_Type& a,
              const typename Distance::Distance_Type& b) const
  {
    return shortest_path_detail::checked_add(a, b);
  }
 
public:
  // =========================================================================
  // Constructors
  // =========================================================================
 
  Shortest_Path_Base(Distance dist = Distance(), SA __sa = SA())
    : sa(__sa), get_pot(dist), heap(get_pot, Heap_Info()),
      painted(false), ptr_g(nullptr), s(nullptr)
  {
    // empty
  }
 
  // =========================================================================
  // State Getters
  // =========================================================================
 
  [[nodiscard]] bool has_computation() const noexcept { return ptr_g != nullptr; }
 
  [[nodiscard]] bool is_painted() const noexcept { return painted; }
 
  [[nodiscard]] typename GT::Node* get_start_node() const noexcept { return s; }
 
  [[nodiscard]] GT* get_graph() const noexcept { return ptr_g; }
 
  // =========================================================================
  // Distance Calculation
  // =========================================================================
 
  typename Distance::Distance_Type
  get_distance(typename GT::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 0;
 
    ah_domain_error_if(not IS_NODE_VISITED(node, Aleph::Spanning_Tree))
      << "node is not reachable from start";
 
    typename Distance::Distance_Type total = 0;
 
    for (auto curr = node; curr != s;)
      {
        auto parent = static_cast<typename GT::Node*>(NODE_COOKIE(curr));
        if (parent == nullptr)
          break;
 
        for (Itor<GT, SA> it(parent, sa); it.has_curr(); it.next_ne())
          {
            auto arc = it.get_current_arc_ne();
            auto tgt = it.get_tgt_node();
            if (tgt == curr and IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
              {
                total += Distance()(arc);
                break;
              }
          }
        curr = parent;
      }
 
    return total;
  }
 
  // =========================================================================
  // Path Extraction from Painted Graph
  // =========================================================================
 
  typename Distance::Distance_Type
  get_min_path(typename GT::Node* end, Path<GT>& path)
  {
    ah_domain_error_if(ptr_g == nullptr) << "Min path has not been computed";
    ah_domain_error_if(not painted) << "Graph has not been painted";
 
    return Aleph::get_min_path<GT, Distance>(s, end, path);
  }
 
  // =========================================================================
  // Copy Painted Tree
  // =========================================================================
 
  struct Total
  {
    typename Distance::Distance_Type dist = 0;
 
    Total() noexcept = default;
 
    bool operator()(typename GT::Arc* a) noexcept
    {
      dist += Distance()(a);
      return true;
    }
  };
 
  typename Distance::Distance_Type
  copy_painted_min_paths_tree(GT& g, GT& tree)
  {
    ah_domain_error_if(not painted) << "Graph has not been painted";
 
    using Paint_Filt = Painted_Min_Spanning_Tree<GT, Distance>;
    Paint_Filt paint_filter;
    (Copy_Graph<GT, Dft_Show_Node<GT>, Paint_Filt>(paint_filter))(tree, g);
 
    return paint_filter.dist;
  }
 
  typename Distance::Distance_Type
  get_min_path(const GT& tree, typename GT::Node* end, Path<GT>& path)
  {
    ah_domain_error_if(ptr_g == nullptr) << "Min path has not been computed";
 
    auto ts = mapped_node<GT>(s);
    auto te = mapped_node<GT>(end);
 
    Path<GT> tree_path(tree);
    (Find_Path_Depth_First<GT, Itor>(sa))(tree, ts, te, tree_path);
 
    // Build path in original graph
    path.empty();
    path.init(s);
 
    for (auto it = tree_path.get_it(); it.has_curr(); it.next())
      {
        auto tree_node = it.get_curr();
        if (tree_node != ts)  // Skip start node (already added via init)
          path.append(mapped_node<GT>(tree_node));
      }
 
    // Sum arc weights from the tree path
    typename Distance::Distance_Type total_dist = 0;
    tree_path.for_each_arc([&total_dist](typename GT::Arc* a)
      {
        total_dist += Distance()(a);
      });
 
    return total_dist;
  }
};
 
 
// Cleanup macros (they are redefined in derived classes with appropriate types)
#undef SP_NODE_INFO
#undef SP_TREE_NODE_INFO
#undef SP_ACC
#undef SP_HEAPNODE
#undef SP_PARENT
#undef SP_TREENODE
#undef SP_ARC_INFO
#undef SP_TREE_ARC_INFO
#undef SP_POT
#undef SP_TREEARC
#undef SP_ARC_DIST
 
} // namespace Aleph
 
#endif // SHORTEST_PATH_COMMON_H