Floyd.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 FLOYD_H
# define FLOYD_H

# include <ahFunction.H>
# include <tpl_matgraph.H>

namespace Aleph
{

    template <class GT, class Distance, class Compare, class Plus> 
void floyd_all_shortest_paths 
  (GT &                                            g, 
   Ady_Mat<GT, typename Distance::Distance_Type> & dist,
   Ady_Mat<GT, long> &                             path);
    template <class GT, class Distance> 
void floyd_all_shortest_paths
  (GT &                                            g, 
   Ady_Mat<GT, typename Distance::Distance_Type> & dist, 
   Ady_Mat<GT, long> &                             path)
{
  typedef typename Distance::Distance_Type Dist_T;

  floyd_all_shortest_paths
    <GT, Distance, Aleph::less<Dist_T>, Aleph::plus<Dist_T> > (g, dist, path);
}
    template <class AM, class Distance>
struct Initialize_Dist_Floyd
{
  typedef typename AM::List_Graph_Type::Arc_Type Arc_Type;
  typedef typename AM::List_Graph_Type GT;
  typedef typename GT::Node Node;
  typedef typename GT::Arc Arc;
  typedef typename Distance::Distance_Type Distance_Type;

      // inicializa cada entrada de la matriz
  void operator () (AM & mat, 
                    Node * src, Node * tgt,
                    const long & i, const long & j,
                    Distance_Type & entry,
                    void *          p)
  {
    Ady_Mat <typename AM::List_Graph_Type, long> & path = 
      * reinterpret_cast <Ady_Mat <typename AM::List_Graph_Type, long> *> (p);

    if (i == j) // ¿es diagonal de la matriz?
      {    // sí ==> la distancia es cero
        entry = Distance::Zero_Distance;
        path(i, j) = j;
        return;
      }
    
    GT & g = mat.get_list_graph();

    Arc * arc = g.search_arc(src, tgt); // arco en representación con listas 

    if (arc == NULL) // ¿existe un arco?
      {    // sí ==> se coloca coste infinito
        entry = Distance::Max_Distance;
        return;
      }
        // existe arco ==> extraiga distancia 
    entry = Distance () (arc); // la coloca en cost(i, j)
    path(i, j) = j; // coloca camino directo
  }
};
    template <class GT, typename Distance, class Compare, class Plus> 
void floyd_all_shortest_paths
  (GT &                                            g, 
   Ady_Mat<GT, typename Distance::Distance_Type> & dist, 
   Ady_Mat<GT, long> &                             path)
{
  typedef typename Distance::Distance_Type Dist_Type;
  typedef Ady_Mat <GT, Dist_Type> Dist_Mat;

  dist.template operate_all_arcs_matrix 
    <Initialize_Dist_Floyd <Dist_Mat, Distance> > (&path);
  const Dist_Type & max = Distance::Max_Distance;
  const long & n = g.get_num_nodes();
  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      if (dist(i, k) < max) // ¿es posible encontrar una distancia menor?
        for (int j = 0; j < n; ++j)
          {    // calcule nueva distancia pasando por k
            Dist_Type new_dist = Plus () (dist(i, k), dist(k, j));
            
            if (Compare()(new_dist, dist(i,j))) // ¿dist(i,j)<dist(i,k)+dist(k,j)?
              {
                dist(i, j) = new_dist;   // actualice menor distancia
                path(i, j) = path(i, k); // actualice nodo intermedio
              }
          }
}

} // end namespace Aleph

# endif // FLOYD_H

---