COIN-OR::LEMON - Graph Library

Changeset 281:e9b4fbe163f5 in lemon-1.2 for lemon/dijkstra.h


Ignore:
Timestamp:
09/26/08 09:52:28 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
280:e7f8647ce760 (diff), 279:6307bbbf285b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r278 r281  
    145145    ///\param g is the digraph, to which we would like to define the
    146146    ///\ref PredMap.
    147     ///\todo The digraph alone may be insufficient for the initialization
    148147    static PredMap *createPredMap(const Digraph &g)
    149148    {
     
    156155    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    157156    ///By default it is a NullMap.
    158     ///\todo If it is set to a real map,
    159     ///Dijkstra::processed() should read this.
    160157    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    161158    ///Instantiates a \ref ProcessedMap.
     
    298295    bool local_heap;
    299296
    300     ///Creates the maps if necessary.
    301     ///\todo Better memory allocation (instead of new).
     297    //Creates the maps if necessary.
    302298    void create_maps()
    303299    {
     
    959955    /// \param g is the digraph, to which we would like to define the
    960956    /// HeapCrossRef.
    961     /// \todo The digraph alone may be insufficient for the initialization
    962957    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
    963958    {
     
    995990    ///\param g is the digraph, to which we would like to define the
    996991    ///\ref PredMap.
    997     ///\todo The digraph alone may be insufficient to initialize
    998992    static PredMap *createPredMap(const Digraph &g)
    999993    {
     
    10061000    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10071001    ///By default it is a NullMap.
    1008     ///\todo If it is set to a real map,
    1009     ///Dijkstra::processed() should read this.
    1010     ///\todo named parameter to set this type, function to read and write.
    10111002    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    10121003    ///Instantiates a \ref ProcessedMap.
     
    10541045  /// The \ref DijkstraWizardBase is a class to be the default traits of the
    10551046  /// \ref DijkstraWizard class.
    1056   /// \todo More named parameters are required...
    10571047  template<class GR,class LM>
    10581048  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
  • lemon/dijkstra.h

    r280 r281  
    3131#include <lemon/error.h>
    3232#include <lemon/maps.h>
     33#include <lemon/path.h>
    3334
    3435namespace lemon {
     
    197198  ///It is also possible to change the underlying priority heap.
    198199  ///
    199   ///There is also a \ref dijkstra() "function type interface" for the
     200  ///There is also a \ref dijkstra() "function-type interface" for the
    200201  ///%Dijkstra algorithm, which is convenient in the simplier cases and
    201202  ///it can be used easier.
     
    983984    ///arcs of the shortest paths.
    984985    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    985     typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
     986    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    986987    ///Instantiates a \ref PredMap.
    987988
     
    989990    ///\param g is the digraph, to which we would like to define the
    990991    ///\ref PredMap.
    991 #ifdef DOXYGEN
    992992    static PredMap *createPredMap(const Digraph &g)
    993 #else
    994     static PredMap *createPredMap(const Digraph &)
    995 #endif
    996     {
    997       return new PredMap();
     993    {
     994      return new PredMap(g);
    998995    }
    999996
     
    10221019    ///The type of the map that stores the distances of the nodes.
    10231020    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1024     typedef NullMap<typename Digraph::Node,Value> DistMap;
     1021    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    10251022    ///Instantiates a \ref DistMap.
    10261023
     
    10281025    ///\param g is the digraph, to which we would like to define
    10291026    ///the \ref DistMap
    1030 #ifdef DOXYGEN
    10311027    static DistMap *createDistMap(const Digraph &g)
    1032 #else
    1033     static DistMap *createDistMap(const Digraph &)
    1034 #endif
    1035     {
    1036       return new DistMap();
    1037     }
     1028    {
     1029      return new DistMap(g);
     1030    }
     1031
     1032    ///The type of the shortest paths.
     1033
     1034    ///The type of the shortest paths.
     1035    ///It must meet the \ref concepts::Path "Path" concept.
     1036    typedef lemon::Path<Digraph> Path;
    10381037  };
    10391038
     
    10561055    //Pointer to the digraph the algorithm runs on.
    10571056    void *_g;
    1058     //Pointer to the length map
     1057    //Pointer to the length map.
    10591058    void *_length;
    10601059    //Pointer to the map of processed nodes.
     
    10641063    //Pointer to the map of distances.
    10651064    void *_dist;
    1066     //Pointer to the source node.
    1067     Node _source;
     1065    //Pointer to the shortest path to the target node.
     1066    void *_path;
     1067    //Pointer to the distance of the target node.
     1068    void *_di;
    10681069
    10691070  public:
     
    10711072
    10721073    /// This constructor does not require parameters, therefore it initiates
    1073     /// all of the attributes to default values (0, INVALID).
     1074    /// all of the attributes to \c 0.
    10741075    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
    1075                            _dist(0), _source(INVALID) {}
     1076                           _dist(0), _path(0), _di(0) {}
    10761077
    10771078    /// Constructor.
    10781079
    1079     /// This constructor requires some parameters,
    1080     /// listed in the parameters list.
    1081     /// Others are initiated to 0.
     1080    /// This constructor requires two parameters,
     1081    /// others are initiated to \c 0.
    10821082    /// \param g The digraph the algorithm runs on.
    10831083    /// \param l The length map.
    1084     /// \param s The source node.
    1085     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
     1084    DijkstraWizardBase(const GR &g,const LM &l) :
    10861085      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    10871086      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
    1088       _processed(0), _pred(0), _dist(0), _source(s) {}
     1087      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
    10891088
    10901089  };
    10911090
    1092   /// Auxiliary class for the function type interface of Dijkstra algorithm.
    1093 
    1094   /// This auxiliary class is created to implement the function type
    1095   /// interface of \ref Dijkstra algorithm. It uses the functions and features
    1096   /// of the plain \ref Dijkstra, but it is much simpler to use it.
    1097   /// It should only be used through the \ref dijkstra() function, which makes
    1098   /// it easier to use the algorithm.
     1091  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
     1092
     1093  /// This auxiliary class is created to implement the
     1094  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
     1095  /// It does not have own \ref run() method, it uses the functions
     1096  /// and features of the plain \ref Dijkstra.
    10991097  ///
    1100   /// Simplicity means that the way to change the types defined
    1101   /// in the traits class is based on functions that returns the new class
    1102   /// and not on templatable built-in classes.
    1103   /// When using the plain \ref Dijkstra
    1104   /// the new class with the modified type comes from
    1105   /// the original class by using the ::
    1106   /// operator. In the case of \ref DijkstraWizard only
    1107   /// a function have to be called, and it will
    1108   /// return the needed class.
    1109   ///
    1110   /// It does not have own \ref run() method. When its \ref run() method
    1111   /// is called, it initiates a plain \ref Dijkstra object, and calls the
    1112   /// \ref Dijkstra::run() method of it.
     1098  /// This class should only be used through the \ref dijkstra() function,
     1099  /// which makes it easier to use the algorithm.
    11131100  template<class TR>
    11141101  class DijkstraWizard : public TR
     
    11351122    ///The type of the map that indicates which nodes are processed.
    11361123    typedef typename TR::ProcessedMap ProcessedMap;
     1124    ///The type of the shortest paths
     1125    typedef typename TR::Path Path;
    11371126    ///The heap type used by the dijkstra algorithm.
    11381127    typedef typename TR::Heap Heap;
     
    11471136    /// Constructor that requires parameters.
    11481137    /// These parameters will be the default values for the traits class.
    1149     DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
    1150       TR(g,l,s) {}
     1138    /// \param g The digraph the algorithm runs on.
     1139    /// \param l The length map.
     1140    DijkstraWizard(const Digraph &g, const LengthMap &l) :
     1141      TR(g,l) {}
    11511142
    11521143    ///Copy constructor
     
    11551146    ~DijkstraWizard() {}
    11561147
    1157     ///Runs Dijkstra algorithm from a source node.
    1158 
    1159     ///Runs Dijkstra algorithm from a source node.
    1160     ///The node can be given with the \ref source() function.
    1161     void run()
    1162     {
    1163       if(Base::_source==INVALID) throw UninitializedParameter();
     1148    ///Runs Dijkstra algorithm from the given source node.
     1149
     1150    ///This method runs %Dijkstra algorithm from the given source node
     1151    ///in order to compute the shortest path to each node.
     1152    void run(Node s)
     1153    {
     1154      if (s==INVALID) throw UninitializedParameter();
    11641155      Dijkstra<Digraph,LengthMap,TR>
    1165         dij(*reinterpret_cast<const Digraph*>(Base::_g),
    1166             *reinterpret_cast<const LengthMap*>(Base::_length));
    1167       if(Base::_processed)
    1168         dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    1169       if(Base::_pred)
    1170         dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    1171       if(Base::_dist)
    1172         dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    1173       dij.run(Base::_source);
    1174     }
    1175 
    1176     ///Runs Dijkstra algorithm from the given node.
    1177 
    1178     ///Runs Dijkstra algorithm from the given node.
    1179     ///\param s is the given source.
    1180     void run(Node s)
    1181     {
    1182       Base::_source=s;
    1183       run();
    1184     }
    1185 
    1186     /// Sets the source node, from which the Dijkstra algorithm runs.
    1187 
    1188     /// Sets the source node, from which the Dijkstra algorithm runs.
    1189     /// \param s is the source node.
    1190     DijkstraWizard<TR> &source(Node s)
    1191     {
    1192       Base::_source=s;
    1193       return *this;
     1156        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
     1157             *reinterpret_cast<const LengthMap*>(Base::_length));
     1158      if (Base::_pred)
     1159        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1160      if (Base::_dist)
     1161        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1162      if (Base::_processed)
     1163        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1164      dijk.run(s);
     1165    }
     1166
     1167    ///Finds the shortest path between \c s and \c t.
     1168
     1169    ///This method runs the %Dijkstra algorithm from node \c s
     1170    ///in order to compute the shortest path to node \c t
     1171    ///(it stops searching when \c t is processed).
     1172    ///
     1173    ///\return \c true if \c t is reachable form \c s.
     1174    bool run(Node s, Node t)
     1175    {
     1176      if (s==INVALID || t==INVALID) throw UninitializedParameter();
     1177      Dijkstra<Digraph,LengthMap,TR>
     1178        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
     1179             *reinterpret_cast<const LengthMap*>(Base::_length));
     1180      if (Base::_pred)
     1181        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1182      if (Base::_dist)
     1183        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1184      if (Base::_processed)
     1185        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1186      dijk.run(s,t);
     1187      if (Base::_path)
     1188        *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
     1189      if (Base::_di)
     1190        *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
     1191      return dijk.reached(t);
    11941192    }
    11951193
     
    12001198      SetPredMapBase(const TR &b) : TR(b) {}
    12011199    };
    1202     ///\brief \ref named-templ-param "Named parameter"
     1200    ///\brief \ref named-func-param "Named parameter"
    12031201    ///for setting \ref PredMap object.
    12041202    ///
    1205     ///\ref named-templ-param "Named parameter"
     1203    ///\ref named-func-param "Named parameter"
    12061204    ///for setting \ref PredMap object.
    12071205    template<class T>
     
    12101208      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    12111209      return DijkstraWizard<SetPredMapBase<T> >(*this);
     1210    }
     1211
     1212    template<class T>
     1213    struct SetDistMapBase : public Base {
     1214      typedef T DistMap;
     1215      static DistMap *createDistMap(const Digraph &) { return 0; };
     1216      SetDistMapBase(const TR &b) : TR(b) {}
     1217    };
     1218    ///\brief \ref named-func-param "Named parameter"
     1219    ///for setting \ref DistMap object.
     1220    ///
     1221    ///\ref named-func-param "Named parameter"
     1222    ///for setting \ref DistMap object.
     1223    template<class T>
     1224    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
     1225    {
     1226      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1227      return DijkstraWizard<SetDistMapBase<T> >(*this);
    12121228    }
    12131229
     
    12181234      SetProcessedMapBase(const TR &b) : TR(b) {}
    12191235    };
    1220     ///\brief \ref named-templ-param "Named parameter"
     1236    ///\brief \ref named-func-param "Named parameter"
    12211237    ///for setting \ref ProcessedMap object.
    12221238    ///
    1223     /// \ref named-templ-param "Named parameter"
     1239    /// \ref named-func-param "Named parameter"
    12241240    ///for setting \ref ProcessedMap object.
    12251241    template<class T>
     
    12311247
    12321248    template<class T>
    1233     struct SetDistMapBase : public Base {
    1234       typedef T DistMap;
    1235       static DistMap *createDistMap(const Digraph &) { return 0; };
    1236       SetDistMapBase(const TR &b) : TR(b) {}
    1237     };
    1238     ///\brief \ref named-templ-param "Named parameter"
    1239     ///for setting \ref DistMap object.
    1240     ///
    1241     ///\ref named-templ-param "Named parameter"
    1242     ///for setting \ref DistMap object.
     1249    struct SetPathBase : public Base {
     1250      typedef T Path;
     1251      SetPathBase(const TR &b) : TR(b) {}
     1252    };
     1253    ///\brief \ref named-func-param "Named parameter"
     1254    ///for getting the shortest path to the target node.
     1255    ///
     1256    ///\ref named-func-param "Named parameter"
     1257    ///for getting the shortest path to the target node.
    12431258    template<class T>
    1244     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
    1245     {
    1246       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1247       return DijkstraWizard<SetDistMapBase<T> >(*this);
     1259    DijkstraWizard<SetPathBase<T> > path(const T &t)
     1260    {
     1261      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1262      return DijkstraWizard<SetPathBase<T> >(*this);
     1263    }
     1264
     1265    ///\brief \ref named-func-param "Named parameter"
     1266    ///for getting the distance of the target node.
     1267    ///
     1268    ///\ref named-func-param "Named parameter"
     1269    ///for getting the distance of the target node.
     1270    DijkstraWizard dist(const Value &d)
     1271    {
     1272      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
     1273      return *this;
    12481274    }
    12491275
    12501276  };
    12511277
    1252   ///Function type interface for Dijkstra algorithm.
     1278  ///Function-type interface for Dijkstra algorithm.
    12531279
    12541280  /// \ingroup shortest_path
    1255   ///Function type interface for Dijkstra algorithm.
     1281  ///Function-type interface for Dijkstra algorithm.
    12561282  ///
    1257   ///This function also has several
    1258   ///\ref named-templ-func-param "named parameters",
     1283  ///This function also has several \ref named-func-param "named parameters",
    12591284  ///they are declared as the members of class \ref DijkstraWizard.
    1260   ///The following
    1261   ///example shows how to use these parameters.
     1285  ///The following examples show how to use these parameters.
    12621286  ///\code
    1263   ///  dijkstra(g,length,source).predMap(preds).run();
     1287  ///  // Compute shortest path from node s to each node
     1288  ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
     1289  ///
     1290  ///  // Compute shortest path from s to t
     1291  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12641292  ///\endcode
    12651293  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     
    12691297  template<class GR, class LM>
    12701298  DijkstraWizard<DijkstraWizardBase<GR,LM> >
    1271   dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
     1299  dijkstra(const GR &digraph, const LM &length)
    12721300  {
    1273     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
     1301    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
    12741302  }
    12751303
Note: See TracChangeset for help on using the changeset viewer.