Tarjan.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 TARJAN_H
#define TARJAN_H
 
# include <ah-graph-concepts.H>
 
#include <tpl_dynListStack.H>
#include <tpl_dynSetTree.H>
#include <htlist.H>
#include <tpl_graph_utils.H>
#include <tpl_find_path.H>
#include <ah-errors.H>
 
namespace Aleph {
template <AlephGraph GT, template <typename, class> class Itor = Out_Iterator, ArcFilter<GT> SA = Dft_Show_Arc<GT>>
class Tarjan_Connected_Components
{
  SA sa_;
 
  GT *g_ptr_ = nullptr;
 
  DynListStack<typename GT::Node *> stack_;
 
  long df_count_ = 0;
  mutable size_t n_ = 0;  // number of nodes in the graph
 
  Path<GT> *path_ptr_ = nullptr;
 
public:
  Tarjan_Connected_Components(const Tarjan_Connected_Components &) = delete;
 
  Tarjan_Connected_Components &operator = (const Tarjan_Connected_Components &) = delete;
 
  Tarjan_Connected_Components(Tarjan_Connected_Components &&) = default;
 
  Tarjan_Connected_Components &operator = (Tarjan_Connected_Components &&) = default;
 
  Tarjan_Connected_Components(SA __sa = SA()) noexcept : sa_(std::move(__sa))
  { /* empty */
  }
 
private:
  struct Init_Tarjan_Node
  {
    void operator () (const GT &g, typename GT::Node *p) const noexcept
    {
      g.reset_bits(p);
      g.reset_counter(p);  // initialize df
      low<GT>(p) = -1;     // initialize low
    }
  };
 
  static bool is_node_in_stack(typename GT::Node *p) noexcept
  {
    assert(p != nullptr);
    return IS_NODE_VISITED(p, Aleph::Min);
  }
 
  void init_node_and_push_in_stack(typename GT::Node *p)
  {
    assert(not is_node_in_stack(p));
 
    stack_.push(p);
    NODE_BITS(p).set_bit(Aleph::Min, true);
    NODE_BITS(p).set_bit(Aleph::Depth_First, true);
    df<GT>(p) = low<GT>(p) = df_count_++;
  }
 
  typename GT::Node *pop_from_stack()
  {
    auto ret = stack_.pop();
    NODE_BITS(ret).set_bit(Aleph::Min, false);
 
    return ret;
  }
 
  long scc_by_blocks(typename GT::Node *v, DynList<GT> &blk_list)
  {
    init_node_and_push_in_stack(v);
 
    // depth-first traverse all nodes connected to v
    for (Itor<GT, SA> it(v, sa_); it.has_curr(); it.next_ne())
      if (auto w = g_ptr_->get_tgt_node(it.get_curr()); not IS_NODE_VISITED(w, Aleph::Depth_First))
        {
          // map_nodes() called inside scc_by_blocks corrupts low<GT>(w)
          // via NODE_COOKIE when w's SCC is finalized.  Save the result
          // before that corruption can propagate to v.
          const long w_low = scc_by_blocks(w, blk_list);
          low<GT>(v) = std::min(low<GT>(v), w_low);
        }
      else if (is_node_in_stack(w))
        // if on stack ==> v was visited before w
        low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
 
    // Save low[v] before the SCC-finalization loop overwrites NODE_COOKIE
    // (via map_nodes) and NODE_COUNTER (with blk_idx) on every node in v's SCC.
    const long result = low<GT>(v);
 
    if (low<GT>(v) == df<GT>(v))                 // first visited node of the block?
      {                                          // yes ==> pop block nodes from stack
        const size_t blk_idx = blk_list.size();  // capture by value, not reference
        GT &blk = blk_list.append(GT());
 
        while (true)  // remove block from stack until v is removed
          {
            auto p = pop_from_stack();
            auto q = blk.insert_node(p->get_info());
            *q = *p;  // copy node content
            NODE_COOKIE(p) = NODE_COOKIE(q) = nullptr;
            GT::map_nodes(p, q);
            NODE_COUNTER(p) = NODE_COUNTER(q) = static_cast<long>(blk_idx);
            if (p == v)
              break;
          }
      }
    return result;
  }
 
