# HG changeset patch # User deba # Date 1129287135 0 # Node ID c0f5e84013730a36c74fe78d4cdea5fa53b2b0ec # Parent 578d8b2b76c6f8ad6fa86b49dcf0bf4e837f060a Named parameter for heap and cross ref It needs some redesign diff -r 578d8b2b76c6 -r c0f5e8401373 lemon/dijkstra.h --- a/lemon/dijkstra.h Fri Oct 14 10:49:51 2005 +0000 +++ b/lemon/dijkstra.h Fri Oct 14 10:52:15 2005 +0000 @@ -50,6 +50,22 @@ typedef LM LengthMap; //The type of the length of the edges. typedef typename LM::Value Value; + /// The cross reference type used by heap. + + /// The cross reference type used by heap. + /// Usually it is \c Graph::NodeMap. + typedef typename Graph::template NodeMap HeapCrossRef; + ///Instantiates a HeapCrossRef. + + ///This function instantiates a \ref HeapCrossRef. + /// \param G is the graph, to which we would like to define the + /// HeapCrossRef. + /// \todo The graph alone may be insufficient for the initialization + static HeapCrossRef *createHeapCrossRef(const GR &G) + { + return new HeapCrossRef(G); + } + ///The heap type used by Dijkstra algorithm. ///The heap type used by Dijkstra algorithm. @@ -60,6 +76,11 @@ typename GR::template NodeMap, std::less > Heap; + static Heap *createHeap(HeapCrossRef& R) + { + return new Heap(R); + } + ///\brief The type of the map that stores the last ///edges of the shortest paths. /// @@ -195,6 +216,8 @@ typedef typename TR::ProcessedMap ProcessedMap; ///The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; + ///The cross reference type used for the current heap. + typedef typename TR::HeapCrossRef HeapCrossRef; ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; private: @@ -214,6 +237,14 @@ ProcessedMap *_processed; ///Indicates if \ref _processed is locally allocated (\c true) or not. bool local_processed; + ///Pointer to the heap cross references. + HeapCrossRef *_heap_cross_ref; + ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not. + bool local_heap_cross_ref; + ///Pointer to the heap. + Heap *_heap; + ///Indicates if \ref _heap is locally allocated (\c true) or not. + bool local_heap; ///Creates the maps if necessary. @@ -233,6 +264,14 @@ local_processed = true; _processed = Traits::createProcessedMap(*G); } + if (!_heap_cross_ref) { + local_heap_cross_ref = true; + _heap_cross_ref = Traits::createHeapCrossRef(*G); + } + if (!_heap) { + local_heap = true; + _heap = Traits::createHeap(*_heap_cross_ref); + } } public : @@ -315,13 +354,34 @@ : public Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> { typedef Dijkstra< Graph, LengthMap, DefGraphProcessedMapTraits> Create; }; + + template + struct DefHeapTraits : public Traits { + typedef CR HeapCrossRef; + typedef H Heap; + static HeapCrossRef *createHeapCrossRef(const Graph &G) { + return new HeapCrossRef(G); + } + static Heap *createHeap(HeapCrossRef &R) + { + return new Heap(R); + } + }; + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type + + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type + /// + template > + struct DefHeap + : public Dijkstra< Graph, LengthMap, DefHeapTraits > { + typedef Dijkstra< Graph, LengthMap, DefHeapTraits > Create; + }; ///@} - private: - typename Graph::template NodeMap _heap_map; - Heap _heap; protected: Dijkstra() {} @@ -337,7 +397,8 @@ _pred(NULL), local_pred(false), _dist(NULL), local_dist(false), _processed(NULL), local_processed(false), - _heap_map(*G,-1),_heap(_heap_map) + _heap_cross_ref(NULL), local_heap_cross_ref(false), + _heap(NULL), local_heap(false) { } ///Destructor. @@ -346,6 +407,8 @@ if(local_pred) delete _pred; if(local_dist) delete _dist; if(local_processed) delete _processed; + if(local_heap_cross_ref) delete _heap_cross_ref; + if(local_heap) delete _heap; } ///Sets the length map. @@ -416,16 +479,14 @@ ///Initializes the internal data structures. /// - ///\todo _heap_map's type could also be in the traits class. - ///\todo The heaps should be able to make themselves empty directly. void init() { create_maps(); - while(!_heap.empty()) _heap.pop(); + _heap->clear(); for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { _pred->set(u,INVALID); _processed->set(u,false); - _heap_map.set(u,Heap::PRE_HEAP); + _heap_cross_ref->set(u,Heap::PRE_HEAP); } } @@ -440,9 +501,10 @@ ///or the shortest path found till then is longer then \c dst. void addSource(Node s,Value dst=0) { - if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst); - else if(_heap[s]state(s) != Heap::IN_HEAP) { + _heap->push(s,dst); + } else if((*_heap)[s]push(s,dst); _pred->set(s,INVALID); } } @@ -456,21 +518,21 @@ ///\warning The priority heap must not be empty! Node processNextNode() { - Node v=_heap.top(); - Value oldvalue=_heap[v]; - _heap.pop(); + Node v=_heap->top(); + Value oldvalue=_heap->prio(); + _heap->pop(); finalizeNodeData(v,oldvalue); for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { Node w=G->target(e); - switch(_heap.state(w)) { + switch(_heap->state(w)) { case Heap::PRE_HEAP: - _heap.push(w,oldvalue+(*length)[e]); + _heap->push(w,oldvalue+(*length)[e]); _pred->set(w,e); break; case Heap::IN_HEAP: - if ( oldvalue+(*length)[e] < _heap[w] ) { - _heap.decrease(w, oldvalue+(*length)[e]); + if ( oldvalue+(*length)[e] < (*_heap)[w] ) { + _heap->decrease(w, oldvalue+(*length)[e]); _pred->set(w,e); } break; @@ -489,7 +551,7 @@ /// is empty. Node nextNode() { - return _heap.empty()?_heap.top():INVALID; + return _heap->empty()?_heap->top():INVALID; } ///\brief Returns \c false if there are nodes @@ -497,12 +559,12 @@ /// ///Returns \c false if there are nodes ///to be processed in the priority heap - bool emptyQueue() { return _heap.empty(); } + bool emptyQueue() { return _heap->empty(); } ///Returns the number of the nodes to be processed in the priority heap ///Returns the number of the nodes to be processed in the priority heap /// - int queueSize() { return _heap.size(); } + int queueSize() { return _heap->size(); } ///Executes the algorithm. @@ -520,7 +582,7 @@ /// void start() { - while ( !_heap.empty() ) processNextNode(); + while ( !_heap->empty() ) processNextNode(); } ///Executes the algorithm until \c dest is reached. @@ -539,8 +601,8 @@ /// void start(Node dest) { - while ( !_heap.empty() && _heap.top()!=dest ) processNextNode(); - if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); + while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); } ///Executes the algorithm until a condition is met. @@ -555,8 +617,8 @@ template void start(const NodeBoolMap &nm) { - while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode(); - if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio()); + while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode(); + if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); } ///Runs %Dijkstra algorithm from node \c s. @@ -683,7 +745,7 @@ ///\warning The source nodes are inditated as unreached. ///\pre \ref run() must be called before using this function. /// - bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; } + bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } ///@} }; @@ -711,15 +773,37 @@ typedef typename LM::Value Value; ///The heap type used by Dijkstra algorithm. + /// The cross reference type used by heap. + + /// The cross reference type used by heap. + /// Usually it is \c Graph::NodeMap. + typedef typename Graph::template NodeMap HeapCrossRef; + ///Instantiates a HeapCrossRef. + + ///This function instantiates a \ref HeapCrossRef. + /// \param G is the graph, to which we would like to define the + /// HeapCrossRef. + /// \todo The graph alone may be insufficient for the initialization + static HeapCrossRef *createHeapCrossRef(const GR &G) + { + return new HeapCrossRef(G); + } + + ///The heap type used by Dijkstra algorithm. + ///The heap type used by Dijkstra algorithm. /// ///\sa BinHeap ///\sa Dijkstra - typedef BinHeap, std::less > Heap; + static Heap *createHeap(HeapCrossRef& R) + { + return new Heap(R); + } + ///\brief The type of the map that stores the last ///edges of the shortest paths. /// @@ -807,8 +891,6 @@ void *_length; ///Pointer to the map of predecessors edges. void *_pred; -// ///Pointer to the map of predecessors nodes. -// void *_predNode; ///Pointer to the map of distances. void *_dist; ///Pointer to the source node. @@ -820,7 +902,6 @@ /// This constructor does not require parameters, therefore it initiates /// all of the attributes to default values (0, INVALID). DijkstraWizardBase() : _g(0), _length(0), _pred(0), -// _predNode(0), _dist(0), _source(INVALID) {} /// Constructor. @@ -833,7 +914,6 @@ /// \param s is the initial value of \ref _source DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : _g((void *)&g), _length((void *)&l), _pred(0), -// _predNode(0), _dist(0), _source(s) {} }; @@ -855,8 +935,8 @@ /// return the needed class. /// /// It does not have own \ref run method. When its \ref run method is called - /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run - /// method of it. + /// it initiates a plain \ref Dijkstra class, and calls the \ref + /// Dijkstra::run method of it. template class DijkstraWizard : public TR { @@ -880,12 +960,8 @@ ///\brief The type of the map that stores the last ///edges of the shortest paths. typedef typename TR::PredMap PredMap; -// ///\brief The type of the map that stores the last but one -// ///nodes of the shortest paths. -// typedef typename TR::PredNodeMap PredNodeMap; ///The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; - ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; public: @@ -914,7 +990,6 @@ Dijkstra dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length); if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred); -// if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode); if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist); dij.run(Base::_source); } @@ -949,27 +1024,6 @@ return DijkstraWizard >(*this); } - -// template -// struct DefPredNodeMapBase : public Base { -// typedef T PredNodeMap; -// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; -// DefPredNodeMapBase(const TR &b) : TR(b) {} -// }; - -// ///\brief \ref named-templ-param "Named parameter" -// ///function for setting PredNodeMap type -// /// -// /// \ref named-templ-param "Named parameter" -// ///function for setting PredNodeMap type -// /// -// template -// DijkstraWizard > predNodeMap(const T &t) -// { -// Base::_predNode=(void *)&t; -// return DijkstraWizard >(*this); -// } - template struct DefDistMapBase : public Base { typedef T DistMap;