Bellman_Ford.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 BELLMAN_FORD_H
#define BELLMAN_FORD_H
 
# include <ah-graph-concepts.H>
 
#include <type_traits>
#include <limits>
#include <vector>
 
#include <tpl_dynListQueue.H>
#include <tpl_dynSetTree.H>
#include <tpl_graph_utils.H>
#include <Tarjan.H>
#include <ah-errors.H>
#include <ah_init_guard.H>
#include <cookie_guard.H>
 
namespace Aleph {
template <AlephGraph GT,
          ArcDistance<GT> Distance = Dft_Dist<GT>,
          template <class, class> class Ait = Arc_Iterator,
          template <class, class> class NAit = Out_Iterator,
          ArcFilter<GT> SA = Dft_Show_Arc<GT>>
class Bellman_Ford
{
  typedef typename Distance::Distance_Type Distance_Type;
 
  using Node = typename GT::Node;
  using Arc = typename GT::Arc;
 
  struct Sni
  {
    Distance_Type accum;
  };
 
  struct Ni : public Sni
  {
    int idx;  // index in the predecessor arrays
  };
 
  static Distance_Type &accum(Node *p) noexcept
  {
    return static_cast<Sni *>(NODE_COOKIE(p))->accum;
  }
 
  static int &idx(Node *p) noexcept
  {
    return static_cast<Ni *>(NODE_COOKIE(p))->idx;
  }
 
  // Checked addition to prevent integer overflow
  Distance_Type checked_add(const Distance_Type &a, const Distance_Type &b) const
  {
    if constexpr (std::is_integral_v<Distance_Type>)
      {
        // Check for positive overflow
        ah_overflow_error_if(b > 0 && a > std::numeric_limits<Distance_Type>::max() - b)
          << "Integer overflow in distance addition: " << a << " + " << b;
 
        // Check for negative overflow (underflow)
        ah_overflow_error_if(b < 0 && a < std::numeric_limits<Distance_Type>::min() - b)
          << "Integer underflow in distance addition: " << a << " + " << b;
      }
 
    return a + b;
  }
 
  DynArray<typename GT::Arc *> arcs_;
  GT &g_;  // Non-const: algorithm modifies node/arc bits and cookies
  const Distance_Type Inf;
  bool painted_ = false;
  Node *s_ = nullptr;
  SA sa_;
  Distance dist_;
 
  void init_simple(Node *start)
  {
    Init_Guard guard([this]()
    {
      uninit<Sni>();
    });
 
    typename GT::Node_Iterator it(g_);
    for (int i = 0; it.has_curr(); ++i, it.next_ne())
      {
        auto p = it.get_curr();
        g_.reset_bit(p, Aleph::Spanning_Tree);  // set bit to zero
        NODE_COOKIE(p) = nullptr;  // clear stale pointer before allocating
        auto ptr = new Sni;
        ptr->accum = Inf;
        NODE_BITS(p).set_bit(Spanning_Tree, false);
        NODE_COOKIE(p) = ptr;
      }
    s_ = start;
    accum(s_) = 0;
    g_.reset_arcs();
 
    guard.release();  // Successful initialization, prevent cleanup
  }
 
  void init_with_indexes(Node *start)
  {
    Init_Guard guard([this]()
    {
      uninit<Ni>();
      arcs_.cut();
    });
 
    const size_t n = g_.get_num_nodes();
    arcs_.cut();  // Clear any previous data
    arcs_.reserve(n);
 
    typename GT::Node_Iterator it(g_);
    for (size_t i = 0; it.has_curr(); ++i, it.next())
      {
        // Use touch() to ensure memory is allocated for index i
        arcs_.touch(i) = nullptr;
        auto p = it.get_curr();
        g_.reset_bit(p, Aleph::Spanning_Tree);  // set bit to zero
        NODE_COOKIE(p) = nullptr;  // clear stale pointer before allocating
        auto ptr = new Ni;
        ptr->accum = Inf;
        ptr->idx = static_cast<int>(i);
        NODE_BITS(p).set_bit(Spanning_Tree, false);
        NODE_BITS(p).set_bit(Depth_First, false);  // indicates if it is in queue
        NODE_COOKIE(p) = ptr;
      }
 
    painted_ = false;
    s_ = start;
    accum(s_) = 0;
 
    g_.reset_arcs();
 
    guard.release();  // Successful initialization, prevent cleanup
  }
 
