tpl_graph_utils.H

# ifndef TPL_GRAPH_UTILS_H
# define TPL_GRAPH_UTILS_H


# include <limits>
# include <tpl_agraph.H> 
# include <tpl_dynListQueue.H>

using namespace Aleph;

namespace Aleph {

    template <class GT, class SA> inline static bool 
__depth_first_traversal(GT & g, typename GT::Node * node,
                        typename GT::Arc *  arc,
                        bool (*visit)(GT & g, typename GT::Node *, 
                                      typename GT::Arc *),
                        size_t & count);

    template <class GT, class SA = Dft_Show_Arc<GT>> inline size_t 
depth_first_traversal(GT & g, typename GT::Node * start_node,
                      bool (*visit)(GT & g, typename GT::Node *, 
                                    typename GT::Arc *),
                      SA sa = SA())
{
  g.reset_bit_nodes(Depth_First); // reiniciar Depth_First de nodos
  g.reset_bit_arcs(Depth_First);  // reiniciar Depth_First de arcos
  size_t counter = 0; // inicialmente no se ha visitado ningún nodo

  __depth_first_traversal<GT,SA>(g, start_node, NULL, visit, counter, sa);

  return counter;
}

  template <class GT, class SA = Dft_Show_Arc<GT>> inline 
size_t depth_first_traversal(GT & g, 
                             bool (*visit)(GT &, typename GT::Node *, 
                                           typename GT::Arc *),
                             SA sa = SA())
{
  return depth_first_traversal <GT, SA> (g, g.get_first_node(), visit, sa);
}

  template <class GT>
struct Default_Visit_Op
{
  bool operator () (GT &, typename GT::Node *, typename GT::Arc *)
  {
    return false;
  }
};

      template <class GT, 
                class Operation = Default_Visit_Op<GT>, 
                class SA        = Dft_Show_Arc<GT>> 
class Depth_First_Traversal
{
  Operation * op;
  SA        & sa;
  size_t      count;
  GT *        g_ptr;

private:

  bool __dft(typename GT::Node * node, typename GT::Arc * arc = NULL)
  {
    if (IS_NODE_VISITED(node, Depth_First)) 
      return false; 

    NODE_BITS(node).set_bit(Depth_First, true); // marca nodo visitado
    count++;

    if ((*op)(*g_ptr, node, arc)) 
      return true; // sí, invóquela

    if (count == g_ptr->get_num_nodes()) // ¿se visitaron todos lo nodos?
      return true;

        // recorrer recursivamente arcos de node 
    for (Node_Arc_Iterator<GT, SA> it(node, sa); it.has_current(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();
        if (IS_ARC_VISITED(arc, Depth_First)) 
          continue;

        ARC_BITS(arc).set_bit(Depth_First, true); // visitado
        if (__dft (it.get_tgt_node(), arc))
          return true; // ya se exploró cabalmente it.get_tgt_node()
      }

    return false; // retorne y siga explorando
  }

  size_t dft(GT & g, typename GT::Node * start_node, Operation & __op)
  {
    op = &__op;
    g_ptr = &g;
    
    g_ptr->reset_bit_nodes(Depth_First); // reiniciar Depth_First de nodos
    g_ptr->reset_bit_arcs(Depth_First);  // reiniciar Depth_First de arcos

    count = 0;

    __dft(start_node);

    return count;
  }

public:

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

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

  size_t operator () (GT & g, Operation && op = Operation()) 
  {
    return dft(g, g.get_first_node(), op);
  }

  size_t operator () (GT & g, Operation & op) 
  {
    return dft(g, g.get_first_node(), op);
  }

  size_t operator () (GT & g, typename GT::Node * sn, 
                      Operation && op = Operation())
  {
    return dft(g, sn, op);
  }

  size_t operator () (GT & g, typename GT::Node * sn, Operation & op)
  {
    return dft(g, sn, op);
  }
};


  template <class GT, class SA> inline static bool
__depth_first_traversal(GT & g, typename GT::Node * node, 
                        typename GT::Arc *  arc,
                        bool (*visit)(GT & g, typename GT::Node *, 
                                      typename GT::Arc *),
                        size_t & count,
                        SA sa = SA())
{
  if (IS_NODE_VISITED(node, Depth_First)) 
    return false; 

  NODE_BITS(node).set_bit(Depth_First, true); // marca nodo visitado
  count++;

  if (visit != NULL) // verifique si hay función de visita
    if ((*visit)(g, node, arc)) 
      return true; // sí, invóquela

  if (count == g.get_num_nodes()) // ¿se visitaron todos lo nodos?
    return true;

      // recorrer recursivamente arcos de node 
  for (Node_Arc_Iterator<GT, SA> it(node, sa); it.has_current(); it.next())
    {
      typename GT::Arc * arc = it.get_current_arc();
      if (IS_ARC_VISITED(arc, Depth_First)) 
        continue;

      ARC_BITS(arc).set_bit(Depth_First, true); // visitado
      if (__depth_first_traversal<GT, SA>(g, it.get_tgt_node(), arc,
                                          visit, count, sa))
        return true; // ya se exploró cabalmente it.get_tgt_node()
    }

  return false; // retorne y siga explorando
} 

