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 <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 <class GT,
            template <typename, class> class Itor = Out_Iterator,
            class 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
      }
    };
 
    bool is_node_in_stack(typename GT::Node *p) const 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;
    }
 
      void 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))
            {
              scc_by_blocks(w, blk_list);
              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 block nodes from stack
            const auto & blk_idx = blk_list.size();
            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) = blk_idx;
              if (p == v)
                break;
            }
        }
    }
 
      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 <class GT,
            template <typename, class> class Itor = Out_Iterator,
            class 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