  template <class Info_Type>
  void uninit()
  {
    for (typename GT::Node_Iterator it(g_); it.has_curr(); it.next())
      {
        auto p = it.get_curr();
        delete static_cast<Info_Type *>(NODE_COOKIE(p));
        NODE_COOKIE(p) = nullptr;
      }
  }
 
  bool check_painted_arcs() noexcept
  {
    if (s_ == nullptr)
      return false;
 
    size_t num_painted_arcs = 0;
    size_t num_painted_nodes = 0;
 
    // Count painted arcs
    for (Ait<GT, SA> it(g_, sa_); it.has_curr(); it.next_ne())
      if (IS_ARC_VISITED(it.get_curr(), Aleph::Spanning_Tree))
        ++num_painted_arcs;
 
    // Count painted nodes and verify each has exactly one incoming painted arc
    for (typename GT::Node_Iterator it(g_); it.has_curr(); it.next_ne())
      {
        auto node = it.get_curr();
        if (not IS_NODE_VISITED(node, Aleph::Spanning_Tree))
          continue;
 
        ++num_painted_nodes;
 
        // Skip root node - it should have no incoming painted arcs
        if (node == s_)
          continue;
 
        // Count incoming painted arcs to this node
        size_t incoming_count = 0;
        for (Ait<GT, SA> ait(g_, sa_); ait.has_curr(); ait.next_ne())
          if (auto arc = ait.get_curr();
              IS_ARC_VISITED(arc, Aleph::Spanning_Tree) and g_.get_tgt_node(arc) == node)
            ++incoming_count;
 
        // Each non-root painted node must have exactly 1 incoming painted arc
        if (incoming_count != 1)
          return false;
      }
 
    // Tree property: #arcs == #nodes - 1
    return num_painted_nodes != 0 and num_painted_arcs == num_painted_nodes - 1;
  }
 
public:
  Bellman_Ford(GT &__g, Distance d = Distance(), SA __sa = SA())
    : g_(__g), Inf(std::numeric_limits<Distance_Type>::max()), painted_(false), sa_(__sa), dist_(d)
  {
    // empty
  }
 
  void clear() noexcept
  {
    if (painted_)
      {
        // Clear Spanning_Tree bits from all nodes and arcs
        for (typename GT::Node_Iterator it(g_); it.has_curr(); it.next_ne())
          NODE_BITS(it.get_curr()).set_bit(Aleph::Spanning_Tree, false);
 
        for (Ait<GT, SA> it(g_, sa_); it.has_curr(); it.next_ne())
          ARC_BITS(it.get_curr()).set_bit(Aleph::Spanning_Tree, false);
      }
 
    arcs_.cut();
    painted_ = false;
    s_ = nullptr;
  }
 
  [[nodiscard]] bool has_computation() const noexcept
  {
    return s_ != nullptr;
  }
 
  [[nodiscard]] bool is_painted() const noexcept
  {
    return painted_;
  }
 
  Node *get_start_node() const noexcept
  {
    return s_;
  }
 
  const GT &get_graph() const noexcept
  {
    return g_;
  }
 
private:
  void relax_arcs() noexcept
  {
    const size_t &n = g_.vsize();
    if (n <= 1)
      return;  // Nothing to relax for empty or single-node graphs
 
    for (size_t i = 0; i < n - 1; ++i)
      for (Ait<GT, SA> it(g_, sa_); it.has_curr(); it.next_ne())
        {
          auto arc = it.get_curr();
          auto src = g_.get_src_node(arc);
          const auto &accum_src = accum(src);
          if (accum_src == Inf)
            continue;
 
          auto tgt = it.get_tgt_node_ne();
          auto w = dist_(arc);
          auto sum = checked_add(accum_src, w);
          auto &accum_tgt = accum(tgt);
          if (sum < accum_tgt)  // Relax Arc
            {
              const auto &index = idx(tgt);
              arcs_(index) = arc;
              accum_tgt = sum;
            }
        }
  }
 
  static void put_in_queue(DynListQueue<typename GT::Node *> &q, typename GT::Node *p)
  {
    if (IS_NODE_VISITED(p, Depth_First))  // is already inside the queue?
      return;
    NODE_BITS(p).set_bit(Depth_First, true);
    q.put(p);
  }
 