  template <class GT, class SA = Dft_Show_Arc<GT>> inline size_t
breadth_first_traversal(GT & g, typename GT::Node * start,
                        bool (*visit)(GT &, typename GT::Node *, 
                                      typename GT::Arc *) )
{
  g.reset_bit_nodes(Breadth_First); 
  g.reset_bit_arcs(Breadth_First);  
  DynListQueue<typename GT::Arc*> q; // cola de arcos pendientes

  // ingresar a la cola los arcos de nodo start
  for (Node_Arc_Iterator<GT, SA> it(start); it.has_current(); it.next())
    q.put(it.get_current_arc());

  NODE_BITS(start).set_bit(Breadth_First, true); 
  size_t node_counter = 1; // contador de nodos visitados

  if (visit != NULL)
    if ((*visit)(g, start, NULL))
      return 1;

  // mientras queden arcos en cola y resten todos por visitar
  while (not q.is_empty() and node_counter < g.get_num_nodes()) 
    {
      typename GT::Arc * arc = q.get();// saque de cola más cercano
      ARC_BITS(arc).set_bit(Breadth_First, true); 

      typename GT::Node * src = g.get_src_node(arc); 
      typename GT::Node * tgt = g.get_tgt_node(arc);
      if (IS_NODE_VISITED(src, Breadth_First) and 
          IS_NODE_VISITED(tgt, Breadth_First)) 
        continue; 

      typename GT::Node * visit_node = // próximo a visitar
        IS_NODE_VISITED(src, Breadth_First) ? tgt : src;

      if (visit != NULL)
        if ((*visit)(g, visit_node, arc))
          break;

      NODE_BITS(visit_node).set_bit(Breadth_First, true); 
      node_counter++;

          // insertar en cola arcos del nodo recién visitado
      for (Node_Arc_Iterator<GT, SA> it(visit_node); it.has_curr(); it.next())
        {
          typename GT::Arc * curr_arc = it.get_current_arc();
            if (IS_ARC_VISITED(curr_arc, Breadth_First)) 
              continue; 

              // revise nodos del arcos para ver si han sido visitados
            if (IS_NODE_VISITED(g.get_src_node(curr_arc), Breadth_First) and 
                IS_NODE_VISITED(g.get_tgt_node(curr_arc), Breadth_First))
              continue; // nodos ya visitados 

            q.put(curr_arc);
          }
    }

    return node_counter;
  }

  template <class GT, class SA = Dft_Show_Arc<GT>> inline size_t
breadth_first_traversal(GT &                g, 
                        bool (*visit)(GT &, typename GT::Node *, 
                                      typename GT::Arc *)
                        )
{
  return breadth_first_traversal<GT, SA>(g, g.get_first_node(), visit);
}

      template <class GT, 
                class Operation = Default_Visit_Op<GT>, 
                class SA        = Dft_Show_Arc<GT>> 
class Breadth_First_Traversal
{
  SA     & sa;
  size_t   count;

  size_t bft(GT & g, typename GT::Node * start, Operation & op)
  {
    g.reset_bit_nodes(Breadth_First); 
    g.reset_bit_arcs(Breadth_First);  
    DynListQueue<typename GT::Arc*> q; // cola de arcos pendientes

    // ingresar a la cola los arcos de nodo start
    for (Node_Arc_Iterator<GT, SA> it(start); it.has_current(); it.next())
      q.put(it.get_current_arc());

    NODE_BITS(start).set_bit(Breadth_First, true); 
    count = 1; // contador de nodos visitados

    if (op (g, start, NULL))
      return 1;

    // mientras queden arcos en cola y resten todos por visitar
    while (not q.is_empty() and count < g.get_num_nodes()) 
      {
        typename GT::Arc * arc = q.get();// saque de cola más cercano
        ARC_BITS(arc).set_bit(Breadth_First, true); 

        typename GT::Node * src = g.get_src_node(arc); 
        typename GT::Node * tgt = g.get_tgt_node(arc);

        if (IS_NODE_VISITED(src, Breadth_First) and
            IS_NODE_VISITED(tgt, Breadth_First))
          continue;

        typename GT::Node * curr = // próximo a visitar
          IS_NODE_VISITED(src, Breadth_First) ? tgt : src;

        if (op (g, curr, arc))
          break;

        NODE_BITS(curr).set_bit(Breadth_First, true); 
        count++;

        // insertar en cola arcos del nodo recién visitado
        for (Node_Arc_Iterator<GT, SA> it(curr); it.has_current(); it.next())
          {
            typename GT::Arc * curr_arc = it.get_current_arc();
            if (IS_ARC_VISITED(curr_arc, Breadth_First)) 
              continue; 

            // revise nodos del arcos para ver si han sido visitados
            if (IS_NODE_VISITED(g.get_src_node(curr_arc), Breadth_First) and 
                IS_NODE_VISITED(g.get_tgt_node(curr_arc), Breadth_First))
              continue; // nodos ya visitados 

            q.put(curr_arc);
          }
      }

    return count;
  }  

public:

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

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

  size_t operator () (GT & g, Operation && op = Operation())
  {
    return bft (g, g.get_first_node(), op);
  }

  size_t operator () (GT & g, Operation & op)
  {
    return bft (g, g.get_first_node(), op);
  }

  size_t operator () (GT & g, typename GT::Node * p, 
                      Operation && op = Operation())
  {
    return bft(g, p, op);
  }

  size_t operator () (GT & g, typename GT::Node * p, Operation & op)
  {
    return bft(g, p, op);
  }
};


      template <class GT> inline static
void __insert_in_queue(GT & g, DynListQueue<Path<GT> *> & q,
                       typename GT::Node * node, typename GT::Arc * arc,
                       Path<GT> * path_ptr = NULL)
{
  unique_ptr<Path<GT>> path_auto;
  if (path_ptr == NULL) // ¿iniciar o copiar*
    path_auto = unique_ptr<Path<GT>>(new Path<GT>(g, node)); // iniciar
  else
    path_auto = unique_ptr<Path<GT>>(new Path<GT>(*path_ptr));// copiar

  path_auto->append(arc);     // añadir el nuevo arco
  q.put(path_auto.get());     // insertar el nuevo camino en cola
  path_auto.release();
}

