alephw/doc/Dijkstra_8H_source.html

 /* Aleph-w

      / \  | | ___ _ __ | |__      __      __
     / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
    / ___ \| |  __/ |_) | | | |_____\ V  V /  version 1.9b
   /_/   \_\_|\___| .__/|_| |_|      \_/\_/   https://github.com/lrleon/Aleph-w
                  |_|

   This file is part of Aleph-w library

   Copyright (c) 2002-2018 Leandro Rabindranath Leon & Alejandro Mujica

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program 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. See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program. If not, see <https://www.gnu.org/licenses/>.
 */
 # ifndef DIJKSTRA_H
 # define DIJKSTRA_H

 # include <ahFunction.H>
 # include <archeap.H>
 # include <tpl_find_path.H>
 # include <tpl_agraph.H>

 namespace Aleph {

     // conversiÃ³n de cookie a Node_Info
 # define DNassert(p) ((Node_Info*) NODE_COOKIE((p)))

     // Acceso al nodo del Ã¡rbol en el grafo
 # define TREENODE(p) (((Tree_Node_Info*)DNassert(p))->tree_node)

 # define ACC(p) (DNassert(p)->dist) // Acceso a la distancia acumulada
 # define HEAPNODE(p) (DNassert(p)->heap_node)
 # define PARENT(p) (DNassert(p)->ret_node)

 # define DAassert(p) ((Arc_Info*) ARC_COOKIE(p))
 # define ARC_DIST(p) (Distance () (p))
 # define TREEARC(p) (((Tree_Arc_Info*)DAassert(p))->tree_arc)
 # define POT(p) (DAassert(p)->pot)
 # define GRAPHNODE(p) (static_cast<typename GT::Node*>(NODE_COOKIE(p)))


   template <class GT,
             class Distance = Dft_Dist<GT>,
             template <typename, class> class Itor = Node_Arc_Iterator,
             class SA       = Dft_Show_Arc<GT>>
 class Dijkstra_Min_Paths
 {
   // Aunque fundamentalmente el algoritmo es el mismo, hay dos enfoques
   // para calcular el camino mÃnimo. El primero es pintar el Ã¡rbol
   // abarcador de todos los caminos mÃnimos a partir de un nodo
   // start. Por pintar se entiende que la soluciÃ³n se encuentra dentro
   // del mismo grafo y que se distingue mediante marcas.
   //
   // El otro enfoque consiste en construir un Ã¡rbol abarcador separado.
   //
   // SegÃºn un enfoque u otro, el grafo se inicializa con informaciÃ³n
   // distinta. AsÃ, las clases que comiencen con el prefijo "Tree" son
   // clases que ataÃ±en a la solucipon que construye un Ã¡rbol abarcador
   // separado.

   // InformaciÃ³n a colocar en el arco para la versiÃ³n que pinta
   struct Arc_Info
   {
     typename Distance::Distance_Type pot; // potencial del arco
   };

   // InformaciÃ³n a colocar en el arco para la versiÃ³n que construye Ã¡rbol
   struct Tree_Arc_Info : public Arc_Info
   {
     typename GT::Arc * tree_arc; // imagen en Ã¡rbol
     typename Distance::Distance_Type pot; // potencial del arco
   };

   // Wrapper de acceso a la distancia (mediante la clase parÃ¡metro Distance)
   struct Get_Potential_Arc : public Distance
   {
     Get_Potential_Arc() noexcept { /* empty */ }

     Get_Potential_Arc(Distance & d) noexcept : Distance(d) { /* empty */ }

     typename Distance::Distance_Type
     operator () (typename GT::Arc *a) const noexcept
     {
       auto arc_info = (Arc_Info*) ARC_COOKIE(a);
       return arc_info->pot;
     }
   };

   // InformaciÃ³n a colocar en el nodo para la versiÃ³n que pinta
   struct Node_Info
   {
     typename Distance::Distance_Type dist      = 0;      // distancia acumulada
     void *                           heap_node = nullptr;
     void *                           ret_node  = nullptr; // padre en Ã¡rbol
   };

   // InformaciÃ³n a colocar en el nodo para la versiÃ³n que construye Ã¡rbol
   struct Tree_Node_Info : public Node_Info
   {
     typename GT::Node *              tree_node = nullptr; // nodo Ã¡rbol abarcador
     typename Distance::Distance_Type dist;      // distancia acumulada
     void *                           heap_node = nullptr;
   };

   // Acceso al heap de arcos
   struct Dijkstra_Heap_Info
   {
         typedef typename
     ArcHeap<GT, Get_Potential_Arc, Dijkstra_Heap_Info>::Node Node;

     Node *& operator () (typename GT::Node * p) const noexcept
     {
       return (Node*&) HEAPNODE(p);
     }
   };

   // InicializaciÃ³n de nodo para la versiÃ³n que pinta
   struct Initialize_Node
   {
     void operator () (const GT & g, typename GT::Node * p) const noexcept
     {
       g.reset_bit(p, Aleph::Spanning_Tree);
       NODE_COOKIE(p) = new Node_Info;
     }
   };

   // LiberaciÃ³n de memoria de nodo para la versiÃ³n que pinta
   struct Destroy_Node
   {
     void operator () (const GT &, typename GT::Node * p) const noexcept
     {
       void * tmp = PARENT(p);
       delete DNassert(p); //bloque a liberar
       NODE_COOKIE(p) = tmp;
     }
   };

   // InicializaciÃ³n de arco para la versiÃ³n que pinta
   struct Initialize_Arc
   {
     void operator () (const GT & g, typename GT::Arc * a) const noexcept
     {
       g.reset_bit(a, Aleph::Spanning_Tree);
       ARC_COOKIE(a) = new Arc_Info;
       POT(a) = 0;
     }
   };

   // LiberaciÃ³n de memoria de arco para la versiÃ³n que pinta
   struct Destroy_Arc
   {
     void operator () (const GT &, typename GT::Arc * ga) const noexcept
     {
       delete DAassert(ga);
     }
   };

   // InicializaciÃ³n de memoria de nodo para la versiÃ³n que construye Ã¡rbol
   struct Initialize_Tree_Node
   {
     void operator () (const GT & g, typename GT::Node * p) const noexcept
     {
       g.reset_bit(p, Aleph::Spanning_Tree);
       NODE_COOKIE(p) = new Tree_Node_Info;
     }
   };

   // LiberaciÃ³n de memoria de nodo y mapeo para versiÃ³n que construye Ã¡rbol
   struct Destroy_Tree_Node
   {
     void operator () (const GT &, typename GT::Node * p) const noexcept
     {
       auto aux = (Tree_Node_Info *) DNassert(p); //bloque a liberar
       auto tp = TREENODE(p); // imagen en Ã¡rbol abarcador
       if (tp != nullptr) // Â¿estÃ¡ este nodo incluÃdo en el Ã¡rbol abarcador?
         {
           NODE_COOKIE(p) = NODE_COOKIE(tp) = nullptr;
           GT::map_nodes (p, tp);
         }
       else
         NODE_COOKIE(p) = nullptr;

       delete aux;
     }
   };

   // InicializaciÃ³n de arco para la versiÃ³n que construye Ã¡rbol
   struct Initialize_Tree_Arc
   {
     void operator () (const GT & g, typename GT::Arc * a) const noexcept
     {
       g.reset_bit(a, Aleph::Spanning_Tree);
       ARC_COOKIE(a) = new Tree_Arc_Info;
       POT(a) = 0;
       TREEARC(a) = nullptr;
     }
   };

   // LiberaciÃ³n de memoria y mapeo para la versiÃ³n que construye Ã¡rbol
   struct Destroy_Tree_Arc
   {
     void operator () (const GT &, typename GT::Arc * ga) const noexcept
     {
       auto aux = (Tree_Arc_Info *) DAassert(ga);
       typename GT::Arc * ta = TREEARC(ga);
       if (ta != nullptr) // Â¿pertenece este arco al Ã¡rbol abarcador?
         {
           assert(IS_ARC_VISITED(ga, Aleph::Spanning_Tree));
           GT::map_arcs (ga, ta); // sÃ ==> mapearlo
         }

       delete aux;
     }
   };

   typedef Dijkstra_Heap_Info Heap_Info;

   typedef ArcHeap<GT, Get_Potential_Arc, Heap_Info> Heap;

   SA                  sa;
   Get_Potential_Arc   get_pot;
   Heap                heap;
   bool                painted = false;
   GT *                ptr_g = nullptr;
   typename GT::Node * s = nullptr;

 public:

   // Constructores

   Dijkstra_Min_Paths(Distance dist = Distance(),
                      SA         __sa = SA())
   noexcept(std::is_nothrow_move_assignable<SA>::value)
     : sa(__sa), get_pot(dist), heap(get_pot, Heap_Info()),
       painted(false), ptr_g(nullptr), s(nullptr)
   {
     // empty
   }

 private:

       template <class IN, class IA>
   void init(const GT & g, typename GT::Node * start)
   {
     heap.empty();

     ptr_g = &const_cast<GT&>(g);
     s     = start;

     Operate_On_Nodes<GT, IN> () (g);

     (Operate_On_Arcs <GT, IA> (sa)) (g);
   }

      template <class DN, class DA>
   void uninit()
   {
     Operate_On_Nodes <GT, DN> () (*ptr_g);

     (Operate_On_Arcs <GT, DA, SA> (sa)) (*ptr_g);
   }

 public:

   typename GT::Node *
   compute_min_paths_tree(const GT & g, typename GT::Node * start, GT & tree)
   {
     init<Initialize_Tree_Node, Initialize_Tree_Arc>(g, start);

     clear_graph(tree); // limpiar Ã¡rbol abarcador destino

     NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
     ACC(start)                   = 0;
     auto ret = TREENODE(start) = tree.insert_node(start->get_info());
     NODE_COOKIE(TREENODE(start)) = start;

     for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
       {
         auto arc = it.get_current_arc_ne();
         POT(arc) = ARC_DIST(arc);
         heap.put_arc(arc, it.get_tgt_node());
       }

     const auto & n = g.get_num_nodes();

     while (tree.get_num_nodes() < n)  // mientras tree no abarque a g
       {
         auto garc  = heap.get_min_arc();
         if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
           continue;

         auto gsrc = g.get_src_node(garc);
         auto gtgt = g.get_tgt_node(garc);

               // Â¿EstÃ¡n los dos nodos visitados?
         if (IS_NODE_VISITED(gsrc, Aleph::Spanning_Tree) and
             IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
           continue; // insertar arco causarÃa ciclo

         ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);

         if (IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
           std::swap(gsrc, gtgt);

         NODE_BITS(gtgt).set_bit(Aleph::Spanning_Tree, true);

         auto ttgt = tree.insert_node(gtgt->get_info());
         TREENODE(gtgt) = ttgt;
         auto tsrc = TREENODE(gsrc);

         auto tarc = tree.insert_arc(tsrc, ttgt, garc->get_info());
         TREEARC(garc) = tarc;

         ACC(gtgt) = ACC(gsrc) + ARC_DIST(garc); // total dist nodo inicial
         const auto & acc = ACC(gtgt);

         // por cada arco calcular potencial e insertarlo en heap
         for (Itor<GT, SA> it(gtgt, sa); it.has_curr(); it.next_ne())
           {
             auto arc = it.get_current_arc_ne();
             if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
               continue;

             auto tgt = it.get_tgt_node();
             if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
               continue; // causarÃa ciclo ==> no se mete en heap

             POT(arc) = acc + ARC_DIST(arc); // calcula potencial
             heap.put_arc(arc, tgt);
           }
       }

     uninit<Destroy_Tree_Node, Destroy_Tree_Arc> ();

     return ret;
   }

   void compute_partial_min_paths_tree(const GT & g,
                                       typename GT::Node * start,
                                       typename GT::Node * end,
                                       GT & tree)
   {
     init <Initialize_Tree_Node, Initialize_Tree_Arc> (g, start);
     clear_graph(tree);

     NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
     ACC(start)                   = 0;
     TREENODE(start)              = tree.insert_node(start->get_info());
     NODE_COOKIE(TREENODE(start)) = start;

     for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
       {
         auto arc = it.get_current_arc_ne();
         POT(arc) = ARC_DIST(arc);
         heap.put_arc(arc, it.get_tgt_node());
       }

     const auto & n = g.get_num_nodes();

     while (tree.get_num_nodes() < n and not heap.is_empty()) // tree no abarque
       {
         auto garc  = heap.get_min_arc();
         if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
           continue;

         auto gsrc = g.get_src_node(garc);
         auto gtgt = g.get_tgt_node(garc);

         // Â¿EstÃ¡n los dos nodos visitados?
         if (IS_NODE_VISITED(gsrc, Aleph::Spanning_Tree) and
             IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
           continue; // insertar arco causarÃa ciclo

         ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);

         if (IS_NODE_VISITED(gtgt, Aleph::Spanning_Tree))
           std::swap(gsrc, gtgt);

         auto ttgt      = tree.insert_node(gtgt->get_info());
         TREENODE(gtgt) = ttgt;
         NODE_BITS(gtgt).set_bit(Aleph::Spanning_Tree, true);

         auto tarc = // insertar nuevo arco en tree
           tree.insert_arc(TREENODE(gsrc), TREENODE(gtgt), garc->get_info());
         TREEARC(garc) = tarc;

         if (gtgt == end) // Â¿estÃ¡ end_node en Ã¡rbol abarcador?
           break; // sÃ ==> camino mÃnimo ya estÃ¡ en Ã¡rbol abarcador

         ACC(gtgt) = ACC(gsrc) + ARC_DIST(garc); // total dist nodo inicial
         const auto & acc = ACC(gtgt);

               // por cada arco calcular potencial e insertarlo en heap
         for (Itor<GT, SA> it(gtgt, sa); it.has_curr(); it.next_ne())
           {
             auto arc = it.get_current_arc_ne();
             if (IS_ARC_VISITED(arc, Aleph::Spanning_Tree))
               continue;

             auto tgt = it.get_tgt_node();
             if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
               continue; // causarÃa ciclo ==> no se mete en heap

             POT(arc) = acc + ARC_DIST(arc); // calcula potencial
             heap.put_arc(arc, tgt);
           }
       }

     uninit <Destroy_Tree_Node, Destroy_Tree_Arc> ();
   }

   bool paint_partial_min_paths_tree(const GT & g,
                                     typename GT::Node * start,
                                     typename GT::Node * end)
   {
     bool ret_val = false;
     init<Initialize_Node, Initialize_Arc> (g, start);

     NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
     ACC(start) = 0;

     for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
       {
         auto arc = it.get_current_arc_ne();
         POT(arc) = ARC_DIST(arc);
         heap.put_arc(arc, it.get_tgt_node());
       }

     const auto & n = g.get_num_nodes();
     size_t tn = 1; // nÃºmero de nodos pintados

     while (tn < n and not heap.is_empty()) // tree no abarque g
       {
         auto garc  = heap.get_min_arc();
         if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
           continue;

         auto src = g.get_src_node(garc);
         auto tgt = g.get_tgt_node(garc);

         // Â¿EstÃ¡n los dos nodos visitados?
         if (IS_NODE_VISITED(src, Aleph::Spanning_Tree) and
             IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
           continue; // este arco causarÃa un ciclo

         ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);

         if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
           std::swap(src, tgt);

         NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
         PARENT(tgt) = src;

         ++tn; // simula que p se metiÃ³ en el Ã¡rbol abarcador

         if (tgt == end) // Â¿estÃ¡ end_node en Ã¡rbol abarcador?
           {
             ret_val = true;
             break; // sÃ ==> camino mÃnimo ya estÃ¡ pintado
           }

         ACC(tgt) = ACC(src) + ARC_DIST(garc); // total dist nodo inicial

         const auto & acc = ACC(tgt);

         // por cada arco calcular potencial e insertarlo en heap
         for (Itor<GT, SA> it(tgt, sa); it.has_curr(); it.next_ne())
           {
             auto a = it.get_current_arc_ne();
             if (IS_ARC_VISITED(a, Aleph::Spanning_Tree))
               continue;

             auto t = it.get_tgt_node();
             if (IS_NODE_VISITED(t, Aleph::Spanning_Tree))
               continue; // causarÃa ciclo ==> no se mete en heap

             POT(a) = acc + ARC_DIST(a); // calcula potencial
             heap.put_arc(a, t);
           }
       }

     uninit<Destroy_Node, Destroy_Arc> ();
     painted = true;

     return ret_val;
   }

   void paint_min_paths_tree(const GT & g, typename GT::Node * start)
   {
     init<Initialize_Node, Initialize_Arc> (g, start);

     NODE_BITS(start).set_bit(Aleph::Spanning_Tree, true);
     ACC(start) = 0;

     for (Itor<GT, SA> it(start, sa); it.has_curr(); it.next_ne())
       {
         auto arc = it.get_current_arc_ne();
         POT(arc) = ARC_DIST(arc);
         heap.put_arc(arc, it.get_tgt_node());
       }

     const auto & n = g.get_num_nodes();
     size_t tn = 1; // nÃºmero de nodos pintados

     while (tn < n and not heap.is_empty()) // tree no abarque g
       {
         auto garc  = heap.get_min_arc();
         if (IS_ARC_VISITED(garc, Aleph::Spanning_Tree))
           continue;

         auto src = g.get_src_node(garc);
         auto tgt = g.get_tgt_node(garc);

         // Â¿EstÃ¡n los dos nodos visitados?
         if (IS_NODE_VISITED(src, Aleph::Spanning_Tree) and
             IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
           continue; // este arco causarÃa un ciclo

         ARC_BITS(garc).set_bit(Aleph::Spanning_Tree, true);

         if (IS_NODE_VISITED(tgt, Aleph::Spanning_Tree))
           std::swap(src, tgt);

         NODE_BITS(tgt).set_bit(Aleph::Spanning_Tree, true);
         PARENT(tgt) = src;

         ++tn; // simula que p se metiÃ³ en el Ã¡rbol abarcador

         ACC(tgt) = ACC(src) + ARC_DIST(garc); // total dist nodo inicial
         const auto & acc = ACC(tgt);

         // por cada arco calcular potencial e insertarlo en heap
         for (Itor<GT, SA> it(tgt, sa); it.has_curr(); it.next_ne())
           {
             auto a = it.get_current_arc_ne();
             if (IS_ARC_VISITED(a, Aleph::Spanning_Tree))
               continue;

             auto t = it.get_tgt_node();
             if (IS_NODE_VISITED(t, Aleph::Spanning_Tree))
               continue; // causarÃa ciclo ==> no se mete en heap

             POT(a) = acc + ARC_DIST(a); // calcula potencial
             heap.put_arc(a, t);
           }
       }

     uninit<Destroy_Node, Destroy_Arc> ();
     painted = true;
   }

       typename Distance::Distance_Type
   get_min_path(typename GT::Node * end, Path<GT> & path)
   {
     if (ptr_g == nullptr)
       throw std::domain_error("Min path has not been computed");

     if (not painted)
       throw std::domain_error("Graph has not previously painted");

     return Aleph::get_min_path<GT, Distance>(s, end, path);
   }

       typename Distance::Distance_Type
   find_min_path(const GT & g,
                 typename GT::Node * start, typename GT::Node * end,
                 Path<GT> & min_path)
   {
     min_path.empty();
     if (paint_partial_min_paths_tree(g, start, end))
       return get_min_path(end, min_path);

     return numeric_limits<typename Distance::Distance_Type>::max();
   }

   void operator () (const GT & g, typename GT::Node * s, GT & tree)
   {
     compute_min_paths_tree(g, s, tree);
   }

       typename Distance::Distance_Type
   copy_painted_min_paths_tree(const GT & g, GT & tree)
   {
     if (not painted)
       throw std::domain_error("Graph has not previously painted");

     using Paint_Filt = Painted_Min_Spanning_Tree<GT, Distance>;
     Paint_Filt painted;
     (Copy_Graph<GT, Dft_Show_Node<GT>, Paint_Filt> (painted)) (tree, g);

     return painted.dist;
   }

   typename Distance::Distance_Type operator () (const GT & g,
                                                 typename GT::Node * s,
                                                 typename GT::Node * e,
                                                 Path<GT> & path)
   {
     return find_min_path (g, s, e, path);
   }

   struct Total
   {
     typename  Distance::Distance_Type dist;

     Total() noexcept : dist(0) { /* empty */ }

     bool operator () (typename GT::Arc * a) noexcept
     {
       dist += ARC_DIST(a);
       return true;
     }
   };

       typename Distance::Distance_Type
   get_min_path(const GT & tree, typename GT::Node * end, Path<GT> & path)
   {
     if (ptr_g == nullptr)
       throw std::domain_error("Min path has not been computed");

     auto ts = mapped_node<GT>(s);
     auto te = mapped_node<GT>(end);

     Path<GT> tree_path(tree);
     Total total;
     (Find_Path_Depth_First<GT, Itor, Total> (total)) (tree, ts, te, tree_path);

     path.empty();
     path.init(s);
     typename Path<GT>::Iterator it(tree_path);
     for (it.next(); it.has_curr(); it.next_ne())
       path.append(mapped_node<GT>(it.get_current_node_ne()));

     return total.dist;
   }
 };


 # undef DNI
 # undef PARENT
 # undef TREENODE
 # undef ACC
 # undef HEAPNODE
 # undef DAI
 # undef ARC_DIST
 # undef TREEARC
 # undef POT
 # undef GRAPHNODE
 } // end namespace Aleph
 # endif // DIJKSTRA_H
Aleph::Copy_Graph
Definition: tpl_graph.H:3633

Aleph::clear_graph
void clear_graph(GT &g) noexcept
Definition: tpl_graph.H:3463

Aleph::Dlink::Iterator::has_curr
bool has_curr() const noexcept
Return true if the iterator has current item.
Definition: dlink.H:658

NODE_COOKIE
#define NODE_COOKIE(p)
Definition: aleph-graph.H:333

Aleph::Dijkstra_Min_Paths::get_min_path
Distance::Distance_Type get_min_path(typename GT::Node *end, Path< GT > &path)
Definition: Dijkstra.H:660

Aleph::Dijkstra_Min_Paths::copy_painted_min_paths_tree
Distance::Distance_Type copy_painted_min_paths_tree(const GT &g, GT &tree)
Definition: Dijkstra.H:741

Aleph::Operate_On_Nodes
Definition: tpl_graph.H:2493

Aleph::Dijkstra_Min_Paths::compute_partial_min_paths_tree
void compute_partial_min_paths_tree(const GT &g, typename GT::Node *start, typename GT::Node *end, GT &tree)
Definition: Dijkstra.H:407

Aleph::Dijkstra_Min_Paths::paint_min_paths_tree
void paint_min_paths_tree(const GT &g, typename GT::Node *start)
Definition: Dijkstra.H:573

IS_NODE_VISITED
#define IS_NODE_VISITED(p, bit)
Definition: aleph-graph.H:327

std

Aleph::Dijkstra_Min_Paths::compute_min_paths_tree
GT::Node * compute_min_paths_tree(const GT &g, typename GT::Node *start, GT &tree)
Definition: Dijkstra.H:321

Aleph::Dijkstra_Min_Paths
Spanning tree calculation of all shortest paths from a given node according to Dijkstra&#39;s algorithm...
Definition: Dijkstra.H:86

ARC_COOKIE
#define ARC_COOKIE(p)
Definition: aleph-graph.H:366

Aleph::Dijkstra_Min_Paths::find_min_path
Distance::Distance_Type find_min_path(const GT &g, typename GT::Node *start, typename GT::Node *end, Path< GT > &min_path)
Definition: Dijkstra.H:690

Aleph::map_arcs
void map_arcs(typename GTS::Arc *p, typename GTT::Arc *q) noexcept
Definition: tpl_graph.H:3445

IS_ARC_VISITED
#define IS_ARC_VISITED(p, bit)
Definition: aleph-graph.H:360

Aleph::Path
Definition: tpl_graph.H:53

Aleph::map_nodes
void map_nodes(typename GTS::Node *p, typename GTT::Node *q) noexcept
Definition: tpl_graph.H:3419

Aleph::Find_Path_Depth_First
Definition: tpl_find_path.H:69

Aleph
Definition: ah-comb.H:35

Aleph::Dijkstra_Min_Paths::get_min_path
Distance::Distance_Type get_min_path(const GT &tree, typename GT::Node *end, Path< GT > &path)
Definition: Dijkstra.H:798

Aleph::Dft_Show_Arc
Definition: tpl_graph.H:1063

Aleph::DynDlist::Iterator::next_ne
void next_ne() noexcept
Definition: tpl_dynDlist.H:433

Aleph::Painted_Min_Spanning_Tree
Definition: tpl_graph.H:3723

NODE_BITS
#define NODE_BITS(p)
Definition: aleph-graph.H:305

Aleph::Dijkstra_Min_Paths::paint_partial_min_paths_tree
bool paint_partial_min_paths_tree(const GT &g, typename GT::Node *start, typename GT::Node *end)
Definition: Dijkstra.H:490

Aleph::Dft_Dist
Definition: tpl_graph_utils.H:1753

Aleph::DynDlist::Iterator::next
void next()
Definition: tpl_dynDlist.H:441

Aleph::Path::init
void init(Node *start_node)
Definition: tpl_graph.H:2722

Aleph::Dijkstra_Min_Paths::operator()
void operator()(const GT &g, typename GT::Node *s, GT &tree)
Definition: Dijkstra.H:722

ARC_BITS
#define ARC_BITS(p)
Definition: aleph-graph.H:351

Aleph::Dijkstra_Min_Paths::Total
Clase totalizadora de distancias.
Definition: Dijkstra.H:763

Aleph::Dijkstra_Min_Paths::Dijkstra_Min_Paths
Dijkstra_Min_Paths(Distance dist=Distance(), SA __sa=SA()) noexcept(std::is_nothrow_move_assignable< SA >::value)
Definition: Dijkstra.H:277

Aleph::Path::empty
void empty()
Clean the path: all the nodes and arc are removed.
Definition: tpl_graph.H:2761

Aleph::Path::append
void append(Arc *arc)
Definition: tpl_graph.H:2808

Aleph::Node_Arc_Iterator
Definition: tpl_graph.H:1177

Aleph::Painted_Min_Spanning_Tree::dist
Distance::Distance_Type dist
Accumutive distance from the first seen arc until the last seen.
Definition: tpl_graph.H:3726

Aleph::Path::Iterator
Definition: tpl_graph.H:3135

Aleph::Operate_On_Arcs
Definition: tpl_graph.H:2540