lemon/dijkstra.h
changeset 304 1e81878b0e54
parent 290 f6899946c1ac
child 313 64f8f7cc6168
equal deleted inserted replaced
17:aebb19620cdd 18:1113938fc00a
   137     ///
   137     ///
   138     ///The type of the map that stores the predecessor
   138     ///The type of the map that stores the predecessor
   139     ///arcs of the shortest paths.
   139     ///arcs of the shortest paths.
   140     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   140     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   141     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   141     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   142     ///Instantiates a \ref PredMap.
   142     ///Instantiates a PredMap.
   143 
   143 
   144     ///This function instantiates a \ref PredMap.
   144     ///This function instantiates a PredMap.
   145     ///\param g is the digraph, to which we would like to define the
   145     ///\param g is the digraph, to which we would like to define the
   146     ///\ref PredMap.
   146     ///PredMap.
   147     static PredMap *createPredMap(const Digraph &g)
   147     static PredMap *createPredMap(const Digraph &g)
   148     {
   148     {
   149       return new PredMap(g);
   149       return new PredMap(g);
   150     }
   150     }
   151 
   151 
   153 
   153 
   154     ///The type of the map that indicates which nodes are processed.
   154     ///The type of the map that indicates which nodes are processed.
   155     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   155     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   156     ///By default it is a NullMap.
   156     ///By default it is a NullMap.
   157     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   157     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   158     ///Instantiates a \ref ProcessedMap.
   158     ///Instantiates a ProcessedMap.
   159 
   159 
   160     ///This function instantiates a \ref ProcessedMap.
   160     ///This function instantiates a ProcessedMap.
   161     ///\param g is the digraph, to which
   161     ///\param g is the digraph, to which
   162     ///we would like to define the \ref ProcessedMap
   162     ///we would like to define the ProcessedMap
   163 #ifdef DOXYGEN
   163 #ifdef DOXYGEN
   164     static ProcessedMap *createProcessedMap(const Digraph &g)
   164     static ProcessedMap *createProcessedMap(const Digraph &g)
   165 #else
   165 #else
   166     static ProcessedMap *createProcessedMap(const Digraph &)
   166     static ProcessedMap *createProcessedMap(const Digraph &)
   167 #endif
   167 #endif
   172     ///The type of the map that stores the distances of the nodes.
   172     ///The type of the map that stores the distances of the nodes.
   173 
   173 
   174     ///The type of the map that stores the distances of the nodes.
   174     ///The type of the map that stores the distances of the nodes.
   175     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   175     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   176     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   176     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   177     ///Instantiates a \ref DistMap.
   177     ///Instantiates a DistMap.
   178 
   178 
   179     ///This function instantiates a \ref DistMap.
   179     ///This function instantiates a DistMap.
   180     ///\param g is the digraph, to which we would like to define
   180     ///\param g is the digraph, to which we would like to define
   181     ///the \ref DistMap
   181     ///the DistMap
   182     static DistMap *createDistMap(const Digraph &g)
   182     static DistMap *createDistMap(const Digraph &g)
   183     {
   183     {
   184       return new DistMap(g);
   184       return new DistMap(g);
   185     }
   185     }
   186   };
   186   };
   325         LEMON_ASSERT(false, "PredMap is not initialized");
   325         LEMON_ASSERT(false, "PredMap is not initialized");
   326         return 0; // ignore warnings
   326         return 0; // ignore warnings
   327       }
   327       }
   328     };
   328     };
   329     ///\brief \ref named-templ-param "Named parameter" for setting
   329     ///\brief \ref named-templ-param "Named parameter" for setting
   330     ///\ref PredMap type.
   330     ///PredMap type.
   331     ///
   331     ///
   332     ///\ref named-templ-param "Named parameter" for setting
   332     ///\ref named-templ-param "Named parameter" for setting
   333     ///\ref PredMap type.
   333     ///PredMap type.
   334     template <class T>
   334     template <class T>
   335     struct SetPredMap
   335     struct SetPredMap
   336       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   336       : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
   337       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   337       typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
   338     };
   338     };
   345         LEMON_ASSERT(false, "DistMap is not initialized");
   345         LEMON_ASSERT(false, "DistMap is not initialized");
   346         return 0; // ignore warnings
   346         return 0; // ignore warnings
   347       }
   347       }
   348     };
   348     };
   349     ///\brief \ref named-templ-param "Named parameter" for setting
   349     ///\brief \ref named-templ-param "Named parameter" for setting
   350     ///\ref DistMap type.
   350     ///DistMap type.
   351     ///
   351     ///
   352     ///\ref named-templ-param "Named parameter" for setting
   352     ///\ref named-templ-param "Named parameter" for setting
   353     ///\ref DistMap type.
   353     ///DistMap type.
   354     template <class T>
   354     template <class T>
   355     struct SetDistMap
   355     struct SetDistMap
   356       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   356       : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
   357       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   357       typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
   358     };
   358     };
   365         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   365         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   366         return 0; // ignore warnings
   366         return 0; // ignore warnings
   367       }
   367       }
   368     };
   368     };
   369     ///\brief \ref named-templ-param "Named parameter" for setting
   369     ///\brief \ref named-templ-param "Named parameter" for setting
   370     ///\ref ProcessedMap type.
   370     ///ProcessedMap type.
   371     ///
   371     ///
   372     ///\ref named-templ-param "Named parameter" for setting
   372     ///\ref named-templ-param "Named parameter" for setting
   373     ///\ref ProcessedMap type.
   373     ///ProcessedMap type.
   374     template <class T>
   374     template <class T>
   375     struct SetProcessedMap
   375     struct SetProcessedMap
   376       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   376       : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
   377       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   377       typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
   378     };
   378     };
   383       {
   383       {
   384         return new ProcessedMap(g);
   384         return new ProcessedMap(g);
   385       }
   385       }
   386     };
   386     };
   387     ///\brief \ref named-templ-param "Named parameter" for setting
   387     ///\brief \ref named-templ-param "Named parameter" for setting
   388     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   388     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   389     ///
   389     ///
   390     ///\ref named-templ-param "Named parameter" for setting
   390     ///\ref named-templ-param "Named parameter" for setting
   391     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   391     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   392     ///If you don't set it explicitly, it will be automatically allocated.
   392     ///If you don't set it explicitly, it will be automatically allocated.
   393     struct SetStandardProcessedMap
   393     struct SetStandardProcessedMap
   394       : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
   394       : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
   395       typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
   395       typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
   396       Create;
   396       Create;
   984     ///
   984     ///
   985     ///The type of the map that stores the predecessor
   985     ///The type of the map that stores the predecessor
   986     ///arcs of the shortest paths.
   986     ///arcs of the shortest paths.
   987     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   987     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   988     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   988     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   989     ///Instantiates a \ref PredMap.
   989     ///Instantiates a PredMap.
   990 
   990 
   991     ///This function instantiates a \ref PredMap.
   991     ///This function instantiates a PredMap.
   992     ///\param g is the digraph, to which we would like to define the
   992     ///\param g is the digraph, to which we would like to define the
   993     ///\ref PredMap.
   993     ///PredMap.
   994     static PredMap *createPredMap(const Digraph &g)
   994     static PredMap *createPredMap(const Digraph &g)
   995     {
   995     {
   996       return new PredMap(g);
   996       return new PredMap(g);
   997     }
   997     }
   998 
   998 
  1000 
  1000 
  1001     ///The type of the map that indicates which nodes are processed.
  1001     ///The type of the map that indicates which nodes are processed.
  1002     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1002     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1003     ///By default it is a NullMap.
  1003     ///By default it is a NullMap.
  1004     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
  1004     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
  1005     ///Instantiates a \ref ProcessedMap.
  1005     ///Instantiates a ProcessedMap.
  1006 
  1006 
  1007     ///This function instantiates a \ref ProcessedMap.
  1007     ///This function instantiates a ProcessedMap.
  1008     ///\param g is the digraph, to which
  1008     ///\param g is the digraph, to which
  1009     ///we would like to define the \ref ProcessedMap.
  1009     ///we would like to define the ProcessedMap.
  1010 #ifdef DOXYGEN
  1010 #ifdef DOXYGEN
  1011     static ProcessedMap *createProcessedMap(const Digraph &g)
  1011     static ProcessedMap *createProcessedMap(const Digraph &g)
  1012 #else
  1012 #else
  1013     static ProcessedMap *createProcessedMap(const Digraph &)
  1013     static ProcessedMap *createProcessedMap(const Digraph &)
  1014 #endif
  1014 #endif
  1019     ///The type of the map that stores the distances of the nodes.
  1019     ///The type of the map that stores the distances of the nodes.
  1020 
  1020 
  1021     ///The type of the map that stores the distances of the nodes.
  1021     ///The type of the map that stores the distances of the nodes.
  1022     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1022     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1023     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
  1023     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
  1024     ///Instantiates a \ref DistMap.
  1024     ///Instantiates a DistMap.
  1025 
  1025 
  1026     ///This function instantiates a \ref DistMap.
  1026     ///This function instantiates a DistMap.
  1027     ///\param g is the digraph, to which we would like to define
  1027     ///\param g is the digraph, to which we would like to define
  1028     ///the \ref DistMap
  1028     ///the DistMap
  1029     static DistMap *createDistMap(const Digraph &g)
  1029     static DistMap *createDistMap(const Digraph &g)
  1030     {
  1030     {
  1031       return new DistMap(g);
  1031       return new DistMap(g);
  1032     }
  1032     }
  1033 
  1033 
  1196       typedef T PredMap;
  1196       typedef T PredMap;
  1197       static PredMap *createPredMap(const Digraph &) { return 0; };
  1197       static PredMap *createPredMap(const Digraph &) { return 0; };
  1198       SetPredMapBase(const TR &b) : TR(b) {}
  1198       SetPredMapBase(const TR &b) : TR(b) {}
  1199     };
  1199     };
  1200     ///\brief \ref named-func-param "Named parameter"
  1200     ///\brief \ref named-func-param "Named parameter"
  1201     ///for setting \ref PredMap object.
  1201     ///for setting PredMap object.
  1202     ///
  1202     ///
  1203     ///\ref named-func-param "Named parameter"
  1203     ///\ref named-func-param "Named parameter"
  1204     ///for setting \ref PredMap object.
  1204     ///for setting PredMap object.
  1205     template<class T>
  1205     template<class T>
  1206     DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
  1206     DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
  1207     {
  1207     {
  1208       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1208       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1209       return DijkstraWizard<SetPredMapBase<T> >(*this);
  1209       return DijkstraWizard<SetPredMapBase<T> >(*this);
  1214       typedef T DistMap;
  1214       typedef T DistMap;
  1215       static DistMap *createDistMap(const Digraph &) { return 0; };
  1215       static DistMap *createDistMap(const Digraph &) { return 0; };
  1216       SetDistMapBase(const TR &b) : TR(b) {}
  1216       SetDistMapBase(const TR &b) : TR(b) {}
  1217     };
  1217     };
  1218     ///\brief \ref named-func-param "Named parameter"
  1218     ///\brief \ref named-func-param "Named parameter"
  1219     ///for setting \ref DistMap object.
  1219     ///for setting DistMap object.
  1220     ///
  1220     ///
  1221     ///\ref named-func-param "Named parameter"
  1221     ///\ref named-func-param "Named parameter"
  1222     ///for setting \ref DistMap object.
  1222     ///for setting DistMap object.
  1223     template<class T>
  1223     template<class T>
  1224     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
  1224     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
  1225     {
  1225     {
  1226       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1226       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1227       return DijkstraWizard<SetDistMapBase<T> >(*this);
  1227       return DijkstraWizard<SetDistMapBase<T> >(*this);
  1232       typedef T ProcessedMap;
  1232       typedef T ProcessedMap;
  1233       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1233       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1234       SetProcessedMapBase(const TR &b) : TR(b) {}
  1234       SetProcessedMapBase(const TR &b) : TR(b) {}
  1235     };
  1235     };
  1236     ///\brief \ref named-func-param "Named parameter"
  1236     ///\brief \ref named-func-param "Named parameter"
  1237     ///for setting \ref ProcessedMap object.
  1237     ///for setting ProcessedMap object.
  1238     ///
  1238     ///
  1239     /// \ref named-func-param "Named parameter"
  1239     /// \ref named-func-param "Named parameter"
  1240     ///for setting \ref ProcessedMap object.
  1240     ///for setting ProcessedMap object.
  1241     template<class T>
  1241     template<class T>
  1242     DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1242     DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1243     {
  1243     {
  1244       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1244       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1245       return DijkstraWizard<SetProcessedMapBase<T> >(*this);
  1245       return DijkstraWizard<SetProcessedMapBase<T> >(*this);