  static typename GT::Node *get_from_queue(DynListQueue<typename GT::Node *> &q)
  {
    auto ret = q.get();
    assert(IS_NODE_VISITED(ret, Depth_First));
    NODE_BITS(ret).set_bit(Depth_First, false);
    return ret;
  }
 
  void relax_arcs(typename GT::Node *src, DynListQueue<typename GT::Node *> &q)
  {
    for (NAit<GT, SA> it(src, sa_); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_curr();
        auto arc_src = g_.get_src_node(arc);
        const auto &accum_src = accum(arc_src);
        if (accum_src == Inf)
          continue;
 
        auto tgt = g_.get_tgt_node(arc);
        auto w = dist_(arc);
        auto sum = checked_add(accum_src, w);
        auto &accum_tgt = accum(tgt);
        if (sum < accum_tgt)  // Relax Arc
          {
            const auto &index = idx(tgt);
            arcs_(index) = arc;
            accum_tgt = sum;
            put_in_queue(q, tgt);
          }
      }
  }
 
  void paint_tree() noexcept
  {  // paint the involved nodes and arcs
    const size_t n = g_.vsize();
    for (size_t i = 0; i < n; ++i)
      {
        auto arc = arcs_(i);
        if (arc == nullptr)
          continue;
 
        ARC_BITS(arc).set_bit(Aleph::Spanning_Tree, true);
        auto src = g_.get_src_node(arc);
        auto tgt = g_.get_tgt_node(arc);
        NODE_BITS(src).set_bit(Aleph::Spanning_Tree, true);
        NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
      }
    NODE_BITS(s_).set_bit(Aleph::Spanning_Tree, true);
 
    assert(check_painted_arcs());
 
    painted_ = true;
  }
 
  bool last_relax_and_prepare_check_negative_cycle() noexcept
  {
    bool negative_cycle = false;
    for (Ait<GT, SA> it(g_, sa_); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_curr();
        auto src = g_.get_src_node(arc);
        auto &accum_src = accum(src);
        if (accum_src == Inf)
          continue;
 
        auto tgt = g_.get_tgt_node(arc);
        auto d = dist_(arc);
        auto &accum_tgt = accum(tgt);
        auto sum = checked_add(accum_src, d);
        if (sum < accum_tgt)
          {
            negative_cycle = true;
            const auto &index = idx(tgt);
            arcs_(index) = arc;
            accum_tgt = sum;
          }
      }
    return negative_cycle;
  }
 
  bool last_relax_and_test_negative_cycle() noexcept
  {
    for (Ait<GT, SA> it(g_, sa_); it.has_curr(); it.next_ne())
      {
        auto arc = it.get_curr();
        auto src = g_.get_src_node(arc);
        auto &accum_src = accum(src);
        if (accum_src == Inf)
          continue;
 
        auto tgt = g_.get_tgt_node(arc);
        auto d = dist_(arc);
        auto &accum_tgt = accum(tgt);
        auto sum = checked_add(accum_src, d);
        if (sum < accum_tgt)
          return true;
      }
    return false;
  }
 
  void link_cookies_and_free(typename GT::Node *start) noexcept
  {
    uninit<Ni>();
 
    // Construct the inverted paths to the start origin node
    const size_t n = g_.vsize();
    for (size_t i = 0; i < n; ++i)
      {
        auto arc = arcs_(i);
        if (arc == nullptr)
          continue;
 
        auto tgt = g_.get_tgt_node(arc);
        NODE_COOKIE(tgt) = g_.get_src_node(arc);
      }
 
    NODE_COOKIE(start) = nullptr;  // just in case there is a negative cycle
  }
 
public:
  bool paint_spanning_tree(Node *start)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
 
    init_with_indexes(start);
 
    relax_arcs();
    const bool negative_cycle = last_relax_and_prepare_check_negative_cycle();
 
    // Only paint the tree if there's no negative cycle
    // A negative cycle makes the shortest path tree meaningless
    if (not negative_cycle)
      paint_tree();
 
    link_cookies_and_free(s_);
 
    return negative_cycle;
  }
 
  bool faster_paint_spanning_tree(Node *start)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
 
    init_with_indexes(start);
 
    const auto &n = g_.get_num_nodes();
 
    DynListQueue<typename GT::Node *> q;
 
    Node __sentinel;
    Node *sentinel = &__sentinel;
 
