Changeset 2247:269a0dcee70b in lemon-0.x for lemon/concept/path.h
- Timestamp:
- 10/17/06 12:50:57 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2997
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/concept/path.h
r1993 r2247 38 38 //! 39 39 //! A skeleton structure for representing directed paths in a graph. 40 //! \param GRThe graph type in which the path is.40 //! \param _Graph The graph type in which the path is. 41 41 //! 42 42 //! In a sense, the path can be treated as a graph, for it has \c NodeIt 43 43 //! and \c EdgeIt with the same usage. These types converts to the \c Node 44 44 //! and \c Edge of the original graph. 45 template<typename GR>45 template<typename _Graph> 46 46 class Path { 47 47 public: 48 48 49 49 /// Type of the underlying graph. 50 typedef /*typename*/ GRGraph;50 typedef _Graph Graph; 51 51 /// Edge type of the underlying graph. 52 typedef typename Graph::Edge GraphEdge;52 typedef typename Graph::Edge Edge; 53 53 /// Node type of the underlying graph. 54 typedef typename Graph::Node GraphNode; 54 typedef typename Graph::Node Node; 55 55 56 class NodeIt; 56 57 class EdgeIt; … … 62 63 } 63 64 64 /// Length of the path .65 /// Length of the path ie. the number of edges in the path. 65 66 int length() const {return 0;} 67 66 68 /// Returns whether the path is empty. 67 69 bool empty() const { return true;} … … 74 76 /// Starting point of the path. 75 77 /// Returns INVALID if the path is empty. 76 GraphNode/*It*/target() const {return INVALID;}78 Node target() const {return INVALID;} 77 79 /// \brief End point of the path. 78 80 /// 79 81 /// End point of the path. 80 82 /// Returns INVALID if the path is empty. 81 GraphNode/*It*/ source() const {return INVALID;} 82 83 /// \brief First NodeIt/EdgeIt. 84 /// 85 /// Initializes node or edge iterator to point to the first 86 /// node or edge. 87 template<typename It> 88 It& first(It &i) const { return i=It(*this); } 83 Node source() const {return INVALID;} 89 84 90 85 /// \brief The target of an edge. … … 100 95 NodeIt source(const EdgeIt&) const {return INVALID;} 101 96 102 103 /* Iterator classes */ 104 105 /** 106 * \brief Iterator class to iterate on the edges of the paths 107 * 108 * This class is used to iterate on the edges of the paths 109 * 110 * Of course it converts to Graph::Edge 111 * 112 */ 97 /// \brief Iterator class to iterate on the nodes of the paths 98 /// 99 /// This class is used to iterate on the nodes of the paths 100 /// 101 /// Of course it converts to Graph::Node. 102 class NodeIt { 103 public: 104 /// Default constructor 105 NodeIt() {} 106 /// Invalid constructor 107 NodeIt(Invalid) {} 108 /// Constructor with starting point 109 NodeIt(const Path &) {} 110 111 ///Conversion to Graph::Node 112 operator Node() const { return INVALID; } 113 /// Next node 114 NodeIt& operator++() {return *this;} 115 116 /// Comparison operator 117 bool operator==(const NodeIt&) const {return true;} 118 /// Comparison operator 119 bool operator!=(const NodeIt&) const {return true;} 120 /// Comparison operator 121 bool operator<(const NodeIt&) const {return false;} 122 123 }; 124 125 /// \brief Iterator class to iterate on the edges of the paths 126 /// 127 /// This class is used to iterate on the edges of the paths 128 /// 129 /// Of course it converts to Graph::Edge 113 130 class EdgeIt { 114 131 public: … … 120 137 EdgeIt(const Path &) {} 121 138 122 operator GraphEdge () const {}139 operator Edge() const { return INVALID; } 123 140 124 141 /// Next edge … … 129 146 /// Comparison operator 130 147 bool operator!=(const EdgeIt&) const {return true;} 131 // /// Comparison operator 132 // /// \todo It is not clear what is the "natural" ordering. 133 // bool operator<(const EdgeIt& e) const {} 134 135 }; 136 137 /** 138 * \brief Iterator class to iterate on the nodes of the paths 139 * 140 * This class is used to iterate on the nodes of the paths 141 * 142 * Of course it converts to Graph::Node. 143 * 144 */ 145 class NodeIt { 146 public: 147 /// Default constructor 148 NodeIt() {} 149 /// Invalid constructor 150 NodeIt(Invalid) {} 151 /// Constructor with starting point 152 NodeIt(const Path &) {} 153 154 ///Conversion to Graph::Node 155 operator const GraphNode& () const {} 156 /// Next node 157 NodeIt& operator++() {return *this;} 158 159 /// Comparison operator 160 bool operator==(const NodeIt&) const {return true;} 161 /// Comparison operator 162 bool operator!=(const NodeIt&) const {return true;} 163 // /// Comparison operator 164 // /// \todo It is not clear what is the "natural" ordering. 165 // bool operator<(const NodeIt& e) const {} 166 167 }; 148 /// Comparison operator 149 bool operator<(const EdgeIt&) const {return false;} 150 151 }; 152 168 153 169 154 friend class Builder; 170 155 171 /** 172 * \brief Class to build paths 173 * 174 * This class is used to fill a path with edges. 175 * 176 * You can push new edges to the front and to the back of the path in 177 * arbitrary order then you should commit these changes to the graph. 178 * 179 * While the builder is active (after the first modifying 180 * operation and until the call of \ref commit()) the 181 * underlining Path is in a "transitional" state (operations on 182 * it have undefined result). 183 */ 156 /// \brief Class to build paths 157 /// 158 /// This class is used to fill a path with edges. 159 /// 160 /// You can push new edges to the front and to the back of the path in 161 /// arbitrary order then you should commit these changes to the graph. 162 /// 163 /// While the builder is active (after the first modifying 164 /// operation and until the call of \ref commit()) the 165 /// underlining Path is in a "transitional" state (operations on 166 /// it have undefined result). 184 167 class Builder { 185 168 public: 186 169 187 Path &P; 188 189 ///\param _p the path you want to fill in. 170 /// Constructor 171 172 /// Constructor 173 /// \param _path the path you want to fill in. 190 174 /// 191 175 192 Builder(Path &_p ) : P(_p) {}176 Builder(Path &_path) { ignore_unused_variable_warning(_path); } 193 177 194 178 /// Sets the starting node of the path. … … 200 184 /// \sa pushFront() 201 185 /// \sa pushBack() 202 void setStartNode(const GraphNode &) {}186 void setStartNode(const Node &) {} 203 187 204 188 ///Push a new edge to the front of the path … … 207 191 ///If the path is empty, you \em must call \ref setStartNode() before 208 192 ///the first use of \ref pushFront(). 209 void pushFront(const GraphEdge&) {}193 void pushFront(const Edge&) {} 210 194 211 195 ///Push a new edge to the back of the path … … 214 198 ///If the path is empty, you \em must call \ref setStartNode() before 215 199 ///the first use of \ref pushBack(). 216 void pushBack(const GraphEdge&) {}200 void pushBack(const Edge&) {} 217 201 218 202 ///Commit the changes to the path. 203 204 ///Commit the changes to the path. 205 /// 219 206 void commit() {} 220 207 … … 232 219 void reserveBack(size_t) {} 233 220 }; 221 222 template <typename _Path> 223 struct Constraints { 224 void constraints() { 225 typedef typename _Path::Node Node; 226 typedef typename _Path::NodeIt NodeIt; 227 typedef typename Graph::Node GraphNode; 228 229 typedef typename _Path::Edge Edge; 230 typedef typename _Path::EdgeIt EdgeIt; 231 typedef typename Graph::Edge GraphEdge; 232 233 typedef typename _Path::Builder Builder; 234 235 path = _Path(graph); 236 237 bool b = cpath.empty(); 238 int l = cpath.length(); 239 240 Node gn; 241 Edge ge; 242 gn = cpath.source(); 243 gn = cpath.target(); 244 245 NodeIt nit; 246 EdgeIt eit(INVALID); 247 nit = path.source(eit); 248 nit = path.target(eit); 249 250 nit = NodeIt(); 251 nit = NodeIt(cpath); 252 nit = INVALID; 253 gn = nit; 254 ++nit; 255 b = nit == nit; 256 b = nit != nit; 257 b = nit < nit; 258 259 eit = EdgeIt(); 260 eit = EdgeIt(cpath); 261 eit = INVALID; 262 ge = eit; 263 ++eit; 264 b = eit == eit; 265 b = eit != eit; 266 b = eit < eit; 267 268 size_t st = 0; 269 270 Builder builder(path); 271 builder.setStartNode(gn); 272 builder.pushFront(ge); 273 builder.pushBack(ge); 274 builder.commit(); 275 builder.reserveFront(st); 276 builder.reserveBack(st); 277 278 ignore_unused_variable_warning(l); 279 ignore_unused_variable_warning(b); 280 } 281 282 const Graph& graph; 283 const _Path& cpath; 284 _Path& path; 285 }; 286 234 287 }; 235 288
Note: See TracChangeset
for help on using the changeset viewer.