Dijkstra.H

00001 
00002 /*
00003   This file is part of Aleph system
00004 
00005   Copyright (c) 2002, 2003, 2004, 2005, 2006
00006   UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  
00007 
00008   - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
00009   - ULA Computer Science Department
00010   - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología
00011 
00012   PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
00013   DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
00014   NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
00015   SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
00016   THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.
00017 
00018   Aleph is distributed in the hope that it will be useful, but WITHOUT
00019   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
00020   or FITNESS FOR A PARTICULAR PURPOSE.
00021 
00022   UNIVERSIDAD DE LOS ANDES requests users of this software to return to 
00023 
00024   Leandro Leon
00025   CEMISID 
00026   Ed La Hechicera 
00027   3er piso, ala sur
00028   Facultad de Ingenieria 
00029   Universidad de Los Andes 
00030   Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or
00031 
00032   lrleon@ula.ve
00033 
00034   any improvements or extensions that they make and grant Universidad 
00035   de Los Andes (ULA) the rights to redistribute these changes. 
00036 
00037   Aleph is (or was) granted by: 
00038   - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
00039     (CDCHT)
00040   - Fundacite Mérida
00041 */
00042 
00043 
00044 # ifndef DIJKSTRA_H
00045 # define DIJKSTRA_H
00046 
00047 # include <ahFunction.H>
00048 # include <tpl_graph.H>
00049 # include <archeap.H>
00050 
00051 namespace Aleph {
00052 
00053     // conversión de cookie a Node_Info 
00054 # define DNI(p) (static_cast<Dijkstra_Node_Info<GT, Distance>*>(NODE_COOKIE((p))))
00055     // Acceso al nodo del árbol en el grafo
00056 # define TREENODE(p) (DNI(p)->tree_node)
00057 # define ACC(p) (DNI(p)->dist) // Acceso a la distancia acumulada
00058 # define HEAPNODE(p) (DNI(p)->heap_node)
00059 # define DAI(p) (static_cast<Dijkstra_Arc_Info<GT, Distance>*>(ARC_COOKIE(p)))
00060 # define ARC_DIST(p) (Distance () (p))
00061 # define TREEARC(p) (DAI(p)->tree_arc)
00062 # define POT(p) (DAI(p)->pot)
00063 # define GRAPHNODE(p) (static_cast<typename GT::Node*>(NODE_COOKIE(p)))
00064     template <class GT, class Distance>
00065 struct Dijkstra_Node_Info
00066 {
00067   typename GT::Node * tree_node; // Imagen del nodo en el árbol abarcador
00068   typename Distance::Distance_Type dist; // distancia acumulada
00069   void *                           heap_node;
00070 
00071   Dijkstra_Node_Info() 
00072     : tree_node(NULL), dist(Distance::Zero_Distance), heap_node(NULL)
00073   {
00074     // empty 
00075   }
00076 };
00077       template <class GT, class Distance, class Compare>
00078 struct Dijkstra_Heap_Info
00079 {
00080       typedef 
00081   typename ArcHeap<GT, Distance, Compare, Dijkstra_Heap_Info>::Node Node;
00082   
00083   Node *& operator () (typename GT::Node * p)
00084   {
00085     return (Node*&) HEAPNODE(p);
00086   }
00087 };
00088   template <class GT, class Distance>
00089 struct Dijkstra_Arc_Info
00090 {
00091   typename GT::Arc *               tree_arc; // imagen en el árbol abarcador
00092   typename Distance::Distance_Type pot;      // potencial del arco
00093 };
00094   template <class GT, class Distance>
00095 struct Initialize_Dijkstra_Node
00096 {
00097   void operator () (GT & g, typename GT::Node * p)
00098   {
00099     g.reset_bit(p, Aleph::Dijkstra);
00100 
00101         // apartar memoria información nodo (acumulado e imagen en árbol)
00102     NODE_COOKIE(p) = new Dijkstra_Node_Info <GT, Distance>; 
00103   }
00104 };
00105     template <class GT, class Distance>
00106 struct Destroy_Dijkstra_Node
00107 {
00108   void operator () (GT &, typename GT::Node * p)
00109   {
00110     Dijkstra_Node_Info <GT, Distance> * aux = DNI(p); // guardar bloque liberar
00111 
00112     GT::map_nodes (p, TREENODE(p));
00113         
00114     delete aux; // liberar bloque
00115   }
00116 };
00117 
00118     template <class GT, typename Distance>
00119 struct Initialize_Dijkstra_Arc
00120 {
00121   void operator () (GT & g, typename GT::Arc * a)
00122   {
00123     g.reset_bit(a, Aleph::Dijkstra);
00124     ARC_COOKIE(a) = new Dijkstra_Arc_Info <GT, Distance>;
00125     POT(a) = Distance::Zero_Distance;
00126     TREEARC(a) = NULL;
00127   }
00128 };
00129     template <class GT, class Distance>
00130 struct Destroy_Dijkstra_Arc
00131 {
00132   void operator () (GT &, typename GT::Arc * ga)
00133   {
00134     Dijkstra_Arc_Info<GT, Distance> * aux = DAI(ga); 
00135 
00136     typename GT::Arc * ta = TREEARC(ga);
00137 
00138     if (ta != NULL) // ¿pertenece este arco al árbol abarcador?
00139 
00140      {    
00141        I(IS_ARC_VISITED(ga, Aleph::Dijkstra));
00142 
00143       GT::map_arcs (ga, ta); // sí ==> mapearlo
00144 
00145       }
00146 
00147 
00148     delete aux;
00149   }
00150 };
00151 
00152   template <class GT, class Compare, class Distance>
00153 struct Compare_Arc_Data
00154 {
00155   bool operator () (typename GT::Arc * a1, typename GT::Arc * a2) const
00156   {
00157     return Compare() (POT(a1), POT(a2));
00158   }
00159 };
00235     template <class GT, class Distance, class Compare, class Plus> inline
00236 void dijkstra_min_spanning_tree(GT &                g,
00237                                 typename GT::Node * start_node, 
00238                                 GT &                tree)
00239 {
00240   tree.clear_graph(); // limpiar árbol abarcador destino 
00241 
00242   g.template operate_on_nodes <Initialize_Dijkstra_Node <GT, Distance> > ();
00243   g.template operate_on_arcs <Initialize_Dijkstra_Arc<GT, Distance> > ();
00244 
00245   ACC(start_node) = Distance::Zero_Distance; // acumulado en start_node es cero 
00246 
00247   NODE_BITS(start_node).set_bit(Aleph::Dijkstra, true); 
00248 
00249         // inserte start_node en árbol abarcador y anótelo en registro
00250   TREENODE(start_node) = tree.insert_node(start_node->get_info());
00251   NODE_COOKIE(TREENODE(start_node)) = start_node;
00252 
00253   {     // bloque adicional para asegurar que el heap se destruya antes que
00254         // los bloques almacenados en los cookies
00255     typedef Dijkstra_Heap_Info<GT, Distance, Compare> Acc_Heap;
00256     ArcHeap<GT, Distance, Compare, Acc_Heap> heap;
00257     for (typename GT::Node_Arc_Iterator it(start_node); it.has_current(); it.next())
00258       {
00259         typename GT::Arc * arc = it.get_current_arc();
00260         ARC_BITS(arc).set_bit(Aleph::Dijkstra, true); 
00261         POT(arc) = ARC_DIST(arc);
00262         heap.put_arc(arc, it.get_tgt_node());
00263       }
00264     while (tree.get_num_nodes() < g.get_num_nodes()) // mientras tree no abarque a g
00265       {
00266         typename GT::Arc * garc = heap.get_min_arc(); // obtener arco de menor potencial
00267 
00268 
00269         I(IS_ARC_VISITED(garc, Aleph::Dijkstra));
00270 
00271             // nodos conectados por el arco
00272         typename GT::Node * gsrc = g.get_src_node(garc);
00273         typename GT::Node * gtgt = g.get_tgt_node(garc);
00274 
00275             // ¿Están los dos nodos visitados?
00276         if (IS_NODE_VISITED(gsrc, Aleph::Dijkstra) and 
00277             IS_NODE_VISITED(gtgt, Aleph::Dijkstra))
00278           continue; // ambos visitados ==> insertar este arco causaría ciclo
00279             
00280         typename GT::Node * new_node = // seleccionar nodo no visitado
00281           IS_NODE_VISITED(gsrc, Aleph::Dijkstra) ? gtgt : gsrc;
00282 
00283             // insertar nuevo nodo en árbol y guardarlo en registro de nodo
00284         typename GT::Node * ttgt = tree.insert_node(new_node->get_info());
00285         NODE_BITS(new_node).set_bit(Aleph::Dijkstra, true);
00286         TREENODE(new_node) = ttgt;
00287 
00288         typename GT::Arc * tarc = // insertar nuevo arco en tree y guardarlo en registro
00289           tree.insert_arc(TREENODE(gsrc), TREENODE(gtgt), garc->get_info());
00290         TREEARC(garc) = tarc;
00291             // actualizar distancia recorrida desde nodo inicial 
00292         ACC(new_node) = POT(garc);
00293         const typename Distance::Distance_Type & acc = ACC(new_node);
00294 
00295             // por cada arco calcular potencial e insertarlo en heap
00296         for (typename GT::Node_Arc_Iterator it(new_node); it.has_current(); it.next())
00297           {
00298             typename GT::Arc * arc = it.get_current_arc();
00299 
00300             if (IS_ARC_VISITED(arc, Aleph::Dijkstra))
00301               continue;
00302 
00303             ARC_BITS(arc).set_bit(Aleph::Dijkstra, true);
00304 
00305             typename GT::Node * tgt = it.get_tgt_node();
00306 
00307             if (IS_NODE_VISITED(tgt, Aleph::Dijkstra)) 
00308               continue; // nodo visitado ==> causará ciclo ==> no se requiere
00309                         // insertar en heap  
00310 
00311             POT(arc) = Plus () (acc, ARC_DIST(arc)); // calcula potencial
00312 
00313             heap.put_arc(arc, tgt);
00314           }
00315       }
00316   } // aquí se destruye el heap
00317 
00318   g.template operate_on_arcs <Destroy_Dijkstra_Arc<GT, Distance> > ();
00319   g.template operate_on_nodes <Destroy_Dijkstra_Node <GT, Distance> > ();
00320 }
00321     template <class GT, class Distance> inline
00322 void dijkstra_min_spanning_tree(GT &                g,
00323                                 typename GT::Node * start_node, 
00324                                 GT &                tree)
00325 {
00326   dijkstra_min_spanning_tree<GT, Distance, 
00327     Aleph::less<typename Distance::Distance_Type>,
00328     Aleph::plus<typename Distance::Distance_Type> > 
00329   (g, start_node, tree);
00330 }
00371     template <class GT, class Distance, class Compare, class Plus> inline
00372 void dijkstra_min_path(GT &                g, 
00373                        typename GT::Node * start_node,
00374                        typename GT::Node * end_node,
00375                        Path<GT> &          min_path)
00376 {
00377   GT tree; // árbol abarcador temporal
00378 
00379   tree.clear_graph(); // limpiar árbol abarcador destino 
00380 
00381   g.template operate_on_nodes <Initialize_Dijkstra_Node <GT, Distance> > ();
00382   g.template operate_on_arcs <Initialize_Dijkstra_Arc<GT, Distance> > ();
00383 
00384   ACC(start_node) = Distance::Zero_Distance; // acumulado en start_node es cero 
00385 
00386   NODE_BITS(start_node).set_bit(Aleph::Dijkstra, true); 
00387 
00388         // inserte start_node en árbol abarcador y anótelo en registro
00389   TREENODE(start_node) = tree.insert_node(start_node->get_info());
00390   NODE_COOKIE(TREENODE(start_node)) = start_node;
00391   {
00392     typedef Dijkstra_Heap_Info<GT, Distance, Compare> Acc_Heap;
00393     ArcHeap<GT, Distance, Compare, Acc_Heap> heap;
00394     for (typename GT::Node_Arc_Iterator it(start_node); it.has_current(); it.next())
00395       {
00396         typename GT::Arc * arc = it.get_current_arc();
00397         ARC_BITS(arc).set_bit(Aleph::Dijkstra, true); 
00398         POT(arc) = ARC_DIST(arc);
00399         heap.put_arc(arc, it.get_tgt_node());
00400       }
00401     while (tree.get_num_nodes() < g.get_num_nodes()) // mientras tree no abarque a g
00402       {
00403         typename GT::Arc * garc = heap.get_min_arc(); // obtener arco de menor potencial
00404 
00405 
00406         I(IS_ARC_VISITED(garc, Aleph::Dijkstra));
00407 
00408             // nodos conectados por el arco
00409         typename GT::Node * gsrc = g.get_src_node(garc);
00410         typename GT::Node * gtgt = g.get_tgt_node(garc);
00411 
00412             // ¿Están los dos nodos visitados?
00413         if (IS_NODE_VISITED(gsrc, Aleph::Dijkstra) and 
00414             IS_NODE_VISITED(gtgt, Aleph::Dijkstra))
00415           continue; // ambos visitados ==> insertar este arco causaría ciclo
00416             
00417         typename GT::Node * new_node = // seleccionar nodo no visitado
00418           IS_NODE_VISITED(gsrc, Aleph::Dijkstra) ? gtgt : gsrc;
00419 
00420             // insertar nuevo nodo en árbol y guardarlo en registro de nodo
00421         typename GT::Node * ttgt = tree.insert_node(new_node->get_info());
00422         NODE_BITS(new_node).set_bit(Aleph::Dijkstra, true);
00423         TREENODE(new_node) = ttgt;
00424 
00425         typename GT::Arc * tarc = // insertar nuevo arco en tree y guardarlo en registro
00426           tree.insert_arc(TREENODE(gsrc), TREENODE(gtgt), garc->get_info());
00427         TREEARC(garc) = tarc;
00428 
00429         if (gtgt == end_node) // ¿está end_node en árbol abarcador? 
00430           break; // sí ==> camino mínimo ya está en árbol abarcador
00431 
00432             // actualizar distancia recorrida desde nodo inicial 
00433         ACC(new_node) = POT(garc);
00434         const typename Distance::Distance_Type & acc = ACC(new_node);
00435 
00436             // por cada arco calcular potencial e insertarlo en heap
00437         for (typename GT::Node_Arc_Iterator it(new_node); it.has_current(); it.next())
00438           {
00439             typename GT::Arc * arc = it.get_current_arc();
00440 
00441             if (IS_ARC_VISITED(arc, Aleph::Dijkstra))
00442               continue;
00443 
00444             ARC_BITS(arc).set_bit(Aleph::Dijkstra, true);
00445 
00446             typename GT::Node * tgt = it.get_tgt_node();
00447 
00448             if (IS_NODE_VISITED(tgt, Aleph::Dijkstra)) 
00449               continue; // nodo visitado ==> causará ciclo ==> no se requiere
00450                         // insertar en heap  
00451 
00452             POT(arc) = Plus () (acc, ARC_DIST(arc)); // calcula potencial
00453 
00454             heap.put_arc(arc, tgt);
00455           }
00456       }
00457   }
00458 
00459   Path<GT> tree_min_path(tree, TREENODE(start_node));
00460   find_path_depth_first(tree, TREENODE(start_node), TREENODE(end_node), 
00461                         tree_min_path); 
00462   min_path.clear_path();
00463   min_path.init(start_node);
00464   typename Path<GT>::Iterator it(tree_min_path);
00465   for (it.next(); it.has_current(); it.next())
00466     {
00467       typename GT::Node * node = it.get_current_node();
00468 
00469       min_path.append(GRAPHNODE(node));
00470     }
00471   g.template operate_on_arcs <Destroy_Dijkstra_Arc<GT, Distance> > ();
00472   g.template operate_on_nodes <Destroy_Dijkstra_Node <GT, Distance> > ();
00473 }
00474     template <class GT, class Distance> inline
00475 void dijkstra_min_path(GT &                g, 
00476                        typename GT::Node * start_node,
00477                        typename GT::Node * end_node,
00478                        Path<GT> &          min_path)
00479 {
00480   dijkstra_min_path<GT, Distance,
00481                     Aleph::less<typename Distance::Distance_Type>,
00482                     Aleph::plus<typename Distance::Distance_Type> >
00483     (g, start_node, end_node, min_path);
00484 }
00485 
00486 # undef DNI
00487 # undef TREENODE
00488 # undef ACC
00489 # undef HEAPNODE
00490 # undef DAI
00491 # undef ARC_DIST
00492 # undef TREEARC
00493 # undef POT
00494 # undef GRAPHNODE
00495 } // end namespace Aleph
00496 # endif // DIJKSTRA_H
00497
Leandro R. León