Tarjan.H

# 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>

namespace Aleph {


     template <class GT, class SA = Dft_Show_Arc<GT>> 
class Tarjan_Connected_Components
{
  SA & sa;

  DynListStack<typename GT::Node*> stack;

  long df_count;
  mutable size_t n; // número de nodos del grafo

      // lista de listas; cada lista almacena los nodos de los bloques
  DynList<DynList<typename GT::Node*>> * list_list_ptr; 

  DynList <GT> * block_list_ptr; // lista de bloques fuertemente
                                 // conexos

  DynList<size_t> * list_len_ptr; // lista de tamaños de componentes

  Path<GT> * path_ptr;

public:

  Tarjan_Connected_Components(SA && __sa = SA()) : sa(__sa) { /* empty */ }

  Tarjan_Connected_Components(SA & __sa) : sa(__sa) { /* empty */ }

private:

  struct Init_Tarjan_Node
  {
    void operator () (GT & g, typename GT::Node * p)
    {
      g.reset_bits(p);
      g.reset_counter(p); // inicializa df
      low <GT> (p) = -1;  // inicializa low
    }
  };
 
  bool is_node_in_stack(typename GT::Node * p)
  {
    return IS_NODE_VISITED(p, Aleph::Min);
  }

  void init_node_and_push_in_stack(typename GT::Node * p)
  {
    I(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()
  {
    typename GT::Node * ret = stack.pop();
    NODE_BITS(ret).set_bit(Aleph::Min, false);

    return ret;
  }

  void scc_by_blocks(typename GT::Node * v)
  {
    init_node_and_push_in_stack(v);

        // recorrer en profundidad todos los nodos conectados a v
    for (Out_Iterator<GT, SA> it(v, sa); it.has_curr(); it.next())
    {
      typename GT::Node * w = it.get_tgt_node();
      if (not IS_NODE_VISITED(w, Aleph::Depth_First))
        {
          scc_by_blocks(w);
          low <GT> (v) = std::min(low <GT> (v), low <GT> (w));
        }
      else if (is_node_in_stack(w))
        // si está en pila ==> v fue visitado antes que p
        low <GT> (v) = std::min(low <GT> (v), df <GT> (w));
    }

    if (low <GT> (v) == df <GT> (v)) // ¿primer nodo visitado del bloque?
      {     // sí ==> saque los nodos del bloque que están en pila
        const size_t & blk_idx = block_list_ptr->size();
        GT & blk = block_list_ptr->append(GT());

        while (true) // sacar el bloque de la pila hasta sacar a v
          {
            typename GT::Node * p = pop_from_stack();
            typename GT::Node * q = blk.insert_node(p->get_info());
            NODE_COOKIE(p) = NODE_COOKIE(q) = NULL;
            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)
  {
    init_node_and_push_in_stack(v);

        // recorrer en profundidad todos los nodos conectados a v
    for (Out_Iterator<GT, SA> it(v, sa); it.has_curr(); it.next())
    { 
      typename GT::Node * w = it.get_tgt_node();
      if (not IS_NODE_VISITED(w, Aleph::Depth_First))
        {
          scc_by_lists(w);
          low <GT> (v) = std::min(low <GT> (v), low <GT> (w));
        }
      else if (is_node_in_stack(w))
        // si está en pila ==> v fue visitado antes que p
        low <GT> (v) = std::min(low <GT> (v), df <GT> (w));
    }

    if (low<GT>(v) == df<GT>(v)) // ¿primer nodo visitado del bloque?
      {     // sí ==> saque los nodos del bloque que están en pila
        DynList<typename GT::Node*> & l = 
          list_list_ptr->append(DynList<typename GT::Node*>());

        while (true) // sacar bloque de pila hasta llegar a v
          {
            typename GT::Node * p = pop_from_stack();
            l.append(p);

            if (p == v)
              break;
          }
      }
  }

  void scc_by_len(typename GT::Node * v)
  {
    init_node_and_push_in_stack(v);

        // recorrer en profundidad todos los nodos conectados a v
    for (Out_Iterator<GT, SA> it(v, sa); it.has_curr(); it.next())
    { 
      typename GT::Node * w = it.get_tgt_node();
      if (not IS_NODE_VISITED(w, Aleph::Depth_First))
        {
          scc_by_len(w);
          low <GT> (v) = std::min(low <GT> (v), low <GT> (w));
        }
      else if (is_node_in_stack(w))
        // si está en pila ==> v fue visitado antes que p
        low <GT> (v) = std::min(low <GT> (v), df <GT> (w));
    }

    if (low<GT>(v) == df<GT>(v)) // ¿primer nodo visitado del bloque?
      {     // sí ==> saque los nodos del bloque que están en pila
        size_t count = 0;

        while (true) // sacar bloque de pila hasta llegar a v
          {
            typename GT::Node * p = pop_from_stack();
            ++count;

            if (p == v)
              break;
          }
        list_len_ptr->append(count);
      }
  }

  void init_tarjan(GT & g)
  {
    if (not g.is_digraph())
      throw std::domain_error("g is not a digraph");

    Operate_On_Nodes <GT, Init_Tarjan_Node> () (g); // inicia bits, df y low

    df_count = 0; // contador de visitas

    stack.empty();

    n = g.get_num_nodes();
  }

      // retorna true si se encuentra un ciclo desde v
  bool has_cycle(typename GT::Node * v)
  {
    init_node_and_push_in_stack(v);

      // recorrer en profundidad todos los nodos conectados a v
    for (Out_Iterator <GT, SA> it(v, sa); it.has_curr(); it.next())
    {
      typename GT::Node * w = it.get_tgt_node();
      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))
            // si está en pila ==> v fue visitado antes que p
        low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
    }

    if (low<GT>(v) == df<GT>(v)) // ¿primer nodo visitado de bloque?
      {     // sí ==> verifique si tiene dos o más nodos
        int i = 0;
        for (; i < 2; ++i) // sacar bloque de la pila hasta sacar a v
          if (pop_from_stack() == v)
            break;
      
        return i >= 2; // si i>= 2 ==> hay un ciclo
      }  

    return false; // se recorrió todo v sin encontrar ciclo
  }

        // construye en el miembro path un ciclo sobre block. Se asume que
        // block es un componente mapeado del grafo.
      void 
  build_path(GT &                                                    block, 
             DynMapAvlTree<typename GT::Node*, typename GT::Node*> & table)
  {
          // buscar ciclo en blk.
    typename GT::Arc * a = block.get_first_arc();
    Path<GT> aux_path(block);

    Find_Path_Depth_First<GT>() (block, block.get_tgt_node(a), 
                                 block.get_src_node(a), aux_path);

    path_ptr->clear_path();
    for (typename Path<GT>::Iterator i(aux_path); i.has_curr(); i.next())
      path_ptr->append(table.find(i.get_current_node()));

    path_ptr->append(table.find(block.get_tgt_node(a)));
  }

      // retorna true si encuentra un ciclo, en cuyo caso lo pone en
      // path. De lo contrario, retorna false y path queda intacto
  bool build_cycle(typename GT::Node * v)
  {
    init_node_and_push_in_stack(v);

    // recorrer en profundidad todos los nodos conectados a v
    for (Out_Iterator <GT, SA> it(v, sa); it.has_curr(); it.next())
      {
        typename GT::Node * w = it.get_tgt_node();
        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))
          // si está en pila ==> v fue visitado antes que p
          low<GT>(v) = std::min(low<GT>(v), df<GT>(w));
      }

    if (low<GT>(v) == df<GT>(v)) // ¿primer nodo visitado del bloque?
      {
        GT blk; // grafo auxiliar

        // mapeo de nodos de g con blk (los cookies están ocupados)
        DynMapAvlTree<typename GT::Node*, typename GT::Node*> table; 
        
            // saque nodos de pila e insertelos en bloque auxiliar
        while (true) // saca el componente y lo inserta en blk
          {
            typename GT::Node * p = pop_from_stack();
            typename GT::Node * q = blk.insert_node(p->get_info());
            table.insert(q, p);
            table.insert(p, q);
            if (p == v)
              break;
          }

        if (blk.get_num_nodes() == 1) 
          return false; // si blk sólo tiene un nodo no hay ciclo

            // terminanos de construir el bloque con los arcos
        for (typename GT::Node_Iterator j(blk); j.has_curr(); j.next())
          {
            typename GT::Node * bsrc = j.get_curr(); 
            typename GT::Node * gsrc = table.find(bsrc); 

                // recorrer los arcos de gsrc
            for (Out_Iterator <GT, SA> k(gsrc, sa); k.has_curr(); k.next())
              {
                typename GT::Node * gtgt      = k.get_tgt_node();
                typename GT::Node ** btgt_ptr = table.test(gtgt);
                if (btgt_ptr == NULL) // ¿arco del bloque?
                  continue;

                typename GT::Arc  * ga = k.get_current_arc();
                blk.insert_arc(bsrc, *btgt_ptr, ga->get_info());
              }
          }

        build_path(blk, table);

        return true;
      }  

    return false;
  }

