Aleph-w: Algoritmos y estructuras de datos

---

Bellman_Ford.H

/*
  This file is part of Aleph-w system

  Copyright (c) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
  Leandro Rabindranath León
  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions are
  met: 
  1. Redistributions of source code must retain the above copyright 
     notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright 
     notice, this list of conditions and the following disclaimer in the 
     documentation and/or other materials provided with the distribution.
  3. All advertising materials mentioning features or use of this software
     must display the following acknowledgement:

     Copyright (c) 2002-2011 Leandro Rabindranath León. See details of 
     licence.     

     This product includes software developed by the Hewlett-Packard
     Company, Free Software Foundation and Silicon Graphics Computer
     Systems, Inc. 
  4. Neither the name of the <organization> nor the
     names of its contributors may be used to endorse or promote products
     derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ''AS IS'' AND ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

  Aleph-w 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.

  I request users of this software to return to 

  Leandro Rabindranath 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
  leandro.r.leon@gmail.com

  any improvements or extensions that they make and grant me the rights
  to redistribute these changes.  
*/

# ifndef BELLMAN_FORD_H
# define BELLMAN_FORD_H

# include <tpl_dynListQueue.H>
# include <tpl_avl.H>
# include <tpl_graph_utils.H>
# include <Tarjan.H>

namespace Aleph {
# define NI(p) (static_cast<Bellman_Ford_Node_Info<GT, Distance>*>(NODE_COOKIE(p)))
# define IDX(p) (NI(p)->idx)
# define ACU(p) (NI(p)->acum)

template <class GT, class Distance> struct Bellman_Ford_Node_Info
{
  int                              idx;
  typename Distance::Distance_Type acum;
};
template <class GT, class Distance, 
          class Compare = Aleph::less<typename Distance::Distance_Type>, 
          class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
          class SA      = Default_Show_Arc<GT> > inline
bool bellman_ford_min_spanning_tree(GT & g, typename GT::Node * start_node, 
                                    GT & tree) 
{
  if (not g.is_digraph())
    throw std::domain_error("Bellman-Ford algorithm only operates on digraphs");
  clear_graph(tree); // limpiar árbol abarcador destino 
  DynArray<typename GT::Node*> pred(g.get_num_nodes());
  DynArray<typename GT::Arc*>  arcs(g.get_num_nodes());
  {
    typename GT::Node_Iterator it(g);
    for (int i = 0; it.has_current(); ++i, it.next())
      {
        pred[i] = NULL; 
        arcs[i] = NULL;
        typename GT::Node * p = it.get_current_node();
        g.reset_bit(p, Aleph::Min); // colocar bit en cero
        Bellman_Ford_Node_Info <GT, Distance> * ptr = 
          new Bellman_Ford_Node_Info <GT, Distance>;
        ptr->idx  = i;                        
        ptr->acum = Distance::Max_Distance; // infinito
        NODE_BITS(p).set_bit(Min, false); 
        NODE_BITS(p).set_bit(Breadth_First, false); 
        NODE_COOKIE(p) = ptr;
    }
  }
  ACU(start_node) = Distance::Zero_Distance;
  g.reset_bit_arcs(Min); 
  for (int i = 0, n = g.get_num_nodes() - 1; i < n; ++i)
    for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next())
      {
        typename GT::Arc * arc  = it.get_current_arc();
        typename GT::Node * src = g.get_src_node(arc);
        typename GT::Node * tgt = g.get_tgt_node(arc);
        const typename Distance::Distance_Type & acum_src = ACU(src);
        if (acum_src == Distance::Max_Distance)
          continue;

        const typename Distance::Distance_Type & dist = Distance () (arc);
        typename Distance::Distance_Type & acum_tgt = ACU(tgt);
        const typename Distance::Distance_Type sum = Plus () (acum_src, dist);
        if (Compare () (sum, acum_tgt)) // ¿sum < acum_tgt?
          {
            const int & idx = IDX(tgt);
            pred[idx]       = src;
            arcs[idx]       = arc;
            acum_tgt        = sum;
          }
      }
  bool negative_cycle = false;
      // recorrer todos los arcos en búsqueda de un ciclo negativo
  for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next())
    {
      typename GT::Arc * arc  = it.get_current_arc();
      typename GT::Node * src = g.get_src_node(arc);
      const typename Distance::Distance_Type & acum_src = ACU(src);
      if (acum_src == Distance::Max_Distance)
        continue;

      typename GT::Node * tgt = g.get_tgt_node(arc);
      const typename Distance::Distance_Type & dist = Distance () (arc);
      typename Distance::Distance_Type & acum_tgt   = ACU(tgt);
      const typename Distance::Distance_Type sum    = Plus ()(acum_src, dist);

      if (Compare () (sum, acum_tgt)) // ¿se relaja arco?
        {     // sí ==> ciclo negativo!
          negative_cycle  = true; 
          const int & idx = IDX(tgt);
          pred[idx]       = src;
          arcs[idx]       = arc;
          acum_tgt        = sum;
        }
    }

      // liberar memoria de los cookies de los nodos
  for (Node_Iterator<GT> it(g); it.has_current(); it.next())
    {
      typename GT::Node * p = it.get_current_node();
      delete NI(p);
      NODE_COOKIE(p) = NULL;
    }

  if (negative_cycle) // ¿hay ciclos negativos?
    // liberar memoria de los cookies de los nodos y terminar

    {
          // liberar memoria de los cookies de los nodos
      for (Node_Iterator<GT> it(g); it.has_current(); it.next())
        {
          typename GT::Node * p = it.get_current_node();
          delete NI(p);
          NODE_COOKIE(p) = NULL;
        }
      return true;
    }

  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, Min))
        tsrc = mapped_node<GT> (gsrc);
      else
        {
          NODE_BITS(gsrc).set_bit(Min, true); // marcar bit
          delete NI(gsrc);
          tsrc = tree.insert_node(gsrc->get_info());
          GT::map_nodes(gsrc, tsrc);
        }

      typename GT::Node * gtgt = g.get_tgt_node(garc);
      typename GT::Node * ttgt = NULL;
      if (IS_NODE_VISITED(gtgt, Min))
        ttgt = mapped_node<GT> (gtgt);
      else
        {
          NODE_BITS(gtgt).set_bit(Min, true); // marcar bit
          delete NI(gtgt);
          ttgt = tree.insert_node(gtgt->get_info());
          GT::map_nodes(gtgt, ttgt);
        }
      typename GT::Arc * tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
      GT::map_arcs(garc, tarc);
      ARC_BITS(garc).set_bit(Min, true);
    }
  return false; // no hay ciclos negativos
}

    template <class GT> inline static 