  void scc_by_lists(typename GT::Node *v, DynList<DynList<typename GT::Node *>> &blks)
  {
    init_node_and_push_in_stack(v);
 
    // depth traversal all nodes connected to v
    for (Itor<GT, SA> it(v, sa_); it.has_curr(); it.next_ne())
      if (auto w = g_ptr_->get_tgt_node(it.get_curr()); not IS_NODE_VISITED(w, Aleph::Depth_First))
        {
          scc_by_lists(w, blks);
          low<GT>(v) = std::min(low<GT>(v), low<GT>(w));
        }
      else if (is_node_in_stack(w))
        // if on stack ==> v was visited before w
        low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
 
    if (low<GT>(v) == df<GT>(v))  // first visited node of the block?
      {                           // yes pop out block nodes that are on stack
        auto &l = blks.append(DynList<typename GT::Node *>());
        while (true)  // remove block from stack until reaching v
          {
            auto p = pop_from_stack();
            l.append(p);
            if (p == v)
              break;
          }
      }
  }
 
  void scc_by_len(typename GT::Node *v, DynList<size_t> &sizes)
  {
    init_node_and_push_in_stack(v);
 
    // depth traverse all nodes connected to v
    for (Itor<GT, SA> it(v, sa_); it.has_curr(); it.next_ne())
      if (auto w = g_ptr_->get_tgt_node(it.get_curr()); not IS_NODE_VISITED(w, Aleph::Depth_First))
        {
          scc_by_len(w, sizes);
          low<GT>(v) = std::min(low<GT>(v), low<GT>(w));
        }
      else if (is_node_in_stack(w))
        // if on stack ==> v was visited before w
        low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
 
    if (low<GT>(v) == df<GT>(v))  // first visited node of the block?
      {                           // yes, pop out block nodes that are on the stack
        size_t count = 0;
        while (true)  // remove block from the stack until reaching v
          {
            auto p = pop_from_stack();
            ++count;
 
            if (p == v)
              break;
          }
        sizes.append(count);
      }
  }
 
  void init_tarjan(const GT &g)
  {
    Operate_On_Nodes<GT, Init_Tarjan_Node>()(g);  // initialize bits, df and low
    df_count_ = 0;                                 // visitor counter
    stack_.empty();
    n_ = g.get_num_nodes();
 
    g_ptr_ = &const_cast<GT &>(g);
  }
 
  bool has_cycle(typename GT::Node *v)
  {
    init_node_and_push_in_stack(v);
 
    // depth traverse all nodes connected to v
    for (Itor<GT, SA> it(v, sa_); it.has_curr(); it.next_ne())
      {
        auto w = g_ptr_->get_tgt_node(it.get_curr());
 
        // Check for self-loop (a cycle of length 1)
        if (w == v)
          return true;
 
        if (not IS_NODE_VISITED(w, Aleph::Depth_First))
          {
            if (has_cycle(w))
              return true;
 
            low<GT>(v) = std::min(low<GT>(v), low<GT>(w));
          }
        else if (is_node_in_stack(w))
          // if on stack ==> v was visited before w
          low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
      }
 
    if (low<GT>(v) == df<GT>(v))  // first visited node of block?
      {                           // yes, check if component has two or more nodes
        size_t count = 0;
        while (true)
          {
            ++count;
            if (pop_from_stack() == v)
              break;
          }
 
        return count >= 2;  // if count >= 2 ==> there is a cycle
      }
 
    return false;  // everything was covered without finding a cycle
  }
 
