# Changeset 1741:7a98fe2ed989 in lemon-0.x for lemon/johnson.h

Ignore:
Timestamp:
10/26/05 12:50:47 (15 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2269
Message:

Some modifications on shortest path algoritms:

• heap traits
• checked execution
File:
1 edited

### Legend:

Unmodified
 r1723 /// \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 /// \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); } /// /// 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 /// \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. ///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. _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 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; }; ///@} public: typedef Johnson Create; /// \brief Constructor. 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; } } ///\name Execution control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). /// \n /// If you need more control on the execution, /// Finally \ref start() will perform the actual path /// computation. ///@{ /// \brief Initializes the internal data structures. /// /// Initializes the internal data structures. void init() { create_maps(); } /// \brief Executes the algorithm. /// /// This method runs the %Johnson algorithm in order to compute /// the shortest path to each node pairs. The algorithm /// computes /// - 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); NullMap predMap; belmannford.predMap(predMap); protected: typedef typename BelmannFord:: template DefOperationTraits:: template DefPredMap >:: Create BelmannFordType; void shiftedRun(const BelmannFordType& belmannford) { belmannford.init(OperationTraits::zero()); belmannford.start(); 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) { 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) { } } public: ///\name Execution control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). /// \n /// If you need more control on the execution, /// Finally \ref start() will perform the actual path /// computation. ///@{ /// \brief Initializes the internal data structures. /// /// Initializes the internal data structures. void init() { create_maps(); } /// \brief Executes the algorithm. /// /// This method runs the %Johnson algorithm in order to compute /// the shortest path to each node pairs. The algorithm /// computes /// - The shortest path tree for each node. /// - The distance between each node pairs. void start() { BelmannFordType belmannford(*graph, *length); NullMap predMap; belmannford.predMap(predMap); belmannford.init(OperationTraits::zero()); belmannford.start(); 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.