void put_in_queue(DynListQueue<typename GT::Node*> & q, typename GT::Node * p)
{
  q.put(p);
  NODE_BITS(p).set_bit(Breadth_First, true); 
}
    template <class GT> inline static typename GT::Node * 
get_from_queue(DynListQueue<typename GT::Node*> & q)
{
  typename GT::Node * p = q.get();
  NODE_BITS(p).set_bit(Breadth_First, false);
  return p;
}
template <class GT> inline static bool is_in_queue(typename GT::Node * p)
{
  return IS_NODE_VISITED(p, Breadth_First);
}

template <class GT, class Distance, 
          class Compare = Aleph::less<typename Distance::Distance_Type>, 
          class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
          class SA      = Default_Show_Arc<GT> > inline
bool q_bellman_ford_min_spanning_tree(GT & g, typename GT::Node * start_node, 
                                      GT & tree)
{
  if (not g.is_digraph())
    throw std::domain_error("Bellman-Ford algorithm only operates on digraphs");
  clear_graph(tree); // limpiar árbol abarcador destino 
  DynArray<typename GT::Node*> pred(g.get_num_nodes());
  DynArray<typename GT::Arc*>  arcs(g.get_num_nodes());
  {
    typename GT::Node_Iterator it(g);
    for (int i = 0; it.has_current(); ++i, it.next())
      {
        pred[i] = NULL; 
        arcs[i] = NULL;
        typename GT::Node * p = it.get_current_node();
        g.reset_bit(p, Aleph::Min); // colocar bit en cero
        Bellman_Ford_Node_Info <GT, Distance> * ptr = 
          new Bellman_Ford_Node_Info <GT, Distance>;
        ptr->idx  = i;                        
        ptr->acum = Distance::Max_Distance; // infinito
        NODE_BITS(p).set_bit(Min, false); 
        NODE_BITS(p).set_bit(Breadth_First, false); 
        NODE_COOKIE(p) = ptr;
    }
  }
  ACU(start_node) = Distance::Zero_Distance;
  g.reset_bit_arcs(Min); 
  DynListQueue<typename GT::Node*> q;
  typename GT::Node __sentinel;
  typename GT::Node * sentinel = &__sentinel;
  put_in_queue <GT> (q, sentinel);
  put_in_queue <GT> (q, start_node);
  for (int i = 0, n = g.get_num_nodes() - 1; not q.is_empty(); )
    {
      typename GT::Node * src = get_from_queue <GT> (q); 
      if (src == sentinel) // ¿se saca el centinela?
        if (i++ == n) 
          break;
        else
          put_in_queue <GT> (q, sentinel);

          // recorrer y relajar arcos del nodo src
      for (Node_Arc_Iterator<GT, SA> it(src); it.has_current(); it.next()) 
        {
          typename GT::Arc * arc = it.get_current_arc();
          const typename Distance::Distance_Type & acum_src = ACU(src);
          if (acum_src == Distance::Max_Distance)
            continue;

          typename GT::Node * tgt = it.get_tgt_node();
          const typename Distance::Distance_Type & w = Distance () (arc);
          const typename Distance::Distance_Type sum_src = 
            Plus () (acum_src, w);
          typename Distance::Distance_Type & acum_tgt = ACU(tgt);
          if (Compare () (sum_src, acum_tgt)) // relajar arco
            {
              const int & idx = IDX(tgt);
              pred[idx]       = src;
              arcs[idx]       = arc;
              acum_tgt        = sum_src;
              if (not is_in_queue <GT> (tgt))
                put_in_queue <GT> (q, tgt);
            }
        }
    }
  bool negative_cycle = false;
      // recorrer todos los arcos en búsqueda de un ciclo negativo
  for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next())
    {
      typename GT::Arc * arc  = it.get_current_arc();
      typename GT::Node * src = g.get_src_node(arc);
      const typename Distance::Distance_Type & acum_src = ACU(src);
      if (acum_src == Distance::Max_Distance)
        continue;

      typename GT::Node * tgt = g.get_tgt_node(arc);
      const typename Distance::Distance_Type & dist = Distance () (arc);
      typename Distance::Distance_Type & acum_tgt   = ACU(tgt);
      const typename Distance::Distance_Type sum    = Plus ()(acum_src, dist);

      if (Compare () (sum, acum_tgt)) // ¿se relaja arco?
        {     // sí ==> ciclo negativo!
          negative_cycle  = true; 
          const int & idx = IDX(tgt);
          pred[idx]       = src;
          arcs[idx]       = arc;
          acum_tgt        = sum;
        }
    }

      // liberar memoria de los cookies de los nodos
  for (Node_Iterator<GT> it(g); it.has_current(); it.next())
    {
      typename GT::Node * p = it.get_current_node();
      delete NI(p);
      NODE_COOKIE(p) = NULL;
    }

  if (negative_cycle) // ¿hay ciclos negativos?
    // liberar memoria de los cookies de los nodos y terminar

    {
          // liberar memoria de los cookies de los nodos
      for (Node_Iterator<GT> it(g); it.has_current(); it.next())
        {
          typename GT::Node * p = it.get_current_node();
          delete NI(p);
          NODE_COOKIE(p) = NULL;
        }
      return true;
    }

  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, Min))
        tsrc = mapped_node<GT> (gsrc);
      else
        {
          NODE_BITS(gsrc).set_bit(Min, true); // marcar bit
          delete NI(gsrc);
          tsrc = tree.insert_node(gsrc->get_info());
          GT::map_nodes(gsrc, tsrc);
        }

      typename GT::Node * gtgt = g.get_tgt_node(garc);
      typename GT::Node * ttgt = NULL;
      if (IS_NODE_VISITED(gtgt, Min))
        ttgt = mapped_node<GT> (gtgt);
      else
        {
          NODE_BITS(gtgt).set_bit(Min, true); // marcar bit
          delete NI(gtgt);
          ttgt = tree.insert_node(gtgt->get_info());
          GT::map_nodes(gtgt, ttgt);
        }
      typename GT::Arc * tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
      GT::map_arcs(garc, tarc);
      ARC_BITS(garc).set_bit(Min, true);
    }
  return false; // no hay ciclos negativos
}
 template <class GT, class Distance, 
           class Compare = Aleph::less<typename Distance::Distance_Type>, 
           class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
           class SA      = Default_Show_Arc<GT> > 
