topological_sort.H

# ifndef TOPOLOGICAL_SORT_H
# define TOPOLOGICAL_SORT_H

# include <tpl_dynListQueue.H>
# include <tpl_graph.H>

namespace Aleph {


    template <class GT, class SA = Dft_Show_Arc<GT> > 
class Topological_Sort
{
  SA & sa;
  GT * gptr;

public:

  Topological_Sort(SA && __sa = SA()) : sa(__sa), gptr(NULL) { /* empty */ }

  Topological_Sort(SA & __sa) : sa(__sa), gptr(NULL)  { /* empty */ }

private:
 
      template <template <class> class List>
  void topological_sort(typename GT::Node * curr, 
                        List<typename GT::Node*> & list)
  {
    I(gptr != NULL);

    if (IS_NODE_VISITED(curr, Depth_First))
      return;

    NODE_BITS(curr).set_bit(Depth_First, 1); // marcarlo como visitado

    const size_t & n = gptr->get_num_nodes();

      // visitar recursivamente en sufijo los nodos adyacentes a curr
    for (Out_Iterator<GT, SA> it(curr, sa); 
         it.has_curr() and list.size() < n; it.next()) 
      topological_sort(it.get_tgt_node(), list);

    list.insert(curr); // inserción sufija de nodo que devino sumidero
  }

public:

  template <template <class> class List>
  List<typename GT::Node*> perform (GT & g)
  {
    if (not g.is_digraph())
      throw std::domain_error("g is not a digraph");

    g.reset_bit_nodes(Depth_First); // iniciar bit de marca de visita en nodos

    gptr = &g;
    List<typename GT::Node*> list;

        // recorrer todos los nodos
    const size_t & n = gptr->get_num_nodes();
    for (typename GT::Node_Iterator it(g); it.has_curr() and list.size() < n; 
         it.next())
    {
      typename GT::Node * curr = it.get_current_node();
      if (not IS_NODE_VISITED(curr, Depth_First))
        topological_sort(curr, list);
    }
    
    return list;
  }

  void operator () (GT & g, DynDlist<typename GT::Node*> & list) 
  {
    perform<DynDlist>(g).swap(list);
  }
};

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

public:

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

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

      template <template <class> class List>
  List<typename GT::Node*> perform (GT & g)
  {
    if (not g.is_digraph())
      throw std::domain_error("g is not a digraph");

    g.reset_counter_nodes();

    List<typename GT::Node*> list;

        // recorra todos los arcos y contar grados de entrada
    for (Arc_Iterator<GT,SA> it(g, sa); it.has_curr(); it.next()) 
      NODE_COUNTER(it.get_tgt_node())++; 

      // buscar nodos con grado de entrada 0 y meterlos en cola
    DynListQueue<typename GT::Node*> q; // cola de fuentes
    for (typename GT::Node_Iterator it(g); it.has_curr(); it.next())
      {
        typename GT::Node * p = it.get_current_node();
        if (NODE_COUNTER(p) == 0) // ¿es un nodo fuente?
          q.put(p); // sí ==> colocarlo en la cola
      }

    while (not q.is_empty()) 
      {
        typename GT::Node * p = q.get(); // saque último fuente

        I(NODE_COUNTER(p) == 0);

        list.append(p); // insértelo en el orden topológico

          // decrementar grado de entrada de cada nodo adyacente a p
        for (Out_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next())
          {
            typename GT::Node * tgt = it.get_tgt_node();
            if (--NODE_COUNTER(tgt) == 0) // ¿tgt deviene fuente?
              q.put(tgt); // sí ==> colóquelo en la cola
          }
      }

    return list;
  }

  template <template <class> class RankList = DynDlist, 
            template <class> class List = DynList>
  RankList<List<typename GT::Node*>> ranks(GT & g)
  {
    if (not g.is_digraph())
      throw std::domain_error("g is not a digraph");

    g.reset_counter_nodes();

        // recorra todos los nodos para contabilizar grado de entrada
    for (typename GT::Node_Iterator i(g); i.has_curr(); i.next()) 
      for (Node_Arc_Iterator <GT, SA> j(i.get_current_node(), sa); 
           j.has_curr(); j.next()) 
        NODE_COUNTER(j.get_tgt_node())++;

        // revisar nodos con grado de entrada 0 y meterlos en cola
    DynListQueue<typename GT::Node*> q; // cola de fuentes
    for (typename GT::Node_Iterator it(g); it.has_curr(); it.next())
      {
        typename GT::Node * p = it.get_current_node();
        if (NODE_COUNTER(p) == 0) // ¿es un nodo fuente?
          q.put(p); // sí ==> colocarlo en la cola
      }
    
    RankList<List<typename GT::Node*>> ranks; // valor de retorno
    while (not q.is_empty()) 
      {
        List<typename GT::Node*> rank;
        DynListQueue<typename GT::Node*> aq;

        while (not q.is_empty()) // saca todos los nodos del nivel i
          {
            typename GT::Node * p = q.get(); // saque último fuente
            rank.append(p); // insértelo en el rango topológico

                // decrementar grado entrada de cada nodo adyacente a p
            for (Out_Iterator<GT, SA> it(p, sa); it.has_curr(); it.next())
              {
                typename GT::Node * tgt = it.get_tgt_node();
                if (--NODE_COUNTER(tgt) == 0) // ¿tgt deviene fuente?
                  aq.put(tgt); // sí ==> colóquelo en cola auxiliar
              }
          }

        ranks.append(std::move(rank));
        q.swap(aq);
      }

    return ranks; 
  }

  void operator () (GT & g, DynDlist<DynList<typename GT::Node *>> & list)
  {
    this->ranks<>(g).swap(list);
  }

  void operator () (GT & g, DynList<DynList<typename GT::Node *>> & list)
  {
    this->ranks<DynList>(g).swap(list);
  }

  void operator () (GT & g, DynDlist<typename GT::Node*> & list) 
  {
    this->perform<DynDlist>(g).swap(list);
  }
};

} // end namespace Aleph

# endif // TOPOLOGICAL_SORT_H