Zero_One_BFS.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 ZERO_ONE_BFS_H
# define ZERO_ONE_BFS_H
 
# include <limits>
# include <type_traits>
# include <tpl_dynDlist.H>
# include <tpl_graph_utils.H>
# include <ah-errors.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>>
class Zero_One_BFS
{
public:
  using Distance_Type = typename Distance::Distance_Type;
  using Node = typename GT::Node;
  using Arc = typename GT::Arc;
 
private:
  SA sa;
  Distance distance;
  bool painted = false;
  GT * ptr_g = nullptr;
  Node * s = nullptr;
 
  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) {}
  };
 
  struct Painted_Info
  {
    Node * parent;
    Distance_Type dist;
  };
 
  DynList<std::pair<Node *, Node_Info *>> owned_node_infos;
  DynList<std::pair<Node *, Painted_Info *>> owned_painted_infos;
 
#define ZOB_INFO(p)   (static_cast<Node_Info *>(NODE_COOKIE(p)))
#define ZOB_PNTD(p)   (static_cast<Painted_Info *>(NODE_COOKIE(p)))
#define ZOB_DIST(p)   (ZOB_INFO(p)->dist)
#define ZOB_PARENT(p) (ZOB_INFO(p)->parent)
#define ZOB_PARENT_ARC(p) (ZOB_INFO(p)->parent_arc)
 
  void release_owned_node_infos() noexcept
  {
    for (auto it = owned_node_infos.get_it(); it.has_curr(); it.next())
      {
        auto item = it.get_curr();
        auto p = item.first;
        auto info = item.second;
        if (info != nullptr)
          delete info;
        if (NODE_COOKIE(p) == info)
          NODE_COOKIE(p) = nullptr;
      }
    owned_node_infos.empty();
  }
 
  void release_owned_painted_infos() noexcept
  {
    for (auto it = owned_painted_infos.get_it(); it.has_curr(); it.next())
      {
        auto item = it.get_curr();
        auto p = item.first;
        auto info = item.second;
        if (info != nullptr)
          delete info;
        if (NODE_COOKIE(p) == info)
          NODE_COOKIE(p) = nullptr;
      }
    owned_painted_infos.empty();
  }
 
  void reset_state_after_failure() noexcept
  {
    painted = false;
    ptr_g = nullptr;
    s = nullptr;
  }
 
  class ZOB_Init_Guard
  {
    Zero_One_BFS * owner = nullptr;
    const GT * g = nullptr;
    bool committed = false;
 
  public:
    ZOB_Init_Guard(Zero_One_BFS & __owner, const GT & __g) noexcept
      : owner(&__owner), g(&__g)
    {
      // empty
    }
 
    ZOB_Init_Guard(const ZOB_Init_Guard &) = delete;
    ZOB_Init_Guard & operator = (const ZOB_Init_Guard &) = delete;
    ZOB_Init_Guard(ZOB_Init_Guard &&) = delete;
    ZOB_Init_Guard & operator = (ZOB_Init_Guard &&) = delete;
 
    void commit() noexcept { committed = true; }
 
    ~ZOB_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);
    release_owned_node_infos();
    release_owned_painted_infos();
    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())
          {
            auto p = it.get_curr();
            auto info = new Node_Info;
            NODE_COOKIE(p) = info;
            try
              {
                owned_node_infos.append({p, info});
              }
            catch (...)
              {
                delete info;
                NODE_COOKIE(p) = nullptr;
                throw;
              }
          }
      }
    catch (...)
      {
        release_owned_node_infos();
        release_owned_painted_infos();
        throw;
      }
  }
 
  void uninit_paint()
  {
    // Two-phase conversion to be exception-safe:
    // 1. Allocate all Painted_Info objects
    // 2. Atomically swap and delete old Node_Info
    DynList<std::pair<Node *, Painted_Info *>> pending;
    try
      {
        for (typename GT::Node_Iterator it(*ptr_g); it.has_curr(); it.next())
          {
            auto p = it.get_curr();
            auto info = ZOB_INFO(p);
            pending.append({p, new Painted_Info{info->parent, info->dist}});
          }
      }
    catch (...)
      {
        for (auto it = pending.get_it(); it.has_curr(); it.next())
          delete it.get_curr().second;
        throw;
      }
 
    // Phase 2: Apply changes
    release_owned_node_infos();
    for (auto it = pending.get_it(); it.has_curr(); it.next())
      {
        auto item = it.get_curr();
        auto p = item.first;
        auto pinfo = item.second;
        NODE_COOKIE(p) = pinfo;
      }
    owned_painted_infos.swap(pending);
  }
 
  void uninit_discard()
  {
    if (ptr_g == nullptr)
      return;
 
    release_owned_node_infos();
    release_owned_painted_infos();
 
    for (typename GT::Node_Iterator it(*ptr_g); it.has_curr(); it.next())
      {
        auto p = it.get_curr();
        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);
  }
 
  void run_bfs(const GT & g, Node * start, Node * end = nullptr)
  {
    ZOB_DIST(start) = 0;
    NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
 
    DynDlist<Node *> deque;
    deque.append(start);
 
    while (not deque.is_empty())
      {
        auto curr = deque.remove_first();
        auto curr_dist = ZOB_DIST(curr);
 
        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);
 
            auto w = distance(arc);
            ah_domain_error_if(w != Distance_Type(0) and w != Distance_Type(1))
              << "Zero_One_BFS: arc weight must be 0 or 1, got " << w;
 
            auto new_dist = curr_dist + w;
 
            if (new_dist < ZOB_DIST(tgt))
              {
                auto prev_parent_arc = ZOB_PARENT_ARC(tgt);
                if (prev_parent_arc != nullptr)
                  ARC_BITS(prev_parent_arc).set_bit(Aleph::Spanning_Tree, false);
 
                ZOB_DIST(tgt) = new_dist;
                ZOB_PARENT(tgt) = curr;
                ZOB_PARENT_ARC(tgt) = arc;
                NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
 
                // Mark the selected parent arc in the spanning tree
                ARC_BITS(arc).set_bit(Aleph::Spanning_Tree, true);
 
                if (w == Distance_Type(0))
                  deque.insert(tgt);   // push front
                else
                  deque.append(tgt);   // push back
              }
          }
      }
  }
 
