COIN-OR::LEMON - Graph Library

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