COIN-OR::LEMON - Graph Library

Changeset 278:931190050520 in lemon for lemon/bfs.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/bfs.h

    r258 r278  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
     31#include <lemon/path.h>
    3132
    3233namespace lemon {
     
    116117  ///This class provides an efficient implementation of the %BFS algorithm.
    117118  ///
    118   ///There is also a \ref bfs() "function type interface" for the BFS
     119  ///There is also a \ref bfs() "function-type interface" for the BFS
    119120  ///algorithm, which is convenient in the simplier cases and it can be
    120121  ///used easier.
     
    842843    ///arcs of the shortest paths.
    843844    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    844     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     845    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    845846    ///Instantiates a \ref PredMap.
    846847
     
    849850    ///\ref PredMap.
    850851    ///\todo The digraph alone may be insufficient to initialize
    851 #ifdef DOXYGEN
    852852    static PredMap *createPredMap(const Digraph &g)
    853 #else
    854     static PredMap *createPredMap(const Digraph &)
    855 #endif
    856     {
    857       return new PredMap();
     853    {
     854      return new PredMap(g);
    858855    }
    859856
     
    862859    ///The type of the map that indicates which nodes are processed.
    863860    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     861    ///By default it is a NullMap.
    864862    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    865863    ///Instantiates a \ref ProcessedMap.
     
    896894    ///The type of the map that stores the distances of the nodes.
    897895    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    898     ///
    899     typedef NullMap<typename Digraph::Node,int> DistMap;
     896    typedef typename Digraph::template NodeMap<int> DistMap;
    900897    ///Instantiates a \ref DistMap.
    901898
     
    903900    ///\param g is the digraph, to which we would like to define
    904901    ///the \ref DistMap
    905 #ifdef DOXYGEN
    906902    static DistMap *createDistMap(const Digraph &g)
    907 #else
    908     static DistMap *createDistMap(const Digraph &)
    909 #endif
    910     {
    911       return new DistMap();
    912     }
     903    {
     904      return new DistMap(g);
     905    }
     906
     907    ///The type of the shortest paths.
     908
     909    ///The type of the shortest paths.
     910    ///It must meet the \ref concepts::Path "Path" concept.
     911    typedef lemon::Path<Digraph> Path;
    913912  };
    914913
     
    940939    //Pointer to the map of distances.
    941940    void *_dist;
    942     //Pointer to the source node.
    943     Node _source;
     941    //Pointer to the shortest path to the target node.
     942    void *_path;
     943    //Pointer to the distance of the target node.
     944    int *_di;
    944945
    945946    public:
     
    947948
    948949    /// This constructor does not require parameters, therefore it initiates
    949     /// all of the attributes to default values (0, INVALID).
     950    /// all of the attributes to \c 0.
    950951    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    951                       _dist(0), _source(INVALID) {}
     952                      _dist(0), _path(0), _di(0) {}
    952953
    953954    /// Constructor.
    954955
    955     /// This constructor requires some parameters,
    956     /// listed in the parameters list.
    957     /// Others are initiated to 0.
     956    /// This constructor requires one parameter,
     957    /// others are initiated to \c 0.
    958958    /// \param g The digraph the algorithm runs on.
    959     /// \param s The source node.
    960     BfsWizardBase(const GR &g, Node s=INVALID) :
     959    BfsWizardBase(const GR &g) :
    961960      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    962       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     961      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    963962
    964963  };
    965964
    966   /// Auxiliary class for the function type interface of BFS algorithm.
    967 
    968   /// This auxiliary class is created to implement the function type
    969   /// interface of \ref Bfs algorithm. It uses the functions and features
    970   /// of the plain \ref Bfs, but it is much simpler to use it.
    971   /// It should only be used through the \ref bfs() function, which makes
    972   /// it easier to use the algorithm.
     965  /// Auxiliary class for the function-type interface of BFS algorithm.
     966
     967  /// This auxiliary class is created to implement the
     968  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
     969  /// It does not have own \ref run() method, it uses the functions
     970  /// and features of the plain \ref Bfs.
    973971  ///
    974   /// Simplicity means that the way to change the types defined
    975   /// in the traits class is based on functions that returns the new class
    976   /// and not on templatable built-in classes.
    977   /// When using the plain \ref Bfs
    978   /// the new class with the modified type comes from
    979   /// the original class by using the ::
    980   /// operator. In the case of \ref BfsWizard only
    981   /// a function have to be called, and it will
    982   /// return the needed class.
    983   ///
    984   /// It does not have own \ref run() method. When its \ref run() method
    985   /// is called, it initiates a plain \ref Bfs object, and calls the
    986   /// \ref Bfs::run() method of it.
     972  /// This class should only be used through the \ref bfs() function,
     973  /// which makes it easier to use the algorithm.
    987974  template<class TR>
    988975  class BfsWizard : public TR
     
    1007994    ///\brief The type of the map that indicates which nodes are processed.
    1008995    typedef typename TR::ProcessedMap ProcessedMap;
     996    ///The type of the shortest paths
     997    typedef typename TR::Path Path;
    1009998
    1010999  public:
     
    10171006    /// Constructor that requires parameters.
    10181007    /// These parameters will be the default values for the traits class.
    1019     BfsWizard(const Digraph &g, Node s=INVALID) :
    1020       TR(g,s) {}
     1008    /// \param g The digraph the algorithm runs on.
     1009    BfsWizard(const Digraph &g) :
     1010      TR(g) {}
    10211011
    10221012    ///Copy constructor
     
    10251015    ~BfsWizard() {}
    10261016
    1027     ///Runs BFS algorithm from a source node.
    1028 
    1029     ///Runs BFS algorithm from a source node.
    1030     ///The node can be given with the \ref source() function.
     1017    ///Runs BFS algorithm from the given source node.
     1018
     1019    ///This method runs BFS algorithm from node \c s
     1020    ///in order to compute the shortest path to each node.
     1021    void run(Node s)
     1022    {
     1023      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1024      if (Base::_pred)
     1025        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1026      if (Base::_dist)
     1027        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1028      if (Base::_reached)
     1029        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1030      if (Base::_processed)
     1031        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1032      if (s!=INVALID)
     1033        alg.run(s);
     1034      else
     1035        alg.run();
     1036    }
     1037
     1038    ///Finds the shortest path between \c s and \c t.
     1039
     1040    ///This method runs BFS algorithm from node \c s
     1041    ///in order to compute the shortest path to node \c t
     1042    ///(it stops searching when \c t is processed).
     1043    ///
     1044    ///\return \c true if \c t is reachable form \c s.
     1045    bool run(Node s, Node t)
     1046    {
     1047      if (s==INVALID || t==INVALID) throw UninitializedParameter();
     1048      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1049      if (Base::_pred)
     1050        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1051      if (Base::_dist)
     1052        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1053      if (Base::_reached)
     1054        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1055      if (Base::_processed)
     1056        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1057      alg.run(s,t);
     1058      if (Base::_path)
     1059        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     1060      if (Base::_di)
     1061        *Base::_di = alg.dist(t);
     1062      return alg.reached(t);
     1063    }
     1064
     1065    ///Runs BFS algorithm to visit all nodes in the digraph.
     1066
     1067    ///This method runs BFS algorithm in order to compute
     1068    ///the shortest path to each node.
    10311069    void run()
    10321070    {
    1033       if(Base::_source==INVALID) throw UninitializedParameter();
    1034       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    1035       if(Base::_reached)
    1036         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    1037       if(Base::_processed)
    1038         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    1039       if(Base::_pred)
    1040         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    1041       if(Base::_dist)
    1042         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    1043       alg.run(Base::_source);
    1044     }
    1045 
    1046     ///Runs BFS algorithm from the given node.
    1047 
    1048     ///Runs BFS algorithm from the given node.
    1049     ///\param s is the given source.
    1050     void run(Node s)
    1051     {
    1052       Base::_source=s;
    1053       run();
    1054     }
    1055 
    1056     /// Sets the source node, from which the Bfs algorithm runs.
    1057 
    1058     /// Sets the source node, from which the Bfs algorithm runs.
    1059     /// \param s is the source node.
    1060     BfsWizard<TR> &source(Node s)
    1061     {
    1062       Base::_source=s;
    1063       return *this;
     1071      run(INVALID);
    10641072    }
    10651073
     
    10701078      SetPredMapBase(const TR &b) : TR(b) {}
    10711079    };
    1072     ///\brief \ref named-templ-param "Named parameter"
     1080    ///\brief \ref named-func-param "Named parameter"
    10731081    ///for setting \ref PredMap object.
    10741082    ///
    1075     /// \ref named-templ-param "Named parameter"
     1083    ///\ref named-func-param "Named parameter"
    10761084    ///for setting \ref PredMap object.
    10771085    template<class T>
     
    10881096      SetReachedMapBase(const TR &b) : TR(b) {}
    10891097    };
    1090     ///\brief \ref named-templ-param "Named parameter"
     1098    ///\brief \ref named-func-param "Named parameter"
    10911099    ///for setting \ref ReachedMap object.
    10921100    ///
    1093     /// \ref named-templ-param "Named parameter"
     1101    /// \ref named-func-param "Named parameter"
    10941102    ///for setting \ref ReachedMap object.
    10951103    template<class T>
     
    10981106      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    10991107      return BfsWizard<SetReachedMapBase<T> >(*this);
     1108    }
     1109
     1110    template<class T>
     1111    struct SetDistMapBase : public Base {
     1112      typedef T DistMap;
     1113      static DistMap *createDistMap(const Digraph &) { return 0; };
     1114      SetDistMapBase(const TR &b) : TR(b) {}
     1115    };
     1116    ///\brief \ref named-func-param "Named parameter"
     1117    ///for setting \ref DistMap object.
     1118    ///
     1119    /// \ref named-func-param "Named parameter"
     1120    ///for setting \ref DistMap object.
     1121    template<class T>
     1122    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1123    {
     1124      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1125      return BfsWizard<SetDistMapBase<T> >(*this);
    11001126    }
    11011127
     
    11061132      SetProcessedMapBase(const TR &b) : TR(b) {}
    11071133    };
    1108     ///\brief \ref named-templ-param "Named parameter"
     1134    ///\brief \ref named-func-param "Named parameter"
    11091135    ///for setting \ref ProcessedMap object.
    11101136    ///
    1111     /// \ref named-templ-param "Named parameter"
     1137    /// \ref named-func-param "Named parameter"
    11121138    ///for setting \ref ProcessedMap object.
    11131139    template<class T>
     
    11191145
    11201146    template<class T>
    1121     struct SetDistMapBase : public Base {
    1122       typedef T DistMap;
    1123       static DistMap *createDistMap(const Digraph &) { return 0; };
    1124       SetDistMapBase(const TR &b) : TR(b) {}
    1125     };
    1126     ///\brief \ref named-templ-param "Named parameter"
    1127     ///for setting \ref DistMap object.
    1128     ///
    1129     /// \ref named-templ-param "Named parameter"
    1130     ///for setting \ref DistMap object.
     1147    struct SetPathBase : public Base {
     1148      typedef T Path;
     1149      SetPathBase(const TR &b) : TR(b) {}
     1150    };
     1151    ///\brief \ref named-func-param "Named parameter"
     1152    ///for getting the shortest path to the target node.
     1153    ///
     1154    ///\ref named-func-param "Named parameter"
     1155    ///for getting the shortest path to the target node.
    11311156    template<class T>
    1132     BfsWizard<SetDistMapBase<T> > distMap(const T &t)
    1133     {
    1134       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1135       return BfsWizard<SetDistMapBase<T> >(*this);
     1157    BfsWizard<SetPathBase<T> > path(const T &t)
     1158    {
     1159      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1160      return BfsWizard<SetPathBase<T> >(*this);
     1161    }
     1162
     1163    ///\brief \ref named-func-param "Named parameter"
     1164    ///for getting the distance of the target node.
     1165    ///
     1166    ///\ref named-func-param "Named parameter"
     1167    ///for getting the distance of the target node.
     1168    BfsWizard dist(const int &d)
     1169    {
     1170      Base::_di=const_cast<int*>(&d);
     1171      return *this;
    11361172    }
    11371173
    11381174  };
    11391175
    1140   ///Function type interface for Bfs algorithm.
     1176  ///Function-type interface for BFS algorithm.
    11411177
    11421178  /// \ingroup search
    1143   ///Function type interface for Bfs algorithm.
     1179  ///Function-type interface for BFS algorithm.
    11441180  ///
    1145   ///This function also has several
    1146   ///\ref named-templ-func-param "named parameters",
     1181  ///This function also has several \ref named-func-param "named parameters",
    11471182  ///they are declared as the members of class \ref BfsWizard.
    1148   ///The following
    1149   ///example shows how to use these parameters.
     1183  ///The following examples show how to use these parameters.
    11501184  ///\code
    1151   ///  bfs(g,source).predMap(preds).run();
     1185  ///  // Compute shortest path from node s to each node
     1186  ///  bfs(g).predMap(preds).distMap(dists).run(s);
     1187  ///
     1188  ///  // Compute shortest path from s to t
     1189  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11521190  ///\endcode
    11531191  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
     
    11571195  template<class GR>
    11581196  BfsWizard<BfsWizardBase<GR> >
    1159   bfs(const GR &g,typename GR::Node s=INVALID)
     1197  bfs(const GR &digraph)
    11601198  {
    1161     return BfsWizard<BfsWizardBase<GR> >(g,s);
     1199    return BfsWizard<BfsWizardBase<GR> >(digraph);
    11621200  }
    11631201
Note: See TracChangeset for help on using the changeset viewer.