Aleph-w: Algoritmos y estructuras de datos

---

Dijkstra.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 DIJKSTRA_H
# define DIJKSTRA_H

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

namespace Aleph {

    // conversión de cookie a Node_Info 
# define DNI(p) ((Node_Info*) NODE_COOKIE((p)))
    // Acceso al nodo del árbol en el grafo
# define TREENODE(p) (((Tree_Node_Info*)DNI(p))->tree_node)
# define ACC(p) (DNI(p)->dist) // Acceso a la distancia acumulada
# define HEAPNODE(p) (DNI(p)->heap_node)
# define DAI(p) ((Arc_Info*) ARC_COOKIE(p))
# define ARC_DIST(p) (Distance () (p))
# define TREEARC(p) (((Tree_Arc_Info*)DAI(p))->tree_arc)
# define POT(p) (DAI(p)->pot)
# define GRAPHNODE(p) (static_cast<typename GT::Node*>(NODE_COOKIE(p)))

  template <class GT, 
        class Distance, 
        class Op = Aleph::plus<typename Distance::Distance_Type>
        >
struct Dft_Plus
{
  Op & op;

  Dft_Plus(Op && __op = Op()) : op(__op) { /* empty */ }

  Dft_Plus(Op & __op) : op(__op) { /* empty */ }

      typename Distance::Distance_Type 
  operator () (typename GT::Arc * /* arc */, 
           const typename Distance::Distance_Type & op1,
           const typename Distance::Distance_Type & op2)
  {
    return op(op1, op2);
  }

      typename Distance::Distance_Type 
  operator () (const typename Distance::Distance_Type & op1,
           const typename Distance::Distance_Type & op2)
  {
    return op(op1, op2);
  }
};


template <class GT, 
      class Distance,
      class Plus = Dft_Plus<GT, Distance, 
                Aleph::plus<typename Distance::Distance_Type> >,
      class Compare = Aleph::less<typename Distance::Distance_Type>, 
      class SA      = Default_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() { /* empty */ }

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

    typename Distance::Distance_Type operator () (typename GT::Arc *a)
    {
      Arc_Info * 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;      // distancia acumulada
    void *                           heap_node;

    Node_Info() : dist(Distance::Zero_Distance), heap_node(NULL) 
    { 
      // empty
    }
  };

  // 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; // nodo árbol abarcador
    typename Distance::Distance_Type dist;      // distancia acumulada
    void *                           heap_node;