    template <class GT, class SA = Dft_Show_Arc<GT>> inline 
bool find_path_breadth_first(GT & g, typename GT::Node * start, 
                             typename GT::Node * end, Path<GT> & path)
{
  if (not path.inside_graph(g))
    throw std::invalid_argument("Path does not belong to graph");

  path.clear_path(); // limpiamos cualquier cosa que esté en path
  g.reset_nodes();
  g.reset_arcs(); 
  
  DynListQueue<typename GT::Arc*> q; // cola de caminos parciales

     // insertar arcs iniciales que salen desde start
  for (Node_Arc_Iterator<GT, SA> i(start); i.has_curr(); i.next())
    q.put(i.get_current_arc());
        
  NODE_BITS(start).set_bit(Find_Path, true); // márquelo visitado

  bool path_found = false;

  while (not q.is_empty()) // mientras queden arcos por visitar
    {
      typename GT::Arc * arc = q.get(); 
      typename GT::Node * src = g.get_src_node(arc); 
      typename GT::Node * tgt = g.get_tgt_node(arc);

      if (IS_NODE_VISITED(src, Find_Path) and IS_NODE_VISITED(tgt, Find_Path))
        continue;
      
      if (IS_NODE_VISITED(tgt, Find_Path))
        std::swap(src, tgt);

      ARC_BITS(arc).set_bit(Find_Path, true); 
      NODE_BITS(tgt).set_bit(Find_Path, true);
      NODE_COOKIE(tgt) = src;
        
      if (tgt == end) // ¿se encontró un camino?
        {
          path_found = true;
          break;
        }

      for (Node_Arc_Iterator<GT,SA> i(tgt); i.has_curr(); i.next())
        {
          typename GT::Arc * a = i.get_current_arc();
          if (IS_ARC_VISITED(a, Find_Path)) // ¿arco visitado?
            continue; // sí ==> avanzar al siguiente 

          // revise nodos del arco para ver si han sido visitados
          if (IS_NODE_VISITED(g.get_src_node(a), Find_Path) and 
              IS_NODE_VISITED(g.get_tgt_node(a), Find_Path))
            continue; // nodos ya visitados ==> no  meter arco

          q.put(a);
        }
    }
  
  if (not path_found)
    return false;

  q.empty();
  path.insert(end);
  typename GT::Node * p = end;
  while (p != start)
    {
      p = (typename GT::Node *) NODE_COOKIE(p);
      path.insert(p);
    }

  return true;
}


    template <class GT, class SA = Dft_Show_Arc<GT>> inline 
bool test_connectivity(GT & g)
{
  if (g.is_digraph()) // sólo es válida para grafos, no digrafos
    throw std::domain_error("test_connectivity() does not work on digraphs");

  if (g.get_num_arcs() < g.get_num_nodes() - 1) 
    return false; 

  return depth_first_traversal<GT, SA>(g, NULL) == g.get_num_nodes();
}