  bool is_connected(typename GT::Node * v)
  {
    init_node_and_push_in_stack(v);

        // recorrer en profundidad todos los nodos conectados a v
    for (Out_Iterator <GT, SA> it(v, sa); it.has_curr(); it.next())
      {
        typename GT::Node * w = it.get_tgt_node();
        if (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)) // ¿primer nodo visitado de bloque?
      {     // saque nodos de pila hasta encontrar a v
        while (pop_from_stack() != v); 

        return stack.is_empty();
      }  

    return true;
  }

public:

  void connected_components(GT & g, DynList <GT> & blk_list,
                            DynList<typename GT::Arc*> & arc_list)
  {
    init_tarjan(g);

    block_list_ptr = &blk_list;

    for (typename GT::Node_Iterator it(g); df_count < n; it.next())
      {
        typename GT::Node * v = it.get_curr();
        if (not IS_NODE_VISITED(v, Aleph::Depth_First)) 
          scc_by_blocks(v); 
      }

    I(stack.is_empty());

        // recorrer cada uno de subgrafos parciales y añadir sus arcos
    for (typename DynList<GT>::Iterator i(blk_list); i.has_curr(); i.next())
      {     // recorrer todos los nodos del bloque
        GT & blk = i.get_curr();
        for (typename GT::Node_Iterator j(blk); j.has_curr(); j.next())
          {
            typename GT::Node * bsrc = j.get_curr();
            typename GT::Node * gsrc = mapped_node<GT>(bsrc);

              // recorrer arcos de gsrc
            for (Out_Iterator<GT, SA> k(gsrc, sa); k.has_curr(); k.next())
              {
                typename GT::Node * gtgt = k.get_tgt_node();
                typename GT::Arc  * ga   = k.get_current_arc();
                if (NODE_COUNTER(gsrc) != NODE_COUNTER(gtgt)) 
                  {   // arco inter-bloque ==> añádalo a arc_list
                    arc_list.append(ga);
                    continue;
                  }

                    // insertar y mapear el arco en el sub-bloque
                typename GT::Node * btgt = mapped_node<GT>(gtgt);
                typename GT::Arc  * ba = 
                  blk.insert_arc(bsrc, btgt, ga->get_info());

                GT::map_arcs(ga, ba);
              }
          }
      }
  }