    Tree_Node_Info() : tree_node(NULL)
    { 
      // empty
    }
  };

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

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

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

  // Liberación de memoria de nodo para la versión que pinta
  struct Destroy_Node
  {
    void operator () (GT &, typename GT::Node * p)
    {
      delete DNI(p); //bloque a liberar
    }
  };

  // Inicialización de arco para la versión que pinta
  struct Initialize_Arc
  {
    void operator () (GT & g, typename GT::Arc * a)
    {
      g.reset_bit(a, Aleph::Dijkstra);
      ARC_COOKIE(a) = new Arc_Info;
      POT(a) = Distance::Zero_Distance;
    }
  };

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

  // Inicialización de memoria de nodo para la versión que construye árbol
  struct Initialize_Tree_Node
  {
    void operator () (GT & g, typename GT::Node * p)
    {
      g.reset_bit(p, Aleph::Dijkstra);
      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 () (GT &, typename GT::Node * p)
    {
      Tree_Node_Info * aux = (Tree_Node_Info *) DNI(p); //bloque a liberar
      typename GT::Node * tp = TREENODE(p); // imagen en árbol abarcador
      if (tp != NULL) // ¿está este nodo incluído en el árbol abarcador? 
    {
      NODE_COOKIE(p) = NODE_COOKIE(tp) = NULL;
      GT::map_nodes (p, tp);
    }
      else
    NODE_COOKIE(p) = NULL;

      delete aux; 
    }
  };

  // Inicialización de arco para la versión que construye árbol
  struct Initialize_Tree_Arc
  {
    void operator () (GT & g, typename GT::Arc * a)
    {
      g.reset_bit(a, Aleph::Dijkstra);
      ARC_COOKIE(a) = new Tree_Arc_Info;
      POT(a) = Distance::Zero_Distance;
      TREEARC(a) = NULL;
    }
  };

  // Liberación de memoria y mapeo para la versión que construye árbol
  struct Destroy_Tree_Arc
  {
    void operator () (GT &, typename GT::Arc * ga)
    {
      Tree_Arc_Info * aux = (Tree_Arc_Info *) DAI(ga); 
      typename GT::Arc * ta = TREEARC(ga);
      if (ta != NULL) // ¿pertenece este arco al árbol abarcador?
    {    
      I(IS_ARC_VISITED(ga, Aleph::Dijkstra));
      GT::map_arcs (ga, ta); // sí ==> mapearlo
    }

      delete aux;
    }
  };

  typedef Dijkstra_Heap_Info Heap_Info;

  typedef ArcHeap<GT, Get_Potential_Arc, Compare, Heap_Info> Heap;

  SA &                sa;
  Get_Potential_Arc   get_pot;
  Plus &              plus;
  Heap                heap;
  bool                painted;
  GT *                ptr_g;
  typename GT::Node * s;

public:

  // Constructores
  
  Dijkstra_Min_Paths(Plus &&     __plus = Plus(),
             Distance && dist = Distance(),  
             Compare &&  cmp  = Compare(),
             SA &&       __sa = SA())
    : sa(__sa), get_pot(dist), plus(__plus), heap(get_pot, cmp, Heap_Info()), 
      painted(false), ptr_g(NULL), s(NULL)
  {
    // empty
  }

  Dijkstra_Min_Paths(Plus & __plus, Distance & dist, Compare & cmp, SA & __sa)
    : sa(__sa), get_pot(dist), plus(__plus), heap(get_pot, cmp, Heap_Info()), 
      painted(false), ptr_g(NULL), s(NULL)
  {
    // empty
  }

private:

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

    ptr_g = &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:

  void compute_min_paths_tree(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::Dijkstra, true); 
    ACC(start)                   = Distance::Zero_Distance; 
    TREENODE(start)              = tree.insert_node(start->get_info());
    NODE_COOKIE(TREENODE(start)) = start;

    for (Out_Iterator<GT, SA> it(start, sa); it.has_curr(); it.next()) 
      {
    typename GT::Arc * arc = it.get_current_arc();
    POT(arc)               = ARC_DIST(arc);
    heap.put_arc(arc, it.get_tgt_node());
      }

    const size_t & n = g.get_num_nodes();

    while (tree.get_num_nodes() < n)  // mientras tree no abarque a g
      {
    typename GT::Arc * garc  = heap.get_min_arc(); 
    if (IS_ARC_VISITED(garc, Aleph::Dijkstra))
      continue;

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

    typename GT::Node * gsrc = g.get_src_node(garc);
    typename GT::Node * gtgt = g.get_tgt_node(garc);

          // ¿Están los dos nodos visitados?
    if (IS_NODE_VISITED(gsrc, Aleph::Dijkstra) and 
        IS_NODE_VISITED(gtgt, Aleph::Dijkstra))
      continue; // insertar arco causaría ciclo

    if (IS_NODE_VISITED(gtgt, Aleph::Dijkstra))
      Aleph::swap(gsrc, gtgt);

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

    typename GT::Node * ttgt = tree.insert_node(gtgt->get_info());
    TREENODE(gtgt)           = ttgt;

    typename GT::Arc * tarc = // insertar nuevo arco en tree 
      tree.insert_arc(TREENODE(gsrc), TREENODE(gtgt), garc->get_info());
    TREEARC(garc) = tarc;

    ACC(gtgt) = plus(ACC(gsrc), ARC_DIST(garc)); // total dist nodo inicial
    const typename Distance::Distance_Type & acc = ACC(gtgt);

    // por cada arco calcular potencial e insertarlo en heap
    for (Out_Iterator<GT, SA> it(gtgt, sa); it.has_curr(); it.next()) 
      {
        typename GT::Arc * arc = it.get_current_arc();
        if (IS_ARC_VISITED(arc, Aleph::Dijkstra))
          continue;

        typename GT::Node * tgt = it.get_tgt_node();
        if (IS_NODE_VISITED(tgt, Aleph::Dijkstra)) 
          continue; // causaría ciclo ==> no se mete en heap  

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

    uninit<Destroy_Tree_Node, Destroy_Tree_Arc> ();
  }

  void compute_partial_min_paths_tree(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::Dijkstra, true); 
    ACC(start)                   = Distance::Zero_Distance; 
    TREENODE(start)              = tree.insert_node(start->get_info());
    NODE_COOKIE(TREENODE(start)) = start;

    for (Out_Iterator<GT, SA> it(start, sa); it.has_curr(); it.next()) 
      {
    typename GT::Arc * arc = it.get_current_arc();
    POT(arc)               = ARC_DIST(arc);
    heap.put_arc(arc, it.get_tgt_node());
      }

    const size_t & n = g.get_num_nodes();

    while (tree.get_num_nodes() < n) // tree no abarque g
      {
    typename GT::Arc * garc  = heap.get_min_arc(); 

    if (IS_ARC_VISITED(garc, Aleph::Dijkstra))
      continue;

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

    typename GT::Node * gsrc = g.get_src_node(garc);
    typename GT::Node * gtgt = g.get_tgt_node(garc);

    // ¿Están los dos nodos visitados?
    if (IS_NODE_VISITED(gsrc, Aleph::Dijkstra) and 
        IS_NODE_VISITED(gtgt, Aleph::Dijkstra))
      continue; // insertar arco causaría ciclo

    if (IS_NODE_VISITED(gtgt, Aleph::Dijkstra))
      Aleph::swap(gsrc, gtgt);

    typename GT::Node * ttgt = tree.insert_node(gtgt->get_info());
    TREENODE(gtgt)           = ttgt;
    NODE_BITS(gtgt).set_bit(Aleph::Dijkstra, true);

    typename GT::Arc * 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) = plus(ACC(gsrc), ARC_DIST(garc)); // total dist nodo inicial
    const typename Distance::Distance_Type & acc = ACC(gtgt);

          // por cada arco calcular potencial e insertarlo en heap
    for (Out_Iterator<GT, SA> it(gtgt, sa); it.has_curr(); it.next()) 
      {
        typename GT::Arc * arc = it.get_current_arc();
        if (IS_ARC_VISITED(arc, Aleph::Dijkstra))
          continue;

        typename GT::Node * tgt = it.get_tgt_node();
        if (IS_NODE_VISITED(tgt, Aleph::Dijkstra)) 
          continue; // causaría ciclo ==> no se mete en heap  

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

    uninit <Destroy_Tree_Node, Destroy_Tree_Arc> ();
  }

  struct Painted     // muestra los arcos cuya bandera Dijstra sea true
  {
    Dijkstra_Min_Paths * ptr;
    typename Distance::Distance_Type dist;

    Painted(Dijkstra_Min_Paths * p) 
      : ptr(p), dist(Distance::Zero_Distance) 
    {
      /* empty */ 
    }

    bool operator () (typename GT::Arc * a)
    {
      if (not IS_ARC_VISITED(a, Aleph::Dijkstra))
    return false;

      dist = ptr->plus(a, dist, ARC_DIST(a));

      return true;
    }
  };

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

    NODE_BITS(start).set_bit(Aleph::Dijkstra, true); 
    ACC(start) = Distance::Zero_Distance; 

    for (Out_Iterator<GT, SA> it(start, sa); it.has_curr(); it.next()) 
      {
    typename GT::Arc * arc = it.get_current_arc();
    POT(arc)               = ARC_DIST(arc);
    heap.put_arc(arc, it.get_tgt_node());
      }

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

    while (tn < n) // tree no abarque g
      {
    typename GT::Arc * garc  = heap.get_min_arc(); 
    if (IS_ARC_VISITED(garc, Aleph::Dijkstra))
      continue;

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

    typename GT::Node * src = g.get_src_node(garc);
    typename GT::Node * tgt = g.get_tgt_node(garc);

    // ¿Están los dos nodos visitados?
    if (IS_NODE_VISITED(src, Aleph::Dijkstra) and 
        IS_NODE_VISITED(tgt, Aleph::Dijkstra))
      continue; // este arco causaría un ciclo

    if (IS_NODE_VISITED(tgt, Aleph::Dijkstra))
      Aleph::swap(src, tgt);

    NODE_BITS(tgt).set_bit(Aleph::Dijkstra, true);

    ++tn; // simula que p se metió en el árbol abarcador

    if (tgt == end) // ¿está end_node en árbol abarcador? 
      break; // sí ==> camino mínimo ya está pintado

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

    const typename Distance::Distance_Type & acc = ACC(tgt);

    // por cada arco calcular potencial e insertarlo en heap
    for (Out_Iterator<GT, SA> it(tgt, sa); it.has_curr(); it.next()) 
      {
        typename GT::Arc * a = it.get_current_arc();
        if (IS_ARC_VISITED(a, Aleph::Dijkstra))
          continue;

        typename GT::Node * t = it.get_tgt_node();
        if (IS_NODE_VISITED(t, Aleph::Dijkstra)) 
          continue; // causaría ciclo ==> no se mete en heap  

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

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

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

    NODE_BITS(start).set_bit(Aleph::Dijkstra, true); 
    ACC(start) = Distance::Zero_Distance; 

    for (Out_Iterator<GT, SA> it(start, sa); it.has_curr(); it.next()) 
      {
    typename GT::Arc * arc = it.get_current_arc();
    POT(arc)               = ARC_DIST(arc);
    heap.put_arc(arc, it.get_tgt_node());
      }

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

    while (tn < n) // tree no abarque g
      {
    typename GT::Arc * garc  = heap.get_min_arc(); 
    if (IS_ARC_VISITED(garc, Aleph::Dijkstra))
      continue;

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

    typename GT::Node * src = g.get_src_node(garc);
    typename GT::Node * tgt = g.get_tgt_node(garc);

    // ¿Están los dos nodos visitados?
    if (IS_NODE_VISITED(src, Aleph::Dijkstra) and 
        IS_NODE_VISITED(tgt, Aleph::Dijkstra))
      continue; // este arco causaría un ciclo

    if (IS_NODE_VISITED(tgt, Aleph::Dijkstra))
      Aleph::swap(src, tgt);

    NODE_BITS(tgt).set_bit(Aleph::Dijkstra, true);

    ++tn; // simula que p se metió en el árbol abarcador

    ACC(tgt) = plus(ACC(src), ARC_DIST(garc)); // total dist nodo inicial
    const typename Distance::Distance_Type & acc = ACC(tgt);

    // por cada arco calcular potencial e insertarlo en heap
    for (Out_Iterator<GT, SA> it(tgt, sa); it.has_curr(); it.next()) 
      {
        typename GT::Arc * a = it.get_current_arc();
        if (IS_ARC_VISITED(a, Aleph::Dijkstra))
          continue;

        typename GT::Node * t = it.get_tgt_node();
        if (IS_NODE_VISITED(t, Aleph::Dijkstra)) 
          continue; // causaría ciclo ==> no se mete en heap  

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

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

      typename Distance::Distance_Type 
  find_min_path(GT & g, 
        typename GT::Node * start, typename GT::Node * end, 
        Path<GT> & min_path)
  {
    paint_partial_min_paths_tree(g, start, end);

    Painted paint(this);
    (Find_Path_Depth_First<GT, Painted> (paint)) (g, start, end, min_path); 

    return paint.dist;
  }
  
  void operator () (GT & g, typename GT::Node * s, GT & tree)
  {
    compute_min_paths_tree(g, s, tree);
  }

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

    Painted paint(this);
    (Copy_Graph<GT, Default_Show_Node<GT>, Painted> (paint)) (tree, g);

    return paint.dist;
  }

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

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

    if (not painted)
      throw std::domain_error("Graph has not previusly painted");
      
    Painted paint(this);
    (Find_Path_Depth_First<GT, Painted> (paint)) (*ptr_g, s, end, path); 

    return paint.dist;
  }

  struct Total
  {
    Dijkstra_Min_Paths * ptr;
    typename  Distance::Distance_Type dist;
    
    Total(Dijkstra_Min_Paths * p) 
      : ptr(p), dist(Distance::Zero_Distance)
    {
      /* empty */ 
    }

    bool operator () (typename GT::Arc * a)
    {
      dist = ptr->plus(a, dist, ARC_DIST(a));

      return true;
    }
  };

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

    typename GT::Node * ts = mapped_node<GT>(s);
    typename GT::Node * te = mapped_node<GT>(end);

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

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

    return total.dist;
  }
};



# undef DNI
# undef TREENODE
# undef ACC
# undef HEAPNODE
# undef DAI
# undef ARC_DIST
# undef TREEARC
# undef POT
# undef GRAPHNODE
} // end namespace Aleph
# endif // DIJKSTRA_H

---