  void build_path(const GT &block, DynMapAvlTree<typename GT::Node *, typename GT::Node *> &table)
  {
    // Search for a cycle in the block
    auto a = block.get_first_arc();
    auto start = block.get_tgt_node(a);
    auto end = block.get_src_node(a);
    assert(start != end);
 
    auto aux_path = Directed_Find_Path<GT, Itor, SA>(block, sa_).dfs(start, end);
    assert(not aux_path.is_empty());  // since it's connected it must be found
 
    // aux_path is about the mapped block. We need to translate it back
    // to the original graph using the mapping table.
    path_ptr_->empty();
    for (typename Path<GT>::Iterator i(aux_path); i.has_curr(); i.next_ne())
      path_ptr_->append_directed(table.find(i.get_current_node_ne()));
 
    path_ptr_->append_directed(path_ptr_->get_first_node());
  }
 
  bool build_cycle(typename GT::Node *v)
  {
    init_node_and_push_in_stack(v);
 
    // depth traverse all nodes connected to v
    for (Itor<GT, SA> it(v, sa_); it.has_curr(); it.next_ne())
      {
        auto w = g_ptr_->get_tgt_node(it.get_curr());
 
        // Check for self-loop (a cycle of length 1)
        if (w == v)
          {
            // Build a simple self-loop path: v -> v
            path_ptr_->empty();
            path_ptr_->init(v);
            path_ptr_->append_directed(v);
            return true;
          }
 
        if (not IS_NODE_VISITED(w, Aleph::Depth_First))
          {
            if (build_cycle(w))
              return true;
 
            low<GT>(v) = std::min(low<GT>(v), low<GT>(w));
          }
        else if (is_node_in_stack(w))
          // if on stack ==> v was visited before w
          low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
      }
 
    if (low<GT>(v) == df<GT>(v))  // first visited node of the block?
      {
        GT blk;  // auxiliary graph
 
        // g node mapping to blk (cookies are busy)
        DynMapAvlTree<typename GT::Node *, typename GT::Node *> table;
 
        // pop nodes from stack and insert them into auxiliary block
        while (true)  // pop the component and insert into blk
          {
            auto p = pop_from_stack();
            auto q = blk.insert_node();
            *q = *p;  // copy node content
            table.insert(q, p);
            table.insert(p, q);
            if (p == v)
              break;
          }
 
        if (blk.get_num_nodes() == 1)
          return false;  // single node without self-loop ==> no cycle
 
        // finish constructing the block with the arcs
        for (typename GT::Node_Iterator j(blk); j.has_curr(); j.next_ne())
          {
            auto bsrc = j.get_curr();
            auto gsrc = table.find(bsrc);
 
            // traverse the arcs of gsrc
            for (Itor<GT, SA> k(gsrc, sa_); k.has_curr(); k.next_ne())
              {
                auto ga = k.get_curr();
                auto gtgt = g_ptr_->get_tgt_node(ga);
                auto ptr = table.search(gtgt);
                if (ptr == nullptr)  // arc of the block?
                  continue;
 
                auto ta = blk.insert_arc(bsrc, ptr->second);
                *ta = *ga;  // copy arc content
              }
          }
 
        build_path(blk, table);
 
        return true;
      }
 
    assert(path_ptr_->is_empty());
 
    return false;
  }
 
