tpl_link_cut_tree_with_edges.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 TPL_LINK_CUT_TREE_WITH_EDGES_H
# define TPL_LINK_CUT_TREE_WITH_EDGES_H
 
# include <functional>
# include <tpl_dynSetHash.H>
# include <tpl_link_cut_tree.H>
 
namespace Aleph
{
  template <typename VT = int,
            typename ET = int,
            class EdgeMonoid = DefaultMonoid<ET>,
            class LazyTag = NoLazyTag<ET>>
    requires LCTMonoid<EdgeMonoid, ET> and LCTLazyTag<LazyTag, ET>
  class Gen_Link_Cut_Tree_WithEdges
  {
    using InternalLCT = Gen_Link_Cut_Tree<ET, EdgeMonoid, LazyTag>;
 
  public:
    using Node = typename InternalLCT::Node;
 
  private:
    struct EdgeKey
    {
      Node *a;
      Node *b;
 
      [[nodiscard]] bool operator==(const EdgeKey &) const noexcept = default;
    };
 
    struct EdgeKeyHash
    {
      [[nodiscard]] size_t operator()(const EdgeKey & key) const noexcept
      {
        const size_t ha = std::hash<Node *>{}(key.a);
        const size_t hb = std::hash<Node *>{}(key.b);
        return ha ^ (hb + 0x9e3779b97f4a7c15ULL + (ha << 6) + (ha >> 2));
      }
    };
 
    struct EdgeKeyEq
    {
      [[nodiscard]] bool operator()(const EdgeKey & lhs,
                                    const EdgeKey & rhs) const noexcept
      {
        return lhs == rhs;
      }
    };
 
    struct NodePtrEq
    {
      [[nodiscard]] bool operator()(Node *lhs, Node *rhs) const noexcept
      {
        return lhs == rhs;
      }
    };
 
    [[nodiscard]] static size_t edge_key_hash(const EdgeKey & key) noexcept
    {
      return EdgeKeyHash{}(key);
    }
 
    [[nodiscard]] static size_t node_ptr_hash(Node *const & nd) noexcept
    {
      return std::hash<Node *>{}(nd);
    }
 
    struct EdgeRec
    {
      Node *u;
      Node *v;
      Node *edge_node;
    };
 
    InternalLCT lct_;
    Array<EdgeRec> edge_recs_;
    // Use the project hash map here so the edge index stays on Aleph containers.
    DynMapHash<EdgeKey, size_t, EdgeKeyEq> edge_idx_{
          Primes::DefaultPrime, edge_key_hash, EdgeKeyEq()
        };
    DynMapHash<Node *, VT, NodePtrEq> vertex_vals_{
          Primes::DefaultPrime, node_ptr_hash, NodePtrEq()
        };
    size_t n_vertices_ = 0;
    size_t n_components_ = 0;
 
    [[nodiscard]] static EdgeKey make_edge_key(Node *u, Node *v) noexcept
    {
      return std::less<Node *>{}(u, v) ? EdgeKey{u, v} : EdgeKey{v, u};
    }
 
    size_t find_edge_idx(Node *u, Node *v) const noexcept
    {
      auto *it = edge_idx_.search(make_edge_key(u, v));
      return it == nullptr ? edge_recs_.size() : it->second;
    }
 
    void remove_edge_at(size_t idx)
    {
      const auto removed = edge_recs_(idx);
      edge_idx_.remove(make_edge_key(removed.u, removed.v));
 
      if (idx + 1 < edge_recs_.size())
        {
          edge_recs_(idx) = edge_recs_(edge_recs_.size() - 1);
          const auto & moved = edge_recs_(idx);
          edge_idx_.find(make_edge_key(moved.u, moved.v)) = idx;
        }
      edge_recs_.remove_last();
    }
 
    [[nodiscard]] const VT &lookup_vertex_val(Node *nd) const
    {
      ah_invalid_argument_if(nd == nullptr) << "null handle";
      auto *entry = vertex_vals_.search(nd);
      ah_domain_error_if(entry == nullptr) << "vertex does not exist";
      return entry->second;
    }
 
    void require_vertex(Node * x) const
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      ah_domain_error_if(vertex_vals_.search(x) == nullptr)
        << "handle does not belong to this tree";
    }
 
  public:
    Gen_Link_Cut_Tree_WithEdges() = default;
 