      template <class GT, class SA> inline static
  bool __test_cycle(GT & g, typename GT::Node * src_node, 
                    typename GT::Node * curr_node);
      template <class GT, class SA = Dft_Show_Arc<GT>> inline 
  bool test_for_cycle(GT & g, typename GT::Node * src_node)
  {
    g.reset_bit_nodes(Test_Cycle); // reiniciar Test_Cycle para nodos
    g.reset_bit_arcs(Test_Cycle);  // reiniciar Test_Cycle para arcos

      // explorar recursivamente por arcos adyacentes a src_node
    for (Node_Arc_Iterator<GT, SA> it(src_node); it.has_current(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();
        if (IS_ARC_VISITED(arc, Test_Cycle)) 
          continue;

        ARC_BITS(arc).set_bit(Test_Cycle, true); // pintar arco

        if (__test_cycle<GT,SA>(g, src_node, it.get_tgt_node()))
          return true; // ciclo detectado
      }
        // Se han explorado todos los caminos desde src_node 
        // sin encontrar de nuevo a src_node ==> no hay ciclo 
    return false;
  }


      template <class GT, class SA> inline static
  bool __test_cycle(GT & g, typename GT::Node * src_node, 
                    typename GT::Node * curr_node)
  {
    if (src_node == curr_node) 
      return true; // ciclo detectado!

    if (IS_NODE_VISITED(curr_node, Test_Cycle)) 
      return false;

    NODE_BITS(curr_node).set_bit(Test_Cycle, true); // marque nodo

      // buscar caminos desde current_node a ver si llega a src_node 
    for (Node_Arc_Iterator<GT, SA> it(curr_node); it.has_current(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();
        if (IS_ARC_VISITED(arc, Test_Cycle)) 
          continue;

        ARC_BITS(arc).set_bit(Test_Cycle, true); // marque arco

        if (__test_cycle<GT,SA>(g, src_node, it.get_tgt_node()))
          return true; // ciclo encontrado desde el arco actual 
      }
        // En este punto se han explorado caminos desde curr_node
        // sin encontrar src_node ==> no existe ciclo por curr_node  
    return false; 
  }  

      template <class GT, class SA> inline static
  bool __is_graph_acyclique(GT & g, typename GT::Node * curr_node)
  {
    if (IS_NODE_VISITED(curr_node, Is_Acyclique)) 
      return false;

    NODE_BITS(curr_node).set_bit(Is_Acyclique, true); // marcar nodo

    for (Node_Arc_Iterator<GT, SA> i(curr_node); i.has_current(); i.next())
      {
        typename GT::Arc * arc = i.get_current_arc();
        if (IS_ARC_VISITED(arc, Is_Acyclique)) 
          continue; 

        ARC_BITS(arc).set_bit(Is_Acyclique, true); 

        if (not __is_graph_acyclique<GT,SA>(g, i.get_tgt_node())) 
          return false;
      }
        // todos los arcos recorridos sin encontrar ciclo ==>
        // el grafo es acíclico pasando por curr_node
    return true; 
  }

    template <class GT, class SA = Dft_Show_Arc<GT>> inline 
bool is_graph_acyclique(GT & g, typename GT::Node * start_node)
{
  if (g.is_digraph())
    throw std::domain_error("is_graph_acyclique() does not work for digraps");
  
  if (g.get_num_arcs() >= g.get_num_nodes()) 
    return false; 

  g.reset_bit_arcs(Is_Acyclique);
  g.reset_bit_nodes(Is_Acyclique);

  return __is_graph_acyclique<GT,SA>(g, start_node);
}

    template <class GT, class SA = Dft_Show_Arc<GT>> inline 
bool is_graph_acyclique(GT & g)
{
  if (g.is_digraph())
    throw std::domain_error("is_graph_acyclique() does not work for digraps");

  if (g.get_num_arcs() >= g.get_num_nodes()) 
    return false; 

  g.reset_bit_arcs(Is_Acyclique);
  g.reset_bit_nodes(Is_Acyclique);

  for (Node_Iterator<GT> it(g); it.has_current(); it.next()) 
    {
      typename GT::Node * current_node = it.get_current_node();
      if (IS_NODE_VISITED(current_node, Is_Acyclique)) 
        continue; 

      if (not __is_graph_acyclique<GT,SA>(g, current_node)) 
        return false;
    }

  return true;
}

      template <class GT, class SA = Dft_Show_Arc<GT>> 
inline bool has_cycle(GT & g)
{
  return not is_graph_acyclique<GT,SA>(g);
}

 
      template <class GT, class SA> inline static
bool __test_for_path(GT & g, typename GT::Node * curr_node,
                     typename GT::Node * end_node);

      template <class GT, class SA = Dft_Show_Arc<GT>> inline 
bool test_for_path(GT& g, typename GT::Node * start_node, 
                   typename GT::Node * end_node)
{      // si el grafo es conexo ==> existe camino
  if (not g.is_digraph() and g.get_num_arcs() >= g.get_num_nodes()) 
    return true;

  g.reset_bit_nodes(Test_Path); 
  g.reset_bit_arcs(Test_Path);

      // buscar recursivamente por arcos adyacentes a start_node
  for (Node_Arc_Iterator<GT, SA> i(start_node); i.has_current(); i.next())
    {
      typename GT::Arc * arc = i.get_current_arc();
      ARC_BITS(arc).set_bit(Test_Path, true); // marcar arco
      if (__test_for_path<GT, SA>(g, i.get_tgt_node(), end_node)) 
        return true; 
    }
        // todos los arcos de start_node han sido explorados sin 
        // encontrar camino hasta end_node ==> no existe camino
  return false;
}


      template <class GT, class SA> inline static
bool __test_for_path(GT & g, typename GT::Node * curr_node, 
                     typename GT::Node * end_node)  
{
  if (curr_node == end_node) 
    return true; // se alcanzó a end_node

  if (IS_NODE_VISITED(curr_node, Test_Path)) // ¿se visitó curr_node?
    return false; // sí, no explore

  NODE_BITS(curr_node).set_bit(Test_Path, true); // pintar curr_node

        // buscar recursivamente a través de arcos de curr_node 
  for (Node_Arc_Iterator<GT, SA> i(curr_node); i.has_current(); i.next())
    { 
      typename GT::Arc * arc = i.get_current_arc();
      if (IS_ARC_VISITED(arc, Test_Path)) 
        continue; 

      ARC_BITS(arc).set_bit(Test_Path, true); // pintar arco
      if (__test_for_path<GT, SA>(g, i.get_tgt_node(), end_node)) 
        return true;
    }

        // todos los arcos adyacentes de curr_node explorados sin
        // encontrar a end_node ==> no existe camino por curr_node
  return false;
}

      template <class GT, class SA = Dft_Show_Arc<GT>> inline 
  void inconnected_components(GT & g, DynDlist<GT> & list);

      template <class GT, class SA = Dft_Show_Arc<GT>> inline 
  void build_subgraph(GT & g, GT & sg, 
                      typename GT::Node * g_src, size_t & node_count); 

    

      template <class GT, class SA> inline 
void inconnected_components(GT & g, DynDlist <GT> & 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_current(); 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.append(GT()); // crea subgrafo y lo inserta en lista
      GT & subgraph = list.get_last(); // grafo insertado en list

      build_subgraph <GT, SA> (g, subgraph, curr, count); 
    }
}


    template <class GT, class SA> inline 
void build_subgraph(GT & g, GT & sg, 
                    typename GT::Node * g_src, size_t & node_count)
{
  if (IS_NODE_VISITED(g_src, Build_Subtree)) 
    return;

  NODE_BITS(g_src).set_bit(Build_Subtree, true); // g_src visitado
  ++node_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); // explore desde g_src 
       node_count < g.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<GT,SA>(g, sg, g_tgt, node_count);
    }
}

  
    template <class GT, class SA> inline static
bool __find_depth_first_spanning_tree(GT &                g, 
                                      typename GT::Node * gnode, 
                                      typename GT::Arc *  garc, 
                                      GT &                tree,
                                      typename GT::Node * tnode);

      template <class GT, class SA = Dft_Show_Arc<GT>> inline
void find_depth_first_spanning_tree(GT & g, typename GT::Node * gnode, 
                                    GT & tree)
{
  g.reset_nodes();
  g.reset_arcs(); 

  clear_graph(tree); // asegurar que árbol destino esté vacío
  
  NODE_BITS(gnode).set_bit(Spanning_Tree, true); // marcar gnode
  
  typename GT::Node * tnode = tree.insert_node(gnode->get_info()); 
  GT::map_nodes(gnode, tnode);
  
  for (Node_Arc_Iterator<GT, SA> i(gnode); i.has_current(); i.next())
    {
      typename GT::Arc * arc = i.get_current_arc();
      if (IS_ARC_VISITED(arc, Spanning_Tree)) 
        continue;

      typename GT::Node * arc_tgt_node = i.get_tgt_node();
      if (IS_NODE_VISITED(arc_tgt_node, Spanning_Tree))
        continue; // destino ya visitado desde otro arco

      if (__find_depth_first_spanning_tree<GT,SA>(g, arc_tgt_node, 
                                                  arc, tree, tnode))
        return; // ya el árbol está calculado 
    }
}

