Changeset - r832:9ae88e7c04a7
« 797:b7e366
833:e20173 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Doc improvements for Path and PathDumper concepts (#331)
0 1 0
default
1 file changed with 44 insertions and 41 deletions:
lemon/concepts/path.h
44
41
↑ Collapse diff ↑
lemon/concepts/path.h
Show white space 8 line context
... ... 
@@ -17,9 +17,9 @@
17 17 
 */
18 18 

			




	19
	19
	
		
///\ingroup concept


			




	20
	20
	
		
///\file


			




	21
	
	
		
///\brief Classes for representing paths in digraphs.


			




	
	21
	
		
///\brief The concept of paths


			




	22
	22
	
		
///


			




	23
	23
	
		

			




	24
	24
	
		
#ifndef LEMON_CONCEPTS_PATH_H


			




	25
	25
	
		
#define LEMON_CONCEPTS_PATH_H


			




	...
	...
	
		
@@ -37,15 +37,24 @@


			




	37
	37
	
		
    /// a digraph.


			




	38
	38
	
		
    ///


			




	39
	39
	
		
    /// A skeleton structure for representing directed paths in a


			




	40
	40
	
		
    /// digraph.


			




	
	41
	
		
    /// In a sense, a path can be treated as a list of arcs.


			




	
	42
	
		
    /// LEMON path types just store this list. As a consequence, they cannot


			




	
	43
	
		
    /// enumerate the nodes on the path directly and a zero length path


			




	
	44
	
		
    /// cannot store its source node.


			




	
	45
	
		
    ///


			




	
	46
	
		
    /// The arcs of a path should be stored in the order of their directions,


			




	
	47
	
		
    /// i.e. the target node of each arc should be the same as the source


			




	
	48
	
		
    /// node of the next arc. This consistency could be checked using


			




	
	49
	
		
    /// \ref checkPath().


			




	
	50
	
		
    /// The source and target nodes of a (consistent) path can be obtained


			




	
	51
	
		
    /// using \ref pathSource() and \ref pathTarget().


			




	
	52
	
		
    ///


			




	
	53
	
		
    /// A path can be constructed from another path of any type using the


			




	
	54
	
		
    /// copy constructor or the assignment operator.


			




	
	55
	
		
    ///


			




	41
	56
	
		
    /// \tparam GR The digraph type in which the path is.


			




	42
	
	
		
    ///


			




	43
	
	
		
    /// In a sense, the path can be treated as a list of arcs. The


			




	44
	
	
		
    /// lemon path type stores just this list. As a consequence it


			




	45
	
	
		
    /// cannot enumerate the nodes in the path and the zero length


			




	46
	
	
		
    /// paths cannot store the source.


			




	47
	
	
		
    ///


			




	48
	57
	
		
    template <typename GR>


			




	49
	58
	
		
    class Path {


			




	50
	59
	
		
    public:


			




	51
	60
	
		

			




	...
	...
	
		
@@ -58,41 +67,41 @@


			




	58
	67
	
		

			




	59
	68
	
		
      /// \brief Default constructor


			




	60
	69
	
		
      Path() {}


			




	61
	70
	
		

			




	62
	
	
		
      /// \brief Template constructor


			




	
	71
	
		
      /// \brief Template copy constructor


			




	63
	72
	
		
      template <typename CPath>


			




	64
	73
	
		
      Path(const CPath& cpath) {}


			




	65
	74
	
		

			




	66
	
	
		
      /// \brief Template assigment


			




	
	75
	
		
      /// \brief Template assigment operator


			




	67
	76
	
		
      template <typename CPath>


			




	68
	77
	
		
      Path& operator=(const CPath& cpath) {


			




	69
	78
	
		
        ignore_unused_variable_warning(cpath);


			




	70
	79
	
		
        return *this;


			




	71
	80
	
		
      }


			




	72
	81
	
		

			




	73
	
	
		
      /// Length of the path ie. the number of arcs in the path.


			




	
	82
	
		
      /// Length of the path, i.e. the number of arcs on the path.


			




	74
	83
	
		
      int length() const { return 0;}


			




	75
	84
	
		

			




	76
	85
	
		
      /// Returns whether the path is empty.


			




	77
	86
	
		
      bool empty() const { return true;}


			




	78
	87
	
		

			




	79
	88
	
		
      /// Resets the path to an empty path.


			




	80
	89
	
		
      void clear() {}


			




	81
	90
	
		

			




	82
	
	
		
      /// \brief LEMON style iterator for path arcs


			




	
	91
	
		
      /// \brief LEMON style iterator for enumerating the arcs of a path.


			




	83
	92
	
		
      ///


			




	84
	
	
		
      /// This class is used to iterate on the arcs of the paths.


			




	
	93
	
		
      /// LEMON style iterator class for enumerating the arcs of a path.


			




	85
	94
	
		
      class ArcIt {


			




	86
	95
	
		
      public:


			




	87
	96
	
		
        /// Default constructor


			




	88
	97
	
		
        ArcIt() {}


			




	89
	98
	
		
        /// Invalid constructor


			




	90
	99
	
		
        ArcIt(Invalid) {}


			




	91
	
	
		
        /// Constructor for first arc


			




	
	100
	
		
        /// Sets the iterator to the first arc of the given path


			




	92
	101
	
		
        ArcIt(const Path &) {}


			




	93
	102
	
		

			




	94
	
	
		
        /// Conversion to Arc


			




	
	103
	
		
        /// Conversion to \c Arc


			




	95
	104
	
		
        operator Arc() const { return INVALID; }


			




	96
	105
	
		

			




	97
	106
	
		
        /// Next arc


			




	98
	107
	
		
        ArcIt& operator++() {return *this;}


			




	...
	...
	
		
@@ -191,26 +200,20 @@


			




	191
	200
	
		

			




	192
	201
	
		
    /// \brief A skeleton structure for path dumpers.


			




	193
	202
	
		
    ///


			




	194
	203
	
		
    /// A skeleton structure for path dumpers. The path dumpers are


			




	195
	
	
		
    /// the generalization of the paths. The path dumpers can


			




	196
	
	
		
    /// enumerate the arcs of the path wheter in forward or in


			




	197
	
	
		
    /// backward order.  In most time these classes are not used


			




	198
	
	
		
    /// directly rather it used to assign a dumped class to a real


			




	199
	
	
		
    /// path type.


			




	
	204
	
		
    /// the generalization of the paths, they can enumerate the arcs


			




	
	205
	
		
    /// of the path either in forward or in backward order.


			




	
	206
	
		
    /// These classes are typically not used directly, they are rather


			




	
	207
	
		
    /// used to be assigned to a real path type.


			




	200
	208
	
		
    ///


			




	201
	209
	
		
    /// The main purpose of this concept is that the shortest path


			




	202
	
	
		
    /// algorithms can enumerate easily the arcs in reverse order.


			




	203
	
	
		
    /// If we would like to give back a real path from these


			




	204
	
	
		
    /// algorithms then we should create a temporarly path object. In


			




	205
	
	
		
    /// LEMON such algorithms gives back a path dumper what can


			




	206
	
	
		
    /// assigned to a real path and the dumpers can be implemented as


			




	
	210
	
		
    /// algorithms can enumerate the arcs easily in reverse order.


			




	
	211
	
		
    /// In LEMON, such algorithms give back a (reverse) path dumper that


			




	
	212
	
		
    /// can be assigned to a real path. The dumpers can be implemented as


			




	207
	213
	
		
    /// an adaptor class to the predecessor map.


			




	208
	214
	
		
    ///


			




	209
	215
	
		
    /// \tparam GR The digraph type in which the path is.


			




	210
	
	
		
    ///


			




	211
	
	
		
    /// The paths can be constructed from any path type by a


			




	212
	
	
		
    /// template constructor or a template assignment operator.


			




	213
	216
	
		
    template <typename GR>


			




	214
	217
	
		
    class PathDumper {


			




	215
	218
	
		
    public:


			




	216
	219
	
		

			




	...
	...
	
		
@@ -218,35 +221,34 @@


			




	218
	221
	
		
      typedef GR Digraph;


			




	219
	222
	
		
      /// Arc type of the underlying digraph.


			




	220
	223
	
		
      typedef typename Digraph::Arc Arc;


			




	221
	224
	
		

			




	222
	
	
		
      /// Length of the path ie. the number of arcs in the path.


			




	
	225
	
		
      /// Length of the path, i.e. the number of arcs on the path.


			




	223
	226
	
		
      int length() const { return 0;}


			




	224
	227
	
		

			




	225
	228
	
		
      /// Returns whether the path is empty.


			




	226
	229
	
		
      bool empty() const { return true;}


			




	227
	230
	
		

			




	228
	231
	
		
      /// \brief Forward or reverse dumping


			




	229
	232
	
		
      ///


			




	230
	
	
		
      /// If the RevPathTag is defined and true then reverse dumping


			




	231
	
	
		
      /// is provided in the path dumper. In this case instead of the


			




	232
	
	
		
      /// ArcIt the RevArcIt iterator should be implemented in the


			




	233
	
	
		
      /// dumper.


			




	
	233
	
		
      /// If this tag is defined to be \c True, then reverse dumping


			




	
	234
	
		
      /// is provided in the path dumper. In this case, \c RevArcIt


			




	
	235
	
		
      /// iterator should be implemented instead of \c ArcIt iterator.


			




	234
	236
	
		
      typedef False RevPathTag;


			




	235
	237
	
		

			




	236
	
	
		
      /// \brief LEMON style iterator for path arcs


			




	
	238
	
		
      /// \brief LEMON style iterator for enumerating the arcs of a path.


			




	237
	239
	
		
      ///


			




	238
	
	
		
      /// This class is used to iterate on the arcs of the paths.


			




	
	240
	
		
      /// LEMON style iterator class for enumerating the arcs of a path.


			




	239
	241
	
		
      class ArcIt {


			




	240
	242
	
		
      public:


			




	241
	243
	
		
        /// Default constructor


			




	242
	244
	
		
        ArcIt() {}


			




	243
	245
	
		
        /// Invalid constructor


			




	244
	246
	
		
        ArcIt(Invalid) {}


			




	245
	
	
		
        /// Constructor for first arc


			




	
	247
	
		
        /// Sets the iterator to the first arc of the given path


			




	246
	248
	
		
        ArcIt(const PathDumper&) {}


			




	247
	249
	
		

			




	248
	
	
		
        /// Conversion to Arc


			




	
	250
	
		
        /// Conversion to \c Arc


			




	249
	251
	
		
        operator Arc() const { return INVALID; }


			




	250
	252
	
		

			




	251
	253
	
		
        /// Next arc


			




	252
	254
	
		
        ArcIt& operator++() {return *this;}


			




	...
	...
	
		
@@ -259,22 +261,23 @@


			




	259
	261
	
		
        bool operator<(const ArcIt&) const {return false;}


			




	260
	262
	
		

			




	261
	263
	
		
      };


			




	262
	264
	
		

			




	263
	
	
		
      /// \brief LEMON style iterator for path arcs


			




	
	265
	
		
      /// \brief LEMON style iterator for enumerating the arcs of a path


			




	
	266
	
		
      /// in reverse direction.


			




	264
	267
	
		
      ///


			




	265
	
	
		
      /// This class is used to iterate on the arcs of the paths in


			




	266
	
	
		
      /// reverse direction.


			




	
	268
	
		
      /// LEMON style iterator class for enumerating the arcs of a path


			




	
	269
	
		
      /// in reverse direction.


			




	267
	270
	
		
      class RevArcIt {


			




	268
	271
	
		
      public:


			




	269
	272
	
		
        /// Default constructor


			




	270
	273
	
		
        RevArcIt() {}


			




	271
	274
	
		
        /// Invalid constructor


			




	272
	275
	
		
        RevArcIt(Invalid) {}


			




	273
	
	
		
        /// Constructor for first arc


			




	
	276
	
		
        /// Sets the iterator to the last arc of the given path


			




	274
	277
	
		
        RevArcIt(const PathDumper &) {}


			




	275
	278
	
		

			




	276
	
	
		
        /// Conversion to Arc


			




	
	279
	
		
        /// Conversion to \c Arc


			




	277
	280
	
		
        operator Arc() const { return INVALID; }


			




	278
	281
	
		

			




	279
	282
	
		
        /// Next arc


			




	280
	283
	
		
        RevArcIt& operator++() {return *this;}


			




        

    






    
    



    


    

     
    
0 comments (0 inline)