COIN-OR::LEMON - Graph Library

Changeset 281:e9b4fbe163f5 in lemon-1.0 for lemon/bfs.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/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
Note: See TracChangeset for help on using the changeset viewer.