lemon/dijkstra.h
changeset 295 7c796c1cf1b0
parent 287 bb40b6db0a58
child 301 9db8964f0cf6
equal deleted inserted replaced
16:b906cdd943b5 17:aebb19620cdd
   223             typename LM=typename GR::template ArcMap<int>,
   223             typename LM=typename GR::template ArcMap<int>,
   224             typename TR=DijkstraDefaultTraits<GR,LM> >
   224             typename TR=DijkstraDefaultTraits<GR,LM> >
   225 #endif
   225 #endif
   226   class Dijkstra {
   226   class Dijkstra {
   227   public:
   227   public:
   228     ///\ref Exception for uninitialized parameters.
       
   229 
       
   230     ///This error represents problems in the initialization of the
       
   231     ///parameters of the algorithm.
       
   232     class UninitializedParameter : public lemon::UninitializedParameter {
       
   233     public:
       
   234       virtual const char* what() const throw() {
       
   235         return "lemon::Dijkstra::UninitializedParameter";
       
   236       }
       
   237     };
       
   238 
   228 
   239     ///The type of the digraph the algorithm runs on.
   229     ///The type of the digraph the algorithm runs on.
   240     typedef typename TR::Digraph Digraph;
   230     typedef typename TR::Digraph Digraph;
   241 
   231 
   242     ///The type of the length of the arcs.
   232     ///The type of the length of the arcs.
   330     template <class T>
   320     template <class T>
   331     struct SetPredMapTraits : public Traits {
   321     struct SetPredMapTraits : public Traits {
   332       typedef T PredMap;
   322       typedef T PredMap;
   333       static PredMap *createPredMap(const Digraph &)
   323       static PredMap *createPredMap(const Digraph &)
   334       {
   324       {
   335         throw UninitializedParameter();
   325         LEMON_ASSERT(false, "PredMap is not initialized");
       
   326         return 0; // ignore warnings
   336       }
   327       }
   337     };
   328     };
   338     ///\brief \ref named-templ-param "Named parameter" for setting
   329     ///\brief \ref named-templ-param "Named parameter" for setting
   339     ///\ref PredMap type.
   330     ///\ref PredMap type.
   340     ///
   331     ///
   349     template <class T>
   340     template <class T>
   350     struct SetDistMapTraits : public Traits {
   341     struct SetDistMapTraits : public Traits {
   351       typedef T DistMap;
   342       typedef T DistMap;
   352       static DistMap *createDistMap(const Digraph &)
   343       static DistMap *createDistMap(const Digraph &)
   353       {
   344       {
   354         throw UninitializedParameter();
   345         LEMON_ASSERT(false, "DistMap is not initialized");
       
   346         return 0; // ignore warnings
   355       }
   347       }
   356     };
   348     };
   357     ///\brief \ref named-templ-param "Named parameter" for setting
   349     ///\brief \ref named-templ-param "Named parameter" for setting
   358     ///\ref DistMap type.
   350     ///\ref DistMap type.
   359     ///
   351     ///
   368     template <class T>
   360     template <class T>
   369     struct SetProcessedMapTraits : public Traits {
   361     struct SetProcessedMapTraits : public Traits {
   370       typedef T ProcessedMap;
   362       typedef T ProcessedMap;
   371       static ProcessedMap *createProcessedMap(const Digraph &)
   363       static ProcessedMap *createProcessedMap(const Digraph &)
   372       {
   364       {
   373         throw UninitializedParameter();
   365         LEMON_ASSERT(false, "ProcessedMap is not initialized");
       
   366         return 0; // ignore warnings
   374       }
   367       }
   375     };
   368     };
   376     ///\brief \ref named-templ-param "Named parameter" for setting
   369     ///\brief \ref named-templ-param "Named parameter" for setting
   377     ///\ref ProcessedMap type.
   370     ///\ref ProcessedMap type.
   378     ///
   371     ///
   406     template <class H, class CR>
   399     template <class H, class CR>
   407     struct SetHeapTraits : public Traits {
   400     struct SetHeapTraits : public Traits {
   408       typedef CR HeapCrossRef;
   401       typedef CR HeapCrossRef;
   409       typedef H Heap;
   402       typedef H Heap;
   410       static HeapCrossRef *createHeapCrossRef(const Digraph &) {
   403       static HeapCrossRef *createHeapCrossRef(const Digraph &) {
   411         throw UninitializedParameter();
   404         LEMON_ASSERT(false, "HeapCrossRef is not initialized");
       
   405         return 0; // ignore warnings
   412       }
   406       }
   413       static Heap *createHeap(HeapCrossRef &)
   407       static Heap *createHeap(HeapCrossRef &)
   414       {
   408       {
   415         throw UninitializedParameter();
   409         LEMON_ASSERT(false, "Heap is not initialized");
       
   410         return 0; // ignore warnings
   416       }
   411       }
   417     };
   412     };
   418     ///\brief \ref named-templ-param "Named parameter" for setting
   413     ///\brief \ref named-templ-param "Named parameter" for setting
   419     ///heap and cross reference type
   414     ///heap and cross reference type
   420     ///
   415     ///
  1156 
  1151 
  1157     ///This method runs %Dijkstra algorithm from the given source node
  1152     ///This method runs %Dijkstra algorithm from the given source node
  1158     ///in order to compute the shortest path to each node.
  1153     ///in order to compute the shortest path to each node.
  1159     void run(Node s)
  1154     void run(Node s)
  1160     {
  1155     {
  1161       if (s==INVALID) throw UninitializedParameter();
       
  1162       Dijkstra<Digraph,LengthMap,TR>
  1156       Dijkstra<Digraph,LengthMap,TR>
  1163         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1157         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1164              *reinterpret_cast<const LengthMap*>(Base::_length));
  1158              *reinterpret_cast<const LengthMap*>(Base::_length));
  1165       if (Base::_pred)
  1159       if (Base::_pred)
  1166         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1160         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1178     ///(it stops searching when \c t is processed).
  1172     ///(it stops searching when \c t is processed).
  1179     ///
  1173     ///
  1180     ///\return \c true if \c t is reachable form \c s.
  1174     ///\return \c true if \c t is reachable form \c s.
  1181     bool run(Node s, Node t)
  1175     bool run(Node s, Node t)
  1182     {
  1176     {
  1183       if (s==INVALID || t==INVALID) throw UninitializedParameter();
       
  1184       Dijkstra<Digraph,LengthMap,TR>
  1177       Dijkstra<Digraph,LengthMap,TR>
  1185         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1178         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1186              *reinterpret_cast<const LengthMap*>(Base::_length));
  1179              *reinterpret_cast<const LengthMap*>(Base::_length));
  1187       if (Base::_pred)
  1180       if (Base::_pred)
  1188         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1181         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));