class Bellman_Ford_Min_Spanning_Tree
{ 
public:

  bool operator () (GT & g, typename GT::Node * start_node, GT & tree)
  {
    return bellman_ford_min_spanning_tree <GT, Distance, Compare, Plus, SA>
      (g, start_node, tree);
  }
};

 template <class GT, class Distance, 
           class Compare = Aleph::less<typename Distance::Distance_Type>, 
           class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
           class SA      = Default_Show_Arc<GT> > 
class Q_Bellman_Ford_Min_Spanning_Tree
{ 
public:

  bool operator () (GT & g, typename GT::Node * start_node, GT & tree)
  {
    return q_bellman_ford_min_spanning_tree <GT, Distance, Compare, Plus, SA>
      (g, start_node, tree);
  }

      inline bool 
  has_negative_cycle(GT & g, typename GT::Node * s, Path<GT> & path) const;
};
     template <class GT>
bool search_cycle(GT & g, DynArray<typename GT::Node *> & pred,
                  DynArray<typename GT::Arc *>  & arcs, Path<GT> & cycle)
{
  const size_t & n = pred.size(); // cantidad de nodos de g
  DynMapAvlTree<typename GT::Node*, typename GT::Node*> nodes_table; 
  GT aux; 
  for (int i = 0; i < n; ++i) // insertar nodos en aux
    {
      typename GT::Node * p = pred.access(i);
      if (p == NULL or NODE_COOKIE(p) != NULL) // ¿insertado y mapeado?
        continue; // sí ==> avance al siguiente

      typename GT::Node * q = aux.insert_node(p->get_info());
      GT::map_nodes(p, q);
      nodes_table.insert(q, p);
    }

  for (int i = 0; i < n; ++i) // insertar arcos en aux
    {
      typename GT::Arc * a = arcs.access(i);
      if (a == NULL or ARC_COOKIE(a) != NULL)
        continue;

      typename GT::Node * gsrc = g.get_src_node(a);
      typename GT::Node * gtgt = g.get_tgt_node(a);
      if (NODE_COOKIE(gsrc) == NULL or NODE_COOKIE(gtgt) == NULL)
        continue; // src o tgt no está en pred ==> no en ciclo

      typename GT::Node * aux_src = mapped_node<GT> (gsrc);
      typename GT::Node * aux_tgt = mapped_node<GT> (gtgt);
      aux.insert_arc(aux_src, aux_tgt);
    }
  Path<GT> path; // buscar ciclo en aux mediante algo de Tarjan
  if (not Compute_Cycle_In_Digraph <GT> () (aux, path))
    return false; // no existe ciclo

  cycle.set_graph(g); // mapear ciclo en aux al camino cyle en g

  for (typename Path<GT>::Iterator it(path); it.has_current(); it.next())
    cycle.append(nodes_table[it.get_current_node()]);

  return true;
}

     template <class GT>
