# HG changeset patch # User alpar # Date 1088607031 0 # Node ID bdc429a557f2c77ead646ddad65069f014a19a5a # Parent 6094295ea31238a50be88a226e039be9c577ca6a - Now, it is possible to have Dijkstra store its result directly in given maps. - More docs. diff -r 6094295ea312 -r bdc429a557f2 src/hugo/dijkstra.h --- a/src/hugo/dijkstra.h Fri Jun 18 12:43:20 2004 +0000 +++ b/src/hugo/dijkstra.h Wed Jun 30 14:50:31 2004 +0000 @@ -72,16 +72,129 @@ typedef typename Graph::template NodeMap DistMap; private: - const Graph& G; - const LM& length; - PredMap predecessor; - PredNodeMap pred_node; - DistMap distance; + const Graph *G; + const LM *length; + // bool local_length; + PredMap *predecessor; + bool local_predecessor; + PredNodeMap *pred_node; + bool local_pred_node; + DistMap *distance; + bool local_distance; + + ///Initialize 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(!length) { +// local_length = true; +// length = new LM(G); +// } + 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 : Dijkstra(const Graph& _G, const LM& _length) : - G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } + G(&_G), length(&_length), + predecessor(NULL), pred_node(NULL), distance(NULL), + local_predecessor(false), local_pred_node(false), local_distance(false) + { } + + ~Dijkstra() + { + // if(local_length) delete length; + if(local_predecessor) delete predecessor; + if(local_pred_node) delete pred_node; + if(local_distance) delete distance; + } + + ///Sets the graph the algorithm will run on. + + ///Sets the graph the algorithm will run on. + ///\return (*this) + Dijkstra &setGraph(const Graph &_G) + { + G = &_G; + return *this; + } + ///Sets the length map. + + ///Sets the length map. + ///\return (*this) + Dijkstra &setLengthMap(const LM &m) + { +// if(local_length) { +// delete length; +// local_length=false; +// } + 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; + } void run(Node s); @@ -91,17 +204,18 @@ ///\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]; } + 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 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 + ///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. - Edge pred(Node v) const { return predecessor[v]; } + Edge pred(Node v) const { return (*predecessor)[v]; } ///Returns the 'previous node' of the shortest path tree. @@ -111,27 +225,27 @@ ///\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]; } + 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;} + 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;} + 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;} + const PredNodeMap &predNodeMap() const { return *pred_node;} ///Checks if a node is reachable from the root. @@ -140,7 +254,7 @@ ///\todo Is this what we want? ///\pre \ref run() must be called before using this function. /// - bool reached(Node v) { return G.valid(predecessor[v]); } + bool reached(Node v) { return G->valid((*predecessor)[v]); } }; @@ -160,14 +274,15 @@ template class Heap > void Dijkstra::run(Node s) { - - NodeIt u; - for ( G.first(u) ; G.valid(u) ; G.next(u) ) { - predecessor.set(u,INVALID); - pred_node.set(u,INVALID); + + init_maps(); + + for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) { + predecessor->set(u,INVALID); + pred_node->set(u,INVALID); } - typename GR::template NodeMap heap_map(G,-1); + typename GR::template NodeMap heap_map(*G,-1); typedef Heap, std::less > @@ -182,32 +297,29 @@ Node v=heap.top(); ValueType oldvalue=heap[v]; heap.pop(); - distance.set(v, oldvalue); + distance->set(v, oldvalue); - { //FIXME this bracket is for e to be local - OutEdgeIt e; - for(G.first(e, v); - G.valid(e); G.next(e)) { - Node w=G.bNode(e); + + for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) { + Node w=G->bNode(e); switch(heap.state(w)) { case HeapType::PRE_HEAP: - heap.push(w,oldvalue+length[e]); - predecessor.set(w,e); - pred_node.set(w,v); + 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); + 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; } } - } //FIXME tis bracket } }