  void connected_components(GT & g, 
                            DynList<DynList<typename GT::Node*>> & blks)
  {
    init_tarjan(g);

    list_list_ptr = &blks;

    for (typename GT::Node_Iterator it(g); df_count < n; it.next())
      {
        typename GT::Node * v = it.get_curr();
        if (not IS_NODE_VISITED(v, Aleph::Depth_First))
          scc_by_lists(v); 
      }
  }

  void connected_components(GT & g, DynList<size_t> & blks)
  {
    init_tarjan(g);

    list_len_ptr = &blks;

    for (typename GT::Node_Iterator it(g); df_count < n; it.next())
      {
        typename GT::Node * v = it.get_curr();
        if (not IS_NODE_VISITED(v, Aleph::Depth_First))
          scc_by_len(v); 
      }
  }

  void operator () (GT &                         g, 
                    DynList <GT> &               blk_list,
                    DynList<typename GT::Arc*> & arc_list)
  {
    connected_components(g, blk_list, arc_list);
  }

  void operator () (GT &                                   g, 
                    DynList<DynList<typename GT::Node*>> & blks)
  {
    connected_components(g, blks);
  }

  void operator () (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())
      {
        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())
      arc_list.append(it.get_curr());
  }

  void operator () (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())
      {
        DynDlist<typename GT::Node*> & tgt_list = 
          blks.append(DynDlist<typename GT::Node*>());

        DynList<typename GT::Node*> & blk = it.get_curr();
        while (not blk.is_empty())
          tgt_list.append(blk.remove_first());
      }   
  }

  bool has_cycle(GT & g)
  {
    init_tarjan(g);

    for (typename GT::Node_Iterator it(g); df_count < n; it.next())
    {
      typename GT::Node * v = it.get_curr();
      if (not IS_NODE_VISITED(v, Aleph::Depth_First)) 
        if (has_cycle(v)) 
          return true;
    }
    
    return false; 
  }

  bool is_dag(GT & g)
  {
    return not has_cycle(g);
  }

  bool compute_cycle(GT & g, Path<GT> & path)
  {
    init_tarjan(g);
    path_ptr = &path;
    path_ptr->set_graph(g);

    for (Node_Iterator<GT> it(g); df_count < n; it.next())
      {
        typename GT::Node * v = it.get_curr();
        if (not IS_NODE_VISITED(v, Aleph::Depth_First)) // ¿p visitado?
          if (build_cycle(v)) 
            return true;
      }

    return false; 
  }

  bool test_connectivity(GT & g)
  {
    init_tarjan(g);

    for (typename GT::Node_Iterator it(g); df_count < n; it.next())
      {
        typename GT::Node * v = it.get_curr();
        if (not IS_NODE_VISITED(v, Aleph::Depth_First)) 
          if (not is_connected(v))
            return false;
      }

    I(stack.is_empty());

    return true;
  }
};



     template <class GT, class SA = Dft_Show_Arc<GT>> 
class Compute_Cycle_In_Digraph
{
  SA & sa;

public:

  Compute_Cycle_In_Digraph(SA && __sa = SA()) : sa(__sa) { /* empty */ }

  Compute_Cycle_In_Digraph(SA & __sa) : sa(__sa) { /* empty */ }

  bool operator () (GT & g, Path<GT> & path) const
  {
    Tarjan_Connected_Components<GT, SA> tarjan(sa);

    return tarjan.compute_cycle(g, path);
  }
};

} // end namespace Aleph

# endif // TARJAN_H