Aleph-w: Algoritmos y estructuras de datos

---

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

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

namespace Aleph
{
template <class GT, typename Distance, 
          class Compare = Aleph::less<typename Distance::Distance_Type>, 
          class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
          class SA      = Default_Show_Arc<GT> > 
void floyd_all_shortest_paths 
  (GT &                                                g, 
   Ady_Mat<GT, typename Distance::Distance_Type, SA> & dist,
   Ady_Mat<GT, long, SA> &                             path);
template <class AM, class Distance, class SA> 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) const
  {
    Ady_Mat <typename AM::List_Graph_Type, long, SA> & path = 
      * (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 = search_arc(g, src, tgt); 
    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 = Aleph::less<typename Distance::Distance_Type>, 
          class Plus    = Aleph::plus<typename Distance::Distance_Type>, 
          class SA      = Default_Show_Arc<GT> > 
void floyd_all_shortest_paths
  (GT &                                                g, 
   Ady_Mat<GT, typename Distance::Distance_Type, SA> & dist, 
   Ady_Mat<GT, long, SA> &                             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, SA> > (&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) // ¿posible encontrar 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)))//d(i,j)<d(i,k)+d(k,j)
              {
                dist(i, j) = new_dist;   // actualice menor distancia
                path(i, j) = path(i, k); // actualice nodo intermedio
              }
          }
}

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

      void 
  operator () (GT &                                                g, 
               Ady_Mat<GT, typename Distance::Distance_Type, SA> & dist, 
               Ady_Mat<GT, long, SA> &                             path) const
  {
    floyd_all_shortest_paths <GT, Distance, Compare, Plus, SA> (g, dist, path);
  }
};

    template <class Mat>
void find_min_path(Mat & p, const long & src_index, const long & tgt_index,
                   Path<typename Mat::Graph_Type> & path);
    template <class Mat>
void find_min_path(Mat & p, typename Mat::Node * src_node, 
                   typename Mat::Node * tgt_node,
                   Path<typename Mat::Graph_Type> & path)
{
  find_min_path(p, p(src_node), p(tgt_node, path));
}

    template <class Mat>
class Find_Min_Path
{
public:

  void operator () (Mat &                                 p, 
                    typename Mat::Node *                  src_node, 
                    typename Mat::Node *                  tgt_node,
                    Path<typename Mat::Graph_Type> & path) const
  {
    find_min_path <Mat> (p, src_node, tgt_node, path);
  }

  void operator () (Mat &                                 p, 
                    const long & src_index, const long &  tgt_index,
                    Path<typename Mat::Graph_Type> & path) const
  {
    find_min_path <Mat> (p, src_index, tgt_index, path);
  }
};

    template <class Mat> void 
find_min_path(Mat & p, const long & src_idx, const long & tgt_idx,
              Path<typename Mat::Graph_Type> & path)
{
  typedef typename Mat::Graph_Type GT;
  GT & g                  = p.get_list_graph();
  typename GT::Node * src = p(src_idx);
  path.set_graph(g, src);
  for (int i = src_idx, j; j != tgt_idx; i = j)
    {
      j = p(i, tgt_idx);
      path.append(p(j));
    }
} 

} // end namespace Aleph

# endif // FLOYD_H

---