public:
  Zero_One_BFS(Distance dist = Distance(), SA __sa = SA())
    : sa(__sa), distance(dist)
  {
    // empty
  }
 
  ~Zero_One_BFS() noexcept
  {
    uninit_discard();
    reset_state_after_failure();
  }
 
  [[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";
 
    if (ptr_g != nullptr)
      uninit_discard();
 
    painted = false;
    s = nullptr;
 
    init(g);
    ZOB_Init_Guard guard(*this, g);
    s = start;
    run_bfs(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";
 
    // O(1) access thanks to Painted_Info
    auto dist_val = ZOB_PNTD(node)->dist;
    if (dist_val != Inf)
      return dist_val;
 
    // Fallback: Compute distance by walking the path
    Distance_Type total = 0;
    for (auto curr = node; curr != s;)
      {
        auto pinfo = ZOB_PNTD(curr);
        auto parent = pinfo->parent;
        if (parent == nullptr)
          break;
 
        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);
                break;
              }
          }
        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";
    ah_domain_error_if(end == nullptr) << "end pointer is null";
 
    path.empty();
    if (end == s)
      {
        path.set_graph(*ptr_g, s);
        return 0;
      }
 
    if (not IS_NODE_VISITED(end, Aleph::Spanning_Tree))
      return Inf;
 
    Distance_Type total = 0;
    path.set_graph(*ptr_g, s);
    DynList<Arc *> arcs;
    for (auto curr = end; curr != s;)
      {
        auto parent = ZOB_PNTD(curr)->parent;
        if (parent == nullptr)
          return Inf;
 
        bool found = false;
        for (Itor<GT, SA> it(parent, sa); it.has_curr(); it.next())
          {
            auto arc = it.get_current_arc();
            if (ptr_g->get_connected_node(arc, parent) == curr and
                IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
              {
                arcs.insert(arc);
                total += distance(arc);
                curr = parent;
                found = true;
                break;
              }
          }
        if (not found)
          return Inf;
      }
 
    for (auto it = arcs.get_it(); it.has_curr(); it.next())
      path.append(it.get_curr());
 
    return total;
  }
 
  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";
 
    if (ptr_g != nullptr)
      uninit_discard();
 
    path.empty();
 
    painted = false;
    s = nullptr;
 
    init(g);
    ZOB_Init_Guard guard(*this, g);
    s = start;
    run_bfs(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 ZOB_INFO
#undef ZOB_PNTD
#undef ZOB_DIST
#undef ZOB_PARENT
#undef ZOB_PARENT_ARC
};
 
} // end namespace Aleph
 
# endif // ZERO_ONE_BFS_H