# HG changeset patch # User deba # Date 1130323847 0 # Node ID 7a98fe2ed98924f605d44a710174e7d0ec38a295 # Parent 4cade85793633fc14679b504bfbe42bc1922e221 Some modifications on shortest path algoritms: - heap traits - checked execution diff -r 4cade8579363 -r 7a98fe2ed989 lemon/belmann_ford.h --- a/lemon/belmann_ford.h Mon Oct 24 17:03:02 2005 +0000 +++ b/lemon/belmann_ford.h Wed Oct 26 10:50:47 2005 +0000 @@ -412,7 +412,7 @@ void start() { int num = countNodes(*graph) - 1; for (int i = 0; i < num; ++i) { - bool ready = true; + bool done = true; for (EdgeIt it(*graph); it != INVALID; ++it) { Node source = graph->source(it); Node target = graph->target(it); @@ -421,14 +421,14 @@ if (OperationTraits::less(relaxed, (*_dist)[target])) { _pred->set(target, it); _dist->set(target, relaxed); - ready = false; + done = false; } } - if (ready) return; + if (done) return; } } - /// \brief Executes the algorithm and check the negative circles. + /// \brief Executes the algorithm and checks the negative circles. /// /// \pre init() must be called and at least one node should be added /// with addSource() before using this function. If there is @@ -442,7 +442,7 @@ bool checkedStart() { int num = countNodes(*graph); for (int i = 0; i < num; ++i) { - bool ready = true; + bool done = true; for (EdgeIt it(*graph); it != INVALID; ++it) { Node source = graph->source(it); Node target = graph->target(it); @@ -451,10 +451,10 @@ if (OperationTraits::less(relaxed, (*_dist)[target])) { _pred->set(target, it); _dist->set(target, relaxed); - ready = false; + done = false; } } - if (ready) return true; + if (done) return true; } return false; } diff -r 4cade8579363 -r 7a98fe2ed989 lemon/dijkstra.h --- a/lemon/dijkstra.h Mon Oct 24 17:03:02 2005 +0000 +++ b/lemon/dijkstra.h Wed Oct 26 10:50:47 2005 +0000 @@ -61,7 +61,6 @@ ///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); @@ -74,8 +73,7 @@ ///\sa BinHeap ///\sa Dijkstra typedef BinHeap, - std::less > Heap; + HeapCrossRef, std::less > Heap; static Heap *createHeap(HeapCrossRef& R) { @@ -360,12 +358,12 @@ struct DefHeapTraits : public Traits { typedef CR HeapCrossRef; typedef H Heap; - static HeapCrossRef *createHeapCrossRef(const Graph &G) { - return new HeapCrossRef(G); + static HeapCrossRef *createHeapCrossRef(const Graph &) { + throw UninitializedParameter(); } - static Heap *createHeap(HeapCrossRef &R) + static Heap *createHeap(HeapCrossRef &) { - return new Heap(R); + throw UninitializedParameter(); } }; ///\ref named-templ-param "Named parameter" for setting heap and cross @@ -379,6 +377,32 @@ : public Dijkstra< Graph, LengthMap, DefHeapTraits > { typedef Dijkstra< Graph, LengthMap, DefHeapTraits > Create; }; + + template + struct DefStandardHeapTraits : 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 with automatic allocation + + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type. It can allocate the heap and the cross reference + ///object if the cross reference's constructor waits for the graph as + ///parameter and the heap's constructor waits for the cross reference. + template > + struct DefStandardHeap + : public Dijkstra< Graph, LengthMap, DefStandardHeapTraits > { + typedef Dijkstra< Graph, LengthMap, DefStandardHeapTraits > + Create; + }; ///@} @@ -456,6 +480,28 @@ return *this; } + ///Sets the heap and the cross reference used by algorithm. + + ///Sets the heap and the cross reference used by 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 &heap(Heap& heap, HeapCrossRef &crossRef) + { + if(local_heap_cross_ref) { + delete _heap_cross_ref; + local_heap_cross_ref=false; + } + _heap_cross_ref = &crossRef; + if(local_heap) { + delete _heap; + local_heap=false; + } + _heap = &heap; + return *this; + } + private: void finalizeNodeData(Node v,Value dst) { diff -r 4cade8579363 -r 7a98fe2ed989 lemon/floyd_warshall.h --- a/lemon/floyd_warshall.h Mon Oct 24 17:03:02 2005 +0000 +++ b/lemon/floyd_warshall.h Wed Oct 26 10:50:47 2005 +0000 @@ -392,9 +392,9 @@ for (NodeIt it(*graph); it != INVALID; ++it) { for (NodeIt jt(*graph); jt != INVALID; ++jt) { _pred->set(it, jt, INVALID); - _dist->set(it, jt, it == jt ? - OperationTraits::zero() : OperationTraits::infinity()); + _dist->set(it, jt, OperationTraits::infinity()); } + _dist->set(it, it, OperationTraits::zero()); } for (EdgeIt it(*graph); it != INVALID; ++it) { Node source = graph->source(it); @@ -427,6 +427,24 @@ } } } + + /// \brief Executes the algorithm and checks the negative circles. + /// + /// This method runs the %FloydWarshall algorithm in order to compute + /// the shortest path to each node pairs. If there is a negative circle + /// in the graph it gives back false. + /// The algorithm computes + /// - The shortest path tree for each node. + /// - The distance between each node pairs. + bool checkedStart() { + start(); + for (NodeIt it(*graph); it != INVALID; ++it) { + if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) { + return false; + } + } + return true; + } /// \brief Runs %FloydWarshall algorithm. /// diff -r 4cade8579363 -r 7a98fe2ed989 lemon/johnson.h --- a/lemon/johnson.h Mon Oct 24 17:03:02 2005 +0000 +++ b/lemon/johnson.h Wed Oct 26 10:50:47 2005 +0000 @@ -106,6 +106,38 @@ /// and the used operation. /// \see JohnsonDefaultOperationTraits typedef JohnsonDefaultOperationTraits OperationTraits; + + /// 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 graph is the graph, to which we would like to define the + /// HeapCrossRef. + static HeapCrossRef *createHeapCrossRef(const Graph& graph) { + return new HeapCrossRef(graph); + } + + ///The heap type used by Dijkstra algorithm. + + ///The heap type used by Dijkstra algorithm. + /// + ///\sa BinHeap + ///\sa Dijkstra + typedef BinHeap > Heap; + + ///Instantiates a Heap. + + ///This function instantiates a \ref Heap. + /// \param crossRef The cross reference for the heap. + static Heap *createHeap(HeapCrossRef& crossRef) { + return new Heap(crossRef); + } /// \brief The type of the matrix map that stores the last edges of the /// shortest paths. @@ -121,7 +153,7 @@ /// This function instantiates a \ref PredMap. /// \param G is the graph, to which we would like to define the PredMap. /// \todo The graph alone may be insufficient for the initialization - static PredMap *createPredMap(const _Graph& graph) { + static PredMap *createPredMap(const Graph& graph) { return new PredMap(graph); } @@ -158,7 +190,9 @@ /// should be used from each node. /// /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or - /// with fibonacci heap O(n^2 * log(n) + n * e). + /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap + /// implementation is slower than either binary heap implementation or the + /// Floyd-Warshall algorithm. /// /// The type of the length is determined by the /// \ref concept::ReadMap::Value "Value" of the length map. @@ -225,6 +259,10 @@ typedef typename _Traits::DistMap DistMap; /// \brief The operation traits. typedef typename _Traits::OperationTraits OperationTraits; + ///The cross reference type used for the current heap. + typedef typename _Traits::HeapCrossRef HeapCrossRef; + ///The heap type used by the dijkstra algorithm. + typedef typename _Traits::Heap Heap; private: /// Pointer to the underlying graph. const Graph *graph; @@ -238,6 +276,14 @@ DistMap *_dist; ///Indicates if \ref _dist is locally allocated (\c true) or not. bool local_dist; + ///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. void create_maps() { @@ -249,9 +295,19 @@ local_dist = true; _dist = Traits::createDistMap(*graph); } + if (!_heap_cross_ref) { + local_heap_cross_ref = true; + _heap_cross_ref = Traits::createHeapCrossRef(*graph); + } + if (!_heap) { + local_heap = true; + _heap = Traits::createHeap(*_heap_cross_ref); + } } - + public : + + typedef Johnson Create; /// \name Named template parameters @@ -308,6 +364,56 @@ : public Johnson< Graph, LengthMap, DefOperationTraitsTraits > { typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits > Create; }; + + template + struct DefHeapTraits : public Traits { + typedef CR HeapCrossRef; + typedef H Heap; + static HeapCrossRef *createHeapCrossRef(const Graph &) { + throw UninitializedParameter(); + } + static Heap *createHeap(HeapCrossRef &) + { + throw UninitializedParameter(); + } + }; + ///\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 Johnson< Graph, LengthMap, DefHeapTraits > { + typedef Johnson< Graph, LengthMap, DefHeapTraits > Create; + }; + + template + struct DefStandardHeapTraits : 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 with automatic allocation + + ///\ref named-templ-param "Named parameter" for setting heap and cross + ///reference type. It can allocate the heap and the cross reference + ///object if the cross reference's constructor waits for the graph as + ///parameter and the heap's constructor waits for the cross reference. + template > + struct DefStandardHeap + : public Johnson< Graph, LengthMap, DefStandardHeapTraits > { + typedef Johnson< Graph, LengthMap, DefStandardHeapTraits > + Create; + }; ///@} @@ -316,6 +422,8 @@ Johnson() {} public: + + typedef Johnson Create; /// \brief Constructor. /// @@ -324,12 +432,16 @@ Johnson(const Graph& _graph, const LengthMap& _length) : graph(&_graph), length(&_length), _pred(0), local_pred(false), - _dist(0), local_dist(false) {} + _dist(0), local_dist(false), + _heap_cross_ref(0), local_heap_cross_ref(false), + _heap(0), local_heap(false) {} ///Destructor. ~Johnson() { - if(local_pred) delete _pred; - if(local_dist) delete _dist; + if (local_pred) delete _pred; + if (local_dist) delete _dist; + if (local_heap_cross_ref) delete _heap_cross_ref; + if (local_heap) delete _heap; } /// \brief Sets the length map. @@ -373,6 +485,43 @@ return *this; } + protected: + + typedef typename BelmannFord:: + template DefOperationTraits:: + template DefPredMap >:: + Create BelmannFordType; + + void shiftedRun(const BelmannFordType& belmannford) { + + typedef PotentialDifferenceMap PotDiffMap; + PotDiffMap potdiff(*graph, belmannford.distMap()); + typedef SubMap ShiftLengthMap; + ShiftLengthMap shiftlen(*length, potdiff); + + typename Dijkstra:: + template DefHeap::Create dijkstra(*graph, shiftlen); + + dijkstra.heap(*_heap, *_heap_cross_ref); + + for (NodeIt it(*graph); it != INVALID; ++it) { + dijkstra.run(it); + for (NodeIt jt(*graph); jt != INVALID; ++jt) { + if (dijkstra.reached(jt)) { + _dist->set(it, jt, dijkstra.dist(jt) + + belmannford.dist(jt) - belmannford.dist(it)); + _pred->set(it, jt, dijkstra.pred(jt)); + } else { + _dist->set(it, jt, OperationTraits::infinity()); + _pred->set(it, jt, INVALID); + } + } + } + } + + public: + ///\name Execution control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). @@ -389,7 +538,7 @@ void init() { create_maps(); } - + /// \brief Executes the algorithm. /// /// This method runs the %Johnson algorithm in order to compute @@ -398,10 +547,6 @@ /// - The shortest path tree for each node. /// - The distance between each node pairs. void start() { - typedef typename BelmannFord:: - template DefOperationTraits:: - template DefPredMap >:: - Create BelmannFordType; BelmannFordType belmannford(*graph, *length); @@ -412,26 +557,32 @@ belmannford.init(OperationTraits::zero()); belmannford.start(); - for (NodeIt it(*graph); it != INVALID; ++it) { - typedef PotentialDifferenceMap PotDiffMap; - PotDiffMap potdiff(*graph, belmannford.distMap()); - typedef SubMap ShiftLengthMap; - ShiftLengthMap shiftlen(*length, potdiff); - Dijkstra dijkstra(*graph, shiftlen); - dijkstra.run(it); - for (NodeIt jt(*graph); jt != INVALID; ++jt) { - if (dijkstra.reached(jt)) { - _dist->set(it, jt, dijkstra.dist(jt) + - belmannford.dist(jt) - belmannford.dist(it)); - _pred->set(it, jt, dijkstra.pred(jt)); - } else { - _dist->set(it, jt, OperationTraits::infinity()); - _pred->set(it, jt, INVALID); - } - } - } + shiftedRun(belmannford); } + + /// \brief Executes the algorithm and checks the negatvie circles. + /// + /// This method runs the %Johnson algorithm in order to compute + /// the shortest path to each node pairs. If the graph contains + /// negative circle it gives back false. The algorithm + /// computes + /// - The shortest path tree for each node. + /// - The distance between each node pairs. + bool checkedStart() { + + BelmannFordType belmannford(*graph, *length); + + NullMap predMap; + + belmannford.predMap(predMap); + + belmannford.init(OperationTraits::zero()); + if (!belmannford.checkedStart()) return false; + + shiftedRun(belmannford); + return true; + } + /// \brief Runs %Johnson algorithm. ///