Changeset 2247:269a0dcee70b in lemon-0.x for lemon
- Timestamp:
- 10/17/06 12:50:57 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2997
- Location:
- lemon
- Files:
-
- 2 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 -
lemon/path.h
r2084 r2247 22 22 ///\brief Classes for representing paths in graphs. 23 23 /// 24 ///\todo Iterators have obsolete style25 24 26 25 #ifndef LEMON_PATH_H 27 26 #define LEMON_PATH_H 28 27 29 #include <deque>30 28 #include <vector> 31 29 #include <algorithm> 32 30 31 #include <lemon/error.h> 33 32 #include <lemon/bits/invalid.h> 34 33 … … 43 42 //! A structure for representing directed path in a graph. 44 43 //! \param Graph The graph type in which the path is. 45 //! \param DM DebugMode, defaults to DefaultDebugMode.46 44 //! 47 45 //! In a sense, the path can be treated as a graph, for is has \c NodeIt … … 51 49 //! \todo Thoroughfully check all the range and consistency tests. 52 50 template<typename Graph> 53 class DirPath {51 class Path { 54 52 public: 55 53 /// Edge type of the underlying graph. 56 typedef typename Graph::Edge GraphEdge;54 typedef typename Graph::Edge Edge; 57 55 /// Node type of the underlying graph. 58 typedef typename Graph::Node GraphNode; 56 typedef typename Graph::Node Node; 57 59 58 class NodeIt; 60 59 class EdgeIt; 61 60 62 protected: 63 const Graph *gr; 64 typedef std::vector<GraphEdge> Container; 65 Container edges; 61 struct PathError : public LogicError { 62 virtual const char* what() const throw() { 63 return "lemon::PathError"; 64 } 65 }; 66 66 67 67 public: 68 68 69 /// \brief Constructor 70 /// 71 /// Constructor 69 72 /// \param _G The graph in which the path is. 70 /// 71 DirPath(const Graph &_G) : gr(&_G) {} 72 73 Path(const Graph &_graph) : graph(&_graph), start(INVALID) {} 74 73 75 /// \brief Subpath constructor. 74 76 /// 75 77 /// Subpath defined by two nodes. 76 78 /// \warning It is an error if the two edges are not in order! 77 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) { 78 gr = P.gr; 79 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 79 Path(const Path &other, const NodeIt &a, const NodeIt &b) { 80 graph = other.graph; 81 start = a; 82 edges.insert(edges.end(), 83 other.edges.begin() + a.id, other.edges.begin() + b.id); 80 84 } 81 85 … … 84 88 /// Subpath defined by two edges. Contains edges in [a,b) 85 89 /// \warning It is an error if the two edges are not in order! 86 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) { 87 gr = P.gr; 88 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx); 89 } 90 91 /// Length of the path. 90 Path(const Path &other, const EdgeIt &a, const EdgeIt &b) { 91 graph = other.graph; 92 start = graph->source(a); 93 edges.insert(edges.end(), 94 other.edges.begin() + a.id, other.edges.begin() + b.id); 95 } 96 97 /// \brief Length of the path. 98 /// 99 /// The number of the edges in the path. It can be zero if the 100 /// path has only one node or it is empty. 92 101 int length() const { return edges.size(); } 93 /// Returns whether the path is empty. 94 bool empty() const { return edges.empty(); } 95 102 103 /// \brief Returns whether the path is empty. 104 /// 105 /// Returns true when the path does not contain neither edge nor 106 /// node. 107 bool empty() const { return start == INVALID; } 108 109 /// \brief Resets the path to an empty path. 110 /// 96 111 /// Resets the path to an empty path. 97 void clear() { edges.clear(); }112 void clear() { edges.clear(); start = INVALID; } 98 113 99 114 /// \brief Starting point of the path. … … 101 116 /// Starting point of the path. 102 117 /// Returns INVALID if the path is empty. 103 GraphNode source() const {104 return empty() ? INVALID : gr->source(edges[0]);118 Node source() const { 119 return start; 105 120 } 106 121 /// \brief End point of the path. … … 108 123 /// End point of the path. 109 124 /// Returns INVALID if the path is empty. 110 GraphNode target() const { 111 return empty() ? INVALID : gr->target(edges[length()-1]); 112 } 113 114 /// \brief Initializes node or edge iterator to point to the first 115 /// node or edge. 116 /// 117 /// \sa nth 118 template<typename It> 119 It& first(It &i) const { return i=It(*this); } 120 121 /// \brief Initializes node iterator to point to the node of a given index. 122 NodeIt& nth(NodeIt &i, int n) const { 123 return i=NodeIt(*this, n); 124 } 125 126 /// \brief Initializes edge iterator to point to the edge of a given index. 127 EdgeIt& nth(EdgeIt &i, int n) const { 128 return i=EdgeIt(*this, n); 125 Node target() const { 126 return length() == 0 ? start : graph->target(edges[length()-1]); 127 } 128 129 /// \brief Gives back a node iterator to point to the node of a 130 /// given index. 131 /// 132 /// Gives back a node iterator to point to the node of a given 133 /// index. 134 /// \pre n should less or equal to \c length() 135 NodeIt nthNode(int n) const { 136 return NodeIt(*this, n); 137 } 138 139 /// \brief Gives back an edge iterator to point to the edge of a 140 /// given index. 141 /// 142 /// Gives back an edge iterator to point to the node of a given 143 /// index. 144 /// \pre n should less than \c length() 145 EdgeIt nthEdge(int n) const { 146 return EdgeIt(*this, n); 147 } 148 149 /// \brief Returns node iterator pointing to the source node of the 150 /// given edge iterator. 151 /// 152 /// Returns node iterator pointing to the source node of the given 153 /// edge iterator. 154 NodeIt source(const EdgeIt& e) const { 155 return NodeIt(*this, e.id); 129 156 } 130 157 131 158 /// \brief Returns node iterator pointing to the target node of the 132 159 /// given edge iterator. 160 /// 161 /// Returns node iterator pointing to the target node of the given 162 /// edge iterator. 133 163 NodeIt target(const EdgeIt& e) const { 134 return NodeIt(*this, e.idx+1); 135 } 136 137 /// \brief Returns node iterator pointing to the source node of the 138 /// given edge iterator. 139 NodeIt source(const EdgeIt& e) const { 140 return NodeIt(*this, e.idx); 141 } 142 143 144 /* Iterator classes */ 145 146 /** 147 * \brief Iterator class to iterate on the edges of the paths 148 * 149 * This class is used to iterate on the edges of the paths 150 * 151 * Of course it converts to Graph::Edge 152 * 153 */ 164 return NodeIt(*this, e.id + 1); 165 } 166 167 168 /// \brief Iterator class to iterate on the nodes of the paths 169 /// 170 /// This class is used to iterate on the nodes of the paths 171 /// 172 /// Of course it converts to Graph::Node 173 class NodeIt { 174 friend class Path; 175 public: 176 177 /// \brief Default constructor 178 /// 179 /// Default constructor 180 NodeIt() {} 181 182 /// \brief Invalid constructor 183 /// 184 /// Invalid constructor 185 NodeIt(Invalid) : id(-1), path(0) {} 186 187 /// \brief Constructor with starting point 188 /// 189 /// Constructor with starting point 190 NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 191 if (id > path->length()) id = -1; 192 } 193 194 /// \brief Conversion to Graph::Node 195 /// 196 /// Conversion to Graph::Node 197 operator Node() const { 198 if (id > 0) { 199 return path->graph->target(path->edges[id - 1]); 200 } else if (id == 0) { 201 return path->start; 202 } else { 203 return INVALID; 204 } 205 } 206 207 /// \brief Steps to the next node 208 /// 209 /// Steps to the next node 210 NodeIt& operator++() { 211 ++id; 212 if (id > path->length()) id = -1; 213 return *this; 214 } 215 216 /// \brief Comparison operator 217 /// 218 /// Comparison operator 219 bool operator==(const NodeIt& n) const { return id == n.id; } 220 221 /// \brief Comparison operator 222 /// 223 /// Comparison operator 224 bool operator!=(const NodeIt& n) const { return id != n.id; } 225 226 /// \brief Comparison operator 227 /// 228 /// Comparison operator 229 bool operator<(const NodeIt& n) const { return id < n.id; } 230 231 private: 232 int id; 233 const Path *path; 234 }; 235 236 /// \brief Iterator class to iterate on the edges of the paths 237 /// 238 /// This class is used to iterate on the edges of the paths 239 /// Of course it converts to Graph::Edge 154 240 class EdgeIt { 155 friend class DirPath; 156 157 int idx; 158 const DirPath *p; 241 friend class Path; 159 242 public: 243 244 /// \brief Default constructor 245 /// 160 246 /// Default constructor 161 247 EdgeIt() {} 248 249 /// \brief Invalid constructor 250 /// 162 251 /// Invalid constructor 163 EdgeIt(Invalid) : idx(-1), p(0) {} 252 EdgeIt(Invalid) : id(-1), path(0) {} 253 254 /// \brief Constructor with starting point 255 /// 164 256 /// Constructor with starting point 165 EdgeIt(const DirPath &_p, int _idx = 0) : 166 idx(_idx), p(&_p) { validate(); } 167 168 ///Validity check 169 bool valid() const { return idx!=-1; } 170 171 ///Conversion to Graph::Edge 172 operator GraphEdge () const { 173 return valid() ? p->edges[idx] : INVALID; 174 } 175 176 /// Next edge 177 EdgeIt& operator++() { ++idx; validate(); return *this; } 178 179 /// Comparison operator 180 bool operator==(const EdgeIt& e) const { return idx==e.idx; } 181 /// Comparison operator 182 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } 183 /// Comparison operator 184 bool operator<(const EdgeIt& e) const { return idx<e.idx; } 257 EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 258 if (id >= path->length()) id = -1; 259 } 260 261 /// \brief Conversion to Graph::Edge 262 /// 263 /// Conversion to Graph::Edge 264 operator Edge() const { 265 return id != -1 ? path->edges[id] : INVALID; 266 } 267 268 /// \brief Steps to the next edge 269 /// 270 /// Steps to the next edge 271 EdgeIt& operator++() { 272 ++id; 273 if (id >= path->length()) id = -1; 274 return *this; 275 } 276 277 /// \brief Comparison operator 278 /// 279 /// Comparison operator 280 bool operator==(const EdgeIt& e) const { return id == e.id; } 281 282 /// \brief Comparison operator 283 /// 284 /// Comparison operator 285 bool operator!=(const EdgeIt& e) const { return id != e.id; } 286 287 /// \brief Comparison operator 288 /// 289 /// Comparison operator 290 bool operator<(const EdgeIt& e) const { return id < e.id; } 185 291 186 292 private: 187 void validate() { if(idx >= p->length() ) idx=-1; } 293 294 int id; 295 const Path *path; 188 296 }; 189 297 190 /** 191 * \brief Iterator class to iterate on the nodes of the paths 192 * 193 * This class is used to iterate on the nodes of the paths 194 * 195 * Of course it converts to Graph::Node 196 * 197 */ 198 class NodeIt { 199 friend class DirPath; 200 201 int idx; 202 const DirPath *p; 298 protected: 299 300 const Graph *graph; 301 302 typedef std::vector<Edge> Container; 303 Container edges; 304 Node start; 305 306 public: 307 308 friend class Builder; 309 310 /// \brief Class to build paths 311 /// 312 /// This class is used to fill a path with edges. 313 /// 314 /// You can push new edges to the front and to the back of the 315 /// path in arbitrary order then you should commit these changes 316 /// to the graph. 317 /// 318 /// Fundamentally, for most "Paths" (classes fulfilling the 319 /// PathConcept) while the builder is active (after the first 320 /// modifying operation and until the commit()) the original Path 321 /// is in a "transitional" state (operations on it have undefined 322 /// result). But in the case of Path the original path remains 323 /// unchanged until the commit. However we don't recomend that you 324 /// use this feature. 325 class Builder { 203 326 public: 204 /// Default constructor 205 NodeIt() {} 206 /// Invalid constructor 207 NodeIt(Invalid) : idx(-1), p(0) {} 208 /// Constructor with starting point 209 NodeIt(const DirPath &_p, int _idx = 0) : 210 idx(_idx), p(&_p) { validate(); } 211 212 ///Validity check 213 bool valid() const { return idx!=-1; } 214 215 ///Conversion to Graph::Node 216 operator GraphNode () const { 217 if(idx >= p->length()) 218 return p->target(); 219 else if(idx >= 0) 220 return p->gr->source(p->edges[idx]); 221 else 222 return INVALID; 223 } 224 /// Next node 225 NodeIt& operator++() { ++idx; validate(); return *this; } 226 227 /// Comparison operator 228 bool operator==(const NodeIt& e) const { return idx==e.idx; } 229 /// Comparison operator 230 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } 231 /// Comparison operator 232 bool operator<(const NodeIt& e) const { return idx<e.idx; } 233 234 private: 235 void validate() { if(idx > p->length() ) idx=-1; } 236 }; 237 238 friend class Builder; 239 240 /** 241 * \brief Class to build paths 242 * 243 * This class is used to fill a path with edges. 244 * 245 * You can push new edges to the front and to the back of the path in 246 * arbitrary order then you should commit these changes to the graph. 247 * 248 * Fundamentally, for most "Paths" (classes fulfilling the 249 * PathConcept) while the builder is active (after the first modifying 250 * operation and until the commit()) the original Path is in a 251 * "transitional" state (operations on it have undefined result). But 252 * in the case of DirPath the original path remains unchanged until the 253 * commit. However we don't recomend that you use this feature. 254 */ 255 class Builder { 256 DirPath &P; 257 Container front, back; 258 259 public: 260 ///\param _p the path you want to fill in. 261 /// 262 Builder(DirPath &_p) : P(_p) {} 263 264 /// Sets the starting node of the path. 265 327 /// \brief Constructor 328 /// 329 /// Constructor 330 /// \param _path the path you want to fill in. 331 Builder(Path &_path) : path(_path), start(INVALID) {} 332 333 /// \brief Destructor 334 /// 335 /// Destructor 336 ~Builder() { 337 LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 338 PathError()); 339 } 340 341 /// \brief Sets the starting node of the path. 342 /// 266 343 /// Sets the starting node of the path. Edge added to the path 267 /// afterwards have to be incident to this node. 268 /// It should be called if and only if 269 /// the path is empty and before any call to 270 /// \ref pushFront() or \ref pushBack() 271 void setStartNode(const GraphNode &) {} 272 273 ///Push a new edge to the front of the path 274 275 ///Push a new edge to the front of the path. 276 ///\sa setStartNode 277 void pushFront(const GraphEdge& e) { 344 /// afterwards have to be incident to this node. It should be 345 /// called if and only if the path is empty and before any call 346 /// to \ref pushFront() or \ref pushBack() 347 void setStartNode(const Node &_start) { 348 LEMON_ASSERT(path.empty() && start == INVALID, PathError()); 349 start = _start; 350 } 351 352 /// \brief Push a new edge to the front of the path 353 /// 354 /// Push a new edge to the front of the path. 355 /// \sa setStartNode 356 void pushFront(const Edge& e) { 357 LEMON_ASSERT(front.empty() || 358 (path.graph->source(front.back()) == 359 path.graph->target(e)), PathError()); 360 LEMON_ASSERT(path.empty() || 361 (path.source() == path.graph->target(e)), PathError()); 362 LEMON_ASSERT(!path.empty() || !front.empty() || 363 (start == path.graph->target(e)), PathError()); 278 364 front.push_back(e); 279 365 } 280 366 281 ///Push a new edge to the back of the path 282 283 ///Push a new edge to the back of the path. 284 ///\sa setStartNode 285 void pushBack(const GraphEdge& e) { 367 /// \brief Push a new edge to the back of the path 368 /// 369 /// Push a new edge to the back of the path. 370 /// \sa setStartNode 371 void pushBack(const Edge& e) { 372 LEMON_ASSERT(back.empty() || 373 (path.graph->target(back.back()) == 374 path.graph->source(e)), PathError()); 375 LEMON_ASSERT(path.empty() || 376 (path.target() == path.graph->source(e)), PathError()); 377 LEMON_ASSERT(!path.empty() || !back.empty() || 378 (start == path.graph->source(e)), PathError()); 286 379 back.push_back(e); 287 380 } 288 381 289 ///Commit the changes to the path. 382 /// \brief Commit the changes to the path. 383 /// 384 /// Commit the changes to the path. 290 385 void commit() { 291 if( !front.empty() || !back.empty() ) {386 if( !front.empty() || !back.empty() || start != INVALID) { 292 387 Container tmp; 293 tmp.reserve(front.size() +back.size()+P.length());388 tmp.reserve(front.size() + back.size() + path.length()); 294 389 tmp.insert(tmp.end(), front.rbegin(), front.rend()); 295 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());390 tmp.insert(tmp.end(), path.edges.begin(), path.edges.end()); 296 391 tmp.insert(tmp.end(), back.begin(), back.end()); 297 P.edges.swap(tmp); 392 path.edges.swap(tmp); 393 if (!front.empty()) { 394 path.start = path.graph->source(front.back()); 395 } else { 396 path.start = start; 397 } 398 start = INVALID; 298 399 front.clear(); 299 400 back.clear(); … … 301 402 } 302 403 303 /// Reserve storage for the builder in advance.304 305 /// If you know a reasonable upper bound of the number of the edges306 /// to add to the front, using this function you can speed up the building.307 404 /// \brief Reserve storage for the builder in advance. 405 /// 406 /// If you know a reasonable upper bound of the number of the 407 /// edges to add to the front, using this function you can speed 408 /// up the building. 308 409 void reserveFront(size_t r) {front.reserve(r);} 309 410 310 /// Reserve storage for the builder in advance.311 312 /// If you know a reasonable upper bound of the number of the edges313 /// to add to the back, using this function you can speed up the building.314 411 /// \brief Reserve storage for the builder in advance. 412 /// 413 /// If you know a reasonable upper bound of the number of the 414 /// edges to add to the back, using this function you can speed 415 /// up the building. 315 416 void reserveBack(size_t r) {back.reserve(r);} 316 417 317 418 private: 318 bool empty() { 319 return front.empty() && back.empty() && P.empty(); 320 } 321 322 GraphNode source() const { 323 if( ! front.empty() ) 324 return P.gr->source(front[front.size()-1]); 325 else if( ! P.empty() ) 326 return P.gr->source(P.edges[0]); 327 else if( ! back.empty() ) 328 return P.gr->source(back[0]); 329 else 330 return INVALID; 331 } 332 GraphNode target() const { 333 if( ! back.empty() ) 334 return P.gr->target(back[back.size()-1]); 335 else if( ! P.empty() ) 336 return P.gr->target(P.edges[P.length()-1]); 337 else if( ! front.empty() ) 338 return P.gr->target(front[0]); 339 else 340 return INVALID; 341 } 419 420 Path &path; 421 Container front, back; 422 Node start; 342 423 343 424 }; … … 345 426 }; 346 427 347 348 349 350 351 352 353 354 355 356 /**********************************************************************/357 358 359 //! \brief A structure for representing undirected path in a graph.360 //!361 //! A structure for representing undirected path in a graph. Ie. this is362 //! a path in a \e directed graph but the edges should not be directed363 //! forward.364 //!365 //! \param Graph The graph type in which the path is.366 //! \param DM DebugMode, defaults to DefaultDebugMode.367 //!368 //! In a sense, the path can be treated as a graph, for is has \c NodeIt369 //! and \c EdgeIt with the same usage. These types converts to the \c Node370 //! and \c Edge of the original graph.371 //!372 //! \todo Thoroughfully check all the range and consistency tests.373 /// \todo May we need just path for undirected graph instead of this.374 template<typename Graph>375 class UPath {376 public:377 /// Edge type of the underlying graph.378 typedef typename Graph::Edge GraphEdge;379 /// Node type of the underlying graph.380 typedef typename Graph::Node GraphNode;381 class NodeIt;382 class EdgeIt;383 384 protected:385 const Graph *gr;386 typedef std::vector<GraphEdge> Container;387 Container edges;388 389 public:390 391 /// \param _G The graph in which the path is.392 ///393 UPath(const Graph &_G) : gr(&_G) {}394 395 /// \brief Subpath constructor.396 ///397 /// Subpath defined by two nodes.398 /// \warning It is an error if the two edges are not in order!399 UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {400 gr = P.gr;401 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);402 }403 404 /// \brief Subpath constructor.405 ///406 /// Subpath defined by two edges. Contains edges in [a,b)407 /// \warning It is an error if the two edges are not in order!408 UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {409 gr = P.gr;410 edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);411 }412 413 /// Length of the path.414 size_t length() const { return edges.size(); }415 /// Returns whether the path is empty.416 bool empty() const { return edges.empty(); }417 418 /// Resets the path to an empty path.419 void clear() { edges.clear(); }420 421 /// \brief Starting point of the path.422 ///423 /// Starting point of the path.424 /// Returns INVALID if the path is empty.425 GraphNode source() const {426 return empty() ? INVALID : gr->source(edges[0]);427 }428 /// \brief End point of the path.429 ///430 /// End point of the path.431 /// Returns INVALID if the path is empty.432 GraphNode target() const {433 return empty() ? INVALID : gr->target(edges[length()-1]);434 }435 436 /// \brief Initializes node or edge iterator to point to the first437 /// node or edge.438 ///439 /// \sa nth440 template<typename It>441 It& first(It &i) const { return i=It(*this); }442 443 /// \brief Initializes node iterator to point to the node of a given index.444 NodeIt& nth(NodeIt &i, int n) const {445 return i=NodeIt(*this, n);446 }447 448 /// \brief Initializes edge iterator to point to the edge of a given index.449 EdgeIt& nth(EdgeIt &i, int n) const {450 return i=EdgeIt(*this, n);451 }452 453 /// Checks validity of a node or edge iterator.454 template<typename It>455 static456 bool valid(const It &i) { return i.valid(); }457 458 /// Steps the given node or edge iterator.459 template<typename It>460 static461 It& next(It &e) {462 return ++e;463 }464 465 /// \brief Returns node iterator pointing to the target node of the466 /// given edge iterator.467 NodeIt target(const EdgeIt& e) const {468 return NodeIt(*this, e.idx+1);469 }470 471 /// \brief Returns node iterator pointing to the source node of the472 /// given edge iterator.473 NodeIt source(const EdgeIt& e) const {474 return NodeIt(*this, e.idx);475 }476 477 478 479 /**480 * \brief Iterator class to iterate on the edges of the paths481 *482 * This class is used to iterate on the edges of the paths483 *484 * Of course it converts to Graph::Edge485 *486 * \todo Its interface differs from the standard edge iterator.487 * Yes, it shouldn't.488 */489 class EdgeIt {490 friend class UPath;491 492 int idx;493 const UPath *p;494 public:495 /// Default constructor496 EdgeIt() {}497 /// Invalid constructor498 EdgeIt(Invalid) : idx(-1), p(0) {}499 /// Constructor with starting point500 EdgeIt(const UPath &_p, int _idx = 0) :501 idx(_idx), p(&_p) { validate(); }502 503 ///Validity check504 bool valid() const { return idx!=-1; }505 506 ///Conversion to Graph::Edge507 operator GraphEdge () const {508 return valid() ? p->edges[idx] : INVALID;509 }510 /// Next edge511 EdgeIt& operator++() { ++idx; validate(); return *this; }512 513 /// Comparison operator514 bool operator==(const EdgeIt& e) const { return idx==e.idx; }515 /// Comparison operator516 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }517 /// Comparison operator518 bool operator<(const EdgeIt& e) const { return idx<e.idx; }519 520 private:521 // FIXME: comparison between signed and unsigned...522 // Jo ez igy? Vagy esetleg legyen a length() int?523 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }524 };525 526 /**527 * \brief Iterator class to iterate on the nodes of the paths528 *529 * This class is used to iterate on the nodes of the paths530 *531 * Of course it converts to Graph::Node532 *533 * \todo Its interface differs from the standard node iterator.534 * Yes, it shouldn't.535 */536 class NodeIt {537 friend class UPath;538 539 int idx;540 const UPath *p;541 public:542 /// Default constructor543 NodeIt() {}544 /// Invalid constructor545 NodeIt(Invalid) : idx(-1), p(0) {}546 /// Constructor with starting point547 NodeIt(const UPath &_p, int _idx = 0) :548 idx(_idx), p(&_p) { validate(); }549 550 ///Validity check551 bool valid() const { return idx!=-1; }552 553 ///Conversion to Graph::Node554 operator const GraphNode& () const {555 if(idx >= p->length())556 return p->target();557 else if(idx >= 0)558 return p->gr->source(p->edges[idx]);559 else560 return INVALID;561 }562 /// Next node563 NodeIt& operator++() { ++idx; validate(); return *this; }564 565 /// Comparison operator566 bool operator==(const NodeIt& e) const { return idx==e.idx; }567 /// Comparison operator568 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }569 /// Comparison operator570 bool operator<(const NodeIt& e) const { return idx<e.idx; }571 572 private:573 void validate() { if( size_t(idx) > p->length() ) idx=-1; }574 };575 576 friend class Builder;577 578 /**579 * \brief Class to build paths580 *581 * This class is used to fill a path with edges.582 *583 * You can push new edges to the front and to the back of the path in584 * arbitrary order then you should commit these changes to the graph.585 *586 * Fundamentally, for most "Paths" (classes fulfilling the587 * PathConcept) while the builder is active (after the first modifying588 * operation and until the commit()) the original Path is in a589 * "transitional" state (operations ot it have undefined result). But590 * in the case of UPath the original path is unchanged until the591 * commit. However we don't recomend that you use this feature.592 */593 class Builder {594 UPath &P;595 Container front, back;596 597 public:598 ///\param _p the path you want to fill in.599 ///600 Builder(UPath &_p) : P(_p) {}601 602 /// Sets the starting node of the path.603 604 /// Sets the starting node of the path. Edge added to the path605 /// afterwards have to be incident to this node.606 /// It should be called if and only if607 /// the path is empty and before any call to608 /// \ref pushFront() or \ref pushBack()609 void setStartNode(const GraphNode &) {}610 611 ///Push a new edge to the front of the path612 613 ///Push a new edge to the front of the path.614 ///\sa setStartNode615 void pushFront(const GraphEdge& e) {616 front.push_back(e);617 }618 619 ///Push a new edge to the back of the path620 621 ///Push a new edge to the back of the path.622 ///\sa setStartNode623 void pushBack(const GraphEdge& e) {624 back.push_back(e);625 }626 627 ///Commit the changes to the path.628 void commit() {629 if( !(front.empty() && back.empty()) ) {630 Container tmp;631 tmp.reserve(front.size()+back.size()+P.length());632 tmp.insert(tmp.end(), front.rbegin(), front.rend());633 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());634 tmp.insert(tmp.end(), back.begin(), back.end());635 P.edges.swap(tmp);636 front.clear();637 back.clear();638 }639 }640 641 642 ///Reserve storage for the builder in advance.643 644 ///If you know a reasonable upper bound of the number of the edges645 ///to add to the front, using this function you can speed up the building.646 647 void reserveFront(size_t r) {front.reserve(r);}648 649 ///Reserve storage for the builder in advance.650 651 ///If you know a reasonable upper bound of the number of the edges652 ///to add to the back, using this function you can speed up the building.653 654 void reserveBack(size_t r) {back.reserve(r);}655 656 private:657 bool empty() {658 return front.empty() && back.empty() && P.empty();659 }660 661 GraphNode source() const {662 if( ! front.empty() )663 return P.gr->source(front[front.size()-1]);664 else if( ! P.empty() )665 return P.gr->source(P.edges[0]);666 else if( ! back.empty() )667 return P.gr->source(back[0]);668 else669 return INVALID;670 }671 GraphNode target() const {672 if( ! back.empty() )673 return P.gr->target(back[back.size()-1]);674 else if( ! P.empty() )675 return P.gr->target(P.edges[P.length()-1]);676 else if( ! front.empty() )677 return P.gr->target(front[0]);678 else679 return INVALID;680 }681 682 };683 684 };685 686 687 428 ///@} 688 429
Note: See TracChangeset
for help on using the changeset viewer.