class Search_Cycle
{
public:

  bool operator () (GT &                            g, 
                    DynArray<typename GT::Node *> & pred,
                    DynArray<typename GT::Arc *>  & arcs,
                    Path<GT> &                      cycle) const
  {
    return search_cycle <GT> (g, pred, arcs, cycle);
  }
};

template <class GT, class Distance, 
          class Compare = Aleph::less<typename Distance::Distance_Type>, 
          class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
          class SA      = Default_Show_Arc<GT> > inline
bool bellman_ford_negative_cycle(GT & g, typename GT::Node * start_node,
                                 Path<GT> & cycle)
{
  GT tree; // árbol sobre el cual opera algoritmo de Bellman-Ford
  if (not g.is_digraph())
    throw std::domain_error("Bellman-Ford algorithm only operates on digraphs");
  clear_graph(tree); // limpiar árbol abarcador destino 
  DynArray<typename GT::Node*> pred(g.get_num_nodes());
  DynArray<typename GT::Arc*>  arcs(g.get_num_nodes());
  {
    typename GT::Node_Iterator it(g);
    for (int i = 0; it.has_current(); ++i, it.next())
      {
        pred[i] = NULL; 
        arcs[i] = NULL;
        typename GT::Node * p = it.get_current_node();
        g.reset_bit(p, Aleph::Min); // colocar bit en cero
        Bellman_Ford_Node_Info <GT, Distance> * ptr = 
          new Bellman_Ford_Node_Info <GT, Distance>;
        ptr->idx  = i;                        
        ptr->acum = Distance::Max_Distance; // infinito
        NODE_BITS(p).set_bit(Min, false); 
        NODE_BITS(p).set_bit(Breadth_First, false); 
        NODE_COOKIE(p) = ptr;
    }
  }
  ACU(start_node) = Distance::Zero_Distance;
  g.reset_bit_arcs(Min); 
  for (int i = 0, n = g.get_num_nodes() - 1; i < n; ++i)
    for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next())
      {
        typename GT::Arc * arc  = it.get_current_arc();
        typename GT::Node * src = g.get_src_node(arc);
        typename GT::Node * tgt = g.get_tgt_node(arc);
        const typename Distance::Distance_Type & acum_src = ACU(src);
        if (acum_src == Distance::Max_Distance)
          continue;

        const typename Distance::Distance_Type & dist = Distance () (arc);
        typename Distance::Distance_Type & acum_tgt = ACU(tgt);
        const typename Distance::Distance_Type sum = Plus () (acum_src, dist);
        if (Compare () (sum, acum_tgt)) // ¿sum < acum_tgt?
          {
            const int & idx = IDX(tgt);
            pred[idx]       = src;
            arcs[idx]       = arc;
            acum_tgt        = sum;
          }
      }
  bool negative_cycle = false;
      // recorrer todos los arcos en búsqueda de un ciclo negativo
  for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next())
    {
      typename GT::Arc * arc  = it.get_current_arc();
      typename GT::Node * src = g.get_src_node(arc);
      const typename Distance::Distance_Type & acum_src = ACU(src);
      if (acum_src == Distance::Max_Distance)
        continue;

      typename GT::Node * tgt = g.get_tgt_node(arc);
      const typename Distance::Distance_Type & dist = Distance () (arc);
      typename Distance::Distance_Type & acum_tgt   = ACU(tgt);
      const typename Distance::Distance_Type sum    = Plus ()(acum_src, dist);

      if (Compare () (sum, acum_tgt)) // ¿se relaja arco?
        {     // sí ==> ciclo negativo!
          negative_cycle  = true; 
          const int & idx = IDX(tgt);
          pred[idx]       = src;
          arcs[idx]       = arc;
          acum_tgt        = sum;
        }
    }

      // liberar memoria de los cookies de los nodos
  for (Node_Iterator<GT> it(g); it.has_current(); it.next())
    {
      typename GT::Node * p = it.get_current_node();
      delete NI(p);
      NODE_COOKIE(p) = NULL;
    }

  if (not negative_cycle)
    return false;

  Search_Cycle <GT> () (g, pred, arcs, cycle);

  return true;
}
template <class GT, class Distance, 
          class Compare = Aleph::less<typename Distance::Distance_Type>, 
          class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
          class SA      = Default_Show_Arc<GT> > inline