    put_in_queue(q, s_);
    put_in_queue(q, sentinel);
 
    for (size_t i = 0; not q.is_empty();)
      {
        auto src = get_from_queue(q);
        if (src == sentinel)  // Is the sentinel removed?
          {
            if (i++ > n)
              {
                while (not q.is_empty())
                  get_from_queue(q);  // clear Depth_First bits on remaining nodes
                break;
              }
 
            put_in_queue(q, sentinel);
          }
        else
          relax_arcs(src, q);
      }
 
    const bool negative_cycle = last_relax_and_prepare_check_negative_cycle();
 
    // Only paint the tree if there's no negative cycle
    // A negative cycle makes the shortest path tree meaningless
    if (not negative_cycle)
      paint_tree();
 
    link_cookies_and_free(s_);
 
    return negative_cycle;
  }
 
private:
  Node *create_dummy_node()
  {
    // RAII guard to ensure cleanup on exception
    struct Dummy_Guard
    {
      GT &graph;
      Node *dummy;
      std::vector<Arc *> inserted_arcs;
      bool released = false;
 
      explicit Dummy_Guard(GT &g, Node *d) : graph(g), dummy(d)
      {
        inserted_arcs.reserve(g.get_num_nodes());
      }
 
      ~Dummy_Guard()
      {
        if (not released)
          {
            // Remove all inserted arcs
            for (auto arc : inserted_arcs)
              graph.remove_arc(arc);
 
            // Remove dummy node
            if (dummy != nullptr)
              graph.remove_node(dummy);
          }
      }
 
      void add_arc(Arc *a)
      {
        inserted_arcs.push_back(a);
      }
      void release()
      {
        released = true;
      }
 
      Dummy_Guard(const Dummy_Guard &) = delete;
 
      Dummy_Guard &operator=(const Dummy_Guard &) = delete;
    };
 
    s_ = g_.insert_node(typename GT::Node_Type());
    Dummy_Guard guard(g_, s_);
 
    for (typename GT::Node_Iterator it(g_); it.has_curr(); it.next_ne())
      {
        auto p = it.get_curr();
        if (p == s_)
          continue;
        auto a = g_.insert_arc(s_, p);
        guard.add_arc(a);
        Distance::set_zero(a);
      }
 
    guard.release();  // Successful creation, prevent cleanup
    return s_;
  }
 
  template <class Info_Type>
  void remove_dummy_node(Node *p)
  {
    delete static_cast<Info_Type *>(NODE_COOKIE(p));
    NODE_COOKIE(p) = nullptr;
    if (p == s_)
      s_ = nullptr;
    g_.remove_node(p);
  }
 
public:
  bool has_negative_cycle(Node *start)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
 
    init_with_indexes(start);
    // Note: s and accum(s) already set by init_with_indexes
 
    relax_arcs();
    const bool negative_cycle = last_relax_and_test_negative_cycle();
    uninit<Ni>();
 
    return negative_cycle;
  }
 
  bool has_negative_cycle()
  {
    Node *dummy = create_dummy_node();
 
    // RAII guard ensures dummy node removal even on exception
    struct Global_Cycle_Guard
    {
      Bellman_Ford &bf;
      Node *dummy_node;
      bool released = false;
 
      Global_Cycle_Guard(Bellman_Ford &b, Node *d) : bf(b), dummy_node(d) {}
 
      ~Global_Cycle_Guard()
      {
        if (not released and dummy_node != nullptr)
          {
            // Clean up: remove dummy node and its arcs
            bf.remove_dummy_node<Ni>(dummy_node);
          }
      }
 
      void release()
      {
        released = true;
      }
    };
 
    Global_Cycle_Guard guard(*this, dummy);
 
    auto ret = has_negative_cycle(dummy);
    guard.release();
    remove_dummy_node<Ni>(dummy);
 
    return ret;
  }
 