      template <class GT, class SA = Dft_Show_Arc<GT>> inline
void find_depth_first_spanning_tree(GT & g, GT & tree)
{
  typename GT::Node * start_node = g.get_first_node();
  find_depth_first_spanning_tree<GT,SA>(g, start_node, tree);
}

  
      template <class GT, class SA> inline static
bool __find_depth_first_spanning_tree(GT & g, typename GT::Node * gnode, 
                                      typename GT::Arc *  garc, 
                                      GT & tree, typename GT::Node * tnode)
{
  NODE_BITS(gnode).set_bit(Spanning_Tree, true); // marcar nodo 
  ARC_BITS(garc).set_bit(Spanning_Tree, true);   // marcar arco

  typename GT::Node * tree_tgt_node = tree.insert_node(gnode->get_info());
  GT::map_nodes(gnode, tree_tgt_node);

  typename GT::Arc * tarc = 
    tree.insert_arc(tnode, tree_tgt_node, garc->get_info()); 
  GT::map_arcs(garc, tarc);

  tnode = tree_tgt_node; 
  if (tree.get_num_nodes() == g.get_num_nodes()) // ¿grafo abarcado?
    return true; // tree ya contiene el árbol abarcador

  I(tree.get_num_nodes() > tree.get_num_arcs()); // debe ser acíclico

  for (Node_Arc_Iterator<GT, SA> i(gnode); i.has_current(); i.next())
    {
      typename GT::Arc * arc = i.get_current_arc();
      if (IS_ARC_VISITED(arc, Spanning_Tree)) 
        continue;

      typename GT::Node * arc_tgt_node = i.get_tgt_node();
      if (IS_NODE_VISITED(arc_tgt_node, Spanning_Tree))
        continue; // destino ya visitado desde otro arco

      if (__find_depth_first_spanning_tree<GT,SA>(g, arc_tgt_node, 
                                                  arc, tree, tnode))
        return false; // ya el árbol está calculado 
    }

  return false;
}

      template <class GT, class SA = Dft_Show_Arc<GT>> inline
void find_breadth_first_spanning_tree(GT & g, typename GT::Node * gp, GT & tree)
{
  g.reset_bit_nodes(Spanning_Tree);
  g.reset_bit_arcs(Spanning_Tree);
  clear_graph(tree); 
  unique_ptr<typename GT::Node> tp_auto(new typename GT::Node(gp));
  tree.insert_node(tp_auto.get());
  GT::map_nodes(gp, tp_auto.release());

  DynListQueue<typename GT::Arc*> q; // insertar en cola arcos gp
  for (Node_Arc_Iterator<GT, SA> i(gp); i.has_current(); i.next())
    q.put(i.get_current_arc());

  NODE_BITS(gp).set_bit(Spanning_Tree, true); 

  while (not q.is_empty()) 
    {
      typename GT::Arc * garc = q.get(); 
      ARC_BITS(garc).set_bit(Spanning_Tree, true); 
      typename GT::Node * gsrc = g.get_src_node(garc);  
      typename GT::Node * gtgt = g.get_tgt_node(garc);

      if (IS_NODE_VISITED(gsrc, Spanning_Tree) and 
          IS_NODE_VISITED(gtgt, Spanning_Tree))
        continue; // los dos nodos de garc ya fueron visitados

      if (IS_NODE_VISITED(gtgt, Spanning_Tree)) // ¿gtgt visitado?
        std::swap(gsrc, gtgt); // sí, intercámbielo con gsrc

      typename GT::Node * tsrc = mapped_node<GT>(gsrc);
      NODE_BITS(gtgt).set_bit(Spanning_Tree, true); // gtgt visitado

            // crear copia de gtgt, insertarlo en tree y mapearlo
      unique_ptr<typename GT::Node> ttgt_auto(new typename GT::Node(gtgt));
      tree.insert_node(ttgt_auto.get());
      typename GT::Node * ttgt = ttgt_auto.release();
      GT::map_nodes(gtgt, ttgt);

            // insertar nuevo arco en tree y mapearlo
      typename GT::Arc * tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
      GT::map_arcs(garc, tarc);
      if (tree.get_num_nodes() == g.get_num_nodes()) // ¿abarca a g?
        break; 

            // insertar en cola arcos de gtgt
      for (Node_Arc_Iterator<GT, SA> i(gtgt); i.has_current(); i.next())
        {
          typename GT::Arc * current_arc = i.get_current_arc();
          if (IS_ARC_VISITED(current_arc, Spanning_Tree)) 
            continue;

                // revise nodos de arcos para ver si han sido visitados
          if (IS_NODE_VISITED(g.get_src_node(current_arc),Spanning_Tree) and 
              IS_NODE_VISITED(g.get_tgt_node(current_arc),Spanning_Tree))
            continue; // nodos ya visitados ==> no meter arco
          q.put(current_arc);
        }
    }
}

      template <class GT>
void build_spanning_tree(GT & g, GT & tree, DynArray<typename GT::Arc> * arcs,
                         const bool with_map = false)
{
  tree.clear();
  for (int i = 0; i < g.get_num_nodes(); ++i)
    {
      typename GT::Arc * garc = arcs[i];
      if (garc == NULL) 
        continue;

      typename GT::Node * gsrc = g.get_src_node(garc);
      typename GT::Node * tsrc = NULL;
      if (IS_NODE_VISITED(gsrc, Spanning_Tree))
        tsrc = mapped_node <GT> (gsrc);
      else
        {
          NODE_BITS(gsrc).set_bit(Spanning_Tree, true); 
          tsrc = tree.insert_node(gsrc->get_info());
        }

      typename GT::Node * gtgt = g.get_tgt_node(garc);
      typename GT::Node * ttgt = NULL;
      if (IS_NODE_VISITED(gtgt, Spanning_Tree))
        ttgt = mapped_node <GT> (gtgt);
      else
        {
          NODE_BITS(gtgt).set_bit(Spanning_Tree, true);
          ttgt = tree.insert_node(gtgt->get_info());
        }

      typename GT::Arc * tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
      ARC_BITS(garc).set_bit(Min, true);
      if (with_map)
        {
          GT::map_nodes(gsrc, tsrc);
          GT::map_nodes(gtgt, ttgt);
          GT::map_arcs(garc, tarc);
        }
    }
}

