kosaraju.H

# ifndef KOSARAJU_H
# define KOSARAJU_H

# include <tpl_graph_utils.H>

namespace Aleph {

     template <class GT, class SA> inline static
void __dfp(GT & g, typename GT::Node * p, DynArray<typename GT::Node*> & df)
{
  if (IS_NODE_VISITED(p, Depth_First))
    return;

  NODE_BITS(p).set_bit(Depth_First, true); 

      // recorre en profundidad los arcos de p 
  for (Node_Arc_Iterator<GT,SA> it(p); it.has_current(); it.next())
    {
      typename GT::Arc * a = it.get_current_arc();
      if (IS_ARC_VISITED(a, Depth_First))
        continue;

      ARC_BITS(a).set_bit(Depth_First, true); 

      __dfp<GT,SA>(g, it.get_tgt_node(), df);
    }
  df.append(p); // asignación de df(p) en sufijo
  NODE_COUNTER(p) = df.size();
}

    /* Recorre el grafo invertido e inserta los nodos alcanzables en el
       sub-grafo blk. A cada bloque le coloca el color color

     */
     template <class GT, class SA> inline static
void __dfp(GT & g, typename GT::Node * p, GT & blk, const int & color)
{
  if (IS_NODE_VISITED(p, Depth_First))
    return;

  NODE_BITS(p).set_bit(Depth_First, true); 

  typename GT::Node * q = blk.insert_node(p->get_info());
  NODE_COUNTER(q) = color;
  GT::map_nodes(p, q);

  for (Node_Arc_Iterator<GT,SA> it(p); it.has_current(); it.next())
    {
      typename GT::Arc * a = it.get_current_arc();

      if (IS_ARC_VISITED(a, Depth_First))
        continue;
      ARC_BITS(a).set_bit(Depth_First, true); 

      __dfp<GT,SA>(g, it.get_tgt_node(), blk, color);
    }
}

     template <class GT, class SA> inline 
void kosaraju_connected_components(GT &                           g, 
                                   DynDlist <GT> &                blk_list,
                                   DynDlist<typename GT::Arc *> & arc_list)
{
  g.reset_nodes();
  g.reset_arcs();

  DynArray<typename GT::Node*> df; // arreglo de df por sufijo

      // recorre en profundidad y marca en sufijo los nodos
  for (Node_Iterator<GT> it(g); it.has_current() and df.size() < g.vsize();
       it.next())
    __dfp<GT,SA>(g, it.get_current(), df);

  GT gi; 
  invert_digraph<GT,SA>(g, gi); // gi es el grafo invertido de g

  DynArray<GT*> array; // areglo de sub-grafos

  for (int i = df.size() - 1, color = 0; i >= 0; i--)
    {
      typename GT::Node * gp = df.access(i);
      typename GT::Node * bp = mapped_node<GT>(gp);

      if (IS_NODE_VISITED(bp, Depth_First))
        continue;
      
      GT & blk = blk_list.append(GT());
      array[color] = &blk;
      
      __dfp<GT,SA>(gi, bp, blk, color++); // recorre el grafo inverso 
                                            // inserta los nodos en blk 
      I(NODE_COLOR(mapped_node<GT>(bp)) == color - 1);
      
    }

  for (Arc_Iterator<GT,SA> it(g); it.has_current(); it.next())
    {
      typename GT::Arc  * a  = it.get_current();
      typename GT::Node * gs = g.get_src_node(a);
      typename GT::Node * gt = g.get_tgt_node(a);

      typename GT::Node * bs = mapped_node<GT>(mapped_node<GT>(gs));
      typename GT::Node * bt = mapped_node<GT>(mapped_node<GT>(gt));

      const long & color = NODE_COLOR(bs);

      if (color == NODE_COLOR(bt))
        {
          typename GT::Arc * ba = array.access(color)->insert_arc(bs, bt);
          GT::map_arcs(a, ba);
        }
      else 
        arc_list.append(a); 
    }
} 


     template <class GT> inline 
void kosaraju_connected_components(GT &                          g, 
                                   DynDlist <GT> &               blk_list,
                                   DynDlist<typename GT::Arc*> & arc_list)
{
  kosaraju_connected_components<GT,Dft_Show_Arc<GT> >
    (g, blk_list, arc_list);
}


    /* Recorre el grafo invertido e inserta los nodos alcanzables en la
       lista list. A cada nodo le coloca el color color

     */
     template <class GT, class SA> inline static
void __dfp(GT & g, typename GT::Node * p, DynDlist<typename GT::Node *> & list)
{
  if (IS_NODE_VISITED(p, Depth_First))
    return;

  NODE_BITS(p).set_bit(Depth_First, true); 

  list.append(mapped_node<GT>(p));

  for (Node_Arc_Iterator<GT,SA> it(p); it.has_current(); it.next())
    {
      typename GT::Arc * a = it.get_current_arc();

      if (IS_ARC_VISITED(a, Depth_First))
        continue;
      ARC_BITS(a).set_bit(Depth_First, true); 

      __dfp<GT,SA>(g, it.get_tgt_node(), list);
    }
}

    template <class GT, class SA> inline 
void kosaraju_connected_components(GT & g, 
                                   DynDlist<DynDlist<typename GT::Node*> > & list)
{
  g.reset_nodes();
  g.reset_arcs();
  DynArray<typename GT::Node*> df; // arreglo de df por sufijo

      // recorre en profundidad y marca en sufijo los nodos
  for (Node_Iterator<GT> it(g); it.has_current() and df.size() < g.vsize();
       it.next())
    __dfp<GT,SA>(g, it.get_current(), df);

  GT gi; 
  invert_digraph<GT,SA>(g, gi); // gi es el grafo invertido de g

  for (int i = df.size() - 1; i >= 0; i--)
    {
      typename GT::Node * gp = df.access(i);
      typename GT::Node * bp = mapped_node<GT>(gp);
      if (IS_NODE_VISITED(bp, Depth_First))
        continue;

      DynDlist<typename GT::Node*> & blk = 
        list.append(DynDlist<typename GT::Node*>());
      
      __dfp<GT,SA>(gi, bp, blk);
    }
} 


     template <class GT> inline 
void kosaraju_connected_components(GT & g, 
                                   DynDlist<DynDlist<typename GT::Node*> > & list)

{
  kosaraju_connected_components<GT,Dft_Show_Arc<GT> > (g, list);
}

    template <class GT, class SA = Dft_Show_Arc<GT> > 
class Kosaraju_Connected_Components
{
public:

  void operator () (GT &                           g, 
                    DynDlist <GT> &                blk_list, 
                    DynDlist<typename GT::Arc *> & arc_list)
  {
    kosaraju_connected_components<GT, SA> (g, blk_list, arc_list);
  }

  void operator () (GT & g, DynDlist<DynDlist<typename GT::Node*> > & list)
  {
    kosaraju_connected_components<GT, SA> (g, list);
  }
};

} // end namespace Aleph

# endif // KOSARAJU_H