1.1 --- a/lemon/concepts/path.h Sun Oct 04 10:15:32 2009 +0200
1.2 +++ b/lemon/concepts/path.h Wed Dec 09 11:14:06 2009 +0100
1.3 @@ -18,7 +18,7 @@
1.4
1.5 ///\ingroup concept
1.6 ///\file
1.7 -///\brief Classes for representing paths in digraphs.
1.8 +///\brief The concept of paths
1.9 ///
1.10
1.11 #ifndef LEMON_CONCEPTS_PATH_H
1.12 @@ -38,13 +38,22 @@
1.13 ///
1.14 /// A skeleton structure for representing directed paths in a
1.15 /// digraph.
1.16 + /// In a sense, a path can be treated as a list of arcs.
1.17 + /// LEMON path types just store this list. As a consequence, they cannot
1.18 + /// enumerate the nodes on the path directly and a zero length path
1.19 + /// cannot store its source node.
1.20 + ///
1.21 + /// The arcs of a path should be stored in the order of their directions,
1.22 + /// i.e. the target node of each arc should be the same as the source
1.23 + /// node of the next arc. This consistency could be checked using
1.24 + /// \ref checkPath().
1.25 + /// The source and target nodes of a (consistent) path can be obtained
1.26 + /// using \ref pathSource() and \ref pathTarget().
1.27 + ///
1.28 + /// A path can be constructed from another path of any type using the
1.29 + /// copy constructor or the assignment operator.
1.30 + ///
1.31 /// \tparam GR The digraph type in which the path is.
1.32 - ///
1.33 - /// In a sense, the path can be treated as a list of arcs. The
1.34 - /// lemon path type stores just this list. As a consequence it
1.35 - /// cannot enumerate the nodes in the path and the zero length
1.36 - /// paths cannot store the source.
1.37 - ///
1.38 template <typename GR>
1.39 class Path {
1.40 public:
1.41 @@ -59,18 +68,18 @@
1.42 /// \brief Default constructor
1.43 Path() {}
1.44
1.45 - /// \brief Template constructor
1.46 + /// \brief Template copy constructor
1.47 template <typename CPath>
1.48 Path(const CPath& cpath) {}
1.49
1.50 - /// \brief Template assigment
1.51 + /// \brief Template assigment operator
1.52 template <typename CPath>
1.53 Path& operator=(const CPath& cpath) {
1.54 ignore_unused_variable_warning(cpath);
1.55 return *this;
1.56 }
1.57
1.58 - /// Length of the path ie. the number of arcs in the path.
1.59 + /// Length of the path, i.e. the number of arcs on the path.
1.60 int length() const { return 0;}
1.61
1.62 /// Returns whether the path is empty.
1.63 @@ -79,19 +88,19 @@
1.64 /// Resets the path to an empty path.
1.65 void clear() {}
1.66
1.67 - /// \brief LEMON style iterator for path arcs
1.68 + /// \brief LEMON style iterator for enumerating the arcs of a path.
1.69 ///
1.70 - /// This class is used to iterate on the arcs of the paths.
1.71 + /// LEMON style iterator class for enumerating the arcs of a path.
1.72 class ArcIt {
1.73 public:
1.74 /// Default constructor
1.75 ArcIt() {}
1.76 /// Invalid constructor
1.77 ArcIt(Invalid) {}
1.78 - /// Constructor for first arc
1.79 + /// Sets the iterator to the first arc of the given path
1.80 ArcIt(const Path &) {}
1.81
1.82 - /// Conversion to Arc
1.83 + /// Conversion to \c Arc
1.84 operator Arc() const { return INVALID; }
1.85
1.86 /// Next arc
1.87 @@ -192,24 +201,18 @@
1.88 /// \brief A skeleton structure for path dumpers.
1.89 ///
1.90 /// A skeleton structure for path dumpers. The path dumpers are
1.91 - /// the generalization of the paths. The path dumpers can
1.92 - /// enumerate the arcs of the path wheter in forward or in
1.93 - /// backward order. In most time these classes are not used
1.94 - /// directly rather it used to assign a dumped class to a real
1.95 - /// path type.
1.96 + /// the generalization of the paths, they can enumerate the arcs
1.97 + /// of the path either in forward or in backward order.
1.98 + /// These classes are typically not used directly, they are rather
1.99 + /// used to be assigned to a real path type.
1.100 ///
1.101 /// The main purpose of this concept is that the shortest path
1.102 - /// algorithms can enumerate easily the arcs in reverse order.
1.103 - /// If we would like to give back a real path from these
1.104 - /// algorithms then we should create a temporarly path object. In
1.105 - /// LEMON such algorithms gives back a path dumper what can
1.106 - /// assigned to a real path and the dumpers can be implemented as
1.107 + /// algorithms can enumerate the arcs easily in reverse order.
1.108 + /// In LEMON, such algorithms give back a (reverse) path dumper that
1.109 + /// can be assigned to a real path. The dumpers can be implemented as
1.110 /// an adaptor class to the predecessor map.
1.111 ///
1.112 /// \tparam GR The digraph type in which the path is.
1.113 - ///
1.114 - /// The paths can be constructed from any path type by a
1.115 - /// template constructor or a template assignment operator.
1.116 template <typename GR>
1.117 class PathDumper {
1.118 public:
1.119 @@ -219,7 +222,7 @@
1.120 /// Arc type of the underlying digraph.
1.121 typedef typename Digraph::Arc Arc;
1.122
1.123 - /// Length of the path ie. the number of arcs in the path.
1.124 + /// Length of the path, i.e. the number of arcs on the path.
1.125 int length() const { return 0;}
1.126
1.127 /// Returns whether the path is empty.
1.128 @@ -227,25 +230,24 @@
1.129
1.130 /// \brief Forward or reverse dumping
1.131 ///
1.132 - /// If the RevPathTag is defined and true then reverse dumping
1.133 - /// is provided in the path dumper. In this case instead of the
1.134 - /// ArcIt the RevArcIt iterator should be implemented in the
1.135 - /// dumper.
1.136 + /// If this tag is defined to be \c True, then reverse dumping
1.137 + /// is provided in the path dumper. In this case, \c RevArcIt
1.138 + /// iterator should be implemented instead of \c ArcIt iterator.
1.139 typedef False RevPathTag;
1.140
1.141 - /// \brief LEMON style iterator for path arcs
1.142 + /// \brief LEMON style iterator for enumerating the arcs of a path.
1.143 ///
1.144 - /// This class is used to iterate on the arcs of the paths.
1.145 + /// LEMON style iterator class for enumerating the arcs of a path.
1.146 class ArcIt {
1.147 public:
1.148 /// Default constructor
1.149 ArcIt() {}
1.150 /// Invalid constructor
1.151 ArcIt(Invalid) {}
1.152 - /// Constructor for first arc
1.153 + /// Sets the iterator to the first arc of the given path
1.154 ArcIt(const PathDumper&) {}
1.155
1.156 - /// Conversion to Arc
1.157 + /// Conversion to \c Arc
1.158 operator Arc() const { return INVALID; }
1.159
1.160 /// Next arc
1.161 @@ -260,20 +262,21 @@
1.162
1.163 };
1.164
1.165 - /// \brief LEMON style iterator for path arcs
1.166 + /// \brief LEMON style iterator for enumerating the arcs of a path
1.167 + /// in reverse direction.
1.168 ///
1.169 - /// This class is used to iterate on the arcs of the paths in
1.170 - /// reverse direction.
1.171 + /// LEMON style iterator class for enumerating the arcs of a path
1.172 + /// in reverse direction.
1.173 class RevArcIt {
1.174 public:
1.175 /// Default constructor
1.176 RevArcIt() {}
1.177 /// Invalid constructor
1.178 RevArcIt(Invalid) {}
1.179 - /// Constructor for first arc
1.180 + /// Sets the iterator to the last arc of the given path
1.181 RevArcIt(const PathDumper &) {}
1.182
1.183 - /// Conversion to Arc
1.184 + /// Conversion to \c Arc
1.185 operator Arc() const { return INVALID; }
1.186
1.187 /// Next arc