Bellman_Ford.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 BELLMAN_FORD_H
# define BELLMAN_FORD_H

# include <tpl_dynListQueue.H>
# include <tpl_graph.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, class Plus> 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");
  tree.clear_graph(); // limpiar árbol abarcador destino 
  DynArray<typename GT::Node*> pred;
  DynArray<typename GT::Arc*> arcs;
  {
    typename GT::Node_Iterator it(g);

    for (int i = 0; it.has_current(); ++i, it.next())
      {
        typename GT::Node * p = it.get_current_node();

        pred[i] = NULL; 
        arcs[i] = NULL;

        g.reset_bit(p, Aleph::Min); // colocar bit en cero

            // apartar memoria para cookie (índice y acumulado en distancia)
        Bellman_Ford_Node_Info <GT, Distance> * ptr = 
          new Bellman_Ford_Node_Info <GT, Distance>;

        NODE_BITS(p).set_bit(Min, false); 
        NODE_BITS(p).set_bit(Breadth_First, false); 
        NODE_COOKIE(p) = ptr;

            // inicializar campos del cookie
        ptr->idx  = i;
        ptr->acum = Distance::Max_Distance;
    }
  }
  ACU(start_node) = Distance::Zero_Distance;
  g.reset_bit_arcs(Min); 
  for (int i = 0, n = g.get_num_nodes() - 1; i < n; ++i)
        // recorrer los arcos para evaluar si relajamiento
    for (typename GT::Arc_Iterator 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 & dist =  Distance () (arc);

        const typename Distance::Distance_Type & acum_src = ACU(src);

        typename Distance::Distance_Type & acum_tgt = ACU(tgt);

        const typename Distance::Distance_Type sum = Plus () (acum_src, dist);

        if (Compare() (sum, acum_tgt))
          {
            const int & idx = IDX(tgt);

            pred[idx] = src;
            arcs[idx] = arc;
            acum_tgt  = sum;
          }
      }
  bool ret_val = true;

      // recorrer todos los arcos en búsqueda de un ciclo negativo
  for (typename GT::Arc_Iterator 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 & dist     = Distance () (arc);
      const typename Distance::Distance_Type & acum_src = ACU(src);
      const typename Distance::Distance_Type & acum_tgt = ACU(tgt);
      const typename Distance::Distance_Type sum        = Plus ()(acum_src, dist);

      if (Compare() (sum, acum_tgt)) // ¿lograría modificarse tgt?
        {
          ret_val = false; // se detectó un ciclo negativo
          break;
        }
    }
  if (not ret_val) // ¿hay ciclos negativos?
    {    // liberar memoria de los cookies de los nodos
      for (typename GT::Node_Iterator it(g); it.has_current(); it.next())
        delete NI(it.get_current_node());

      return false;
    }
  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 true; // 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, class Plus> 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");
  tree.clear_graph(); // limpiar árbol abarcador destino 
  DynArray<typename GT::Node*> pred;
  DynArray<typename GT::Arc*> arcs;
  {
    typename GT::Node_Iterator it(g);

    for (int i = 0; it.has_current(); ++i, it.next())
      {
        typename GT::Node * p = it.get_current_node();

        pred[i] = NULL; 
        arcs[i] = NULL;

        g.reset_bit(p, Aleph::Min); // colocar bit en cero

            // apartar memoria para cookie (índice y acumulado en distancia)
        Bellman_Ford_Node_Info <GT, Distance> * ptr = 
          new Bellman_Ford_Node_Info <GT, Distance>;

        NODE_BITS(p).set_bit(Min, false); 
        NODE_BITS(p).set_bit(Breadth_First, false); 
        NODE_COOKIE(p) = ptr;

            // inicializar campos del cookie
        ptr->idx  = i;
        ptr->acum = Distance::Max_Distance;
    }
  }
  ACU(start_node) = Distance::Zero_Distance;
  g.reset_bit_arcs(Min); 
  DynListQueue<typename GT::Node*> q;
  put_in_queue <GT> (q, start_node);
  for (int i = 0, n = (g.get_num_nodes() - 1)*g.get_num_arcs(); 
       (not q.is_empty()) and i < n; // cola no vacía y no más de V.E arcos
       /* nothing */)
    {
      typename GT::Node * src = get_from_queue <GT> (q);

          // recorrer y relajar arcos del nodo src
      for (typename GT::Node_Arc_Iterator it(src); 
           it.has_current() and i < n; // haya arco y no más de V.E arcos
           it.next(), ++i) // avanza a siguiente arco de nodo y cuenta arco
        {
          typename GT::Arc * arc = it.get_current_arc();

          typename GT::Node * tgt = it.get_tgt_node();

          const typename Distance::Distance_Type & acum_src = ACU(src);

          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);

              // relajar arco
          if (Compare () (sum_src, acum_tgt)) // acum_src < acum_tgt 
            {
              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 ret_val = true;

      // recorrer todos los arcos en búsqueda de un ciclo negativo
  for (typename GT::Arc_Iterator 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 & dist     = Distance () (arc);
      const typename Distance::Distance_Type & acum_src = ACU(src);
      const typename Distance::Distance_Type & acum_tgt = ACU(tgt);
      const typename Distance::Distance_Type sum        = Plus ()(acum_src, dist);

      if (Compare() (sum, acum_tgt)) // ¿lograría modificarse tgt?
        {
          ret_val = false; // se detectó un ciclo negativo
          break;
        }
    }
  if (not ret_val) // ¿hay ciclos negativos?
    {    // liberar memoria de los cookies de los nodos
      for (typename GT::Node_Iterator it(g); it.has_current(); it.next())
        delete NI(it.get_current_node());

      return false;
    }
  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 true; // no hay ciclos negativos
}
    template <class GT, class Distance> inline
bool bellman_ford_min_spanning_tree(GT &                g,
                                    typename GT::Node * start_node, 
                                    GT &                tree)
{
  return bellman_ford_min_spanning_tree
    <GT, Distance, Aleph::less<typename Distance::Distance_Type>,
     Aleph::plus<typename Distance::Distance_Type> > (g, start_node, tree);
}

    template <class GT, class Distance> inline
bool q_bellman_ford_min_spanning_tree(GT &                g,
                                      typename GT::Node * start_node, 
                                      GT &                tree)
{
  return q_bellman_ford_min_spanning_tree
    <GT, Distance, Aleph::less<typename Distance::Distance_Type>,
     Aleph::plus<typename Distance::Distance_Type> > (g, start_node, tree);
}

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

# endif // BELLMAN_FORD_H

---