    template <class GT> inline static 
long & df(typename GT::Node * p)
{
  return NODE_COUNTER(p);
}

    template <class GT> inline static 
long & low(typename GT::Node * p)
{
  return reinterpret_cast<long&>(NODE_COOKIE(p));
}

    template <class GT> 
struct Init_Low
{
  void operator () (GT & g, typename GT::Node * node) 
  {
    g.reset_counter(node); // inicializa df
    low <GT> (node) = -1;  // inicializa low
  }
};

      template <class GT, class SA> inline static
void __compute_cut_nodes(GT & g, DynDlist<typename GT::Node *> & list, 
                         typename GT::Node * p, typename GT::Arc * a,
                         long & curr_df);

      template <class GT, class SA = Dft_Show_Arc<GT>>
void compute_cut_nodes(GT & g, typename GT::Node * start,
                       DynDlist<typename GT::Node *> & list)
{
  Operate_On_Nodes <GT, Init_Low <GT>> () (g);
  g.reset_arcs();
  long current_df = 0; // contador global de visitas 
  NODE_BITS(start).set_bit(Depth_First, true); // marcar start
  df <GT> (start) = current_df++;
  int call_counter = 0; // contador llamadas recursivas
  
      // Recorra los arcos de start mientras g no haya sido abarcado
  for (Node_Arc_Iterator<GT, SA> i(start); 
       i.has_current() and current_df < g.get_num_nodes(); i.next())
    {
      typename GT::Node * tgt = i.get_tgt_node();
      if (IS_NODE_VISITED(tgt, Depth_First)) 
        continue; 

      typename GT::Arc * arc = i.get_current_arc();
      if (IS_ARC_VISITED(arc, Depth_First)) 
        continue;

      ARC_BITS(arc).set_bit(Depth_First, true);
      __compute_cut_nodes <GT, SA> (g, list, tgt, arc, current_df); 
      ++call_counter;
    }

    if (call_counter > 1) // ¿es la raíz un punto de articulación?
      {
        NODE_BITS(start).set_bit(Cut, true);
        list.append(start);
      }
  }
      
      template <class GT, class SA> inline static
void __compute_cut_nodes(GT & g, DynDlist<typename GT::Node *> & list, 
                         typename GT::Node * p, typename GT::Arc * a, 
                         long & curr_df)
{
  NODE_BITS(p).set_bit(Depth_First, true); // pinte p visitado
  low <GT> (p) = df <GT> (p) = curr_df++;  // asígnele df

      // recorrer arcos de p mientras no se abarque a g
  bool p_is_cut_node = false;
  for (Node_Arc_Iterator <GT, SA> i(p); i.has_current(); i.next())
    {
      typename GT::Arc * arc = i.get_current_arc();
      if (arc == a) 
        continue; // a es el padre de arc ==> ignorarlo

      typename GT::Node * tgt = i.get_tgt_node();
      if (IS_NODE_VISITED(tgt, Depth_First)) 
        { 
          if (not IS_ARC_VISITED(arc, Depth_First)) // no abarcador?
            if (df<GT>(tgt) < low<GT>(p)) // sí, verificar valor low
              low<GT>(p) = df<GT>(tgt); // actualizar low(p)

          continue;
        }

      if (IS_ARC_VISITED(arc, Depth_First)) 
        continue;

      ARC_BITS(arc).set_bit(Depth_First, true); // marque arco

      __compute_cut_nodes<GT, SA>(g, list, tgt, arc, curr_df);

      if (low<GT>(tgt) < low<GT>(p)) 
        low<GT>(p) = low<GT>(tgt); // actualizar low(p)

      if (low<GT>(tgt) >= df<GT>(p) and df<GT>(tgt) != 0) // ¿de corte?
        p_is_cut_node = true;
    }

        // aquí, p ya fue explorado recursivamente
  if (p_is_cut_node)
    {
      NODE_BITS(p).set_bit(Cut, true);
      list.append(p);
    }
}

const long Cross_Arc = -1;

    template <class GT> inline static 
bool is_a_cross_arc(typename GT::Arc * a) 
{
  return ARC_COUNTER(a) == Cross_Arc; 
}

     template <class GT> inline static 
bool is_a_cut_node(typename GT::Node * p)
{
  return NODE_BITS(p).get_bit(Cut);
}

      template <class GT> inline static 
bool is_an_cut_arc(typename GT::Arc * a)
{
  return ARC_BITS(a).get_bit(Cut);
}
      template <class GT> inline static 
bool is_node_painted(typename GT::Node * p)
{
  return NODE_COUNTER(p) > 0;
}

      template <class GT> inline static 
bool is_arc_painted(typename GT::Arc * arc)
{
  return ARC_COUNTER(arc) > 0;
}

      template <class GT> inline static 
void paint_node(typename GT::Node * p, const long & color)
{
  NODE_COUNTER(p) = color;
}

      template <class GT> inline static 
void paint_arc(typename GT::Arc * a, const long & color)
{
  ARC_COUNTER(a) = color;
}

      template <class GT> inline static 
const long & get_color(typename GT::Node * p)
{
  return NODE_COUNTER(p);
}

      template <class GT> inline static 
const long & get_color(typename GT::Arc * a)
{
  return ARC_COUNTER(a);
}

      template <class GT, class SA> inline static
void __paint_subgraph(GT &                g,
                      typename GT::Node * p, // Nodo actual
                      typename GT::Arc *  a, // Arco que conduce a p
                      const long &        current_color);

