tpl_graph_utils.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef TPL_GRAPH_UTILS_H
# define TPL_GRAPH_UTILS_H

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

using namespace Aleph;

namespace Aleph {

      template <class GT> 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> inline 
  size_t depth_first_traversal(GT &                g, 
                               typename GT::Node * start_node,
                               bool (*visit)(GT & g, typename GT::Node *, 
                                             typename GT::Arc *) )
  {
    g.reset_bit_nodes(Depth_First); // reiniciar bit Depth_First de los nodos
    g.reset_bit_arcs(Depth_First);  // reiniciar bit Depth_First de los arcos

    size_t counter = 0; // inicialmente no se ha visitado ningún nodo

        // iniciar la exploración recursiva
    __depth_first_traversal <GT> (g, start_node, NULL, visit, counter);

    return counter;
  }
      template <class GT> inline 
  size_t depth_first_traversal(GT & g, 
                               bool (*visit)(GT &, typename GT::Node *, 
                                             typename GT::Arc *) )
  {
    
    return depth_first_traversal <GT> (g, g.get_first_node(), visit);
  }
      template <class GT> 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)
  {
    if (IS_NODE_VISITED(node, Depth_First)) // ¿Fue el nodo visitado?
      return false; // Sí ==> retorne y siga explorando

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

        // Aquí se visita el nodo mediante la función de visita

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


        // recorrer arcos de node y visitar recursivamente nodos conectados 
    for (typename GT::Node_Arc_Iterator it(node); it.has_current(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();

        if (IS_ARC_VISITED(arc, Depth_First)) // ¿Ya se pasó por este arco?
          continue; // sí ==> ignórelo y vea el siguiente

        ARC_BITS(arc).set_bit(Depth_First, true); // marca arco actual visitado

        if (__depth_first_traversal(g, it.get_tgt_node(), arc, visit, count))
          return true; // ya se exploró cabalmente it.get_tgt_node()
      }

    return false; // retorne y siga explorando
  }
      template <class 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); // reiniciar bit Breadth_First de nodos
    g.reset_bit_arcs(Breadth_First);  // reiniciar bit Breadth_First de arcos

    DynListQueue<typename GT::Arc*> q; // cola de arcos pendientes

        // ingresar a la cola los arcos de nodo start
    for (typename GT::Node_Arc_Iterator it(start); it.has_current(); it.next())
      q.put(it.get_current_arc());

    NODE_BITS(start).set_bit(Breadth_First, true); // marcar visitado start

    size_t node_counter = 0; // contador de nodos visitados

        // mientras queden arcos en la cola y no se hayan visitado todos
        // los nodos 
    while (not q.is_empty() and node_counter < g.get_num_nodes()) 
      {
        typename GT::Arc * arc = q.get(); // extraiga arco más cercano de la cola

        ARC_BITS(arc).set_bit(Breadth_First, true); // marcar arco

            // obtener nodos conectados al arco
        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; // si alguno de los nodos ha sido visitado entonces
                    // avanzamos al siguiente arco en la cola 

        typename GT::Node * visit_node = // seleccionar nodo a visitar
          IS_NODE_VISITED(src, Breadth_First) ? tgt : src;

             // Aquí se visita el nodo mediante la función de visita

        if (visit not_eq 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 (typename GT::Node_Arc_Iterator it(visit_node); 
             it.has_current(); it.next())
          {
            typename GT::Arc * curr_arc = it.get_current_arc();

            if (IS_ARC_VISITED(curr_arc, Breadth_First))
              continue; // ya fue previamente introducido desde el otro nodo

                // 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 ==> no vale la pena meter el arco

            q.put(curr_arc);
          }
      }

    return node_counter;
  }
      template <class GT> inline size_t
  breadth_first_traversal(GT &                g, 
                          bool (*visit)(GT &, typename GT::Node *, 
                                        typename GT::Arc *)
                          )
  {
    return breadth_first_traversal(g, g.get_first_node(), visit);
  }
      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)
  {
    auto_ptr<Path<GT> > path_auto;

    if (path_ptr == NULL)
      path_auto = // crear camino nuevo con origen en node
        auto_ptr<Path<GT> > ( new Path<GT> (g, node) );
    else
      path_auto = // crear copia de camino *path_ptr
        auto_ptr<Path<GT> > ( new Path<GT> (*path_ptr) );
    
    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> 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_bit_nodes(Find_Path);
    g.reset_bit_arcs(Find_Path); 

    DynListQueue<Path<GT>*> q; // cola de caminos parciales
    Path<GT> * path_ptr = NULL; 


    try
      { 

            // insertar los caminos parciales con nodo inicio start 
        for (typename GT::Node_Arc_Iterator i(start); i.has_current(); i.next())
          __insert_in_queue<GT>(g, q, start, i.get_current_arc());
        
        NODE_BITS(start).set_bit(Find_Path, true); // márquelo visitado

        while (not q.is_empty()) // repetir mientras haya arcos sin visitar
          {
            path_ptr = q.get(); // extraiga camino actual

            typename GT::Arc * arc = path_ptr->get_last_arc(); 

            ARC_BITS(arc).set_bit(Find_Path, true); // marcar arco

            typename GT::Node * tgt = path_ptr->get_last_node();
            
            if (IS_NODE_VISITED(tgt, Find_Path)) // ¿visitó último nodo de camino?
              {     // sí ==> el camino no conduce al nodo end ==> borrar camino
                delete path_ptr;
                continue;
              }

            if (tgt == end) // ¿se encontró un camino?
              {     // sí ==> path_ptr contiene el camino buscado
                path.swap(*path_ptr); // copiar resultado al parámetro path

                while (not q.is_empty())
                  delete q.get();

                delete path_ptr;

                return true;
              }

            NODE_BITS(tgt).set_bit(Find_Path, true); // marcar último nodo camino

                // insertar en cola arcos del nodo recién visitado
            for (typename GT::Node_Arc_Iterator i(tgt); i.has_current(); i.next())
              {
                typename GT::Arc * curr_arc = i.get_current_arc();

                if (IS_ARC_VISITED(curr_arc, Find_Path)) // ¿se visitó arco?
                  continue; // sí ==> avanzar al siguiente (ya fue visto)

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

                __insert_in_queue<GT>(g, q, NULL, curr_arc, path_ptr);
              }
        
            delete path_ptr; // borrar camino extraído de la cola
          } // fin while (not q.is_empty())

      }
    catch (...) // hay excepción 
      { 
        while (not q.is_empty())
          delete q.get(); // antes de propagar excepción

        delete path_ptr;

        throw; // propagar la excepción
      }


    while (not q.is_empty())
      delete q.get();

    delete path_ptr;

    return false;
  }
      template <class GT> inline 
  bool test_connectivity(GT & g)
  {
        // un grafo con menos arcos que nodos no puede ser conexo
    if (not g.is_digraph() and g.get_num_arcs() < g.get_num_nodes() - 1)
      return false;

    return depth_first_traversal <GT> (g, NULL) == g.get_num_nodes();
  }
      template <class 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_path(g, src, tgt);
  }
      template <class GT> inline static
  bool __test_cycle(GT &                g, 
                    typename GT::Node * src_node, 
                    typename GT::Node * curr_node);
      template <class GT> inline 
  bool test_cycle(GT & g, typename GT::Node * src_node)
  {
    g.reset_bit_nodes(Test_Cycle); // reiniciar bit Test_Cycle para los nodos
    g.reset_bit_arcs(Test_Cycle);  // reiniciar bit Test_Cycle para los arcos

        // explorar recursivamente a través de los arcos adyacentes a src_node
    for (typename GT::Node_Arc_Iterator 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
        
            // ¿se encuentra un ciclo por el arco arc?
        if (__test_cycle <GT> (g, src_node, it.get_tgt_node()))
          return true; // sí ==> retornar true y detener la exploración
      }
        // En este punto se han explorado todos los caminos desde src_node
        // sin encontrar de nuevo a src_node ==> no existe ciclo 
    return false;
  }
      template <class GT> inline static
  bool __test_cycle(GT &                g, 
                    typename GT::Node * src_node, 
                    typename GT::Node * curr_node)
  {
    if (src_node == curr_node) // verificar si se alcanza nodo origen 
      return true; // ciclo detectado

    if (IS_NODE_VISITED(curr_node, Test_Cycle))
      return false; // ya se visitó este nodo 

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

        // busque los caminos desde current_node a ver si llega a src_node 
    for (typename GT::Node_Arc_Iterator it(curr_node); it.has_current(); 
         it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();

        if (IS_ARC_VISITED(arc, Test_Cycle)) // se pasó por este arco?
          continue; // sí ==> ignorar y ver el próximo 

        ARC_BITS(arc).set_bit(Test_Cycle, true); // marque arco
            
        if (__test_cycle <GT> (g, src_node, it.get_tgt_node()))
          return true; // ciclo encontrado desde el arco actual 
      }
        // En este punto se han explorado todos los caminos desde curr_node
        // sin encontrar src_node ==> no existe ciclo que pase por curr_node  
    return false; 
  }  
      template <typename GT> inline static
  bool __is_acyclique(GT & g, typename GT::Node * curr_node)
  {
    if (IS_NODE_VISITED(curr_node, Is_Acyclique)) // ¿ha sido el nodo visitado?
      return false; // sí ==> se regresa desde arco no visitado ==> ciclo!

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

        // recorremos en profundidad curr_node 
    for (typename GT::Node_Arc_Iterator i(curr_node); i.has_current(); i.next())
      {
        typename GT::Arc * arc = i.get_current_arc();

        if (IS_ARC_VISITED(arc, Is_Acyclique)) 
          continue; // arco ya visitado, pase al siguiente

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

            // ¿se detectó ciclo pasando por curr_node?
        if (not __is_acyclique(g, i.get_tgt_node()))
          return false; // sí ==> detenemos ejecución porque sabemos respuesta
      }
        // todos los arcos recorridos sin encontrar ciclo ==> el grafo es
        // acíclico pasando por curr_node
    return true; 
  }
      template <typename GT> inline 
  bool is_acyclique(GT & g, typename GT::Node * start_node)
  {
    if (not g.is_digraph() and g.get_num_arcs() >= g.get_num_nodes())
      return false; 

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

    return __is_acyclique(g, start_node);
  }    template <typename GT> inline 
  bool is_acyclique(GT & g)
  {
    if (not g.is_digraph() and g.get_num_arcs() >= g.get_num_nodes())
      return false; 

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

        // recorrer todos los nodos
    for (typename GT::Node_Iterator 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; // nodo ya probado, avance al siguiente
        
            // ¿es acíclico desde current_node?
        if (not __is_acyclique(g, current_node)) 
          return false; // sí ==>
      }
    return true;
  }
  template <typename GT> inline bool has_cycle(GT & g)
  {
    return not is_acyclique(g);
  }
      template <class GT> inline static
  bool __test_path(GT&                 g, 
                   typename GT::Node * curr_node,  // nodo procedencia
                   typename GT::Node * end_node);  // arco destino
      template <class GT> inline 
  bool test_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);  // reiniciar bit Test_Path para nodos y arcos
    g.reset_bit_arcs(Test_Path);

        // buscar recursivamente caminos por arcos adyacentes a start_node
    for (typename GT::Node_Arc_Iterator 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

            // ¿existe camino hasta end_node pasando por arc?
        if (__test_path(g, i.get_tgt_node(), end_node))
          return true; // sí, retornar 
      }
        // todos los arcos de start_node han sido explorados sin encontrar un
        // camino hasta end_node ==> no existe camino
    return false;
  }
      template <class GT> inline static
  bool __test_path(GT &                g, 
                   typename GT::Node * curr_node, // nodo procedencia
                   typename GT::Node * end_node)  // arco destino
  {
    if (curr_node == end_node) // ¿se encontró end_node?
      return true; // sí ==> existe camino; retornar true

    if (IS_NODE_VISITED(curr_node, Test_Path)) // ¿Ya 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 (typename GT::Node_Arc_Iterator i(curr_node); i.has_current(); i.next())
      {
        typename GT::Arc * arc = i.get_current_arc();
        
        if (IS_ARC_VISITED(arc, Test_Path)) // ¿Ya se vio este arco?
          continue; // sí, ignórelo y siga al siguiente 

        ARC_BITS(arc).set_bit(Test_Path, true); // pintar arco
        
            // buscar camino por el arco actual arc 
        if (__test_path <GT> (g, i.get_tgt_node(), end_node))
          return true;
      }
        // todos los arcos adyacente de curr_node fueron explorados sin
        // encontrar a end_node ==> no existe camino pasando por curr_node
    return false;
  }
      template <class GT> inline 
  void inconnected_components(GT & g, DynDlist<GT> & list);
      template <class GT> inline 
  void build_subgraph(GT &                g,           // grafo original
                      GT &                sg,          // componente inconexo
                      typename GT::Node * g_src,       // nodo actual en g
                      size_t &            node_count); // contador de nodos
      template <class GT> inline 
  void inconnected_components(GT & g, DynDlist <GT> & list)
  {
    g.reset_nodes(); 
    g.reset_arcs();  

    size_t count = 0; // contador de nodos visitados

        // Recorrer todos los nodos de g
    for (typename GT::Node_Iterator i(g);
         count < g.get_num_nodes() and i.has_current(); i.next())
      {
        typename GT::Node * curr_node = i.get_current_node();

        if (IS_NODE_VISITED(curr_node, Build_Subtree))
          continue;; // nodo ya fue visitado en otro recorrido, avance al próximo

            // crear subgrafo donde se colocará el componente inconexo que se
            // descubrirá a partir de curr_node 
        list.append(GT()); // crea subgrafo y lo inserta en lista

        GT & subgraph = list.get_last(); // obtiene una referencia al grafo
                                         // recién creado e insertado en list

            // construir subgrafo conexo a partir de curr_node
        build_subgraph(g, subgraph, curr_node, count); 
      }
  }
      template <class GT> inline 
  void build_subgraph(GT &                g,      // grafo original
                      GT &                sg,     // subgrafo componente inconexo
                      typename GT::Node * g_src,  // nodo actual en g
                      size_t &            node_count)
  {

    if (sg.get_num_nodes() != 0)
      throw std::domain_error("sg is not empty");

    if (IS_NODE_VISITED(g_src, Build_Subtree))
      return;

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

    typename GT::Node * sg_src =  // obtener imagen de g_src en sg
      static_cast<typename GT::Node *>(NODE_COOKIE(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);
      }

        // explore en profundidad a partir de g_src 
    for (typename GT::Node_Arc_Iterator i(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 a próximo arco

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

            // ahora observe el nodo destino del arco
        typename GT::Node * g_tgt  = i.get_tgt_node();  
        typename GT::Node * sg_tgt = 
          static_cast<typename GT::Node *>(NODE_COOKIE(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 los nodos en el subgrafo, insertamos el arco
        typename GT::Arc * sg_arc = 
          sg.insert_arc(sg_src, sg_tgt, arc->get_info());

        GT::map_arcs(arc, sg_arc); 
        
            // continue recorriendo en profundidad y construyendo el subgrafo
        build_subgraph(g, sg, g_tgt, node_count);
      }
  }
      template <class GT> inline 
  void strongly_connected_components(GT & g, DynDlist <GT> & list)
  {

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

    inconnected_components(g, list);
  }
      template <class GT> inline
  bool find_depth_first_spanning_tree(GT &                g, 
                                      typename GT::Node * gnode, 
                                      GT &                tree)
  {
    g.reset_nodes();
    g.reset_arcs(); 

    tree.clear_graph(); // asegurar que árbol destino esté vacío

    NODE_BITS(gnode).set_bit(Spanning_Tree, true); // marcar gnode

        // crear imagen de start_node en árbol abarcador y mapearla
    typename GT::Node * tnode = tree.insert_node(gnode->get_info());
    GT::map_nodes(gnode, tnode);
    for (typename GT::Node_Arc_Iterator 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; // nodo destino también ya ha sido visitado desde otro arco

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

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

    if (not find_depth_first_spanning_tree(g, start_node, tree))
      return NULL;

    return start_node;
  }
      template <class GT> 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

        // insertar tgt_node en árbol y mapearlo
    typename GT::Node * tree_tgt_node = tree.insert_node(gnode->get_info());
    GT::map_nodes(gnode, tree_tgt_node);

        // insertar arc en árbol y mapearlo
    typename GT::Arc * tarc = 
      tree.insert_arc(tnode, tree_tgt_node, garc->get_info()); 
    GT::map_arcs(garc, tarc);

    tnode = tree_tgt_node; // esto hace que el bloque de recorrido sea el mismo
    
    if (tree.get_num_nodes() == g.get_num_nodes()) // ¿se ha abarcado el grafo?
      return true; // tree ya contiene el árbol abarcador


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

    for (typename GT::Node_Arc_Iterator 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; // nodo destino también ya ha sido visitado desde otro arco

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

    return false;
  }
      template <class GT> inline
  void find_breadth_first_spanning_tree(GT &                g, 
                                        typename GT::Node * gnode, 
                                        GT &                tree)
  {
    g.reset_bit_nodes(Spanning_Tree);
    g.reset_bit_arcs(Spanning_Tree);

        // inicialice árbol e inserte copia mapeada de gnode
    tree.clear_graph();
    auto_ptr<typename GT::Node> tnode_auto (new typename GT::Node(gnode));
    tree.insert_node(tnode_auto.get());
    GT::map_nodes(gnode, tnode_auto.release());

        // recorra arcos de gnode e insértelos en cola
    DynListQueue<typename GT::Arc*> q;
    for (typename GT::Node_Arc_Iterator i(gnode); i.has_current(); i.next())
      q.put(i.get_current_arc());

    NODE_BITS(gnode).set_bit(Spanning_Tree, true); // marque visitado gnode

    while (not q.is_empty()) // repita mientras queden arcos en la cola
      {
        typename GT::Arc * garc = q.get();

        ARC_BITS(garc).set_bit(Spanning_Tree, true); // marque visitado garc

            // obtenga nodos del arco en g garc
        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 del arco ya fueron visitados

            // decidir cual es el nodo ya marcado y mapeado
        if (IS_NODE_VISITED(gtgt, Spanning_Tree)) // ¿es gtgt?
          Aleph::swap(gsrc, gtgt); // sí, intercámbielo con gsrc
          
        typename GT::Node * tsrc = // obtener imagen de gsrc en tree
          static_cast<typename GT::Node*>(NODE_COOKIE(gsrc));

        NODE_BITS(gtgt).set_bit(Spanning_Tree, true); // marque gtgt visitado

            // crear copia de gtgt, insertarlo en tree y mapearlo
        auto_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()) // ¿tree abarca a g?
          break; // sí, terminar

            // insertar en cola arcos de gtgt
        for (typename GT::Node_Arc_Iterator 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; // ya fue previamente introducido desde el otro nodo

                // 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 vale la pena meter el arco

            q.put(current_arc);
          }
      }
  }
  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 <typename 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 <typename GT> 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 <typename GT>
  void compute_cut_nodes(GT &                            g, 
                         typename GT::Node *             start,
                         DynDlist<typename GT::Node *> & list)
  {
    g.template operate_on_nodes <Init_Low <GT> > ();
    g.reset_arcs();

    long current_df = 0; // contador global de visitas 

    NODE_BITS(start).set_bit(Depth_First, true); // pintar visitado start
    df <GT> (start) = current_df++;
      
    int call_counter = 0; // contador de llamadas recursivas
        // Recorra los arcos de start mientras g no haya sido abarcado
    for (typename GT::Node_Arc_Iterator 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(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 <typename GT> 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 como visitado
    low <GT> (p) = df <GT> (p) = curr_df++; // asígnele df

        // Recorrer recursivamente arcos de p mientras g no haya sido abarcado
    bool p_is_cut_node = false;
    for (typename GT::Node_Arc_Iterator i(p); i.has_current(); i.next())
      {
        typename GT::Arc * arc = i.get_current_arc();
   
        if (arc == a) // ¿es el arco del padre? 
          continue; // sí ==> avance al siguiente arco

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

            continue;
          }

        if (IS_ARC_VISITED(arc, Depth_First)) // ¿arco ya visitado?
          continue; // sí ==> avance al siguiente

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

        __compute_cut_nodes(g, list, tgt, arc, curr_df);

        if (low <GT> (tgt) < low <GT> (p)) // verificar hijo de p - low(tgt) 
          low <GT> (p) = low <GT> (tgt); // actualizar low(p)

            // detección de nodo de corte
        if (low <GT> (tgt) >= df <GT> (p) and df <GT> (tgt) != 0)
          p_is_cut_node = true;
      }
        // p fue explorado recursivamente
    if (p_is_cut_node)
      {
        NODE_BITS(p).set_bit(Cut, true);
        list.append(p);
      }
  }
      template <typename GT>
  void compute_cut_nodes(GT &                            g, 
                         DynDlist<typename GT::Node *> & list)
  {
    compute_cut_nodes(g, g.get_first_node(), list);
  }
  const long Cross_Arc = -1;
      template <typename GT> inline static 
  bool is_a_cross_arc(typename GT::Arc * a)
  {
    return ARC_COUNTER(a) == Cross_Arc;
  }
     template <typename GT> inline static 
  bool is_a_cut_node(typename GT::Node * p)
  {
    return NODE_BITS(p).get_bit(Cut);
  }

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

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

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

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

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

      template <typename GT> inline static 
  const long & get_color(typename GT::Arc * a)
  {
    return ARC_COUNTER(a);
  }
      template <typename GT> inline static
  void __paint_subgraph(typename GT::Node * p, // Nodo actual
                        typename GT::Arc *  a, // Arco que conduce a p
                        const long &        current_color)
  {
    if (is_a_cut_node  <GT>  (p)) // ¿es un nodo de corte?
      return; // Sí, ignórelo
   
    paint_arc <GT> (a, current_color); 

    if (is_node_painted <GT> (p)) // ¿ya está el nodo pintado?
      return; // Sí, ignórelo

    paint_node <GT> (p, current_color);

        // recorrer y pintar recursivamente el bloque a través de arcos de p
    for (typename GT::Node_Arc_Iterator it(p); it.has_current(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();

        if (is_arc_painted <GT> (arc)) 
          continue;

        __paint_subgraph <GT> (it.get_tgt_node(), arc, current_color);
      }
  }
      template <typename GT> inline static
  void __paint_subgraph(typename GT::Node * p, // Nodo de inicio
                        const long &        current_color)
  {

    I(not is_a_cut_node <GT> (p) and not is_node_painted <GT> (p));

    paint_node <GT> (p, current_color);

    for (typename GT::Node_Arc_Iterator it(p); it.has_current(); it.next())
      {
        typename GT::Arc * arc = it.get_current_arc();

        if (is_arc_painted <GT> (arc)) 
          continue;

            // recorrer y pintar recursivamente el bloque a través de arcos de p
        __paint_subgraph <GT> (it.get_tgt_node(), arc, current_color);
      }
  }
      template <typename GT> inline static
  void __paint_from_cut_node(typename GT::Node *           p, // un nodo de corte
                             long &                        current_color)
  {

    I(is_a_cut_node <GT> (p));

        // pintar recursivamente con distintos colores los bloques conectados a p
    for (typename GT::Node_Arc_Iterator 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 arco como de corte
            continue; // avance a próximo arco
          }
        else 
          {
            paint_arc <GT> (arc, Cross_Arc); // marque arco como de cruce

            if (is_node_painted <GT> (tgt_node)) // ¿pintado el nodo destino?
              continue; // sí, avanzar entonces al próximo arco
          }

            // pintar recursivamente con current_color el nodo conectado a arc
            // (que no es ni de corte ni de cruce) 
        __paint_subgraph <GT> (tgt_node, current_color);

            // cambiar color (siguiente arco que se visite pertenece a
            // otro bloque 
        current_color++; 

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

      }
  }
      template <typename 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> (i.get_current(), current_color);

    return current_color;
  }
      template <typename GT> inline static
  void __map_subgraph(GT &                g,    // grafo con ptos de corte
                      GT &                sg,   // subgrafo donde se copia bloque
                      typename GT::Node * gsrc, // nodo de g ya copiado en sg
                      const long &        color)
  {

    I(get_color <GT> (gsrc) == color);
    I(NODE_COOKIE(gsrc) != NULL);

    typename GT::Node * tsrc = // obtener imagen de gsrc en sg
      static_cast<typename GT::Node*>(NODE_COOKIE(gsrc));

        // recorrer arcos de gsrc y añadir a sg aquellos con el color de interés
    for (typename GT::Node_Arc_Iterator 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); // marque arco

        typename GT::Node * gtgt = i.get_tgt_node(); // nodo destino de garc


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

            // obtener imagen de gtgt en sg
        typename GT::Node * ttgt = NULL;
        if (IS_NODE_VISITED(gtgt, Build_Subtree)) // ¿gtgt ya está en sg?
          ttgt = static_cast<typename GT::Node*>(NODE_COOKIE(gtgt)); // sí
        else
          {     // gtgt no está en sg ==> copiarlo y mapearlo
            auto_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); // marque gtgt

            ttgt = ttgt_auto.release(); 
          }

            // copiar y mapear arco en sg
        typename GT::Arc * tarc = sg.insert_arc(tsrc, ttgt, garc->get_info());
        GT::map_arcs(garc, tarc);
        
        __map_subgraph(g, sg, gtgt, color); // proseguir recursivamente con gtgt
      }
  }
      template <typename GT>
  void map_subgraph(GT & g, GT & sg, const long & color)
  {
    sg.clear_graph();

        // busque el primer nodo con el color
    typename GT::Node * first = NULL;
    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
    auto_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); // márquelo visitado


    try
      {    

        __map_subgraph(g, sg, first, color); // mapee recursivamente desde first

      }
    catch (...)
      {
        sg.clear_graph();
      }

  }
      template <typename GT>
  void map_cut_graph(GT &                           g, 
                     DynDlist<typename GT::Node*> & cut_node_list,
                     GT &                           cut_graph,
                     DynDlist<typename GT::Arc*> &  cross_arc_list)
  {
    cut_graph.clear_graph();

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

        I (is_a_cut_node <GT> (gp));


        auto_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 los arcos; inserte en sg los que no sean de corte, en
        // cut_arc_list los que sean de corte y en cross_arc_list los que
        // sean de cruce    
    for (typename GT::Arc_Iterator 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 = 
          static_cast<typename GT::Node*>(NODE_COOKIE(g.get_src_node(garc)));

        typename GT::Node * tgt = 
          static_cast<typename GT::Node*>(NODE_COOKIE(g.get_tgt_node(garc)));


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

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

        GT::map_arcs(garc, cut_arc);
      }
  }
    template <class GT, class Distance, class Compare> 
  struct Distance_Compare
  {
    bool operator () (typename GT::Arc * a1, typename GT::Arc * a2) const
    {
      return Compare () (Distance() (a1) , Distance() (a2) );
    }
  };
      template <class GT, class Distance, class Compare, class Plus>
  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 (typename GT::Arc_Iterator it(g); it.has_current(); it.next())
      sum = Plus () (sum, Distance () (it.get_current_arc()));

    return sum;
  }
      template <class GT, class Distance>
  typename Distance::Distance_Type total_cost(GT & g)
  {
    typedef Aleph::less<typename Distance::Distance_Type> Less;
    typedef Aleph::plus<typename Distance::Distance_Type> Plus;

    return total_cost <GT, Distance, Less, Plus> (g);
  }
     template <class GT> static inline
  void __topological_sort(GT &                           g, 
                          typename GT::Node *            curr,
                          DynDlist<typename GT::Node*> & list)
  {
    if (IS_NODE_VISITED(curr, Depth_First)) 
      return;

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

        // visitar recursivamente en sufijo los nodos adyacentes a curr
    for (typename GT::Arc_Node_Iterator it(g, curr); 
         it.has_current() and list.size() < g.get_num_nodes(); it.next()) 
      __topological_sort(g, it.get_tgt_node(), list);
    
    list.insert(curr); // inserción en sufijo de un nodo que devino sumidero
  }
     template <class GT> inline
  void topological_sort(GT & g, DynDlist<typename GT::Node*> & list)
  {

    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

    for (typename GT::Node_Iterator it(g); 
         it.has_current() and list.size() < g.get_num_nodes(); it.next())
      {
        typename GT::Node * curr = it.get_current_node();

        if (not IS_NODE_VISITED(curr, Depth_First))
          __topological_sort(g, curr, list);
      }
  }
     template <class GT> inline
  void q_topological_sort(GT & g, DynDlist<typename GT::Node*> & list)
  {

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

    g.reset_counter_nodes();

        // recorra todos los nodos para contabilizar su grado de entrada
    for (typename GT::Node_Iterator it(g); it.has_current(); it.next()) 
      NODE_COUNTER(it.get_current_node())++;

    DynListQueue<typename GT::Node*> q; // cola de fuentes

        // revisar cuáles nodos tienen grado de entrada 0; esos son fuente
    for (typename GT::Node_Iterator it(g); it.has_current(); 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 nodo 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 (typename GT::Node_Arc_Iterator it(g, p); it.has_current(); it.next())
          {
            typename GT::Node * tgt = it.get_tgt_node();
            
            if (--NODE_COUNTER(tgt) == 0) // ¿tgt deviene nodo fuente?
              q.put(tgt); // sí ==> colóquelo en la cola
          }
      }
  }

} // end namespace Aleph

# endif // TPL_GRAPH_UTILS_H

---