bool bellman_ford_negative_cycle(GT &                g, 
                                 typename GT::Node * start_node,
                                 GT &                tree,
                                 Path<GT> &          cycle)
{
  if (not g.is_digraph())
    throw std::domain_error("Bellman-Ford algorithm only operates on digraphs");
  clear_graph(tree); // limpiar árbol abarcador destino 
  DynArray<typename GT::Node*> pred(g.get_num_nodes());
  DynArray<typename GT::Arc*>  arcs(g.get_num_nodes());
  {
    typename GT::Node_Iterator it(g);
    for (int i = 0; it.has_current(); ++i, it.next())
      {
        pred[i] = NULL; 
        arcs[i] = NULL;
        typename GT::Node * p = it.get_current_node();
        g.reset_bit(p, Aleph::Min); // colocar bit en cero
        Bellman_Ford_Node_Info <GT, Distance> * ptr = 
          new Bellman_Ford_Node_Info <GT, Distance>;
        ptr->idx  = i;                        
        ptr->acum = Distance::Max_Distance; // infinito
        NODE_BITS(p).set_bit(Min, false); 
        NODE_BITS(p).set_bit(Breadth_First, false); 
        NODE_COOKIE(p) = ptr;
    }
  }
  ACU(start_node) = Distance::Zero_Distance;
  g.reset_bit_arcs(Min); 
  DynListQueue<typename GT::Node*> q;
  typename GT::Node __sentinel;
  typename GT::Node * sentinel = &__sentinel;
  put_in_queue <GT> (q, sentinel);
  put_in_queue <GT> (q, start_node);
  for (int i = 0, n = g.get_num_nodes() - 1; not q.is_empty(); )
    {
      typename GT::Node * src = get_from_queue <GT> (q); 
      if (src == sentinel) // ¿se saca el centinela?
        if (i++ == n) 
          break;
        else
          put_in_queue <GT> (q, sentinel);

          // recorrer y relajar arcos del nodo src
      for (Node_Arc_Iterator<GT, SA> it(src); it.has_current(); it.next()) 
        {
          typename GT::Arc * arc = it.get_current_arc();
          const typename Distance::Distance_Type & acum_src = ACU(src);
          if (acum_src == Distance::Max_Distance)
            continue;

          typename GT::Node * tgt = it.get_tgt_node();
          const typename Distance::Distance_Type & w = Distance () (arc);
          const typename Distance::Distance_Type sum_src = 
            Plus () (acum_src, w);
          typename Distance::Distance_Type & acum_tgt = ACU(tgt);
          if (Compare () (sum_src, acum_tgt)) // relajar arco
            {
              const int & idx = IDX(tgt);
              pred[idx]       = src;
              arcs[idx]       = arc;
              acum_tgt        = sum_src;
              if (not is_in_queue <GT> (tgt))
                put_in_queue <GT> (q, tgt);
            }
        }
    }
  bool negative_cycle = false;
      // recorrer todos los arcos en búsqueda de un ciclo negativo
  for (Arc_Iterator<GT, SA> it(g); it.has_current(); it.next())
    {
      typename GT::Arc * arc  = it.get_current_arc();
      typename GT::Node * src = g.get_src_node(arc);
      const typename Distance::Distance_Type & acum_src = ACU(src);
      if (acum_src == Distance::Max_Distance)
        continue;

      typename GT::Node * tgt = g.get_tgt_node(arc);
      const typename Distance::Distance_Type & dist = Distance () (arc);
      typename Distance::Distance_Type & acum_tgt   = ACU(tgt);
      const typename Distance::Distance_Type sum    = Plus ()(acum_src, dist);

      if (Compare () (sum, acum_tgt)) // ¿se relaja arco?
        {     // sí ==> ciclo negativo!
          negative_cycle  = true; 
          const int & idx = IDX(tgt);
          pred[idx]       = src;
          arcs[idx]       = arc;
          acum_tgt        = sum;
        }
    }
      // liberar memoria de los cookies de los nodos
  for (Node_Iterator<GT> it(g); it.has_current(); it.next())
    {
      typename GT::Node * p = it.get_current_node();
      delete NI(p);
      NODE_COOKIE(p) = NULL;
    }

  if (not negative_cycle)
        // liberar memoria de los cookies de los nodos
    for (Node_Iterator<GT> it(g); it.has_current(); it.next())
      {
        typename GT::Node * p = it.get_current_node();
        delete NI(p);
        NODE_COOKIE(p) = NULL;
      }
    {
      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, Min))
            tsrc = static_cast<typename GT::Node*>(NODE_COOKIE(gsrc));
          else
            {
              NODE_BITS(gsrc).set_bit(Min, true); // marcar bit
              delete NI(gsrc);
              tsrc = tree.insert_node(gsrc->get_info());
              GT::map_nodes(gsrc, tsrc);
            }

          typename GT::Node * gtgt = g.get_tgt_node(garc);
          typename GT::Node * ttgt = NULL;
          if (IS_NODE_VISITED(gtgt, Min))
            ttgt = static_cast<typename GT::Node*>(NODE_COOKIE(gtgt));
          else
            {
              NODE_BITS(gtgt).set_bit(Min, true); // marcar bit
              delete NI(gtgt);
              ttgt = tree.insert_node(gtgt->get_info());
              GT::map_nodes(gtgt, ttgt);
            }

          typename GT::Arc * tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
          GT::map_arcs(garc, tarc);
          ARC_BITS(garc).set_bit(Min, true);
        }
      return false; // no hay ciclos negativos
    }

  Search_Cycle <GT> () (g, pred, arcs, cycle);

  return true;
}
template <class GT, class Distance, 
          class Compare = Aleph::less<typename Distance::Distance_Type>, 
          class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
          class SA      = Default_Show_Arc<GT> > inline