      template <class GT, class SA> inline static
void __paint_subgraph(GT & g, typename GT::Node * p, const long & current_color)
{
  I(not is_a_cut_node <GT> (p));

  if (is_node_painted <GT> (p)) 
    return; 

  paint_node <GT> (p, current_color);

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

      typename GT::Node * tgt = it.get_tgt_node();
      if (is_a_cut_node <GT> (tgt))
        continue;

      paint_arc <GT> (arc, current_color); 

      __paint_subgraph <GT, SA> (g, tgt, current_color); 
    }
}

    template <class GT, class SA> inline static
void __paint_from_cut_node(GT & g, typename GT::Node * p, long & current_color)
{
  I(is_a_cut_node <GT> (p));

      // pintar recursivamente con dif colores bloques conectados a p
  for (Node_Arc_Iterator<GT, SA> it(p); it.has_current(); it.next())
    {
      typename GT::Arc * arc = it.get_current_arc();

      I(not is_arc_painted <GT> (arc));

      typename GT::Node * tgt_node = it.get_tgt_node();
      if (is_a_cut_node <GT> (tgt_node)) // ¿ es un arco de corte?
        {
          ARC_BITS(arc).set_bit(Cut, true); // marque como de corte
          continue; // avance a próximo arco
        }
      else 
        {
          paint_arc <GT> (arc, Cross_Arc); // marque como de cruce
          if (is_node_painted <GT> (tgt_node)) 
            continue; 
        }

          // pintar recursivamente nodo conectado a arc
      __paint_subgraph <GT, SA> (g, tgt_node, current_color);

      current_color++; // cambiar color (sig arco en otro bloque)

      I(not is_arc_painted <GT> (arc));
    }
}

    template <class GT, class SA = Dft_Show_Arc<GT>> inline long 
paint_subgraphs(GT & g, const DynDlist<typename GT::Node*> & cut_node_list)
{
  g.reset_counter_nodes();
  g.reset_counter_arcs();
  long current_color = 1;

        // Recorrer cada nodo de corte y pintar sus bloques
  for (typename DynDlist<typename GT::Node*>::Iterator 
         i(cut_node_list); i.has_current(); i.next())
    __paint_from_cut_node<GT,SA>(g, i.get_current(), current_color);

  return current_color;
}

         

       template <class GT, class SA> inline static
void __map_subgraph(GT & g, GT & sg, typename GT::Node * gsrc, 
                    const long & color)
{
  I(get_color <GT> (gsrc) == color);

  typename GT::Node * tsrc = mapped_node<GT>(gsrc); // gsrc en sg

      // recorrer arcos de gsrc y añadir a sg los del color de interés
  for (Node_Arc_Iterator <GT, SA> i(gsrc); i.has_current(); i.next())
    {
      typename GT::Arc * garc = i.get_current_arc();
      if (get_color<GT>(garc) != color or IS_ARC_VISITED(garc, Build_Subtree))
        continue; // arco es de otro color o ya está visitado 

      ARC_BITS(garc).set_bit(Build_Subtree, true); 

      typename GT::Node * gtgt = i.get_tgt_node(); 

      I(get_color <GT> (gtgt) == color);

      typename GT::Node * ttgt = NULL; // imagen gtgt en sg
      if (IS_NODE_VISITED(gtgt, Build_Subtree)) // ¿gtgt en sg?
        ttgt = mapped_node<GT> (gtgt);
      else
        {     // gtgt no está en sg ==> copiarlo y mapearlo
          unique_ptr<typename GT::Node> ttgt_auto(new typename GT::Node(gtgt));
          sg.insert_node(ttgt_auto.get());
          GT::map_nodes(gtgt, ttgt_auto.get());
          NODE_BITS(gtgt).set_bit(Build_Subtree, true); 
          ttgt = ttgt_auto.release(); 
        }

      typename GT::Arc * tarc = sg.insert_arc(tsrc, ttgt, garc->get_info());
      GT::map_arcs(garc, tarc);

      __map_subgraph<GT, SA> (g, sg, gtgt, color);
    }
}

      template <class GT, class SA = Dft_Show_Arc<GT>>
void map_subgraph(GT & g, GT & sg, const long & color)
{
  clear_graph(sg);
  typename GT::Node * first = NULL; // busque primer nodo con color
  for (typename GT::Node_Iterator it(g); it.has_current(); it.next())
    if (get_color <GT> (it.get_current_node()) == color)
      first = it.get_current_node();

  if (first == NULL) // Encontró el color?
    throw std::domain_error("Color does not exist in the graph");

        // cree first, insértelo en sg y mapéelo
  unique_ptr<typename GT::Node> auto_tsrc(new typename GT::Node(first));
  sg.insert_node(auto_tsrc.get());
  GT::map_nodes(first, auto_tsrc.release());
  NODE_BITS(first).set_bit(Build_Subtree, true);

  try
    {    
      __map_subgraph <GT, SA> (g, sg, first, color); // mapee first
    }
  catch (...)
    {
      clear_graph(sg);
    }
}


      template <class GT, class SA = Dft_Show_Arc<GT>>
void map_cut_graph(GT & g, DynDlist<typename GT::Node*> & cut_node_list,
                   GT & cut_graph, 
                   DynDlist<typename GT::Arc*> &  cross_arc_list)
{
  clear_graph(cut_graph);

        // recorra lista de nodos de corte e insértelos en cut_graph
  for (typename DynDlist<typename GT::Node*>::Iterator 
         it(cut_node_list); it.has_curr(); it.next())
    {
      typename GT::Node * gp = it.get_current();

      I (is_a_cut_node <GT> (gp));

      unique_ptr<typename GT::Node> tp_auto(new typename GT::Node(gp));
      cut_graph.insert_node(tp_auto.get());
      GT::map_nodes(gp, tp_auto.release());
    }

        // recorra arcos de g ==> cut_graph = {arcos no corte} U 
        // cross_arc_list = {arcos de cruce}
  for (Arc_Iterator <GT, SA> it(g); it.has_current(); it.next())
    {
      typename GT::Arc * garc = it.get_current_arc();
      if (is_a_cross_arc <GT> (garc))
        {
          cross_arc_list.append(garc); 
          continue;
        }

      if (not is_an_cut_arc <GT> (garc)) 
        continue;

      typename GT::Node * src = mapped_node<GT>(g.get_src_node(garc));
      typename GT::Node * tgt = mapped_node<GT>(g.get_tgt_node(garc));

      I(src != NULL and tgt != NULL);

      typename GT::Arc * arc = cut_graph.insert_arc(src, tgt, garc->get_info());
      GT::map_arcs(garc, arc);
    }
}


    template <class GT, class Distance> 
