COIN-OR::LEMON - Graph Library

Changeset 281:e9b4fbe163f5 in lemon-1.0


Ignore:
Timestamp:
09/26/08 09:52:28 (15 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

Location:
lemon
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r278 r281  
    5555    ///\param g is the digraph, to which we would like to define the
    5656    ///\ref PredMap.
    57     ///\todo The digraph alone may be insufficient to initialize
    5857    static PredMap *createPredMap(const Digraph &g)
    5958    {
     
    6564    ///The type of the map that indicates which nodes are processed.
    6665    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    67     ///By default it is a NullMap.
    6866    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6967    ///Instantiates a \ref ProcessedMap.
     
    197195    int _curr_dist;
    198196
    199     ///Creates the maps if necessary.
    200     ///\todo Better memory allocation (instead of new).
     197    //Creates the maps if necessary.
    201198    void create_maps()
    202199    {
     
    849846    ///\param g is the digraph, to which we would like to define the
    850847    ///\ref PredMap.
    851     ///\todo The digraph alone may be insufficient to initialize
    852848    static PredMap *createPredMap(const Digraph &g)
    853849    {
     
    13711367    int _list_front, _list_back;
    13721368
    1373     ///Creates the maps if necessary.
    1374     ///\todo Better memory allocation (instead of new).
     1369    //Creates the maps if necessary.
    13751370    void create_maps() {
    13761371      if(!_reached) {
  • lemon/bfs.h

    r280 r281  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
     31#include <lemon/path.h>
    3132
    3233namespace lemon {
     
    114115  ///This class provides an efficient implementation of the %BFS algorithm.
    115116  ///
    116   ///There is also a \ref bfs() "function type interface" for the BFS
     117  ///There is also a \ref bfs() "function-type interface" for the BFS
    117118  ///algorithm, which is convenient in the simplier cases and it can be
    118119  ///used easier.
     
    839840    ///arcs of the shortest paths.
    840841    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    841     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     842    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    842843    ///Instantiates a \ref PredMap.
    843844
     
    845846    ///\param g is the digraph, to which we would like to define the
    846847    ///\ref PredMap.
    847 #ifdef DOXYGEN
    848848    static PredMap *createPredMap(const Digraph &g)
    849 #else
    850     static PredMap *createPredMap(const Digraph &)
    851 #endif
    852     {
    853       return new PredMap();
     849    {
     850      return new PredMap(g);
    854851    }
    855852
     
    858855    ///The type of the map that indicates which nodes are processed.
    859856    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     857    ///By default it is a NullMap.
    860858    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    861859    ///Instantiates a \ref ProcessedMap.
     
    892890    ///The type of the map that stores the distances of the nodes.
    893891    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    894     ///
    895     typedef NullMap<typename Digraph::Node,int> DistMap;
     892    typedef typename Digraph::template NodeMap<int> DistMap;
    896893    ///Instantiates a \ref DistMap.
    897894
     
    899896    ///\param g is the digraph, to which we would like to define
    900897    ///the \ref DistMap
    901 #ifdef DOXYGEN
    902898    static DistMap *createDistMap(const Digraph &g)
    903 #else
    904     static DistMap *createDistMap(const Digraph &)
    905 #endif
    906     {
    907       return new DistMap();
    908     }
     899    {
     900      return new DistMap(g);
     901    }
     902
     903    ///The type of the shortest paths.
     904
     905    ///The type of the shortest paths.
     906    ///It must meet the \ref concepts::Path "Path" concept.
     907    typedef lemon::Path<Digraph> Path;
    909908  };
    910909
     
    936935    //Pointer to the map of distances.
    937936    void *_dist;
    938     //Pointer to the source node.
    939     Node _source;
     937    //Pointer to the shortest path to the target node.
     938    void *_path;
     939    //Pointer to the distance of the target node.
     940    int *_di;
    940941
    941942    public:
     
    943944
    944945    /// This constructor does not require parameters, therefore it initiates
    945     /// all of the attributes to default values (0, INVALID).
     946    /// all of the attributes to \c 0.
    946947    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    947                       _dist(0), _source(INVALID) {}
     948                      _dist(0), _path(0), _di(0) {}
    948949
    949950    /// Constructor.
    950951
    951     /// This constructor requires some parameters,
    952     /// listed in the parameters list.
    953     /// Others are initiated to 0.
     952    /// This constructor requires one parameter,
     953    /// others are initiated to \c 0.
    954954    /// \param g The digraph the algorithm runs on.
    955     /// \param s The source node.
    956     BfsWizardBase(const GR &g, Node s=INVALID) :
     955    BfsWizardBase(const GR &g) :
    957956      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    958       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     957      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    959958
    960959  };
    961960
    962   /// Auxiliary class for the function type interface of BFS algorithm.
    963 
    964   /// This auxiliary class is created to implement the function type
    965   /// interface of \ref Bfs algorithm. It uses the functions and features
    966   /// of the plain \ref Bfs, but it is much simpler to use it.
    967   /// It should only be used through the \ref bfs() function, which makes
    968   /// it easier to use the algorithm.
     961  /// Auxiliary class for the function-type interface of BFS algorithm.
     962
     963  /// This auxiliary class is created to implement the
     964  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
     965  /// It does not have own \ref run() method, it uses the functions
     966  /// and features of the plain \ref Bfs.
    969967  ///
    970   /// Simplicity means that the way to change the types defined
    971   /// in the traits class is based on functions that returns the new class
    972   /// and not on templatable built-in classes.
    973   /// When using the plain \ref Bfs
    974   /// the new class with the modified type comes from
    975   /// the original class by using the ::
    976   /// operator. In the case of \ref BfsWizard only
    977   /// a function have to be called, and it will
    978   /// return the needed class.
    979   ///
    980   /// It does not have own \ref run() method. When its \ref run() method
    981   /// is called, it initiates a plain \ref Bfs object, and calls the
    982   /// \ref Bfs::run() method of it.
     968  /// This class should only be used through the \ref bfs() function,
     969  /// which makes it easier to use the algorithm.
    983970  template<class TR>
    984971  class BfsWizard : public TR
     
    1003990    ///\brief The type of the map that indicates which nodes are processed.
    1004991    typedef typename TR::ProcessedMap ProcessedMap;
     992    ///The type of the shortest paths
     993    typedef typename TR::Path Path;
    1005994
    1006995  public:
     
    10131002    /// Constructor that requires parameters.
    10141003    /// These parameters will be the default values for the traits class.
    1015     BfsWizard(const Digraph &g, Node s=INVALID) :
    1016       TR(g,s) {}
     1004    /// \param g The digraph the algorithm runs on.
     1005    BfsWizard(const Digraph &g) :
     1006      TR(g) {}
    10171007
    10181008    ///Copy constructor
     
    10211011    ~BfsWizard() {}
    10221012
    1023     ///Runs BFS algorithm from a source node.
    1024 
    1025     ///Runs BFS algorithm from a source node.
    1026     ///The node can be given with the \ref source() function.
     1013    ///Runs BFS algorithm from the given source node.
     1014
     1015    ///This method runs BFS algorithm from node \c s
     1016    ///in order to compute the shortest path to each node.
     1017    void run(Node s)
     1018    {
     1019      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1020      if (Base::_pred)
     1021        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1022      if (Base::_dist)
     1023        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1024      if (Base::_reached)
     1025        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1026      if (Base::_processed)
     1027        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1028      if (s!=INVALID)
     1029        alg.run(s);
     1030      else
     1031        alg.run();
     1032    }
     1033
     1034    ///Finds the shortest path between \c s and \c t.
     1035
     1036    ///This method runs BFS algorithm from node \c s
     1037    ///in order to compute the shortest path to node \c t
     1038    ///(it stops searching when \c t is processed).
     1039    ///
     1040    ///\return \c true if \c t is reachable form \c s.
     1041    bool run(Node s, Node t)
     1042    {
     1043      if (s==INVALID || t==INVALID) throw UninitializedParameter();
     1044      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1045      if (Base::_pred)
     1046        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1047      if (Base::_dist)
     1048        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1049      if (Base::_reached)
     1050        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1051      if (Base::_processed)
     1052        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1053      alg.run(s,t);
     1054      if (Base::_path)
     1055        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     1056      if (Base::_di)
     1057        *Base::_di = alg.dist(t);
     1058      return alg.reached(t);
     1059    }
     1060
     1061    ///Runs BFS algorithm to visit all nodes in the digraph.
     1062
     1063    ///This method runs BFS algorithm in order to compute
     1064    ///the shortest path to each node.
    10271065    void run()
    10281066    {
    1029       if(Base::_source==INVALID) throw UninitializedParameter();
    1030       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    1031       if(Base::_reached)
    1032         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    1033       if(Base::_processed)
    1034         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    1035       if(Base::_pred)
    1036         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    1037       if(Base::_dist)
    1038         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    1039       alg.run(Base::_source);
    1040     }
    1041 
    1042     ///Runs BFS algorithm from the given node.
    1043 
    1044     ///Runs BFS algorithm from the given node.
    1045     ///\param s is the given source.
    1046     void run(Node s)
    1047     {
    1048       Base::_source=s;
    1049       run();
    1050     }
    1051 
    1052     /// Sets the source node, from which the Bfs algorithm runs.
    1053 
    1054     /// Sets the source node, from which the Bfs algorithm runs.
    1055     /// \param s is the source node.
    1056     BfsWizard<TR> &source(Node s)
    1057     {
    1058       Base::_source=s;
    1059       return *this;
     1067      run(INVALID);
    10601068    }
    10611069
     
    10661074      SetPredMapBase(const TR &b) : TR(b) {}
    10671075    };
    1068     ///\brief \ref named-templ-param "Named parameter"
     1076    ///\brief \ref named-func-param "Named parameter"
    10691077    ///for setting \ref PredMap object.
    10701078    ///
    1071     /// \ref named-templ-param "Named parameter"
     1079    ///\ref named-func-param "Named parameter"
    10721080    ///for setting \ref PredMap object.
    10731081    template<class T>
     
    10841092      SetReachedMapBase(const TR &b) : TR(b) {}
    10851093    };
    1086     ///\brief \ref named-templ-param "Named parameter"
     1094    ///\brief \ref named-func-param "Named parameter"
    10871095    ///for setting \ref ReachedMap object.
    10881096    ///
    1089     /// \ref named-templ-param "Named parameter"
     1097    /// \ref named-func-param "Named parameter"
    10901098    ///for setting \ref ReachedMap object.
    10911099    template<class T>
     
    10941102      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    10951103      return BfsWizard<SetReachedMapBase<T> >(*this);
     1104    }
     1105
     1106    template<class T>
     1107    struct SetDistMapBase : public Base {
     1108      typedef T DistMap;
     1109      static DistMap *createDistMap(const Digraph &) { return 0; };
     1110      SetDistMapBase(const TR &b) : TR(b) {}
     1111    };
     1112    ///\brief \ref named-func-param "Named parameter"
     1113    ///for setting \ref DistMap object.
     1114    ///
     1115    /// \ref named-func-param "Named parameter"
     1116    ///for setting \ref DistMap object.
     1117    template<class T>
     1118    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1119    {
     1120      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1121      return BfsWizard<SetDistMapBase<T> >(*this);
    10961122    }
    10971123
     
    11021128      SetProcessedMapBase(const TR &b) : TR(b) {}
    11031129    };
    1104     ///\brief \ref named-templ-param "Named parameter"
     1130    ///\brief \ref named-func-param "Named parameter"
    11051131    ///for setting \ref ProcessedMap object.
    11061132    ///
    1107     /// \ref named-templ-param "Named parameter"
     1133    /// \ref named-func-param "Named parameter"
    11081134    ///for setting \ref ProcessedMap object.
    11091135    template<class T>
     
    11151141
    11161142    template<class T>
    1117     struct SetDistMapBase : public Base {
    1118       typedef T DistMap;
    1119       static DistMap *createDistMap(const Digraph &) { return 0; };
    1120       SetDistMapBase(const TR &b) : TR(b) {}
    1121     };
    1122     ///\brief \ref named-templ-param "Named parameter"
    1123     ///for setting \ref DistMap object.
    1124     ///
    1125     /// \ref named-templ-param "Named parameter"
    1126     ///for setting \ref DistMap object.
     1143    struct SetPathBase : public Base {
     1144      typedef T Path;
     1145      SetPathBase(const TR &b) : TR(b) {}
     1146    };
     1147    ///\brief \ref named-func-param "Named parameter"
     1148    ///for getting the shortest path to the target node.
     1149    ///
     1150    ///\ref named-func-param "Named parameter"
     1151    ///for getting the shortest path to the target node.
    11271152    template<class T>
    1128     BfsWizard<SetDistMapBase<T> > distMap(const T &t)
    1129     {
    1130       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1131       return BfsWizard<SetDistMapBase<T> >(*this);
     1153    BfsWizard<SetPathBase<T> > path(const T &t)
     1154    {
     1155      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1156      return BfsWizard<SetPathBase<T> >(*this);
     1157    }
     1158
     1159    ///\brief \ref named-func-param "Named parameter"
     1160    ///for getting the distance of the target node.
     1161    ///
     1162    ///\ref named-func-param "Named parameter"
     1163    ///for getting the distance of the target node.
     1164    BfsWizard dist(const int &d)
     1165    {
     1166      Base::_di=const_cast<int*>(&d);
     1167      return *this;
    11321168    }
    11331169
    11341170  };
    11351171
    1136   ///Function type interface for Bfs algorithm.
     1172  ///Function-type interface for BFS algorithm.
    11371173
    11381174  /// \ingroup search
    1139   ///Function type interface for Bfs algorithm.
     1175  ///Function-type interface for BFS algorithm.
    11401176  ///
    1141   ///This function also has several
    1142   ///\ref named-templ-func-param "named parameters",
     1177  ///This function also has several \ref named-func-param "named parameters",
    11431178  ///they are declared as the members of class \ref BfsWizard.
    1144   ///The following
    1145   ///example shows how to use these parameters.
     1179  ///The following examples show how to use these parameters.
    11461180  ///\code
    1147   ///  bfs(g,source).predMap(preds).run();
     1181  ///  // Compute shortest path from node s to each node
     1182  ///  bfs(g).predMap(preds).distMap(dists).run(s);
     1183  ///
     1184  ///  // Compute shortest path from s to t
     1185  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11481186  ///\endcode
    11491187  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     
    11531191  template<class GR>
    11541192  BfsWizard<BfsWizardBase<GR> >
    1155   bfs(const GR &g,typename GR::Node s=INVALID)
     1193  bfs(const GR &digraph)
    11561194  {
    1157     return BfsWizard<BfsWizardBase<GR> >(g,s);
     1195    return BfsWizard<BfsWizardBase<GR> >(digraph);
    11581196  }
    11591197
  • lemon/concepts/path.h

    r278 r281  
    2121///\brief Classes for representing paths in digraphs.
    2222///
    23 ///\todo Iterators have obsolete style
    2423
    2524#ifndef LEMON_CONCEPT_PATH_H
  • lemon/concepts/path.h

    r280 r281  
    6666      /// \brief Template assigment
    6767      template <typename CPath>
    68       Path& operator=(const CPath& cpath) {}
     68      Path& operator=(const CPath& cpath) {
     69        ignore_unused_variable_warning(cpath);
     70        return *this;
     71      }
    6972
    7073      /// Length of the path ie. the number of arcs in the path.
  • lemon/dfs.h

    r278 r281  
    5656    ///\param g is the digraph, to which we would like to define the
    5757    ///\ref PredMap.
    58     ///\todo The digraph alone may be insufficient to initialize
    5958    static PredMap *createPredMap(const Digraph &g)
    6059    {
     
    6665    ///The type of the map that indicates which nodes are processed.
    6766    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    68     ///By default it is a NullMap.
    6967    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    7068    ///Instantiates a \ref ProcessedMap.
     
    197195    int _stack_head;
    198196
    199     ///Creates the maps if necessary.
    200     ///\todo Better memory allocation (instead of new).
     197    //Creates the maps if necessary.
    201198    void create_maps()
    202199    {
     
    783780    ///\param g is the digraph, to which we would like to define the
    784781    ///\ref PredMap.
    785     ///\todo The digraph alone may be insufficient to initialize
    786782    static PredMap *createPredMap(const Digraph &g)
    787783    {
     
    13181314    int _stack_head;
    13191315
    1320     ///Creates the maps if necessary.
    1321     ///\todo Better memory allocation (instead of new).
     1316    //Creates the maps if necessary.
    13221317    void create_maps() {
    13231318      if(!_reached) {
  • lemon/dfs.h

    r280 r281  
    3030#include <lemon/assert.h>
    3131#include <lemon/maps.h>
     32#include <lemon/path.h>
    3233
    3334namespace lemon {
     
    115116  ///This class provides an efficient implementation of the %DFS algorithm.
    116117  ///
    117   ///There is also a \ref dfs() "function type interface" for the DFS
     118  ///There is also a \ref dfs() "function-type interface" for the DFS
    118119  ///algorithm, which is convenient in the simplier cases and it can be
    119120  ///used easier.
     
    773774    ///arcs of the %DFS paths.
    774775    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    775     ///
    776     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     776    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    777777    ///Instantiates a \ref PredMap.
    778778
     
    780780    ///\param g is the digraph, to which we would like to define the
    781781    ///\ref PredMap.
    782 #ifdef DOXYGEN
    783782    static PredMap *createPredMap(const Digraph &g)
    784 #else
    785     static PredMap *createPredMap(const Digraph &)
    786 #endif
    787     {
    788       return new PredMap();
     783    {
     784      return new PredMap(g);
    789785    }
    790786
     
    793789    ///The type of the map that indicates which nodes are processed.
    794790    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     791    ///By default it is a NullMap.
    795792    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    796793    ///Instantiates a \ref ProcessedMap.
     
    827824    ///The type of the map that stores the distances of the nodes.
    828825    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    829     ///
    830     typedef NullMap<typename Digraph::Node,int> DistMap;
     826    typedef typename Digraph::template NodeMap<int> DistMap;
    831827    ///Instantiates a \ref DistMap.
    832828
     
    834830    ///\param g is the digraph, to which we would like to define
    835831    ///the \ref DistMap
    836 #ifdef DOXYGEN
    837832    static DistMap *createDistMap(const Digraph &g)
    838 #else
    839     static DistMap *createDistMap(const Digraph &)
    840 #endif
    841     {
    842       return new DistMap();
    843     }
     833    {
     834      return new DistMap(g);
     835    }
     836
     837    ///The type of the DFS paths.
     838
     839    ///The type of the DFS paths.
     840    ///It must meet the \ref concepts::Path "Path" concept.
     841    typedef lemon::Path<Digraph> Path;
    844842  };
    845843
     
    871869    //Pointer to the map of distances.
    872870    void *_dist;
    873     //Pointer to the source node.
    874     Node _source;
     871    //Pointer to the DFS path to the target node.
     872    void *_path;
     873    //Pointer to the distance of the target node.
     874    int *_di;
    875875
    876876    public:
     
    878878
    879879    /// This constructor does not require parameters, therefore it initiates
    880     /// all of the attributes to default values (0, INVALID).
     880    /// all of the attributes to \c 0.
    881881    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    882                       _dist(0), _source(INVALID) {}
     882                      _dist(0), _path(0), _di(0) {}
    883883
    884884    /// Constructor.
    885885
    886     /// This constructor requires some parameters,
    887     /// listed in the parameters list.
    888     /// Others are initiated to 0.
     886    /// This constructor requires one parameter,
     887    /// others are initiated to \c 0.
    889888    /// \param g The digraph the algorithm runs on.
    890     /// \param s The source node.
    891     DfsWizardBase(const GR &g, Node s=INVALID) :
     889    DfsWizardBase(const GR &g) :
    892890      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    893       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     891      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    894892
    895893  };
    896894
    897   /// Auxiliary class for the function type interface of DFS algorithm.
    898 
    899   /// This auxiliary class is created to implement the function type
    900   /// interface of \ref Dfs algorithm. It uses the functions and features
    901   /// of the plain \ref Dfs, but it is much simpler to use it.
    902   /// It should only be used through the \ref dfs() function, which makes
    903   /// it easier to use the algorithm.
     895  /// Auxiliary class for the function-type interface of DFS algorithm.
     896
     897  /// This auxiliary class is created to implement the
     898  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
     899  /// It does not have own \ref run() method, it uses the functions
     900  /// and features of the plain \ref Dfs.
    904901  ///
    905   /// Simplicity means that the way to change the types defined
    906   /// in the traits class is based on functions that returns the new class
    907   /// and not on templatable built-in classes.
    908   /// When using the plain \ref Dfs
    909   /// the new class with the modified type comes from
    910   /// the original class by using the ::
    911   /// operator. In the case of \ref DfsWizard only
    912   /// a function have to be called, and it will
    913   /// return the needed class.
    914   ///
    915   /// It does not have own \ref run() method. When its \ref run() method
    916   /// is called, it initiates a plain \ref Dfs object, and calls the
    917   /// \ref Dfs::run() method of it.
     902  /// This class should only be used through the \ref dfs() function,
     903  /// which makes it easier to use the algorithm.
    918904  template<class TR>
    919905  class DfsWizard : public TR
     
    930916
    931917    ///\brief The type of the map that stores the predecessor
    932     ///arcs of the shortest paths.
     918    ///arcs of the DFS paths.
    933919    typedef typename TR::PredMap PredMap;
    934920    ///\brief The type of the map that stores the distances of the nodes.
     
    938924    ///\brief The type of the map that indicates which nodes are processed.
    939925    typedef typename TR::ProcessedMap ProcessedMap;
     926    ///The type of the DFS paths
     927    typedef typename TR::Path Path;
    940928
    941929  public:
     
    948936    /// Constructor that requires parameters.
    949937    /// These parameters will be the default values for the traits class.
    950     DfsWizard(const Digraph &g, Node s=INVALID) :
    951       TR(g,s) {}
     938    /// \param g The digraph the algorithm runs on.
     939    DfsWizard(const Digraph &g) :
     940      TR(g) {}
    952941
    953942    ///Copy constructor
     
    956945    ~DfsWizard() {}
    957946
    958     ///Runs DFS algorithm from a source node.
    959 
    960     ///Runs DFS algorithm from a source node.
    961     ///The node can be given with the \ref source() function.
     947    ///Runs DFS algorithm from the given source node.
     948
     949    ///This method runs DFS algorithm from node \c s
     950    ///in order to compute the DFS path to each node.
     951    void run(Node s)
     952    {
     953      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     954      if (Base::_pred)
     955        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     956      if (Base::_dist)
     957        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     958      if (Base::_reached)
     959        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     960      if (Base::_processed)
     961        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     962      if (s!=INVALID)
     963        alg.run(s);
     964      else
     965        alg.run();
     966    }
     967
     968    ///Finds the DFS path between \c s and \c t.
     969
     970    ///This method runs DFS algorithm from node \c s
     971    ///in order to compute the DFS path to node \c t
     972    ///(it stops searching when \c t is processed).
     973    ///
     974    ///\return \c true if \c t is reachable form \c s.
     975    bool run(Node s, Node t)
     976    {
     977      if (s==INVALID || t==INVALID) throw UninitializedParameter();
     978      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     979      if (Base::_pred)
     980        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     981      if (Base::_dist)
     982        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     983      if (Base::_reached)
     984        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     985      if (Base::_processed)
     986        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     987      alg.run(s,t);
     988      if (Base::_path)
     989        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     990      if (Base::_di)
     991        *Base::_di = alg.dist(t);
     992      return alg.reached(t);
     993      }
     994
     995    ///Runs DFS algorithm to visit all nodes in the digraph.
     996
     997    ///This method runs DFS algorithm in order to compute
     998    ///the DFS path to each node.
    962999    void run()
    9631000    {
    964       if(Base::_source==INVALID) throw UninitializedParameter();
    965       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    966       if(Base::_reached)
    967         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    968       if(Base::_processed)
    969         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    970       if(Base::_pred)
    971         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    972       if(Base::_dist)
    973         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    974       alg.run(Base::_source);
    975     }
    976 
    977     ///Runs DFS algorithm from the given node.
    978 
    979     ///Runs DFS algorithm from the given node.
    980     ///\param s is the given source.
    981     void run(Node s)
    982     {
    983       Base::_source=s;
    984       run();
    985     }
    986 
    987     /// Sets the source node, from which the Dfs algorithm runs.
    988 
    989     /// Sets the source node, from which the Dfs algorithm runs.
    990     /// \param s is the source node.
    991     DfsWizard<TR> &source(Node s)
    992     {
    993       Base::_source=s;
    994       return *this;
     1001      run(INVALID);
    9951002    }
    9961003
     
    10011008      SetPredMapBase(const TR &b) : TR(b) {}
    10021009    };
    1003     ///\brief \ref named-templ-param "Named parameter"
     1010    ///\brief \ref named-func-param "Named parameter"
    10041011    ///for setting \ref PredMap object.
    10051012    ///
    1006     ///\ref named-templ-param "Named parameter"
     1013    ///\ref named-func-param "Named parameter"
    10071014    ///for setting \ref PredMap object.
    10081015    template<class T>
     
    10191026      SetReachedMapBase(const TR &b) : TR(b) {}
    10201027    };
    1021     ///\brief \ref named-templ-param "Named parameter"
     1028    ///\brief \ref named-func-param "Named parameter"
    10221029    ///for setting \ref ReachedMap object.
    10231030    ///
    1024     /// \ref named-templ-param "Named parameter"
     1031    /// \ref named-func-param "Named parameter"
    10251032    ///for setting \ref ReachedMap object.
    10261033    template<class T>
     
    10291036      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    10301037      return DfsWizard<SetReachedMapBase<T> >(*this);
     1038    }
     1039
     1040    template<class T>
     1041    struct SetDistMapBase : public Base {
     1042      typedef T DistMap;
     1043      static DistMap *createDistMap(const Digraph &) { return 0; };
     1044      SetDistMapBase(const TR &b) : TR(b) {}
     1045    };
     1046    ///\brief \ref named-func-param "Named parameter"
     1047    ///for setting \ref DistMap object.
     1048    ///
     1049    /// \ref named-func-param "Named parameter"
     1050    ///for setting \ref DistMap object.
     1051    template<class T>
     1052    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1053    {
     1054      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1055      return DfsWizard<SetDistMapBase<T> >(*this);
    10311056    }
    10321057
     
    10371062      SetProcessedMapBase(const TR &b) : TR(b) {}
    10381063    };
    1039     ///\brief \ref named-templ-param "Named parameter"
     1064    ///\brief \ref named-func-param "Named parameter"
    10401065    ///for setting \ref ProcessedMap object.
    10411066    ///
    1042     /// \ref named-templ-param "Named parameter"
     1067    /// \ref named-func-param "Named parameter"
    10431068    ///for setting \ref ProcessedMap object.
    10441069    template<class T>
     
    10501075
    10511076    template<class T>
    1052     struct SetDistMapBase : public Base {
    1053       typedef T DistMap;
    1054       static DistMap *createDistMap(const Digraph &) { return 0; };
    1055       SetDistMapBase(const TR &b) : TR(b) {}
    1056     };
    1057     ///\brief \ref named-templ-param "Named parameter"
    1058     ///for setting \ref DistMap object.
    1059     ///
    1060     ///\ref named-templ-param "Named parameter"
    1061     ///for setting \ref DistMap object.
     1077    struct SetPathBase : public Base {
     1078      typedef T Path;
     1079      SetPathBase(const TR &b) : TR(b) {}
     1080    };
     1081    ///\brief \ref named-func-param "Named parameter"
     1082    ///for getting the DFS path to the target node.
     1083    ///
     1084    ///\ref named-func-param "Named parameter"
     1085    ///for getting the DFS path to the target node.
    10621086    template<class T>
    1063     DfsWizard<SetDistMapBase<T> > distMap(const T &t)
    1064     {
    1065       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1066       return DfsWizard<SetDistMapBase<T> >(*this);
     1087    DfsWizard<SetPathBase<T> > path(const T &t)
     1088    {
     1089      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1090      return DfsWizard<SetPathBase<T> >(*this);
     1091    }
     1092
     1093    ///\brief \ref named-func-param "Named parameter"
     1094    ///for getting the distance of the target node.
     1095    ///
     1096    ///\ref named-func-param "Named parameter"
     1097    ///for getting the distance of the target node.
     1098    DfsWizard dist(const int &d)
     1099    {
     1100      Base::_di=const_cast<int*>(&d);
     1101      return *this;
    10671102    }
    10681103
    10691104  };
    10701105
    1071   ///Function type interface for Dfs algorithm.
     1106  ///Function-type interface for DFS algorithm.
    10721107
    10731108  ///\ingroup search
    1074   ///Function type interface for Dfs algorithm.
     1109  ///Function-type interface for DFS algorithm.
    10751110  ///
    1076   ///This function also has several
    1077   ///\ref named-templ-func-param "named parameters",
     1111  ///This function also has several \ref named-func-param "named parameters",
    10781112  ///they are declared as the members of class \ref DfsWizard.
    1079   ///The following
    1080   ///example shows how to use these parameters.
     1113  ///The following examples show how to use these parameters.
    10811114  ///\code
    1082   ///  dfs(g,source).predMap(preds).run();
     1115  ///  // Compute the DFS tree
     1116  ///  dfs(g).predMap(preds).distMap(dists).run(s);
     1117  ///
     1118  ///  // Compute the DFS path from s to t
     1119  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    10831120  ///\endcode
     1121
    10841122  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
    10851123  ///to the end of the parameter list.
     
    10881126  template<class GR>
    10891127  DfsWizard<DfsWizardBase<GR> >
    1090   dfs(const GR &g,typename GR::Node s=INVALID)
     1128  dfs(const GR &digraph)
    10911129  {
    1092     return DfsWizard<DfsWizardBase<GR> >(g,s);
     1130    return DfsWizard<DfsWizardBase<GR> >(digraph);
    10931131  }
    10941132
  • 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.