COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bfs.h

    r247 r341  
    2929#include <lemon/error.h>
    3030#include <lemon/maps.h>
     31#include <lemon/path.h>
    3132
    3233namespace lemon {
    … …  
    4950    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    5051    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    51     ///Instantiates a \ref PredMap.
    52 
    53     ///This function instantiates a \ref PredMap.
     52    ///Instantiates a PredMap.
     53
     54    ///This function instantiates a PredMap. 
    5455    ///\param g is the digraph, to which we would like to define the
    55     ///\ref PredMap.
    56     ///\todo The digraph alone may be insufficient to initialize
     56    ///PredMap.
    5757    static PredMap *createPredMap(const Digraph &g)
    5858    {
    … …  
    6464    ///The type of the map that indicates which nodes are processed.
    6565    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    66     ///By default it is a NullMap.
    6766    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    68     ///Instantiates a \ref ProcessedMap.
    69 
    70     ///This function instantiates a \ref ProcessedMap.
     67    ///Instantiates a ProcessedMap.
     68
     69    ///This function instantiates a ProcessedMap.
    7170    ///\param g is the digraph, to which
    72     ///we would like to define the \ref ProcessedMap
     71    ///we would like to define the ProcessedMap
    7372#ifdef DOXYGEN
    7473    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    8281    ///The type of the map that indicates which nodes are reached.
    8382
    84     ///The type of the map that indicates which nodes are reached.
    85     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8684    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    87     ///Instantiates a \ref ReachedMap.
    88 
    89     ///This function instantiates a \ref ReachedMap.
     85    ///Instantiates a ReachedMap.
     86
     87    ///This function instantiates a ReachedMap.
    9088    ///\param g is the digraph, to which
    91     ///we would like to define the \ref ReachedMap.
     89    ///we would like to define the ReachedMap.
    9290    static ReachedMap *createReachedMap(const Digraph &g)
    9391    {
    … …  
    10098    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    10199    typedef typename Digraph::template NodeMap<int> DistMap;
    102     ///Instantiates a \ref DistMap.
    103 
    104     ///This function instantiates a \ref DistMap.
     100    ///Instantiates a DistMap.
     101
     102    ///This function instantiates a DistMap.
    105103    ///\param g is the digraph, to which we would like to define the
    106     ///\ref DistMap.
     104    ///DistMap.
    107105    static DistMap *createDistMap(const Digraph &g)
    108106    {
    … …  
    116114  ///This class provides an efficient implementation of the %BFS algorithm.
    117115  ///
    118   ///There is also a \ref bfs() "function type interface" for the BFS
     116  ///There is also a \ref bfs() "function-type interface" for the BFS
    119117  ///algorithm, which is convenient in the simplier cases and it can be
    120118  ///used easier.
    … …  
    137135  class Bfs {
    138136  public:
    139     ///\ref Exception for uninitialized parameters.
    140 
    141     ///This error represents problems in the initialization of the
    142     ///parameters of the algorithm.
    143     class UninitializedParameter : public lemon::UninitializedParameter {
    144     public:
    145       virtual const char* what() const throw() {
    146         return "lemon::Bfs::UninitializedParameter";
    147       }
    148     };
    149137
    150138    ///The type of the digraph the algorithm runs on.
    … …  
    196184    int _curr_dist;
    197185
    198     ///Creates the maps if necessary.
    199     ///\todo Better memory allocation (instead of new).
     186    //Creates the maps if necessary.
    200187    void create_maps()
    201188    {
    … …  
    231218
    232219    template <class T>
    233     struct DefPredMapTraits : public Traits {
     220    struct SetPredMapTraits : public Traits {
    234221      typedef T PredMap;
    235222      static PredMap *createPredMap(const Digraph &)
    236223      {
    237         throw UninitializedParameter();
     224        LEMON_ASSERT(false, "PredMap is not initialized");
     225        return 0; // ignore warnings
    238226      }
    239227    };
    240228    ///\brief \ref named-templ-param "Named parameter" for setting
    241     ///\ref PredMap type.
     229    ///PredMap type.
    242230    ///
    243231    ///\ref named-templ-param "Named parameter" for setting
    244     ///\ref PredMap type.
     232    ///PredMap type.
    245233    template <class T>
    246     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
    247       typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
     234    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
     235      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
    248236    };
    249237
    250238    template <class T>
    251     struct DefDistMapTraits : public Traits {
     239    struct SetDistMapTraits : public Traits {
    252240      typedef T DistMap;
    253241      static DistMap *createDistMap(const Digraph &)
    254242      {
    255         throw UninitializedParameter();
     243        LEMON_ASSERT(false, "DistMap is not initialized");
     244        return 0; // ignore warnings
    256245      }
    257246    };
    258247    ///\brief \ref named-templ-param "Named parameter" for setting
    259     ///\ref DistMap type.
     248    ///DistMap type.
    260249    ///
    261250    ///\ref named-templ-param "Named parameter" for setting
    262     ///\ref DistMap type.
     251    ///DistMap type.
    263252    template <class T>
    264     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
    265       typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
     253    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
     254      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
    266255    };
    267256
    268257    template <class T>
    269     struct DefReachedMapTraits : public Traits {
     258    struct SetReachedMapTraits : public Traits {
    270259      typedef T ReachedMap;
    271260      static ReachedMap *createReachedMap(const Digraph &)
    272261      {
    273         throw UninitializedParameter();
     262        LEMON_ASSERT(false, "ReachedMap is not initialized");
     263        return 0; // ignore warnings
    274264      }
    275265    };
    276266    ///\brief \ref named-templ-param "Named parameter" for setting
    277     ///\ref ReachedMap type.
     267    ///ReachedMap type.
    278268    ///
    279269    ///\ref named-templ-param "Named parameter" for setting
    280     ///\ref ReachedMap type.
     270    ///ReachedMap type.
    281271    template <class T>
    282     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
    283       typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
     272    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
     273      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
    284274    };
    285275
    286276    template <class T>
    287     struct DefProcessedMapTraits : public Traits {
     277    struct SetProcessedMapTraits : public Traits {
    288278      typedef T ProcessedMap;
    289279      static ProcessedMap *createProcessedMap(const Digraph &)
    290280      {
    291         throw UninitializedParameter();
     281        LEMON_ASSERT(false, "ProcessedMap is not initialized");
     282        return 0; // ignore warnings
    292283      }
    293284    };
    294285    ///\brief \ref named-templ-param "Named parameter" for setting
    295     ///\ref ProcessedMap type.
     286    ///ProcessedMap type.
    296287    ///
    297288    ///\ref named-templ-param "Named parameter" for setting
    298     ///\ref ProcessedMap type.
     289    ///ProcessedMap type.
    299290    template <class T>
    300     struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
    301       typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
     291    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
     292      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
    302293    };
    303294
    304     struct DefDigraphProcessedMapTraits : public Traits {
     295    struct SetStandardProcessedMapTraits : public Traits {
    305296      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    306297      static ProcessedMap *createProcessedMap(const Digraph &g)
    307298      {
    308299        return new ProcessedMap(g);
     300        return 0; // ignore warnings
    309301      }
    310302    };
    311303    ///\brief \ref named-templ-param "Named parameter" for setting
    312     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     304    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    313305    ///
    314306    ///\ref named-templ-param "Named parameter" for setting
    315     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     307    ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
    316308    ///If you don't set it explicitly, it will be automatically allocated.
    317     template <class T>
    318     struct DefProcessedMapToBeDefaultMap :
    319       public Bfs< Digraph, DefDigraphProcessedMapTraits> {
    320       typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
     309    struct SetStandardProcessedMap :
     310      public Bfs< Digraph, SetStandardProcessedMapTraits > {
     311      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
    321312    };
    322313
    … …  
    608599    ///
    609600    ///This method runs the %BFS algorithm from the root node(s)
    610     ///in order to compute the shortest path to \c dest.
     601    ///in order to compute the shortest path to \c t.
    611602    ///
    612603    ///The algorithm computes
    613     ///- the shortest path to \c dest,
    614     ///- the distance of \c dest from the root(s).
     604    ///- the shortest path to \c t,
     605    ///- the distance of \c t from the root(s).
    615606    ///
    616607    ///\pre init() must be called and at least one root node should be
    … …  
    624615    ///  }
    625616    ///\endcode
    626     void start(Node dest)
     617    void start(Node t)
    627618    {
    628619      bool reach = false;
    629       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     620      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    630621    }
    631622
    … …  
    665656    }
    666657
    667     ///Runs the algorithm from the given node.
     658    ///Runs the algorithm from the given source node.
    668659
    669660    ///This method runs the %BFS algorithm from node \c s
    … …  
    689680
    690681    ///This method runs the %BFS algorithm from node \c s
    691     ///in order to compute the shortest path to \c t.
    692     ///
    693     ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
    694     ///if \c t is reachable form \c s, \c 0 otherwise.
     682    ///in order to compute the shortest path to node \c t
     683    ///(it stops searching when \c t is processed).
     684    ///
     685    ///\return \c true if \c t is reachable form \c s.
    695686    ///
    696687    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
    … …  
    701692    ///  b.start(t);
    702693    ///\endcode
    703     int run(Node s,Node t) {
     694    bool run(Node s,Node t) {
    704695      init();
    705696      addSource(s);
    706697      start(t);
    707       return reached(t) ? _curr_dist : 0;
     698      return reached(t);
    708699    }
    709700
    … …  
    843834    ///arcs of the shortest paths.
    844835    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    845     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
    846     ///Instantiates a \ref PredMap.
    847 
    848     ///This function instantiates a \ref PredMap.
     836    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     837    ///Instantiates a PredMap.
     838
     839    ///This function instantiates a PredMap.
    849840    ///\param g is the digraph, to which we would like to define the
    850     ///\ref PredMap.
    851     ///\todo The digraph alone may be insufficient to initialize
    852 #ifdef DOXYGEN
     841    ///PredMap.
    853842    static PredMap *createPredMap(const Digraph &g)
    854 #else
    855     static PredMap *createPredMap(const Digraph &)
    856 #endif
    857     {
    858       return new PredMap();
     843    {
     844      return new PredMap(g);
    859845    }
    860846
    … …  
    863849    ///The type of the map that indicates which nodes are processed.
    864850    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     851    ///By default it is a NullMap.
    865852    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    866     ///Instantiates a \ref ProcessedMap.
    867 
    868     ///This function instantiates a \ref ProcessedMap.
     853    ///Instantiates a ProcessedMap.
     854
     855    ///This function instantiates a ProcessedMap.
    869856    ///\param g is the digraph, to which
    870     ///we would like to define the \ref ProcessedMap.
     857    ///we would like to define the ProcessedMap.
    871858#ifdef DOXYGEN
    872859    static ProcessedMap *createProcessedMap(const Digraph &g)
    … …  
    883870    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    884871    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    885     ///Instantiates a \ref ReachedMap.
    886 
    887     ///This function instantiates a \ref ReachedMap.
     872    ///Instantiates a ReachedMap.
     873
     874    ///This function instantiates a ReachedMap.
    888875    ///\param g is the digraph, to which
    889     ///we would like to define the \ref ReachedMap.
     876    ///we would like to define the ReachedMap.
    890877    static ReachedMap *createReachedMap(const Digraph &g)
    891878    {
    … …  
    897884    ///The type of the map that stores the distances of the nodes.
    898885    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    899     ///
    900     typedef NullMap<typename Digraph::Node,int> DistMap;
    901     ///Instantiates a \ref DistMap.
    902 
    903     ///This function instantiates a \ref DistMap.
     886    typedef typename Digraph::template NodeMap<int> DistMap;
     887    ///Instantiates a DistMap.
     888
     889    ///This function instantiates a DistMap.
    904890    ///\param g is the digraph, to which we would like to define
    905     ///the \ref DistMap
    906 #ifdef DOXYGEN
     891    ///the DistMap
    907892    static DistMap *createDistMap(const Digraph &g)
    908 #else
    909     static DistMap *createDistMap(const Digraph &)
    910 #endif
    911     {
    912       return new DistMap();
    913     }
     893    {
     894      return new DistMap(g);
     895    }
     896
     897    ///The type of the shortest paths.
     898
     899    ///The type of the shortest paths.
     900    ///It must meet the \ref concepts::Path "Path" concept.
     901    typedef lemon::Path<Digraph> Path;
    914902  };
    915903
    916   /// Default traits class used by \ref BfsWizard
     904  /// Default traits class used by BfsWizard
    917905
    918906  /// To make it easier to use Bfs algorithm
    … …  
    941929    //Pointer to the map of distances.
    942930    void *_dist;
    943     //Pointer to the source node.
    944     Node _source;
     931    //Pointer to the shortest path to the target node.
     932    void *_path;
     933    //Pointer to the distance of the target node.
     934    int *_di;
    945935
    946936    public:
    … …  
    948938
    949939    /// This constructor does not require parameters, therefore it initiates
    950     /// all of the attributes to default values (0, INVALID).
     940    /// all of the attributes to \c 0.
    951941    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    952                       _dist(0), _source(INVALID) {}
     942                      _dist(0), _path(0), _di(0) {}
    953943
    954944    /// Constructor.
    955945
    956     /// This constructor requires some parameters,
    957     /// listed in the parameters list.
    958     /// Others are initiated to 0.
     946    /// This constructor requires one parameter,
     947    /// others are initiated to \c 0.
    959948    /// \param g The digraph the algorithm runs on.
    960     /// \param s The source node.
    961     BfsWizardBase(const GR &g, Node s=INVALID) :
     949    BfsWizardBase(const GR &g) :
    962950      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    963       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     951      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    964952
    965953  };
    966954
    967   /// Auxiliary class for the function type interface of BFS algorithm.
    968 
    969   /// This auxiliary class is created to implement the function type
    970   /// interface of \ref Bfs algorithm. It uses the functions and features
    971   /// of the plain \ref Bfs, but it is much simpler to use it.
    972   /// It should only be used through the \ref bfs() function, which makes
    973   /// it easier to use the algorithm.
     955  /// Auxiliary class for the function-type interface of BFS algorithm.
     956
     957  /// This auxiliary class is created to implement the
     958  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
     959  /// It does not have own \ref run() method, it uses the functions
     960  /// and features of the plain \ref Bfs.
    974961  ///
    975   /// Simplicity means that the way to change the types defined
    976   /// in the traits class is based on functions that returns the new class
    977   /// and not on templatable built-in classes.
    978   /// When using the plain \ref Bfs
    979   /// the new class with the modified type comes from
    980   /// the original class by using the ::
    981   /// operator. In the case of \ref BfsWizard only
    982   /// a function have to be called, and it will
    983   /// return the needed class.
    984   ///
    985   /// It does not have own \ref run() method. When its \ref run() method
    986   /// is called, it initiates a plain \ref Bfs object, and calls the
    987   /// \ref Bfs::run() method of it.
     962  /// This class should only be used through the \ref bfs() function,
     963  /// which makes it easier to use the algorithm.
    988964  template<class TR>
    989965  class BfsWizard : public TR
    … …  
    1008984    ///\brief The type of the map that indicates which nodes are processed.
    1009985    typedef typename TR::ProcessedMap ProcessedMap;
     986    ///The type of the shortest paths
     987    typedef typename TR::Path Path;
    1010988
    1011989  public:
    … …  
    1018996    /// Constructor that requires parameters.
    1019997    /// These parameters will be the default values for the traits class.
    1020     BfsWizard(const Digraph &g, Node s=INVALID) :
    1021       TR(g,s) {}
     998    /// \param g The digraph the algorithm runs on.
     999    BfsWizard(const Digraph &g) :
     1000      TR(g) {}
    10221001
    10231002    ///Copy constructor
    … …  
    10261005    ~BfsWizard() {}
    10271006
    1028     ///Runs BFS algorithm from a source node.
    1029 
    1030     ///Runs BFS algorithm from a source node.
    1031     ///The node can be given with the \ref source() function.
     1007    ///Runs BFS algorithm from the given source node.
     1008
     1009    ///This method runs BFS algorithm from node \c s
     1010    ///in order to compute the shortest path to each node.
     1011    void run(Node s)
     1012    {
     1013      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1014      if (Base::_pred)
     1015        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1016      if (Base::_dist)
     1017        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1018      if (Base::_reached)
     1019        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1020      if (Base::_processed)
     1021        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1022      if (s!=INVALID)
     1023        alg.run(s);
     1024      else
     1025        alg.run();
     1026    }
     1027
     1028    ///Finds the shortest path between \c s and \c t.
     1029
     1030    ///This method runs BFS algorithm from node \c s
     1031    ///in order to compute the shortest path to node \c t
     1032    ///(it stops searching when \c t is processed).
     1033    ///
     1034    ///\return \c true if \c t is reachable form \c s.
     1035    bool run(Node s, Node t)
     1036    {
     1037      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     1038      if (Base::_pred)
     1039        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     1040      if (Base::_dist)
     1041        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     1042      if (Base::_reached)
     1043        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     1044      if (Base::_processed)
     1045        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     1046      alg.run(s,t);
     1047      if (Base::_path)
     1048        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     1049      if (Base::_di)
     1050        *Base::_di = alg.dist(t);
     1051      return alg.reached(t);
     1052    }
     1053
     1054    ///Runs BFS algorithm to visit all nodes in the digraph.
     1055
     1056    ///This method runs BFS algorithm in order to compute
     1057    ///the shortest path to each node.
    10321058    void run()
    10331059    {
    1034       if(Base::_source==INVALID) throw UninitializedParameter();
    1035       Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    1036       if(Base::_reached)
    1037         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    1038       if(Base::_processed)
    1039         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    1040       if(Base::_pred)
    1041         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    1042       if(Base::_dist)
    1043         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    1044       alg.run(Base::_source);
    1045     }
    1046 
    1047     ///Runs BFS algorithm from the given node.
    1048 
    1049     ///Runs BFS algorithm from the given node.
    1050     ///\param s is the given source.
    1051     void run(Node s)
    1052     {
    1053       Base::_source=s;
    1054       run();
    1055     }
    1056 
    1057     /// Sets the source node, from which the Bfs algorithm runs.
    1058 
    1059     /// Sets the source node, from which the Bfs algorithm runs.
    1060     /// \param s is the source node.
    1061     BfsWizard<TR> &source(Node s)
    1062     {
    1063       Base::_source=s;
    1064       return *this;
     1060      run(INVALID);
    10651061    }
    10661062
    10671063    template<class T>
    1068     struct DefPredMapBase : public Base {
     1064    struct SetPredMapBase : public Base {
    10691065      typedef T PredMap;
    10701066      static PredMap *createPredMap(const Digraph &) { return 0; };
    1071       DefPredMapBase(const TR &b) : TR(b) {}
     1067      SetPredMapBase(const TR &b) : TR(b) {}
    10721068    };
    1073     ///\brief \ref named-templ-param "Named parameter"
    1074     ///for setting \ref PredMap object.
    1075     ///
    1076     /// \ref named-templ-param "Named parameter"
    1077     ///for setting \ref PredMap object.
     1069    ///\brief \ref named-func-param "Named parameter"
     1070    ///for setting PredMap object.
     1071    ///
     1072    ///\ref named-func-param "Named parameter"
     1073    ///for setting PredMap object.
    10781074    template<class T>
    1079     BfsWizard<DefPredMapBase<T> > predMap(const T &t)
     1075    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    10801076    {
    10811077      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    1082       return BfsWizard<DefPredMapBase<T> >(*this);
     1078      return BfsWizard<SetPredMapBase<T> >(*this);
    10831079    }
    10841080
    10851081    template<class T>
    1086     struct DefReachedMapBase : public Base {
     1082    struct SetReachedMapBase : public Base {
    10871083      typedef T ReachedMap;
    10881084      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
    1089       DefReachedMapBase(const TR &b) : TR(b) {}
     1085      SetReachedMapBase(const TR &b) : TR(b) {}
    10901086    };
    1091     ///\brief \ref named-templ-param "Named parameter"
    1092     ///for setting \ref ReachedMap object.
    1093     ///
    1094     /// \ref named-templ-param "Named parameter"
    1095     ///for setting \ref ReachedMap object.
     1087    ///\brief \ref named-func-param "Named parameter"
     1088    ///for setting ReachedMap object.
     1089    ///
     1090    /// \ref named-func-param "Named parameter"
     1091    ///for setting ReachedMap object.
    10961092    template<class T>
    1097     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
     1093    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    10981094    {
    10991095      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    1100       return BfsWizard<DefReachedMapBase<T> >(*this);
     1096      return BfsWizard<SetReachedMapBase<T> >(*this);
    11011097    }
    11021098
    11031099    template<class T>
    1104     struct DefProcessedMapBase : public Base {
     1100    struct SetDistMapBase : public Base {
     1101      typedef T DistMap;
     1102      static DistMap *createDistMap(const Digraph &) { return 0; };
     1103      SetDistMapBase(const TR &b) : TR(b) {}
     1104    };
     1105    ///\brief \ref named-func-param "Named parameter"
     1106    ///for setting DistMap object.
     1107    ///
     1108    /// \ref named-func-param "Named parameter"
     1109    ///for setting DistMap object.
     1110    template<class T>
     1111    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1112    {
     1113      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1114      return BfsWizard<SetDistMapBase<T> >(*this);
     1115    }
     1116
     1117    template<class T>
     1118    struct SetProcessedMapBase : public Base {
    11051119      typedef T ProcessedMap;
    11061120      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
    1107       DefProcessedMapBase(const TR &b) : TR(b) {}
     1121      SetProcessedMapBase(const TR &b) : TR(b) {}
    11081122    };
    1109     ///\brief \ref named-templ-param "Named parameter"
    1110     ///for setting \ref ProcessedMap object.
    1111     ///
    1112     /// \ref named-templ-param "Named parameter"
    1113     ///for setting \ref ProcessedMap object.
     1123    ///\brief \ref named-func-param "Named parameter"
     1124    ///for setting ProcessedMap object.
     1125    ///
     1126    /// \ref named-func-param "Named parameter"
     1127    ///for setting ProcessedMap object.
    11141128    template<class T>
    1115     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
     1129    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    11161130    {
    11171131      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
    1118       return BfsWizard<DefProcessedMapBase<T> >(*this);
     1132      return BfsWizard<SetProcessedMapBase<T> >(*this);
    11191133    }
    11201134
    11211135    template<class T>
    1122     struct DefDistMapBase : public Base {
    1123       typedef T DistMap;
    1124       static DistMap *createDistMap(const Digraph &) { return 0; };
    1125       DefDistMapBase(const TR &b) : TR(b) {}
     1136    struct SetPathBase : public Base {
     1137      typedef T Path;
     1138      SetPathBase(const TR &b) : TR(b) {}
    11261139    };
    1127     ///\brief \ref named-templ-param "Named parameter"
    1128     ///for setting \ref DistMap object.
    1129     ///
    1130     /// \ref named-templ-param "Named parameter"
    1131     ///for setting \ref DistMap object.
     1140    ///\brief \ref named-func-param "Named parameter"
     1141    ///for getting the shortest path to the target node.
     1142    ///
     1143    ///\ref named-func-param "Named parameter"
     1144    ///for getting the shortest path to the target node.
    11321145    template<class T>
    1133     BfsWizard<DefDistMapBase<T> > distMap(const T &t)
    1134     {
    1135       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1136       return BfsWizard<DefDistMapBase<T> >(*this);
     1146    BfsWizard<SetPathBase<T> > path(const T &t)
     1147    {
     1148      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1149      return BfsWizard<SetPathBase<T> >(*this);
     1150    }
     1151
     1152    ///\brief \ref named-func-param "Named parameter"
     1153    ///for getting the distance of the target node.
     1154    ///
     1155    ///\ref named-func-param "Named parameter"
     1156    ///for getting the distance of the target node.
     1157    BfsWizard dist(const int &d)
     1158    {
     1159      Base::_di=const_cast<int*>(&d);
     1160      return *this;
    11371161    }
    11381162
    11391163  };
    11401164
    1141   ///Function type interface for Bfs algorithm.
     1165  ///Function-type interface for BFS algorithm.
    11421166
    11431167  /// \ingroup search
    1144   ///Function type interface for Bfs algorithm.
     1168  ///Function-type interface for BFS algorithm.
    11451169  ///
    1146   ///This function also has several
    1147   ///\ref named-templ-func-param "named parameters",
     1170  ///This function also has several \ref named-func-param "named parameters",
    11481171  ///they are declared as the members of class \ref BfsWizard.
    1149   ///The following
    1150   ///example shows how to use these parameters.
     1172  ///The following examples show how to use these parameters.
    11511173  ///\code
    1152   ///  bfs(g,source).predMap(preds).run();
     1174  ///  // Compute shortest path from node s to each node
     1175  ///  bfs(g).predMap(preds).distMap(dists).run(s);
     1176  ///
     1177  ///  // Compute shortest path from s to t
     1178  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
    11531179  ///\endcode
    11541180  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
    … …  
    11581184  template<class GR>
    11591185  BfsWizard<BfsWizardBase<GR> >
    1160   bfs(const GR &g,typename GR::Node s=INVALID)
     1186  bfs(const GR &digraph)
    11611187  {
    1162     return BfsWizard<BfsWizardBase<GR> >(g,s);
     1188    return BfsWizard<BfsWizardBase<GR> >(digraph);
    11631189  }
    11641190
    … …  
    12411267    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12421268
    1243     /// \brief Instantiates a \ref ReachedMap.
    1244     ///
    1245     /// This function instantiates a \ref ReachedMap.
     1269    /// \brief Instantiates a ReachedMap.
     1270    ///
     1271    /// This function instantiates a ReachedMap.
    12461272    /// \param digraph is the digraph, to which
    1247     /// we would like to define the \ref ReachedMap.
     1273    /// we would like to define the ReachedMap.
    12481274    static ReachedMap *createReachedMap(const Digraph &digraph) {
    12491275      return new ReachedMap(digraph);
    … …  
    12621288  /// class. It works with callback mechanism, the BfsVisit object calls
    12631289  /// the member functions of the \c Visitor class on every BFS event.
     1290  ///
     1291  /// This interface of the BFS algorithm should be used in special cases
     1292  /// when extra actions have to be performed in connection with certain
     1293  /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
     1294  /// instead.
    12641295  ///
    12651296  /// \tparam _Digraph The type of the digraph the algorithm runs on.
    … …  
    12811312  template <typename _Digraph = ListDigraph,
    12821313            typename _Visitor = BfsVisitor<_Digraph>,
    1283             typename _Traits = BfsDefaultTraits<_Digraph> >
     1314            typename _Traits = BfsVisitDefaultTraits<_Digraph> >
    12841315#endif
    12851316  class BfsVisit {
    12861317  public:
    1287 
    1288     /// \brief \ref Exception for uninitialized parameters.
    1289     ///
    1290     /// This error represents problems in the initialization
    1291     /// of the parameters of the algorithm.
    1292     class UninitializedParameter : public lemon::UninitializedParameter {
    1293     public:
    1294       virtual const char* what() const throw()
    1295       {
    1296         return "lemon::BfsVisit::UninitializedParameter";
    1297       }
    1298     };
    12991318
    13001319    ///The traits class.
    … …  
    13291348    int _list_front, _list_back;
    13301349
    1331     ///Creates the maps if necessary.
    1332     ///\todo Better memory allocation (instead of new).
     1350    //Creates the maps if necessary.
    13331351    void create_maps() {
    13341352      if(!_reached) {
    … …  
    13501368    ///@{
    13511369    template <class T>
    1352     struct DefReachedMapTraits : public Traits {
     1370    struct SetReachedMapTraits : public Traits {
    13531371      typedef T ReachedMap;
    13541372      static ReachedMap *createReachedMap(const Digraph &digraph) {
    1355         throw UninitializedParameter();
     1373        LEMON_ASSERT(false, "ReachedMap is not initialized");
     1374        return 0; // ignore warnings
    13561375      }
    13571376    };
    … …  
    13611380    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
    13621381    template <class T>
    1363     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
    1364                                             DefReachedMapTraits<T> > {
    1365       typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
     1382    struct SetReachedMap : public BfsVisit< Digraph, Visitor,
     1383                                            SetReachedMapTraits<T> > {
     1384      typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
    13661385    };
    13671386    ///@}
    … …  
    15801599    ///
    15811600    /// This method runs the %BFS algorithm from the root node(s)
    1582     /// in order to compute the shortest path to \c dest.
     1601    /// in order to compute the shortest path to \c t.
    15831602    ///
    15841603    /// The algorithm computes
    1585     /// - the shortest path to \c dest,
    1586     /// - the distance of \c dest from the root(s).
     1604    /// - the shortest path to \c t,
     1605    /// - the distance of \c t from the root(s).
    15871606    ///
    15881607    /// \pre init() must be called and at least one root node should be
    … …  
    15961615    ///   }
    15971616    /// \endcode
    1598     void start(Node dest) {
     1617    void start(Node t) {
    15991618      bool reach = false;
    1600       while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
     1619      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
    16011620    }
    16021621
    … …  
    16361655    }
    16371656
    1638     /// \brief Runs the algorithm from the given node.
     1657    /// \brief Runs the algorithm from the given source node.
    16391658    ///
    16401659    /// This method runs the %BFS algorithm from node \c s
    … …  
    16551674      addSource(s);
    16561675      start();
     1676    }
     1677
     1678    /// \brief Finds the shortest path between \c s and \c t.
     1679    ///
     1680    /// This method runs the %BFS algorithm from node \c s
     1681    /// in order to compute the shortest path to node \c t
     1682    /// (it stops searching when \c t is processed).
     1683    ///
     1684    /// \return \c true if \c t is reachable form \c s.
     1685    ///
     1686    /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
     1687    /// shortcut of the following code.
     1688    ///\code
     1689    ///   b.init();
     1690    ///   b.addSource(s);
     1691    ///   b.start(t);
     1692    ///\endcode
     1693    bool run(Node s,Node t) {
     1694      init();
     1695      addSource(s);
     1696      start(t);
     1697      return reached(t);
    16571698    }
    16581699
Note: See TracChangeset for help on using the changeset viewer.