lemon/dijkstra.h
changeset 555 b779c4dc7496
parent 440 88ed40ad0d4f
child 559 c5fd2d996909
equal deleted inserted replaced
23:5f5e9a5f2538 24:c63c1a4939a1
    71     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    71     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    72     typedef LM LengthMap;
    72     typedef LM LengthMap;
    73     ///The type of the length of the arcs.
    73     ///The type of the length of the arcs.
    74     typedef typename LM::Value Value;
    74     typedef typename LM::Value Value;
    75 
    75 
    76     /// Operation traits for Dijkstra algorithm.
    76     /// Operation traits for %Dijkstra algorithm.
    77 
    77 
    78     /// This class defines the operations that are used in the algorithm.
    78     /// This class defines the operations that are used in the algorithm.
    79     /// \see DijkstraDefaultOperationTraits
    79     /// \see DijkstraDefaultOperationTraits
    80     typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    80     typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    81 
    81 
    82     /// The cross reference type used by the heap.
    82     /// The cross reference type used by the heap.
    83 
    83 
    84     /// The cross reference type used by the heap.
    84     /// The cross reference type used by the heap.
    85     /// Usually it is \c Digraph::NodeMap<int>.
    85     /// Usually it is \c Digraph::NodeMap<int>.
    86     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    86     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    87     ///Instantiates a \ref HeapCrossRef.
    87     ///Instantiates a \c HeapCrossRef.
    88 
    88 
    89     ///This function instantiates a \ref HeapCrossRef.
    89     ///This function instantiates a \ref HeapCrossRef.
    90     /// \param g is the digraph, to which we would like to define the
    90     /// \param g is the digraph, to which we would like to define the
    91     /// \ref HeapCrossRef.
    91     /// \ref HeapCrossRef.
    92     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
    92     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
    93     {
    93     {
    94       return new HeapCrossRef(g);
    94       return new HeapCrossRef(g);
    95     }
    95     }
    96 
    96 
    97     ///The heap type used by the Dijkstra algorithm.
    97     ///The heap type used by the %Dijkstra algorithm.
    98 
    98 
    99     ///The heap type used by the Dijkstra algorithm.
    99     ///The heap type used by the Dijkstra algorithm.
   100     ///
   100     ///
   101     ///\sa BinHeap
   101     ///\sa BinHeap
   102     ///\sa Dijkstra
   102     ///\sa Dijkstra
   103     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
   103     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
   104     ///Instantiates a \ref Heap.
   104     ///Instantiates a \c Heap.
   105 
   105 
   106     ///This function instantiates a \ref Heap.
   106     ///This function instantiates a \ref Heap.
   107     static Heap *createHeap(HeapCrossRef& r)
   107     static Heap *createHeap(HeapCrossRef& r)
   108     {
   108     {
   109       return new Heap(r);
   109       return new Heap(r);
   114     ///
   114     ///
   115     ///The type of the map that stores the predecessor
   115     ///The type of the map that stores the predecessor
   116     ///arcs of the shortest paths.
   116     ///arcs of the shortest paths.
   117     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   117     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   118     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   118     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   119     ///Instantiates a PredMap.
   119     ///Instantiates a \c PredMap.
   120 
   120 
   121     ///This function instantiates a PredMap.
   121     ///This function instantiates a \ref PredMap.
   122     ///\param g is the digraph, to which we would like to define the
   122     ///\param g is the digraph, to which we would like to define the
   123     ///PredMap.
   123     ///\ref PredMap.
   124     static PredMap *createPredMap(const Digraph &g)
   124     static PredMap *createPredMap(const Digraph &g)
   125     {
   125     {
   126       return new PredMap(g);
   126       return new PredMap(g);
   127     }
   127     }
   128 
   128 
   130 
   130 
   131     ///The type of the map that indicates which nodes are processed.
   131     ///The type of the map that indicates which nodes are processed.
   132     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   132     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   133     ///By default it is a NullMap.
   133     ///By default it is a NullMap.
   134     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   134     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   135     ///Instantiates a ProcessedMap.
   135     ///Instantiates a \c ProcessedMap.
   136 
   136 
   137     ///This function instantiates a ProcessedMap.
   137     ///This function instantiates a \ref ProcessedMap.
   138     ///\param g is the digraph, to which
   138     ///\param g is the digraph, to which
   139     ///we would like to define the ProcessedMap
   139     ///we would like to define the \ref ProcessedMap.
   140 #ifdef DOXYGEN
   140 #ifdef DOXYGEN
   141     static ProcessedMap *createProcessedMap(const Digraph &g)
   141     static ProcessedMap *createProcessedMap(const Digraph &g)
   142 #else
   142 #else
   143     static ProcessedMap *createProcessedMap(const Digraph &)
   143     static ProcessedMap *createProcessedMap(const Digraph &)
   144 #endif
   144 #endif
   149     ///The type of the map that stores the distances of the nodes.
   149     ///The type of the map that stores the distances of the nodes.
   150 
   150 
   151     ///The type of the map that stores the distances of the nodes.
   151     ///The type of the map that stores the distances of the nodes.
   152     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   152     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   153     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   153     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   154     ///Instantiates a DistMap.
   154     ///Instantiates a \c DistMap.
   155 
   155 
   156     ///This function instantiates a DistMap.
   156     ///This function instantiates a \ref DistMap.
   157     ///\param g is the digraph, to which we would like to define
   157     ///\param g is the digraph, to which we would like to define
   158     ///the DistMap
   158     ///the \ref DistMap.
   159     static DistMap *createDistMap(const Digraph &g)
   159     static DistMap *createDistMap(const Digraph &g)
   160     {
   160     {
   161       return new DistMap(g);
   161       return new DistMap(g);
   162     }
   162     }
   163   };
   163   };
   214     typedef PredMapPath<Digraph, PredMap> Path;
   214     typedef PredMapPath<Digraph, PredMap> Path;
   215     ///The cross reference type used for the current heap.
   215     ///The cross reference type used for the current heap.
   216     typedef typename TR::HeapCrossRef HeapCrossRef;
   216     typedef typename TR::HeapCrossRef HeapCrossRef;
   217     ///The heap type used by the algorithm.
   217     ///The heap type used by the algorithm.
   218     typedef typename TR::Heap Heap;
   218     typedef typename TR::Heap Heap;
   219     ///The operation traits class.
   219     ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
       
   220     ///of the algorithm.
   220     typedef typename TR::OperationTraits OperationTraits;
   221     typedef typename TR::OperationTraits OperationTraits;
   221 
   222 
   222     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
   223     ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
   223     typedef TR Traits;
   224     typedef TR Traits;
   224 
   225 
   230     typedef typename Digraph::OutArcIt OutArcIt;
   231     typedef typename Digraph::OutArcIt OutArcIt;
   231 
   232 
   232     //Pointer to the underlying digraph.
   233     //Pointer to the underlying digraph.
   233     const Digraph *G;
   234     const Digraph *G;
   234     //Pointer to the length map.
   235     //Pointer to the length map.
   235     const LengthMap *length;
   236     const LengthMap *_length;
   236     //Pointer to the map of predecessors arcs.
   237     //Pointer to the map of predecessors arcs.
   237     PredMap *_pred;
   238     PredMap *_pred;
   238     //Indicates if _pred is locally allocated (true) or not.
   239     //Indicates if _pred is locally allocated (true) or not.
   239     bool local_pred;
   240     bool local_pred;
   240     //Pointer to the map of distances.
   241     //Pointer to the map of distances.
   295         LEMON_ASSERT(false, "PredMap is not initialized");
   296         LEMON_ASSERT(false, "PredMap is not initialized");
   296         return 0; // ignore warnings
   297         return 0; // ignore warnings
   297       }
   298       }
   298     };
   299     };
   299     ///\brief \ref named-templ-param "Named parameter" for setting
   300     ///\brief \ref named-templ-param "Named parameter" for setting
   300     ///PredMap type.
   301     ///\c PredMap type.
   301     ///
   302     ///
   302     ///\ref named-templ-param "Named parameter" for setting
   303     ///\ref named-templ-param "Named parameter" for setting
   303     ///PredMap type.
   304     ///\c PredMap type.
   304     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   305     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   305     template <class T>
   306     template <class T>
   306     struct SetPredMap
   307     struct SetPredMap
   307       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   308       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   308       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   309       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   316         LEMON_ASSERT(false, "DistMap is not initialized");
   317         LEMON_ASSERT(false, "DistMap is not initialized");
   317         return 0; // ignore warnings
   318         return 0; // ignore warnings
   318       }
   319       }
   319     };
   320     };
   320     ///\brief \ref named-templ-param "Named parameter" for setting
   321     ///\brief \ref named-templ-param "Named parameter" for setting
   321     ///DistMap type.
   322     ///\c DistMap type.
   322     ///
   323     ///
   323     ///\ref named-templ-param "Named parameter" for setting
   324     ///\ref named-templ-param "Named parameter" for setting
   324     ///DistMap type.
   325     ///\c DistMap type.
   325     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   326     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   326     template <class T>
   327     template <class T>
   327     struct SetDistMap
   328     struct SetDistMap
   328       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   329       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   329       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   330       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   337         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   338         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   338         return 0; // ignore warnings
   339         return 0; // ignore warnings
   339       }
   340       }
   340     };
   341     };
   341     ///\brief \ref named-templ-param "Named parameter" for setting
   342     ///\brief \ref named-templ-param "Named parameter" for setting
   342     ///ProcessedMap type.
   343     ///\c ProcessedMap type.
   343     ///
   344     ///
   344     ///\ref named-templ-param "Named parameter" for setting
   345     ///\ref named-templ-param "Named parameter" for setting
   345     ///ProcessedMap type.
   346     ///\c ProcessedMap type.
   346     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   347     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   347     template <class T>
   348     template <class T>
   348     struct SetProcessedMap
   349     struct SetProcessedMap
   349       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   350       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   350       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   351       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   356       {
   357       {
   357         return new ProcessedMap(g);
   358         return new ProcessedMap(g);
   358       }
   359       }
   359     };
   360     };
   360     ///\brief \ref named-templ-param "Named parameter" for setting
   361     ///\brief \ref named-templ-param "Named parameter" for setting
   361     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   362     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   362     ///
   363     ///
   363     ///\ref named-templ-param "Named parameter" for setting
   364     ///\ref named-templ-param "Named parameter" for setting
   364     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   365     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   365     ///If you don't set it explicitly, it will be automatically allocated.
   366     ///If you don't set it explicitly, it will be automatically allocated.
   366     struct SetStandardProcessedMap
   367     struct SetStandardProcessedMap
   367       : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
   368       : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
   368       typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
   369       typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
   369       Create;
   370       Create;
   437 
   438 
   438     /// \brief \ref named-templ-param "Named parameter" for setting
   439     /// \brief \ref named-templ-param "Named parameter" for setting
   439     ///\c OperationTraits type
   440     ///\c OperationTraits type
   440     ///
   441     ///
   441     ///\ref named-templ-param "Named parameter" for setting
   442     ///\ref named-templ-param "Named parameter" for setting
   442     ///\ref OperationTraits type.
   443     ///\c OperationTraits type.
   443     template <class T>
   444     template <class T>
   444     struct SetOperationTraits
   445     struct SetOperationTraits
   445       : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   446       : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
   446       typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
   447       typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
   447       Create;
   448       Create;
   456   public:
   457   public:
   457 
   458 
   458     ///Constructor.
   459     ///Constructor.
   459 
   460 
   460     ///Constructor.
   461     ///Constructor.
   461     ///\param _g The digraph the algorithm runs on.
   462     ///\param g The digraph the algorithm runs on.
   462     ///\param _length The length map used by the algorithm.
   463     ///\param length The length map used by the algorithm.
   463     Dijkstra(const Digraph& _g, const LengthMap& _length) :
   464     Dijkstra(const Digraph& g, const LengthMap& length) :
   464       G(&_g), length(&_length),
   465       G(&g), _length(&length),
   465       _pred(NULL), local_pred(false),
   466       _pred(NULL), local_pred(false),
   466       _dist(NULL), local_dist(false),
   467       _dist(NULL), local_dist(false),
   467       _processed(NULL), local_processed(false),
   468       _processed(NULL), local_processed(false),
   468       _heap_cross_ref(NULL), local_heap_cross_ref(false),
   469       _heap_cross_ref(NULL), local_heap_cross_ref(false),
   469       _heap(NULL), local_heap(false)
   470       _heap(NULL), local_heap(false)
   483 
   484 
   484     ///Sets the length map.
   485     ///Sets the length map.
   485     ///\return <tt> (*this) </tt>
   486     ///\return <tt> (*this) </tt>
   486     Dijkstra &lengthMap(const LengthMap &m)
   487     Dijkstra &lengthMap(const LengthMap &m)
   487     {
   488     {
   488       length = &m;
   489       _length = &m;
   489       return *this;
   490       return *this;
   490     }
   491     }
   491 
   492 
   492     ///Sets the map that stores the predecessor arcs.
   493     ///Sets the map that stores the predecessor arcs.
   493 
   494 
   636 
   637 
   637       for(OutArcIt e(*G,v); e!=INVALID; ++e) {
   638       for(OutArcIt e(*G,v); e!=INVALID; ++e) {
   638         Node w=G->target(e);
   639         Node w=G->target(e);
   639         switch(_heap->state(w)) {
   640         switch(_heap->state(w)) {
   640         case Heap::PRE_HEAP:
   641         case Heap::PRE_HEAP:
   641           _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
   642           _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
   642           _pred->set(w,e);
   643           _pred->set(w,e);
   643           break;
   644           break;
   644         case Heap::IN_HEAP:
   645         case Heap::IN_HEAP:
   645           {
   646           {
   646             Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
   647             Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
   647             if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
   648             if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
   648               _heap->decrease(w, newvalue);
   649               _heap->decrease(w, newvalue);
   649               _pred->set(w,e);
   650               _pred->set(w,e);
   650             }
   651             }
   651           }
   652           }