struct Distance_Compare
{
  Distance & dist;

  Distance_Compare(Distance && __dist = Distance())
    : dist(__dist)
  {
    // empty
  }

  Distance_Compare(Distance & __dist)
    : dist(__dist)
  {
    // empty
  }

  bool operator () (typename GT::Arc * a1, typename GT::Arc * a2)
  {
    return dist(a1) < dist(a2);
  }
};

      template <class GT, class SA = Dft_Show_Arc<GT>>
bool is_reachable(GT & g, typename GT::Node * src, typename GT::Node * tgt)
{
  if (not g.is_digraph())
    throw std::domain_error("g is not a digraph");

  return test_for_path <GT, SA> (g, src, tgt);
}

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

    bool operator () (GT & g, typename GT::Node * src, 
                      typename GT::Node * tgt) const
    {
      return is_reachable<GT, SA> (g, src, tgt);
    }
  };

      template <class GT, class SA = Dft_Show_Arc<GT>> 
void invert_digraph(GT & g, GT & gi, SA && sa = SA())
{
  if (not g.is_digraph())
    throw std::domain_error("g is not a digraph");

  if (not gi.is_digraph())
    throw std::domain_error("gi is not a digraph");

  clear_graph(gi);
  g.reset_nodes();

        // recorrer todos los arcos del digrafo g
  for (Arc_Iterator<GT, SA> it(g, sa); it.has_current(); it.next())
    {
      typename GT::Arc * arc   = it.get_current();

            // procesar nodo origen
      typename GT::Node * ssrc = g.get_src_node(arc); 
      typename GT::Node * rsrc = mapped_node<GT> (ssrc);
      if (rsrc == NULL) // ¿ya está creado ssrc en gi?
        {     // no == crearlo, insertarlo y mapearlo
          unique_ptr<typename GT::Node> rsrc_auto(new typename GT::Node(ssrc));
          gi.insert_node(rsrc_auto.get());
          GT::map_nodes(ssrc, rsrc_auto.get());
          rsrc = rsrc_auto.release(); 
        }

            // procesar nodo origen
      typename GT::Node * stgt = g.get_tgt_node(arc);
      typename GT::Node * rtgt = mapped_node<GT> (stgt);
      if (rtgt == NULL) // ¿ya está creado ssrc en gi?
        {     // no == crearlo, insertarlo y mapearlo
          unique_ptr<typename GT::Node> rtgt_auto(new typename GT::Node(stgt));
          gi.insert_node(rtgt_auto.get());
          GT::map_nodes(stgt, rtgt_auto.get());
          rtgt = rtgt_auto.release(); 
        }

      typename GT::Arc * ai = gi.insert_arc(rtgt, rsrc, arc->get_info());
      GT::map_arcs(arc, ai);
    }

  I(g.get_num_arcs() == gi.get_num_arcs() and 
    g.get_num_nodes() == gi.get_num_nodes());
}


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

public:

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

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

  void operator () (GT & g, GT & gi) const
  {
    invert_digraph <GT, SA> (g, gi, sa);
  }
};

    template <class GT>
class Dft_Dist
{
public:

  typedef typename GT::Arc_Type Distance_Type;

  static const Distance_Type Zero_Distance = 0;

  static const Distance_Type Max_Distance;

  Distance_Type & operator () (typename GT::Arc * a) const
  {
    return a->get_info();
  }  
};

template <class GT>
const typename Dft_Dist<GT>::Distance_Type Dft_Dist<GT>::Max_Distance =
  std::numeric_limits<typename Dft_Dist<GT>::Distance_Type>::max();


template <class GT, class Distance = Dft_Dist<GT>>
typename Distance::Distance_Type 
get_min_path(typename GT::Node * s, typename GT::Node * end, 
             Path<GT> & path)
{
  typename Distance::Distance_Type dist = 0;
   path.clear_path();
   path.insert(end);

   typename GT::Node * p = end;
   do
     {
       p = (typename GT::Node *) NODE_COOKIE(p);
       path.insert(p);
       dist = dist + Distance()(path.get_first_arc());
     }
   while (p != s);

   return dist;
}

template <class GT, 
          class Distance = Dft_Dist<GT>, 
          class Plus     = Aleph::plus<typename Distance::Distance_Type>, 
          class SA       = Dft_Show_Arc<GT>>
class Total_Cost
{
  Distance & dist;
  Plus &     plus;
  SA &       sa;

public:

  Total_Cost(Distance && __dist = Distance(), 
             Plus &&     __plus = Plus(),
             SA &&       __sa   = SA()) 
    : dist(__dist), plus(__plus), sa(__sa)
  {
    // empty
  }

  Total_Cost(Distance & __dist, Plus & __plus, SA & __sa) 
    : dist(__dist), plus(__plus), sa(__sa)
  {
    // empty
  }

public:

  typename Distance::Distance_Type total_cost(GT & g)
  {
    typename Distance::Distance_Type sum = Distance::Zero_Distance;
  
        // recorrer todos los arcos y sumar su peso
    for (Arc_Iterator <GT, SA> it(g, sa); it.has_curr(); it.next())
      sum = plus(sum, dist(it.get_current_arc()));

    return sum;
  }

public:

  typename Distance::Distance_Type operator () (GT & g)
  {
    return total_cost (g);
  }
};



} // end namespace Aleph

# endif // TPL_GRAPH_UTILS_H