/* -*- C++ -*-
* src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
*
* Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Combinatorial Optimization Research Group, EGRES).
*
* Permission to use, modify and distribute this software is granted
* provided that this copyright notice appears in all copies. For
* precise terms see the accompanying LICENSE file.
*
* This software is provided "AS IS" with no warranty of any kind,
* express or implied, and with no claim as to its suitability for any
* purpose.
*
*/
#ifndef LEMON_DIJKSTRA_H
#define LEMON_DIJKSTRA_H
///\ingroup flowalgs
///\file
///\brief Dijkstra algorithm.
#include
#include
namespace lemon {
/// \addtogroup flowalgs
/// @{
///%Dijkstra algorithm class.
///This class provides an efficient implementation of %Dijkstra algorithm.
///The edge lengths are passed to the algorithm using a
///\ref skeleton::ReadMap "ReadMap",
///so it is easy to change it to any kind of length.
///
///The type of the length is determined by the
///\ref skeleton::ReadMap::ValueType "ValueType" of the length map.
///
///It is also possible to change the underlying priority heap.
///
///\param GR The graph type the algorithm runs on.
///\param LM This read-only
///EdgeMap
///determines the
///lengths of the edges. It is read once for each edge, so the map
///may involve in relatively time consuming process to compute the edge
///length if it is necessary. The default map type is
///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap"
///\param Heap The heap type used by the %Dijkstra
///algorithm. The default
///is using \ref BinHeap "binary heap".
///
///\author Jacint Szabo and Alpar Juttner
///\todo We need a typedef-names should be standardized. (-:
///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
///should not be fixed. (Problematic to solve).
#ifdef DOXYGEN
template
#else
template ,
template class Heap = BinHeap >
#endif
class Dijkstra{
public:
///The type of the underlying graph.
typedef GR Graph;
///\e
typedef typename Graph::Node Node;
///\e
typedef typename Graph::NodeIt NodeIt;
///\e
typedef typename Graph::Edge Edge;
///\e
typedef typename Graph::OutEdgeIt OutEdgeIt;
///The type of the length of the edges.
typedef typename LM::ValueType ValueType;
///The type of the map that stores the edge lengths.
typedef LM LengthMap;
///\brief The type of the map that stores the last
///edges of the shortest paths.
typedef typename Graph::template NodeMap PredMap;
///\brief The type of the map that stores the last but one
///nodes of the shortest paths.
typedef typename Graph::template NodeMap PredNodeMap;
///The type of the map that stores the dists of the nodes.
typedef typename Graph::template NodeMap DistMap;
private:
/// Pointer to the underlying graph.
const Graph *G;
/// Pointer to the length map
const LM *length;
///Pointer to the map of predecessors edges.
PredMap *predecessor;
///Indicates if \ref predecessor is locally allocated (\c true) or not.
bool local_predecessor;
///Pointer to the map of predecessors nodes.
PredNodeMap *pred_node;
///Indicates if \ref pred_node is locally allocated (\c true) or not.
bool local_pred_node;
///Pointer to the map of distances.
DistMap *distance;
///Indicates if \ref distance is locally allocated (\c true) or not.
bool local_distance;
///The source node of the last execution.
Node source;
///Initializes the maps.
///\todo Error if \c G or are \c NULL. What about \c length?
///\todo Better memory allocation (instead of new).
void init_maps()
{
if(!predecessor) {
local_predecessor = true;
predecessor = new PredMap(*G);
}
if(!pred_node) {
local_pred_node = true;
pred_node = new PredNodeMap(*G);
}
if(!distance) {
local_distance = true;
distance = new DistMap(*G);
}
}
public :
///Constructor.
///\param _G the graph the algorithm will run on.
///\param _length the length map used by the algorithm.
Dijkstra(const Graph& _G, const LM& _length) :
G(&_G), length(&_length),
predecessor(NULL), local_predecessor(false),
pred_node(NULL), local_pred_node(false),
distance(NULL), local_distance(false)
{ }
///Destructor.
~Dijkstra()
{
if(local_predecessor) delete predecessor;
if(local_pred_node) delete pred_node;
if(local_distance) delete distance;
}
///Sets the length map.
///Sets the length map.
///\return ` (*this) `
Dijkstra &setLengthMap(const LM &m)
{
length = &m;
return *this;
}
///Sets the map storing the predecessor edges.
///Sets the map storing the predecessor edges.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destuctor deallocates this
///automatically allocated map, of course.
///\return ` (*this) `
Dijkstra &setPredMap(PredMap &m)
{
if(local_predecessor) {
delete predecessor;
local_predecessor=false;
}
predecessor = &m;
return *this;
}
///Sets the map storing the predecessor nodes.
///Sets the map storing the predecessor nodes.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destuctor deallocates this
///automatically allocated map, of course.
///\return ` (*this) `
Dijkstra &setPredNodeMap(PredNodeMap &m)
{
if(local_pred_node) {
delete pred_node;
local_pred_node=false;
}
pred_node = &m;
return *this;
}
///Sets the map storing the distances calculated by the algorithm.
///Sets the map storing the distances calculated by the algorithm.
///If you don't use this function before calling \ref run(),
///it will allocate one. The destuctor deallocates this
///automatically allocated map, of course.
///\return ` (*this) `
Dijkstra &setDistMap(DistMap &m)
{
if(local_distance) {
delete distance;
local_distance=false;
}
distance = &m;
return *this;
}
///Runs %Dijkstra algorithm from node \c s.
///This method runs the %Dijkstra algorithm from a root node \c s
///in order to
///compute the
///shortest path to each node. The algorithm computes
///- The shortest path tree.
///- The distance of each node from the root.
void run(Node s) {
init_maps();
source = s;
for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
predecessor->set(u,INVALID);
pred_node->set(u,INVALID);
}
typename GR::template NodeMap heap_map(*G,-1);
typedef Heap,
std::less >
HeapType;
HeapType heap(heap_map);
heap.push(s,0);
while ( !heap.empty() ) {
Node v=heap.top();
ValueType oldvalue=heap[v];
heap.pop();
distance->set(v, oldvalue);
for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
Node w=G->head(e);
switch(heap.state(w)) {
case HeapType::PRE_HEAP:
heap.push(w,oldvalue+(*length)[e]);
predecessor->set(w,e);
pred_node->set(w,v);
break;
case HeapType::IN_HEAP:
if ( oldvalue+(*length)[e] < heap[w] ) {
heap.decrease(w, oldvalue+(*length)[e]);
predecessor->set(w,e);
pred_node->set(w,v);
}
break;
case HeapType::POST_HEAP:
break;
}
}
}
}
///The distance of a node from the root.
///Returns the distance of a node from the root.
///\pre \ref run() must be called before using this function.
///\warning If node \c v in unreachable from the root the return value
///of this funcion is undefined.
ValueType dist(Node v) const { return (*distance)[v]; }
///Returns the 'previous edge' of the shortest path tree.
///For a node \c v it returns the 'previous edge' of the shortest path tree,
///i.e. it returns the last edge of a shortest path from the root to \c
///v. It is \ref INVALID
///if \c v is unreachable from the root or if \c v=s. The
///shortest path tree used here is equal to the shortest path tree used in
///\ref predNode(Node v). \pre \ref run() must be called before using
///this function.
///\todo predEdge could be a better name.
Edge pred(Node v) const { return (*predecessor)[v]; }
///Returns the 'previous node' of the shortest path tree.
///For a node \c v it returns the 'previous node' of the shortest path tree,
///i.e. it returns the last but one node from a shortest path from the
///root to \c /v. It is INVALID if \c v is unreachable from the root or if
///\c v=s. The shortest path tree used here is equal to the shortest path
///tree used in \ref pred(Node v). \pre \ref run() must be called before
///using this function.
Node predNode(Node v) const { return (*pred_node)[v]; }
///Returns a reference to the NodeMap of distances.
///Returns a reference to the NodeMap of distances. \pre \ref run() must
///be called before using this function.
const DistMap &distMap() const { return *distance;}
///Returns a reference to the shortest path tree map.
///Returns a reference to the NodeMap of the edges of the
///shortest path tree.
///\pre \ref run() must be called before using this function.
const PredMap &predMap() const { return *predecessor;}
///Returns a reference to the map of nodes of shortest paths.
///Returns a reference to the NodeMap of the last but one nodes of the
///shortest path tree.
///\pre \ref run() must be called before using this function.
const PredNodeMap &predNodeMap() const { return *pred_node;}
///Checks if a node is reachable from the root.
///Returns \c true if \c v is reachable from the root.
///\note The root node is reported to be reached!
///\pre \ref run() must be called before using this function.
///
bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
};
/// @}
} //END OF NAMESPACE LEMON
#endif