  bool is_connected(typename GT::Node *v)
  {
    init_node_and_push_in_stack(v);
 
    // depth-first traverse all nodes connected to v
    for (Itor<GT, SA> it(v, sa_); it.has_curr(); it.next_ne())
      {
        if (auto w = g_ptr_->get_tgt_node(it.get_curr()); not IS_NODE_VISITED(w, Aleph::Depth_First))
          {
            if (not is_connected(w))
              return false;
 
            low<GT>(v) = std::min(low<GT>(v), low<GT>(w));
          }
        else if (is_node_in_stack(w))
          low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
      }
 
    if (low<GT>(v) == df<GT>(v))  // first visited node of the block?
      {                           // pop nodes from stack until v is found
        while (pop_from_stack() != v)
          ;
 
        return stack_.is_empty();
      }
 
    return true;
  }
 
public:
  void connected_components(const GT &g, DynList<GT> &blk_list, DynList<typename GT::Arc *> &arc_list)
  {
    init_tarjan(g);
 
    for (typename GT::Node_Iterator it(g); df_count_ < n_; it.next_ne())
      if (auto v = it.get_curr(); not IS_NODE_VISITED(v, Aleph::Depth_First))
        scc_by_blocks(v, blk_list);
 
    assert(stack_.is_empty());
 
    // traverse each partial subgraph and add its arcs
    for (typename DynList<GT>::Iterator i(blk_list); i.has_curr(); i.next_ne())
      {  // traverse all nodes of the block
        GT &blk = i.get_curr();
        for (typename GT::Node_Iterator j(blk); j.has_curr(); j.next_ne())
          {
            auto bsrc = j.get_curr();
            auto gsrc = mapped_node<GT>(bsrc);
 
            // traverse arcs of gsrc
            for (Itor<GT, SA> k(gsrc, sa_); k.has_curr(); k.next_ne())
              {
                auto ga = k.get_curr();
                auto gtgt = g_ptr_->get_tgt_node(ga);
                if (NODE_COUNTER(gsrc) != NODE_COUNTER(gtgt))
                  {  // inter-block arc ==> add it to arc_list
                    arc_list.append(ga);
                    continue;
                  }
 
                // insert and map the arc in the sub-block
                auto btgt = mapped_node<GT>(gtgt);
                auto ba = blk.insert_arc(bsrc, btgt);
                *ba = *ga;  // copy arc content
                GT::map_arcs(ga, ba);
              }
          }
      }
  }
 
  void connected_components(const GT &g, DynList<DynList<typename GT::Node *>> &blks)
  {
    init_tarjan(g);
    for (typename GT::Node_Iterator it(g); df_count_ < n_; it.next_ne())
      if (auto v = it.get_curr(); not IS_NODE_VISITED(v, Aleph::Depth_First))
        scc_by_lists(v, blks);
  }
 
  [[nodiscard]] DynList<DynList<typename GT::Node *>> connected_components(const GT &g)
  {
    DynList<DynList<typename GT::Node *>> blks;
    connected_components(g, blks);
    return blks;
  }
 
  [[nodiscard]] size_t num_connected_components(const GT &g)
  {
    DynList<size_t> sizes;
    connected_components(g, sizes);
    return sizes.size();
  }
 
  void connected_components(const GT &g, DynList<size_t> &blks)
  {
    init_tarjan(g);
    for (typename GT::Node_Iterator it(g); df_count_ < n_; it.next_ne())
      if (auto v = it.get_curr(); not IS_NODE_VISITED(v, Aleph::Depth_First))
        scc_by_len(v, blks);
  }
 
  void operator () (const GT &g, DynList<GT> &blk_list, DynList<typename GT::Arc *> &arc_list)
  {
    connected_components(g, blk_list, arc_list);
  }
 
  void operator () (const GT &g, DynList<DynList<typename GT::Node *>> &blks)
  {
    connected_components(g, blks);
  }
 
  DynList<DynList<typename GT::Node *>> operator () (const GT &g)
  {
    return connected_components(g);
  }
 
  void operator () (const GT &g, DynDlist<GT> &blk_list, DynDlist<typename GT::Arc *> &arc_list)
  {
    DynList<GT> blist;
    DynList<typename GT::Arc *> alist;
    connected_components(g, blist, alist);
 
    for (typename DynList<GT>::Iterator it(blist); it.has_curr(); it.next_ne())
      {
        GT &curr = it.get_curr();
        GT &block = blk_list.append(GT());
        curr.swap(block);
      }
 
    for (typename DynList<typename GT::Arc *>::Iterator it(alist); it.has_curr(); it.next_ne())
      arc_list.append(it.get_curr());
  }
 