    Gen_Link_Cut_Tree_WithEdges(const Gen_Link_Cut_Tree_WithEdges &) = delete;
 
    Gen_Link_Cut_Tree_WithEdges &operator=(const Gen_Link_Cut_Tree_WithEdges &) = delete;
 
    Gen_Link_Cut_Tree_WithEdges(Gen_Link_Cut_Tree_WithEdges &&) = delete;
 
    Gen_Link_Cut_Tree_WithEdges &operator=(Gen_Link_Cut_Tree_WithEdges &&) = delete;
 
    Node * make_vertex(const VT & val = VT{})
    {
      auto *nd = lct_.make_vertex(EdgeMonoid::identity());
      try
        {
          vertex_vals_.insert(nd, val);
        }
      catch (...)
        {
          lct_.destroy_vertex(nd);
          throw;
        }
      ++n_vertices_;
      ++n_components_;
      return nd;
    }
 
    [[nodiscard]] size_t size() const noexcept { return n_vertices_; }
 
    [[nodiscard]] size_t num_components() const noexcept
    {
      return n_components_;
    }
 
    [[nodiscard]] size_t num_edges() const noexcept
    {
      return edge_recs_.size();
    }
 
    [[nodiscard]] const VT &get_vertex_val(Node *x) const
    {
      return lookup_vertex_val(x);
    }
 
    void set_vertex_val(Node *x, const VT & val)
    {
      require_vertex(x);
      vertex_vals_.find(x) = val;
    }
 
    [[nodiscard]] bool connected(Node *u, Node *v)
    {
      require_vertex(u);
      require_vertex(v);
      return lct_.connected(u, v);
    }
 
    void link(Node *u, Node *v, const ET & weight)
    {
      require_vertex(u);
      require_vertex(v);
      ah_invalid_argument_if(u == v) << "self-loop";
      ah_domain_error_if(lct_.connected(u, v)) << "already connected";
 
      const size_t idx = edge_recs_.size();
      const auto key = make_edge_key(u, v);
 
      edge_recs_.reserve(idx + 1);
      edge_recs_.append({u, v, nullptr});
 
      Node *e = nullptr;
      bool linked_u = false;
      bool linked_v = false;
 
      try
        {
          auto *entry = edge_idx_.insert(key, idx);
          ah_domain_error_if(entry == nullptr) << "edge already exists";
 
          e = lct_.make_vertex(weight);
          lct_.link(u, e);
          linked_u = true;
          lct_.link(e, v);
          linked_v = true;
          edge_recs_(idx).edge_node = e;
        }
      catch (...)
        {
          if (linked_v)
            lct_.cut(e, v);
          if (linked_u)
            lct_.cut(u, e);
          if (e != nullptr)
            lct_.destroy_vertex(e);
          edge_recs_.remove_last();
          if (edge_idx_.contains(key))
            edge_idx_.remove(key);
          throw;
        }
 
      --n_components_;
    }
 
    void cut(Node *u, Node *v)
    {
      require_vertex(u);
      require_vertex(v);
      size_t idx = find_edge_idx(u, v);
      ah_domain_error_if(idx == edge_recs_.size()) << "edge does not exist";
 
      Node *e = edge_recs_(idx).edge_node;
      lct_.cut(u, e);
      lct_.cut(e, v);
      remove_edge_at(idx);
      lct_.destroy_vertex(e);
      ++n_components_;
    }
 
    [[nodiscard]] ET path_query(Node *u, Node *v)
    {
      require_vertex(u);
      require_vertex(v);
      return lct_.path_query(u, v);
    }
 
    void make_root(Node *x)
    {
      require_vertex(x);
      lct_.make_root(x);
    }
 
    [[nodiscard]] Node * find_root(Node *x)
    {
      require_vertex(x);
      return lct_.find_root(x);
    }
 
    [[nodiscard]] size_t path_size(Node *u, Node *v)
    {
      require_vertex(u);
      require_vertex(v);
      const size_t internal_size = lct_.path_size(u, v);
      return (internal_size + 1) / 2;
    }
 
    void set_edge_val(Node *u, Node *v, const ET & new_weight)
    {
      require_vertex(u);
      require_vertex(v);
      size_t idx = find_edge_idx(u, v);
      ah_domain_error_if(idx == edge_recs_.size()) << "edge does not exist";
 
      lct_.set_val(edge_recs_(idx).edge_node, new_weight);
    }
 
