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 <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 <class GT,
            class Distance = Dft_Dist<GT>,
            template <class, class> class Ait = Arc_Iterator,
            template <class, class> class NAit = Out_Iterator,
            class 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
          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
          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;
        }
 
      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())
            {
              auto arc = ait.get_curr();
              if (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
      // (or num_painted_arcs < num_painted_nodes for disconnected graphs)
      return num_painted_arcs < num_painted_nodes or
             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)
                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));
      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);
        }
 
      const bool negative_cycle = last_relax_and_prepare_check_negative_cycle();
      if (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);
        }
 
      const bool negative_cycle = last_relax_and_prepare_check_negative_cycle();
      if (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 <class GT,
            class Distance = Dft_Dist<GT>,
            template <class, class> class Ait = Arc_Iterator,
            template <class, class> class NAit = Node_Arc_Iterator,
            class 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