  void operator () (const GT &g, DynDlist<DynDlist<typename GT::Node *>> &blks)
  {
    DynList<DynList<typename GT::Node *>> b;
    connected_components(g, b);
 
    for (typename DynList<DynList<typename GT::Node *>>::Iterator it(b); it.has_curr(); it.next_ne())
      {
        auto &tgt_list = blks.append(DynDlist<typename GT::Node *>());
 
        auto &blk = it.get_curr();
        while (not blk.is_empty())
          tgt_list.append(blk.remove_first());
      }
  }
 
  [[nodiscard]] bool has_cycle(const GT &g)
  {
    init_tarjan(g);
    for (typename GT::Node_Iterator it(g); df_count_ < n_; it.next_ne())
      if (auto v = it.get_curr(); not IS_NODE_VISITED(v, Aleph::Depth_First))
        if (has_cycle(v))
          return true;
 
    return false;
  }
 
  [[nodiscard]] bool is_dag(const GT &g)
  {
    return not has_cycle(g);
  }
 
  bool compute_cycle(const GT &g, Path<GT> &path)
  {
    init_tarjan(g);
    path_ptr_ = &path;
    path_ptr_->set_graph(g);
 
    for (typename GT::Node_Iterator it(g); df_count_ < n_; it.next_ne())
      if (auto v = it.get_curr(); not IS_NODE_VISITED(v, Aleph::Depth_First))  // p visited?
        if (build_cycle(v))
          return true;
 
    path.empty();
    return false;
  }
 
  [[nodiscard]] bool compute_cycle(const GT &g, typename GT::Node *src, Path<GT> &path)
  {
    ah_domain_error_if(src == nullptr) << "compute_cycle: source node cannot be null";
 
    init_tarjan(g);
    path_ptr_ = &path;
    path_ptr_->set_graph(g);
    return build_cycle(src);
  }
 
  [[nodiscard]] bool test_connectivity(const GT &g)
  {
    init_tarjan(g);
 
    // In a strongly connected graph, a single DFS from any node should reach
    // all nodes. If we have to start from a second unvisited node, it means
    // the graph has multiple disconnected components.
    bool started = false;
    for (typename GT::Node_Iterator it(g); df_count_ < n_; it.next_ne())
      if (auto v = it.get_curr(); not IS_NODE_VISITED(v, Aleph::Depth_First))
        {
          if (started)  // Second DFS root → not strongly connected
            return false;
          started = true;
          if (not is_connected(v))
            return false;
        }
 
    assert(stack_.is_empty());
 
    return true;
  }
 
 
  SA &get_filter() noexcept
  {
    return sa_;
  }
 
  const SA &get_filter() const noexcept
  {
    return sa_;
  }
 
  [[nodiscard]] bool has_computation() const noexcept
  {
    return g_ptr_ != nullptr;
  }
 
  [[nodiscard]] GT *get_graph() const noexcept
  {
    return g_ptr_;
  }
 
};
 
template <AlephGraph GT, template <typename, class> class Itor = Out_Iterator, ArcFilter<GT> SA = Dft_Show_Arc<GT>>
class Compute_Cycle_In_Digraph
{
  SA sa_;
 
public:
  Compute_Cycle_In_Digraph(SA __sa = SA()) : sa_(std::move(__sa))
  { /* empty */
  }
 
  [[nodiscard]] bool operator () (const GT &g, Path<GT> &path) const
  {
    Tarjan_Connected_Components<GT, Itor, SA> tarjan(sa_);
 
    return tarjan.compute_cycle(g, path);
  }
 
  [[nodiscard]] Path<GT> operator () (const GT &g) const
  {
    Path<GT> ret(g);
    Tarjan_Connected_Components<GT, Itor, SA>(sa_).compute_cycle(g, ret);
    return ret;
  }
 
  [[nodiscard]] Path<GT> operator () (const GT &g, typename GT::Node *src) const
  {
    Path<GT> ret(g);
    (void) Tarjan_Connected_Components<GT, Itor, SA>(sa_).compute_cycle(g, src, ret);
    return ret;
  }
};
}  // end namespace Aleph
 
#endif  // TARJAN_H