    [[nodiscard]] const ET &get_edge_val(Node *u, Node *v)
    {
      require_vertex(u);
      require_vertex(v);
      size_t idx = find_edge_idx(u, v);
      ah_domain_error_if(idx == edge_recs_.size()) << "edge does not exist";
 
      return lct_.get_val(edge_recs_(idx).edge_node);
    }
 
    // ---- snapshot export ----
 
    struct ExportData
    {
      Node *lct_node; 
      VT vertex_value; 
      ET parent_edge; 
    };
 
    [[nodiscard]] Tree_Node<ExportData> * export_to_tree_node(Node *root)
    {
      require_vertex(root);
      make_root(root);
 
      using TN = Tree_Node<ExportData>;
 
      // Build adjacency from edge records (only edges in root's component)
      // adj[i] = list of (neighbor_vertex_index, edge_weight)
      struct AdjEntry
      {
        size_t neighbor;
        ET weight;
      };
 
      // Collect vertices in root's component; use a hash map for O(1) lookup
      Array<Node *> verts;
      DynMapHash<Node *, size_t, NodePtrEq> node_to_idx(
          Primes::DefaultPrime, node_ptr_hash, NodePtrEq());
      auto add_vert = [&](Node * nd) {
        if (node_to_idx.search(nd) == nullptr)
          {
            node_to_idx.insert(nd, verts.size());
            verts.append(nd);
          }
      };
      add_vert(root);
      for (size_t i = 0; i < edge_recs_.size(); ++i)
        if (const auto & er = edge_recs_(i); lct_.connected(er.u, root))
          {
            add_vert(er.u);
            add_vert(er.v);
          }
 
      // Build adjacency lists
      size_t nv = verts.size();
      Array<Array<AdjEntry>> adj;
      for (size_t i = 0; i < nv; ++i)
        adj.append(Array<AdjEntry>());
 
      for (size_t i = 0; i < edge_recs_.size(); ++i)
        {
          const auto & er = edge_recs_(i);
          auto * up = node_to_idx.search(er.u);
          auto * vp = node_to_idx.search(er.v);
          if (up != nullptr and vp != nullptr)
            {
              ET w = lct_.get_val(er.edge_node);
              adj(up->second).append({vp->second, w});
              adj(vp->second).append({up->second, w});
            }
        }
 
      // BFS from root to build Tree_Node tree
      Array<TN *> tn(nv);
      tn.putn(nv);
      for (size_t i = 0; i < nv; ++i)
        tn(i) = nullptr;
 
      size_t root_idx = node_to_idx.search(root)->second;
 
      // RAII guard: calls destroy_tree on the root TN if an exception escapes.
      // Each new TN is linked to its parent immediately after allocation, so
      // destroy_tree(root) reaches all allocated nodes on any exception path.
      struct ScopedTreeOwner
      {
        TN * root = nullptr;
        ~ScopedTreeOwner() noexcept { if (root != nullptr) destroy_tree(root); }
        TN * release() noexcept { TN * r = root; root = nullptr; return r; }
      } guard;
 
      guard.root = new TN({root, lookup_vertex_val(root), EdgeMonoid::identity()});
      tn(root_idx) = guard.root;
 
      // BFS queue (simple array-based)
      Array<size_t> queue;
      queue.append(root_idx);
      size_t qfront = 0;
 
      while (qfront < queue.size())
        {
          size_t ci = queue(qfront++);
          for (size_t j = 0; j < adj(ci).size(); ++j)
            if (auto [ni, w] = adj(ci)(j); tn(ni) == nullptr)
              {
                tn(ni) = new TN({verts(ni), lookup_vertex_val(verts(ni)), w});
                tn(ci)->insert_rightmost_child(tn(ni));
                queue.append(ni);
              }
        }
 
      return guard.release();
    }
  };
 
  template <typename EdgeT = int, class Monoid = DefaultMonoid<EdgeT>>
  using Link_Cut_Tree_WithEdges = Gen_Link_Cut_Tree_WithEdges<int, EdgeT, Monoid>;
} // namespace Aleph
 
# endif /* TPL_LINK_CUT_TREE_WITH_EDGES_H */