private:
  Path<GT> search_negative_cycle_on_partial_graph()
  {
    GT aux = build_spanning_tree<GT>(arcs_);
 
    // we map because Tarjan algorithm modifies cookies
    DynMapTree<Node *, Node *> table;
    for (typename GT::Node_Iterator it(aux); it.has_curr(); it.next_ne())
      {
        auto p = it.get_curr();
        table.insert(p, static_cast<Node *>(NODE_COOKIE(p)));
      }
 
    // Save and restore cookies around Tarjan call (Tarjan modifies cookies)
    Cookie_Saver<GT> cookie_saver(aux, true, false);  // only save node cookies
 
    // Clear cookies for Tarjan's use
    for (typename GT::Node_Iterator it(aux); it.has_curr(); it.next_ne())
      NODE_COOKIE(it.get_curr()) = nullptr;
 
    if (Path<GT> path(aux); Tarjan_Connected_Components<GT, NAit, SA>(sa_).compute_cycle(aux, path))
      {
        Path<GT> ret(g_);
        for (typename Path<GT>::Iterator it(path); it.has_current_node(); it.next_ne())
          ret.append_directed(static_cast<Node *>(table.find(it.get_current_node_ne())));
        return ret;
      }
 
    return Path<GT>(g_);
  }
 
public:
  Path<GT> test_negative_cycle(Node *start)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
 
    init_with_indexes(start);
 
    relax_arcs();
    const bool negative_cycle = last_relax_and_prepare_check_negative_cycle();
    if (not negative_cycle)
      {
        link_cookies_and_free(s_);
        return Path<GT>(g_);
      }
 
    Path<GT> ret = search_negative_cycle_on_partial_graph();
    if (ret.is_empty())
      WARNING(
        "Serious inconsistency. Bellman-Ford algorithm has detected\n"
        "a negative cycle, but Tarjan algorithm executed on partial\n"
        "graph has not found such cycle\n\n"
        "Be very careful, this is provably a bug");
 
    link_cookies_and_free(s_);
    return ret;
  }
 
  Path<GT> test_negative_cycle()
  {
    auto start = create_dummy_node();
 
    // RAII guard ensures dummy node removal even on exception
    Init_Guard guard([this, start]()
    {
      remove_dummy_node<Ni>(start);
    });
 
    auto ret_val = test_negative_cycle(start);
    guard.release();
    remove_dummy_node<Ni>(start);
    return ret_val;
  }
 
  std::tuple<Path<GT>, size_t> search_negative_cycle(Node *start, double it_factor, const size_t step)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
 
    init_with_indexes(start);
 
    const auto &n = g_.get_num_nodes();
    DynListQueue<typename GT::Node *> q;
    Node __sentinel;
    Node *sentinel = &__sentinel;
    put_in_queue(q, s_);
    put_in_queue(q, sentinel);
 
    double threshold = it_factor * n;
    Path<GT> ret(g_);
 
    size_t i = 0;
    while (not q.is_empty())
      {
        auto src = get_from_queue(q);
        if (src == sentinel)
          {
            if (i++ > n)
              break;
 
            put_in_queue(q, sentinel);
            if (i >= threshold)  // must I search negative cycles?
              {
                ret = search_negative_cycle_on_partial_graph();
                if (not ret.is_empty())  // negative cycle found?
                  {
                    link_cookies_and_free(s_);
                    return std::make_tuple(std::forward<Path<GT>>(ret), i);
                  }
                threshold += step;
              }
          }
        else
          relax_arcs(src, q);
      }
 
    if (const bool negative_cycle = last_relax_and_prepare_check_negative_cycle())
      {
        ret = search_negative_cycle_on_partial_graph();
        if (ret.is_empty())
          WARNING(
            "Serious inconsistency. Bellman-Ford algorithm has detected\n"
            "a negative cycle, but Tarjan algorithm executed on partial\n"
            "graph has not found such cycle\n\n"
            "Be very careful, this provably is a bug");
      }
 
    link_cookies_and_free(s_);
    return std::make_tuple(std::forward<Path<GT>>(ret), i);
  }
 
  Path<GT> search_negative_cycle(Node *start)
  {
    ah_domain_error_if(start == nullptr) << "start node cannot be null";
 
    init_with_indexes(start);
 
    const auto &n = g_.get_num_nodes();
    DynListQueue<typename GT::Node *> q;
    Node __sentinel;
    Node *sentinel = &__sentinel;
    put_in_queue(q, s_);
    put_in_queue(q, sentinel);
 
    Path<GT> ret(g_);
    for (size_t i = 0; not q.is_empty(); /* nothing */)
      {
        auto src = get_from_queue(q);
        if (src == sentinel)
          {
            if (i++ > n)
              break;
 
            put_in_queue(q, sentinel);
          }
        else
          relax_arcs(src, q);
      }
 
    if (const bool negative_cycle = last_relax_and_prepare_check_negative_cycle())
      {
        ret = search_negative_cycle_on_partial_graph();
        if (ret.is_empty())
          WARNING(
            "Serious inconsistency. Bellman-Ford algorithm has detected\n"
            "a negative cycle, but Tarjan algorithm executed on partial\n"
            "graph has not found such cycle\n\n"
            "Be very careful, this provably is a bug");
      }
 
    link_cookies_and_free(s_);
 
    return ret;
  }
 
  std::tuple<Path<GT>, size_t> search_negative_cycle(double it_factor, const size_t step)
  {
    auto start = create_dummy_node();
 
    // RAII guard ensures dummy node removal even on exception
    Init_Guard guard([this, start]()
    {
      remove_dummy_node<Ni>(start);
    });
 
    auto ret_val = search_negative_cycle(start, it_factor, step);
    guard.release();
    remove_dummy_node<Ni>(start);
    return ret_val;
  }
 
  Path<GT> search_negative_cycle()
  {
    auto start = create_dummy_node();
 
    // RAII guard ensures dummy node removal even on exception
    Init_Guard guard([this, start]()
    {
      remove_dummy_node<Ni>(start);
    });
 
    auto ret_val = search_negative_cycle(start);
    guard.release();
    remove_dummy_node<Ni>(start);
    return ret_val;
  }
 
  DynArray<Arc *> extract_min_spanning_tree()
  {
    ah_domain_error_if(not painted_) << "Spanning tree has not been painted";
 
    return arcs_;
  }
 
  Distance_Type get_distance(typename GT::Node *node)
  {
    ah_domain_error_if(not painted_) << "Graph has not been previously painted";
 
    ah_domain_error_if(node == nullptr) << "node cannot be null";
 
    // Follow predecessor chain to verify reachability
    auto curr = node;
    while (curr != s_)
      {
        auto parent = static_cast<Node *>(NODE_COOKIE(curr));
        ah_domain_error_if(parent == nullptr) << "Node is not reachable from start node";
        curr = parent;
      }
 
    // Compute distance by following the path
    Distance_Type total = 0;
    curr = node;
    while (curr != s_)
      {
        auto parent = static_cast<Node *>(NODE_COOKIE(curr));
 
        // Find the arc from parent to curr
        for (NAit<GT, SA> it(parent, sa_); it.has_curr(); it.next_ne())
          if (auto arc = it.get_curr();
              g_.get_tgt_node(arc) == curr && IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
            {
              total = checked_add(total, dist_(arc));
              break;
            }
        curr = parent;
      }
    return total;
  }
 
  void build_tree(GT &tree, bool with_map = true)
  {
    ah_domain_error_if(not painted_ and with_map) << "Spanning tree has not been painted";
 
    clear_graph(tree);
 
    DynMapTree<Node *, Node *> table;
    for (typename GT::Node_Iterator it(g_); it.has_curr(); it.next_ne())
      {
        auto gp = it.get_curr();
        auto tp = tree.insert_node(gp->get_info());
        table.insert(gp, tp);
      }
 
    for (typename GT::Node_Iterator it(g_); it.has_curr(); it.next_ne())
      {
        auto gtgt = it.get_curr();
        auto gsrc = static_cast<Node *>(NODE_COOKIE(gtgt));
        if (gsrc == nullptr)
          continue;  // This is the source node of the spanning tree
 
        // Find the spanning tree arc from gsrc to gtgt
        Arc *garc = nullptr;
        for (Out_Iterator<GT, SA> ait(gsrc, sa_); ait.has_curr(); ait.next_ne())
          {
            auto a = ait.get_curr();
            if (g_.get_tgt_node(a) == gtgt and IS_ARC_VISITED(a, Aleph::Spanning_Tree))
              {
                garc = a;
                break;
              }
          }
        ah_logic_error_unless(garc != nullptr) << "Arc not found between nodes in spanning tree";
 
        auto tsrc_ptr = table.search(gsrc);
        auto ttgt_ptr = table.search(gtgt);
        ah_logic_error_unless(tsrc_ptr) << "Source node not found in mapping table";
        ah_logic_error_unless(ttgt_ptr) << "Target node not found in mapping table";
        auto tarc = tree.insert_arc(tsrc_ptr->second, ttgt_ptr->second, garc->get_info());
        if (with_map)
          GT::map_arcs(garc, tarc);
      }
 
    if (with_map)
      table.for_each([](const auto &p)
      {
        GT::map_nodes(p.first, p.second);
      });
  }
 
  bool test_negative_cycle(typename GT::Node *s, Path<GT> &cycle)
  {
    cycle = test_negative_cycle(s);
    return not cycle.is_empty();
  }
 
  bool test_negative_cycle(Path<GT> &cycle)
  {
    cycle = test_negative_cycle();
    return not cycle.is_empty();
  }
 
  Distance_Type get_min_path(typename GT::Node *end, Path<GT> &path)
  {
    ah_domain_error_if(not painted_) << "Graph has not been previously painted";
 
    return Aleph::get_min_path<GT, Distance>(s_, end, path);
  }
 
  DynMapTree<Node *, Distance_Type> compute_nodes_weights()
  {
    Node *dummy = create_dummy_node();
 
    Init_Guard guard([this, dummy]()
    {
      uninit<Ni>();
      arcs_.cut();
      if (dummy != nullptr)
        remove_dummy_node<Ni>(dummy);
    });
 
    init_with_indexes(s_);
 
    const auto &n = g_.get_num_nodes();
 
    DynListQueue<typename GT::Node *> q;
 
    Node __sentinel;
    Node *sentinel = &__sentinel;
 
    put_in_queue(q, s_);
    put_in_queue(q, sentinel);
 
    for (size_t i = 0; not q.is_empty(); /* nothing */)
      {
        auto src = get_from_queue(q);
        if (src == sentinel)  // Is the sentinel removed?
          {
            if (i++ > n)
              break;
            put_in_queue(q, sentinel);
          }
        else
          relax_arcs(src, q);
      }
 
    const bool negative_cycle = last_relax_and_prepare_check_negative_cycle();
 
    DynMapTree<Node *, Distance_Type> ret;
 
    // build mapping if there are no negative cycles
    if (not negative_cycle)
      for (auto it = g_.get_node_it(); it.has_curr(); it.next_ne())
        {
          auto p = it.get_curr();
          if (p == dummy)  // Skip the dummy node
            continue;
          ret.insert(p, accum(p));
        }
 
    // Manual cleanup before throwing (guard will handle cleanup on exception)
    uninit<Ni>();
    arcs_.cut();
    remove_dummy_node<Ni>(dummy);
    guard.release();  // Prevent double cleanup
 
    ah_domain_error_if(negative_cycle) << "negative cycles detected";
 
    return ret;
  }
};
 
