COIN-OR::LEMON - Graph Library

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

    r258 r278  
    3030#include <lemon/assert.h>
    3131#include <lemon/maps.h>
     32#include <lemon/path.h>
    3233
    3334namespace lemon {
     
    117118  ///This class provides an efficient implementation of the %DFS algorithm.
    118119  ///
    119   ///There is also a \ref dfs() "function type interface" for the DFS
     120  ///There is also a \ref dfs() "function-type interface" for the DFS
    120121  ///algorithm, which is convenient in the simplier cases and it can be
    121122  ///used easier.
     
    776777    ///arcs of the %DFS paths.
    777778    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    778     ///
    779     typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
     779    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    780780    ///Instantiates a \ref PredMap.
    781781
     
    784784    ///\ref PredMap.
    785785    ///\todo The digraph alone may be insufficient to initialize
    786 #ifdef DOXYGEN
    787786    static PredMap *createPredMap(const Digraph &g)
    788 #else
    789     static PredMap *createPredMap(const Digraph &)
    790 #endif
    791     {
    792       return new PredMap();
     787    {
     788      return new PredMap(g);
    793789    }
    794790
     
    797793    ///The type of the map that indicates which nodes are processed.
    798794    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     795    ///By default it is a NullMap.
    799796    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    800797    ///Instantiates a \ref ProcessedMap.
     
    831828    ///The type of the map that stores the distances of the nodes.
    832829    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    833     ///
    834     typedef NullMap<typename Digraph::Node,int> DistMap;
     830    typedef typename Digraph::template NodeMap<int> DistMap;
    835831    ///Instantiates a \ref DistMap.
    836832
     
    838834    ///\param g is the digraph, to which we would like to define
    839835    ///the \ref DistMap
    840 #ifdef DOXYGEN
    841836    static DistMap *createDistMap(const Digraph &g)
    842 #else
    843     static DistMap *createDistMap(const Digraph &)
    844 #endif
    845     {
    846       return new DistMap();
    847     }
     837    {
     838      return new DistMap(g);
     839    }
     840
     841    ///The type of the DFS paths.
     842
     843    ///The type of the DFS paths.
     844    ///It must meet the \ref concepts::Path "Path" concept.
     845    typedef lemon::Path<Digraph> Path;
    848846  };
    849847
     
    875873    //Pointer to the map of distances.
    876874    void *_dist;
    877     //Pointer to the source node.
    878     Node _source;
     875    //Pointer to the DFS path to the target node.
     876    void *_path;
     877    //Pointer to the distance of the target node.
     878    int *_di;
    879879
    880880    public:
     
    882882
    883883    /// This constructor does not require parameters, therefore it initiates
    884     /// all of the attributes to default values (0, INVALID).
     884    /// all of the attributes to \c 0.
    885885    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    886                       _dist(0), _source(INVALID) {}
     886                      _dist(0), _path(0), _di(0) {}
    887887
    888888    /// Constructor.
    889889
    890     /// This constructor requires some parameters,
    891     /// listed in the parameters list.
    892     /// Others are initiated to 0.
     890    /// This constructor requires one parameter,
     891    /// others are initiated to \c 0.
    893892    /// \param g The digraph the algorithm runs on.
    894     /// \param s The source node.
    895     DfsWizardBase(const GR &g, Node s=INVALID) :
     893    DfsWizardBase(const GR &g) :
    896894      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    897       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
     895      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
    898896
    899897  };
    900898
    901   /// Auxiliary class for the function type interface of DFS algorithm.
    902 
    903   /// This auxiliary class is created to implement the function type
    904   /// interface of \ref Dfs algorithm. It uses the functions and features
    905   /// of the plain \ref Dfs, but it is much simpler to use it.
    906   /// It should only be used through the \ref dfs() function, which makes
    907   /// it easier to use the algorithm.
     899  /// Auxiliary class for the function-type interface of DFS algorithm.
     900
     901  /// This auxiliary class is created to implement the
     902  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
     903  /// It does not have own \ref run() method, it uses the functions
     904  /// and features of the plain \ref Dfs.
    908905  ///
    909   /// Simplicity means that the way to change the types defined
    910   /// in the traits class is based on functions that returns the new class
    911   /// and not on templatable built-in classes.
    912   /// When using the plain \ref Dfs
    913   /// the new class with the modified type comes from
    914   /// the original class by using the ::
    915   /// operator. In the case of \ref DfsWizard only
    916   /// a function have to be called, and it will
    917   /// return the needed class.
    918   ///
    919   /// It does not have own \ref run() method. When its \ref run() method
    920   /// is called, it initiates a plain \ref Dfs object, and calls the
    921   /// \ref Dfs::run() method of it.
     906  /// This class should only be used through the \ref dfs() function,
     907  /// which makes it easier to use the algorithm.
    922908  template<class TR>
    923909  class DfsWizard : public TR
     
    934920
    935921    ///\brief The type of the map that stores the predecessor
    936     ///arcs of the shortest paths.
     922    ///arcs of the DFS paths.
    937923    typedef typename TR::PredMap PredMap;
    938924    ///\brief The type of the map that stores the distances of the nodes.
     
    942928    ///\brief The type of the map that indicates which nodes are processed.
    943929    typedef typename TR::ProcessedMap ProcessedMap;
     930    ///The type of the DFS paths
     931    typedef typename TR::Path Path;
    944932
    945933  public:
     
    952940    /// Constructor that requires parameters.
    953941    /// These parameters will be the default values for the traits class.
    954     DfsWizard(const Digraph &g, Node s=INVALID) :
    955       TR(g,s) {}
     942    /// \param g The digraph the algorithm runs on.
     943    DfsWizard(const Digraph &g) :
     944      TR(g) {}
    956945
    957946    ///Copy constructor
     
    960949    ~DfsWizard() {}
    961950
    962     ///Runs DFS algorithm from a source node.
    963 
    964     ///Runs DFS algorithm from a source node.
    965     ///The node can be given with the \ref source() function.
     951    ///Runs DFS algorithm from the given source node.
     952
     953    ///This method runs DFS algorithm from node \c s
     954    ///in order to compute the DFS path to each node.
     955    void run(Node s)
     956    {
     957      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     958      if (Base::_pred)
     959        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     960      if (Base::_dist)
     961        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     962      if (Base::_reached)
     963        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     964      if (Base::_processed)
     965        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     966      if (s!=INVALID)
     967        alg.run(s);
     968      else
     969        alg.run();
     970    }
     971
     972    ///Finds the DFS path between \c s and \c t.
     973
     974    ///This method runs DFS algorithm from node \c s
     975    ///in order to compute the DFS path to node \c t
     976    ///(it stops searching when \c t is processed).
     977    ///
     978    ///\return \c true if \c t is reachable form \c s.
     979    bool run(Node s, Node t)
     980    {
     981      if (s==INVALID || t==INVALID) throw UninitializedParameter();
     982      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
     983      if (Base::_pred)
     984        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
     985      if (Base::_dist)
     986        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
     987      if (Base::_reached)
     988        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     989      if (Base::_processed)
     990        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
     991      alg.run(s,t);
     992      if (Base::_path)
     993        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
     994      if (Base::_di)
     995        *Base::_di = alg.dist(t);
     996      return alg.reached(t);
     997      }
     998
     999    ///Runs DFS algorithm to visit all nodes in the digraph.
     1000
     1001    ///This method runs DFS algorithm in order to compute
     1002    ///the DFS path to each node.
    9661003    void run()
    9671004    {
    968       if(Base::_source==INVALID) throw UninitializedParameter();
    969       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    970       if(Base::_reached)
    971         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    972       if(Base::_processed)
    973         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    974       if(Base::_pred)
    975         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    976       if(Base::_dist)
    977         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    978       alg.run(Base::_source);
    979     }
    980 
    981     ///Runs DFS algorithm from the given node.
    982 
    983     ///Runs DFS algorithm from the given node.
    984     ///\param s is the given source.
    985     void run(Node s)
    986     {
    987       Base::_source=s;
    988       run();
    989     }
    990 
    991     /// Sets the source node, from which the Dfs algorithm runs.
    992 
    993     /// Sets the source node, from which the Dfs algorithm runs.
    994     /// \param s is the source node.
    995     DfsWizard<TR> &source(Node s)
    996     {
    997       Base::_source=s;
    998       return *this;
     1005      run(INVALID);
    9991006    }
    10001007
     
    10051012      SetPredMapBase(const TR &b) : TR(b) {}
    10061013    };
    1007     ///\brief \ref named-templ-param "Named parameter"
     1014    ///\brief \ref named-func-param "Named parameter"
    10081015    ///for setting \ref PredMap object.
    10091016    ///
    1010     ///\ref named-templ-param "Named parameter"
     1017    ///\ref named-func-param "Named parameter"
    10111018    ///for setting \ref PredMap object.
    10121019    template<class T>
     
    10231030      SetReachedMapBase(const TR &b) : TR(b) {}
    10241031    };
    1025     ///\brief \ref named-templ-param "Named parameter"
     1032    ///\brief \ref named-func-param "Named parameter"
    10261033    ///for setting \ref ReachedMap object.
    10271034    ///
    1028     /// \ref named-templ-param "Named parameter"
     1035    /// \ref named-func-param "Named parameter"
    10291036    ///for setting \ref ReachedMap object.
    10301037    template<class T>
     
    10331040      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    10341041      return DfsWizard<SetReachedMapBase<T> >(*this);
     1042    }
     1043
     1044    template<class T>
     1045    struct SetDistMapBase : public Base {
     1046      typedef T DistMap;
     1047      static DistMap *createDistMap(const Digraph &) { return 0; };
     1048      SetDistMapBase(const TR &b) : TR(b) {}
     1049    };
     1050    ///\brief \ref named-func-param "Named parameter"
     1051    ///for setting \ref DistMap object.
     1052    ///
     1053    /// \ref named-func-param "Named parameter"
     1054    ///for setting \ref DistMap object.
     1055    template<class T>
     1056    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
     1057    {
     1058      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
     1059      return DfsWizard<SetDistMapBase<T> >(*this);
    10351060    }
    10361061
     
    10411066      SetProcessedMapBase(const TR &b) : TR(b) {}
    10421067    };
    1043     ///\brief \ref named-templ-param "Named parameter"
     1068    ///\brief \ref named-func-param "Named parameter"
    10441069    ///for setting \ref ProcessedMap object.
    10451070    ///
    1046     /// \ref named-templ-param "Named parameter"
     1071    /// \ref named-func-param "Named parameter"
    10471072    ///for setting \ref ProcessedMap object.
    10481073    template<class T>
     
    10541079
    10551080    template<class T>
    1056     struct SetDistMapBase : public Base {
    1057       typedef T DistMap;
    1058       static DistMap *createDistMap(const Digraph &) { return 0; };
    1059       SetDistMapBase(const TR &b) : TR(b) {}
    1060     };
    1061     ///\brief \ref named-templ-param "Named parameter"
    1062     ///for setting \ref DistMap object.
    1063     ///
    1064     ///\ref named-templ-param "Named parameter"
    1065     ///for setting \ref DistMap object.
     1081    struct SetPathBase : public Base {
     1082      typedef T Path;
     1083      SetPathBase(const TR &b) : TR(b) {}
     1084    };
     1085    ///\brief \ref named-func-param "Named parameter"
     1086    ///for getting the DFS path to the target node.
     1087    ///
     1088    ///\ref named-func-param "Named parameter"
     1089    ///for getting the DFS path to the target node.
    10661090    template<class T>
    1067     DfsWizard<SetDistMapBase<T> > distMap(const T &t)
    1068     {
    1069       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    1070       return DfsWizard<SetDistMapBase<T> >(*this);
     1091    DfsWizard<SetPathBase<T> > path(const T &t)
     1092    {
     1093      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
     1094      return DfsWizard<SetPathBase<T> >(*this);
     1095    }
     1096
     1097    ///\brief \ref named-func-param "Named parameter"
     1098    ///for getting the distance of the target node.
     1099    ///
     1100    ///\ref named-func-param "Named parameter"
     1101    ///for getting the distance of the target node.
     1102    DfsWizard dist(const int &d)
     1103    {
     1104      Base::_di=const_cast<int*>(&d);
     1105      return *this;
    10711106    }
    10721107
    10731108  };
    10741109
    1075   ///Function type interface for Dfs algorithm.
     1110  ///Function-type interface for DFS algorithm.
    10761111
    10771112  ///\ingroup search
    1078   ///Function type interface for Dfs algorithm.
     1113  ///Function-type interface for DFS algorithm.
    10791114  ///
    1080   ///This function also has several
    1081   ///\ref named-templ-func-param "named parameters",
     1115  ///This function also has several \ref named-func-param "named parameters",
    10821116  ///they are declared as the members of class \ref DfsWizard.
    1083   ///The following
    1084   ///example shows how to use these parameters.
     1117  ///The following examples show how to use these parameters.
    10851118  ///\code
    1086   ///  dfs(g,source).predMap(preds).run();
     1119  ///  // Compute the DFS tree
     1120  ///  dfs(g).predMap(preds).distMap(dists).run(s);
     1121  ///
     1122  ///  // Compute the DFS path from s to t
     1123  ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
    10871124  ///\endcode
     1125
    10881126  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
    10891127  ///to the end of the parameter list.
     
    10921130  template<class GR>
    10931131  DfsWizard<DfsWizardBase<GR> >
    1094   dfs(const GR &g,typename GR::Node s=INVALID)
     1132  dfs(const GR &digraph)
    10951133  {
    1096     return DfsWizard<DfsWizardBase<GR> >(g,s);
     1134    return DfsWizard<DfsWizardBase<GR> >(digraph);
    10971135  }
    10981136
Note: See TracChangeset for help on using the changeset viewer.