tpl_components.H

# ifndef TPL_COMPONENTS_H
# define TPL_COMPONENTS_H

# include <htlist.H>

namespace Aleph {


      template <class GT, class SA = Dft_Show_Arc<GT> > 
class Build_Subgraph
{
  SA & sa;
  GT * gptr;
  size_t count;

public:

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

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

private:

  void build_subgraph(GT & sg, typename GT::Node * g_src)
  {
    if (IS_NODE_VISITED(g_src, Build_Subtree)) 
      return;

    NODE_BITS(g_src).set_bit(Build_Subtree, true); // g_src visitado
    ++count; 

    typename GT::Node * sg_src = mapped_node <GT> (g_src);
    if (sg_src == NULL) // ¿está mapeado g_src?
      {     // No, cree imagen de g_src en el subgrafo sg y mapee
        sg_src = sg.insert_node(g_src->get_info());
        GT::map_nodes(g_src, sg_src);
      }

    for (Node_Arc_Iterator<GT, SA> i(g_src, sa); // explore desde g_src 
         count < gptr->get_num_nodes() and i.has_current(); i.next())
      {
        typename GT::Arc * arc = i.get_current_arc();
        if (IS_ARC_VISITED(arc, Build_Subtree)) 
          continue; // avance próximo arco

        ARC_BITS(arc).set_bit(Build_Subtree, true); // arc visitado

        typename GT::Node * g_tgt  = i.get_tgt_node(); // destino de arc
        typename GT::Node * sg_tgt = mapped_node <GT> (g_tgt);

        if (sg_tgt == NULL) // ¿está mapeado en sg?
          {    // no, hay que mapearlo e insertarlo en el subgrafo sg
            sg_tgt = sg.insert_node(g_tgt->get_info()); 
            GT::map_nodes(g_tgt, sg_tgt); 
          }

            // tenemos nodos en subgrafo, insertamos arco y mapeamos
        typename GT::Arc * sg_arc = 
          sg.insert_arc(sg_src, sg_tgt, arc->get_info());

        GT::map_arcs(arc, sg_arc); 

        build_subgraph(sg, g_tgt);
      }
  }

      template <template <class> class List>
  void build_subgraph(List<typename GT::Node*> & l, typename GT::Node * p)
  {
    if (IS_NODE_VISITED(p, Build_Subtree)) 
      return;

    NODE_BITS(p).set_bit(Build_Subtree, true); // g_src visitado
    ++count; 
    l.append(p);

    for (Node_Arc_Iterator<GT, SA> it(p, sa); // explore desde g_src 
         count < gptr->get_num_nodes() and it.has_curr(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();
        if (IS_ARC_VISITED(arc, Build_Subtree)) 
          continue; // avance próximo arco

        ARC_BITS(arc).set_bit(Build_Subtree, true); // arc visitado

        build_subgraph(l, it.get_tgt_node());
      }
  }
    
  public:

  void operator () (GT & g, GT & sg, typename GT::Node * g_src) 
  {
    gptr = &g;
    count = 0;
    build_subgraph (sg, g_src);
  }

  void operator () (GT & g, DynDlist<typename GT::Node*> & list, 
                    typename GT::Node * src) 
  {
    gptr = &g;
    count = 0;
    build_subgraph<DynDlist>(list, src);
  }

  void operator () (GT & g, DynList<typename GT::Node*> & list, 
                    typename GT::Node * src) 
  {
    gptr = &g;
    count = 0;
    build_subgraph<DynList>(list, src);
  }
}; 


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


public:

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

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

      template <template <class> class List>
  void compute_blocks(GT & g, List <GT> & list)
  {
    g.reset_nodes(); 
    g.reset_arcs();  
    size_t count = 0; // contador de nodos visitados
    for (typename GT::Node_Iterator it(g); // recorrer nodos de g
         count < g.get_num_nodes() and it.has_curr(); it.next())
      {
        typename GT::Node * curr = it.get_current_node();
        if (IS_NODE_VISITED(curr, Build_Subtree)) 
          continue;

        GT & subgraph = list.append(GT()); // grafo insertado en list

        Build_Subgraph <GT, SA> build(sa);
        build(g, subgraph, curr); 
        
        count += subgraph.get_num_nodes();
      }
  }

      template <template <class> class List>
  void compute_lists(GT & g, List<List<typename GT::Node*> > & list)
  {
    g.reset_nodes(); 
    g.reset_arcs();  
    size_t count = 0; // contador de nodos visitados
    for (typename GT::Node_Iterator i(g); // recorrer nodos de g
         count < g.get_num_nodes() and i.has_curr(); i.next())
      {
        typename GT::Node * curr = i.get_current_node();
        if (IS_NODE_VISITED(curr, Build_Subtree)) 
          continue;

        // crear subgrafo componente inconexo conectado por curr_node 
        List<typename GT::Node*> & l = 
          list.append(List<typename GT::Node*>()); 

        Build_Subgraph <GT, SA> build(sa);
        build(g, l, curr); 
        
        count += l.size();
      }
  }
    
  void operator () (GT & g, DynDlist <GT> & list)
  {
    compute_blocks<DynDlist>(g, list);
  }

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

  void operator () (GT & g, DynList <GT> & list)
  {
    compute_blocks<DynList>(g, list);
  }

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


} // end namespace Aleph

# endif //  TPL_COMPONENTS_H