template <AlephGraph GT,
          ArcDistance<GT> Distance = Dft_Dist<GT>,
          template <class, class> class Ait = Arc_Iterator,
          template <class, class> class NAit = Node_Arc_Iterator,
          ArcFilter<GT> SA = Dft_Show_Arc<GT>>
struct Bellman_Ford_Negative_Cycle
{
  bool operator()(GT &g, Path<GT> &path, Distance &d, SA &sa) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).test_negative_cycle(path);
  }
 
  bool operator()(GT &g, Path<GT> &path, Distance &&d = Distance(), SA &&sa = SA()) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).test_negative_cycle(path);
  }
 
  bool operator()(GT &g, typename GT::Node *s, Path<GT> &path, Distance &d, SA &sa) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).test_negative_cycle(s, path);
  }
 
  bool operator()(GT &g,
                  typename GT::Node *s,
                  Path<GT> &path,
                  Distance &&d = Distance(),
                  SA &&sa = SA()) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).test_negative_cycle(s, path);
  }
 
  Path<GT> operator()(GT &g, typename GT::Node *s, Distance &d, SA &sa) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).search_negative_cycle(s);
  }
 
  Path<GT> operator()(GT &g, typename GT::Node *s, Distance &&d = Distance(), SA &&sa = SA()) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).search_negative_cycle(s);
  }
 
  Path<GT> operator()(GT &g, Distance &d, SA &sa) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).search_negative_cycle();
  }
 
  Path<GT> operator()(GT &g, Distance &&d = Distance(), SA &&sa = SA()) const
  {
    return Bellman_Ford<GT, Distance, Ait, NAit, SA>(g, d, sa).search_negative_cycle();
  }
};
}  // end namespace Aleph
 
#endif  // BELLMAN_FORD_H