bool bellman_ford_negative_cycle(GT & g, Path<GT> & cycle)
{
  DynDlist<DynDlist<typename GT::Node*> > blocks; 

  Tarjan_Connected_Components <GT, SA> () (g, blocks);

      // recorrer todos los bloques
  for (typename DynDlist<DynDlist<typename GT::Node*> >::Iterator 
         it(blocks); it.has_current(); it.next())
    {     
      DynDlist<typename GT::Node*> & block = it.get_current();
      if (block.size() == 1)
        continue;

      typename GT::Node * src = block.get_first(); // nodo inicio
      if (bellman_ford_negative_cycle<GT,Distance,Compare,Plus,SA>
          (g, src, cycle))
        return true;
    }
  return false;
}
 template <class GT, class Distance, 
           class Compare = Aleph::less<typename Distance::Distance_Type>, 
           class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
           class SA      = Default_Show_Arc<GT> > 
class Bellman_Ford_Negative_Cycle
{ 
public:

  bool operator () (GT & g, typename GT::Node * s, Path<GT> & path) const
  {
    return bellman_ford_negative_cycle <GT, Distance, Compare, Plus, SA>
      (g, s, path);
  }

      bool 
  operator () (GT & g, typename GT::Node * s, GT & tree, Path<GT> & path) const
  {
    return bellman_ford_negative_cycle <GT, Distance, Compare, Plus, SA>
      (g, s, tree, path);
  }

      bool 
  operator () (GT & g, Path<GT> & cycle) const
  {
    return
      bellman_ford_negative_cycle <GT, Distance, Compare, Plus, SA> (g, cycle);
  }
};

    template <class GT, class Distance, class Compare, class Plus, class SA> 
bool Q_Bellman_Ford_Min_Spanning_Tree
    <GT, Distance, Compare, Plus, SA>::
    has_negative_cycle(GT & g, typename GT::Node * s, Path<GT> & path) const
{
  return bellman_ford_negative_cycle <GT, Distance, Compare, Plus, SA>
    (g, s, path);
}

# undef NI
# undef IDX
# undef ACU
} // end namespace Aleph

# endif // BELLMAN_FORD_H

---