COIN-OR::LEMON - Graph Library

Changeset 278:931190050520 in lemon-1.0 for lemon/dijkstra.h


Ignore:
Timestamp:
09/22/08 15:33:23 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dijkstra.h

    r258 r278  
    3131#include <lemon/error.h>
    3232#include <lemon/maps.h>
     33#include <lemon/path.h>
    3334
    3435namespace lemon {
     
    200201  ///It is also possible to change the underlying priority heap.
    201202  ///
    202   ///There is also a \ref dijkstra() "function type interface" for the
     203  ///There is also a \ref dijkstra() "function-type interface" for the
    203204  ///%Dijkstra algorithm, which is convenient in the simplier cases and
    204205  ///it can be used easier.
     
    988989    ///arcs of the shortest paths.
    989990    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    990     typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
     991    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    991992    ///Instantiates a \ref PredMap.
    992993
     
    995996    ///\ref PredMap.
    996997    ///\todo The digraph alone may be insufficient to initialize
    997 #ifdef DOXYGEN
    998998    static PredMap *createPredMap(const Digraph &g)
    999 #else
    1000     static PredMap *createPredMap(const Digraph &)
    1001 #endif
    1002     {
    1003       return new PredMap();
     999    {
     1000      return new PredMap(g);
    10041001    }
    10051002
     
    10311028    ///The type of the map that stores the distances of the nodes.
    10321029    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1033     typedef NullMap<typename Digraph::Node,Value> DistMap;
     1030    typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
    10341031    ///Instantiates a \ref DistMap.
    10351032
     
    10371034    ///\param g is the digraph, to which we would like to define
    10381035    ///the \ref DistMap
    1039 #ifdef DOXYGEN
    10401036    static DistMap *createDistMap(const Digraph &g)
    1041 #else
    1042     static DistMap *createDistMap(const Digraph &)
    1043 #endif
    1044     {
    1045       return new DistMap();
    1046     }
     1037    {
     1038      return new DistMap(g);
     1039    }
     1040
     1041    ///The type of the shortest paths.
     1042
     1043    ///The type of the shortest paths.
     1044    ///It must meet the \ref concepts::Path "Path" concept.
     1045    typedef lemon::Path<Digraph> Path;
    10471046  };
    10481047
     
    10661065    //Pointer to the digraph the algorithm runs on.
    10671066    void *_g;
    1068     //Pointer to the length map
     1067    //Pointer to the length map.
    10691068    void *_length;
    10701069    //Pointer to the map of processed nodes.
     
    10741073    //Pointer to the map of distances.
    10751074    void *_dist;
    1076     //Pointer to the source node.
    1077     Node _source;
     1075    //Pointer to the shortest path to the target node.
     1076    void *_path;
     1077    //Pointer to the distance of the target node.
     1078    void *_di;
    10781079
    10791080  public:
     
    10811082
    10821083    /// This constructor does not require parameters, therefore it initiates
    1083     /// all of the attributes to default values (0, INVALID).
     1084    /// all of the attributes to \c 0.
    10841085    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
    1085                            _dist(0), _source(INVALID) {}
     1086                           _dist(0), _path(0), _di(0) {}
    10861087
    10871088    /// Constructor.
    10881089
    1089     /// This constructor requires some parameters,
    1090     /// listed in the parameters list.
    1091     /// Others are initiated to 0.
     1090    /// This constructor requires two parameters,
     1091    /// others are initiated to \c 0.
    10921092    /// \param g The digraph the algorithm runs on.
    10931093    /// \param l The length map.
    1094     /// \param s The source node.
    1095     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
     1094    DijkstraWizardBase(const GR &g,const LM &l) :
    10961095      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    10971096      _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
    1098       _processed(0), _pred(0), _dist(0), _source(s) {}
     1097      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
    10991098
    11001099  };
    11011100
    1102   /// Auxiliary class for the function type interface of Dijkstra algorithm.
    1103 
    1104   /// This auxiliary class is created to implement the function type
    1105   /// interface of \ref Dijkstra algorithm. It uses the functions and features
    1106   /// of the plain \ref Dijkstra, but it is much simpler to use it.
    1107   /// It should only be used through the \ref dijkstra() function, which makes
    1108   /// it easier to use the algorithm.
     1101  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
     1102
     1103  /// This auxiliary class is created to implement the
     1104  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
     1105  /// It does not have own \ref run() method, it uses the functions
     1106  /// and features of the plain \ref Dijkstra.
    11091107  ///
    1110   /// Simplicity means that the way to change the types defined
    1111   /// in the traits class is based on functions that returns the new class
    1112   /// and not on templatable built-in classes.
    1113   /// When using the plain \ref Dijkstra
    1114   /// the new class with the modified type comes from
    1115   /// the original class by using the ::
    1116   /// operator. In the case of \ref DijkstraWizard only
    1117   /// a function have to be called, and it will
    1118   /// return the needed class.
    1119   ///
    1120   /// It does not have own \ref run() method. When its \ref run() method
    1121   /// is called, it initiates a plain \ref Dijkstra object, and calls the
    1122   /// \ref Dijkstra::run() method of it.
     1108  /// This class should only be used through the \ref dijkstra() function,
     1109  /// which makes it easier to use the algorithm.
    11231110  template<class TR>
    11241111  class DijkstraWizard : public TR
     
    11451132    ///The type of the map that indicates which nodes are processed.
    11461133    typedef typename TR::ProcessedMap ProcessedMap;
     1134    ///The type of the shortest paths
     1135    typedef typename TR::Path Path;
    11471136    ///The heap type used by the dijkstra algorithm.
    11481137    typedef typename TR::Heap Heap;
     
    11571146    /// Constructor that requires parameters.
    11581147    /// These parameters will be the default values for the traits class.
    1159     DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
    1160       TR(g,l,s) {}
     1148    /// \param g The digraph the algorithm runs on.
     1149    /// \param l The length map.
     1150    DijkstraWizard(const Digraph &g, const LengthMap &l) :
     1151      TR(g,l) {}
    11611152
    11621153    ///Copy constructor
     
    11651156    ~DijkstraWizard() {}
    11661157
    1167     ///Runs Dijkstra algorithm from a source node.
    1168 
    1169     ///Runs Dijkstra algorithm from a source node.
    1170     ///The node can be given with the \ref source() function.
    1171     void run()
    1172     {
    1173       if(Base::_source==INVALID) throw UninitializedParameter();
     1158    ///Runs Dijkstra algorithm from the given source node.
     1159
     1160    ///This method runs %Dijkstra algorithm from the given source node
     1161    ///in order to compute the shortest path to each node.
     1162    void run(Node s)
     1163    {
     1164      if (s==INVALID) throw UninitializedParameter();
    11741165      Dijkstra<Digraph,LengthMap,TR>
    1175         dij(*reinterpret_cast<const Digraph*>(Base::_g),
    1176             *reinterpret_cast<const LengthMap*>(Base::_length));
    1177       if(Base::_processed)
    1178         dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    1179       if(Base::_pred)
    1180         dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    1181       if(Base::_dist)
    1182         dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    1183       dij.run(Base::_source);
    1184     }
    1185 
    1186     ///Runs Dijkstra algorithm from the given node.
    1187 
    1188     ///Runs Dijkstra algorithm from the given node.
    1189     ///\param s is the given source.
    1190     void run(Node s)
    1191     {
    1192       Base::_source=s;
    1193       run();
    1194     }
    1195 
    1196     /// Sets the source node, from which the Dijkstra algorithm runs.
    1197 
    1198     /// Sets the source node, from which the Dijkstra algorithm runs.
    1199     /// \param s is the source node.
    1200     DijkstraWizard<TR> &source(Node s)
    1201     {
    1202       Base::_source=s;
    1203       return *this;
     1166        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
     1167             *reinterpret_cast<const LengthMap*>(Base::_length));
     1168      if (Base::_pred)
     1169        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1170      if (Base::_dist)
     1171        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1172      if (Base::_processed)
     1173        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1174      dijk.run(s);
     1175    }
     1176
     1177    ///Finds the shortest path between \c s and \c t.
     1178
     1179    ///This method runs the %Dijkstra algorithm from node \c s
     1180    ///in order to compute the shortest path to node \c t
     1181    ///(it stops searching when \c t is processed).
     1182    ///
     1183    ///\return \c true if \c t is reachable form \c s.
     1184    bool run(Node s, Node t)
     1185    {
     1186      if (s==INVALID || t==INVALID) throw UninitializedParameter();
     1187      Dijkstra<Digraph,LengthMap,TR>
     1188        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
     1189             *reinterpret_cast<const LengthMap*>(Base::_length));
     1190      if (Base::_pred)
     1191        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1192      if (Base::_dist)
     1193        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1194      if (Base::_processed)
     1195        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1196      dijk.run(s,t);
     1197      if (Base::_path)
     1198        *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
     1199      if (Base::_di)
     1200        *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
     1201      return dijk.reached(t);
    12041202    }
    12051203
     
    12101208      SetPredMapBase(const TR &b) : TR(b) {}
    12111209    };
    1212     ///\brief \ref named-templ-param "Named parameter"
     1210    ///\brief \ref named-func-param "Named parameter"
    12131211    ///for setting \ref PredMap object.
    12141212    ///
    1215     ///\ref named-templ-param "Named parameter"
     1213    ///\ref named-func-param "Named parameter"
    12161214    ///for setting \ref PredMap object.
    12171215    template<class T>
     
    12201218      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    12211219      return DijkstraWizard<SetPredMapBase<T> >(*this);
     1220    }
     1221
     1222    template<class T>
     1223    struct SetDistMapBase : public Base {
     1224      typedef T DistMap;
     1225      static DistMap *createDistMap(const Digraph &) { return 0; };
     1226      SetDistMapBase(const TR &b) : TR(b) {}
     1227    };
     1228    ///\brief \ref named-func-param "Named parameter"
     1229    ///for setting \ref DistMap object.
     1230    ///
     1231    ///\ref named-func-param "Named parameter"
     1232    ///for setting \ref DistMap object.
     1233    template<class T>
     1234    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
     1235    {
     1236      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1237      return DijkstraWizard<SetDistMapBase<T> >(*this);
    12221238    }
    12231239
     
    12281244      SetProcessedMapBase(const TR &b) : TR(b) {}
    12291245    };
    1230     ///\brief \ref named-templ-param "Named parameter"
     1246    ///\brief \ref named-func-param "Named parameter"
    12311247    ///for setting \ref ProcessedMap object.
    12321248    ///
    1233     /// \ref named-templ-param "Named parameter"
     1249    /// \ref named-func-param "Named parameter"
    12341250    ///for setting \ref ProcessedMap object.
    12351251    template<class T>
     
    12411257
    12421258    template<class T>
    1243     struct SetDistMapBase : public Base {
    1244       typedef T DistMap;
    1245       static DistMap *createDistMap(const Digraph &) { return 0; };
    1246       SetDistMapBase(const TR &b) : TR(b) {}
    1247     };
    1248     ///\brief \ref named-templ-param "Named parameter"
    1249     ///for setting \ref DistMap object.
    1250     ///
    1251     ///\ref named-templ-param "Named parameter"
    1252     ///for setting \ref DistMap object.
     1259    struct SetPathBase : public Base {
     1260      typedef T Path;
     1261      SetPathBase(const TR &b) : TR(b) {}
     1262    };
     1263    ///\brief \ref named-func-param "Named parameter"
     1264    ///for getting the shortest path to the target node.
     1265    ///
     1266    ///\ref named-func-param "Named parameter"
     1267    ///for getting the shortest path to the target node.
    12531268    template<class T>
    1254     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
    1255     {
    1256       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1257       return DijkstraWizard<SetDistMapBase<T> >(*this);
     1269    DijkstraWizard<SetPathBase<T> > path(const T &t)
     1270    {
     1271      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1272      return DijkstraWizard<SetPathBase<T> >(*this);
     1273    }
     1274
     1275    ///\brief \ref named-func-param "Named parameter"
     1276    ///for getting the distance of the target node.
     1277    ///
     1278    ///\ref named-func-param "Named parameter"
     1279    ///for getting the distance of the target node.
     1280    DijkstraWizard dist(const Value &d)
     1281    {
     1282      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
     1283      return *this;
    12581284    }
    12591285
    12601286  };
    12611287
    1262   ///Function type interface for Dijkstra algorithm.
     1288  ///Function-type interface for Dijkstra algorithm.
    12631289
    12641290  /// \ingroup shortest_path
    1265   ///Function type interface for Dijkstra algorithm.
     1291  ///Function-type interface for Dijkstra algorithm.
    12661292  ///
    1267   ///This function also has several
    1268   ///\ref named-templ-func-param "named parameters",
     1293  ///This function also has several \ref named-func-param "named parameters",
    12691294  ///they are declared as the members of class \ref DijkstraWizard.
    1270   ///The following
    1271   ///example shows how to use these parameters.
     1295  ///The following examples show how to use these parameters.
    12721296  ///\code
    1273   ///  dijkstra(g,length,source).predMap(preds).run();
     1297  ///  // Compute shortest path from node s to each node
     1298  ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
     1299  ///
     1300  ///  // Compute shortest path from s to t
     1301  ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
    12741302  ///\endcode
    12751303  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
     
    12791307  template<class GR, class LM>
    12801308  DijkstraWizard<DijkstraWizardBase<GR,LM> >
    1281   dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
     1309  dijkstra(const GR &digraph, const LM &length)
    12821310  {
    1283     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
     1311    return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
    12841312  }
    12851313
Note: See TracChangeset for help on using the changeset viewer.