1.1 --- a/src/work/klao/debug.h Tue May 11 22:49:13 2004 +0000
1.2 +++ b/src/work/klao/debug.h Tue May 11 22:50:09 2004 +0000
1.3 @@ -18,12 +18,15 @@
1.4 //! after deleting an item from UnionFindEnum set its value in the
1.5 //! corresponding map to NULL...
1.6 static const bool ensure_safe_state = true;
1.7 +
1.8 + static const int verbose = 5;
1.9 };
1.10
1.11 struct DebugOff {
1.12 static const bool consistensy_check = false;
1.13 static const bool range_check = false;
1.14 static const bool ensure_safe_state = false;
1.15 + static const int verbose = 0;
1.16 };
1.17
1.18 #ifdef DEBUG
2.1 --- a/src/work/klao/path.h Tue May 11 22:49:13 2004 +0000
2.2 +++ b/src/work/klao/path.h Tue May 11 22:50:09 2004 +0000
2.3 @@ -23,6 +23,7 @@
2.4
2.5 //! \brief A structure for representing directed path in a graph.
2.6 //!
2.7 + //! A structure for representing directed path in a graph.
2.8 //! \param Graph The graph type in which the path is.
2.9 //! \param DM DebugMode, defaults to DefaultDebugMode.
2.10 //!
2.11 @@ -54,14 +55,27 @@
2.12 ///
2.13 /// Subpath defined by two nodes.
2.14 /// \warning It is an error if the two edges are not in order!
2.15 - /// \todo Implement!
2.16 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b);
2.17 + DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
2.18 + if( DM::range_check && (!a.valid() || !b.valid) ) {
2.19 + // FIXME: this check should be more elaborate...
2.20 + fault("DirPath, subpath ctor: invalid bounding nodes");
2.21 + }
2.22 + gr = P.gr;
2.23 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.24 + }
2.25 +
2.26 /// \brief Subpath constructor.
2.27 ///
2.28 /// Subpath defined by two edges. Contains edges in [a,b)
2.29 /// \warning It is an error if the two edges are not in order!
2.30 - /// \todo Implement!
2.31 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b);
2.32 + DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
2.33 + if( DM::range_check && (!a.valid() || !b.valid) ) {
2.34 + // FIXME: this check should be more elaborate...
2.35 + fault("DirPath, subpath ctor: invalid bounding nodes");
2.36 + }
2.37 + gr = P.gr;
2.38 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.39 + }
2.40
2.41 /// Length of the path.
2.42 size_t length() const { return edges.size(); }
2.43 @@ -93,23 +107,29 @@
2.44 template<typename It>
2.45 It& first(It &i) const { return i=It(*this); }
2.46
2.47 - /// \brief Initializes node or edge iterator to point to the node or edge
2.48 - /// of a given index.
2.49 - template<typename It>
2.50 - It& nth(It &i, int n) const {
2.51 - // FIXME: this test should be different for NodeIt and EdgeIt:
2.52 + /// \brief Initializes node iterator to point to the node of a given index.
2.53 + NodeIt& nth(NodeIt &i, int n) const {
2.54 if( DM::range_check && (n<0 || n>int(length())) )
2.55 fault("DirPath::nth: index out of range");
2.56 - return i=It(*this, n);
2.57 + return i=NodeIt(*this, n);
2.58 + }
2.59 +
2.60 + /// \brief Initializes edge iterator to point to the edge of a given index.
2.61 + EdgeIt& nth(EdgeIt &i, int n) const {
2.62 + if( DM::range_check && (n<0 || n>=int(length())) )
2.63 + fault("DirPath::nth: index out of range");
2.64 + return i=EdgeIt(*this, n);
2.65 }
2.66
2.67 /// Checks validity of a node or edge iterator.
2.68 template<typename It>
2.69 - bool valid(const It &i) const { return i.valid(); }
2.70 + static
2.71 + bool valid(const It &i) { return i.valid(); }
2.72
2.73 /// Steps the given node or edge iterator.
2.74 template<typename It>
2.75 - It& next(It &e) const {
2.76 + static
2.77 + It& next(It &e) {
2.78 if( DM::range_check && !e.valid() )
2.79 fault("DirPath::next() on invalid iterator");
2.80 return ++e;
2.81 @@ -118,12 +138,16 @@
2.82 /// \brief Returns node iterator pointing to the head node of the
2.83 /// given edge iterator.
2.84 NodeIt head(const EdgeIt& e) const {
2.85 + if( DM::range_check && !e.valid() )
2.86 + fault("DirPath::head() on invalid iterator");
2.87 return NodeIt(*this, e.idx+1);
2.88 }
2.89
2.90 /// \brief Returns node iterator pointing to the tail node of the
2.91 /// given edge iterator.
2.92 NodeIt tail(const EdgeIt& e) const {
2.93 + if( DM::range_check && !e.valid() )
2.94 + fault("DirPath::tail() on invalid iterator");
2.95 return NodeIt(*this, e.idx);
2.96 }
2.97
2.98 @@ -170,7 +194,7 @@
2.99
2.100 bool valid() const { return idx!=-1; }
2.101
2.102 - operator const GraphEdge& () const {
2.103 + operator const GraphNode& () const {
2.104 if(idx >= p->length())
2.105 return p->to();
2.106 else if(idx >= 0)
2.107 @@ -197,7 +221,7 @@
2.108 * This class is used to fill a path with edges.
2.109 *
2.110 * You can push new edges to the front and to the back of the path in
2.111 - * arbitrary order the you can commit these changes to the graph.
2.112 + * arbitrary order then you should commit these changes to the graph.
2.113 *
2.114 * Fundamentally, for most "Paths" (classes fulfilling the
2.115 * PathConcept) while the builder is active (after the first modifying
2.116 @@ -215,24 +239,18 @@
2.117 ///
2.118 Builder(DirPath &_P) : P(_P) {}
2.119
2.120 - ///Sets the first node of the path.
2.121 + /// Sets the starting node of the path.
2.122
2.123 - ///Sets the first node of the path. If the path is empty, this
2.124 - ///function or setTo() have to be called before any call to \ref
2.125 - ///pushFront() or \ref pushBack()
2.126 - void setFrom(const GraphNode &) {}
2.127 -
2.128 - ///Sets the last node of the path.
2.129 -
2.130 - ///Sets the last node of the path. If the path is empty, this
2.131 - ///function or setFrom() have to be called before any call of \ref
2.132 - ///pushFront() or \ref pushBack()
2.133 - void setTo(const GraphNode &) {}
2.134 -
2.135 + /// Sets the starting node of the path. Edge added to the path
2.136 + /// afterwards have to be incident to this node.
2.137 + /// It should be called iff the path is empty and before any call to
2.138 + /// \ref pushFront() or \ref pushBack()
2.139 + void setStart(const GraphNode &) {}
2.140 +
2.141 ///Push a new edge to the front of the path
2.142
2.143 ///Push a new edge to the front of the path.
2.144 - ///\sa setTo
2.145 + ///\sa setStart
2.146 void pushFront(const GraphEdge& e) {
2.147 if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
2.148 fault("DirPath::Builder::pushFront: nonincident edge");
2.149 @@ -243,7 +261,7 @@
2.150 ///Push a new edge to the back of the path
2.151
2.152 ///Push a new edge to the back of the path.
2.153 - ///\sa setFrom
2.154 + ///\sa setStart
2.155 void pushBack(const GraphEdge& e) {
2.156 if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
2.157 fault("DirPath::Builder::pushBack: nonincident edge");
2.158 @@ -265,13 +283,319 @@
2.159 }
2.160 }
2.161
2.162 -// ///Desctuctor
2.163 + // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.164 + // Hogy kenyelmes egy ilyet hasznalni?
2.165 + void reserve(size_t r) {
2.166 + front.reserve(r);
2.167 + back.reserve(r);
2.168 + }
2.169
2.170 -// ///The desctuctor.
2.171 -// ///It commit also commit the changes.
2.172 -// ///\todo Is this what we want?
2.173 -// Nope. Let's use commit() explicitly.
2.174 -// ~Builder() { commit(); }
2.175 + private:
2.176 + bool empty() {
2.177 + return front.empty() && back.empty() && P.empty();
2.178 + }
2.179 +
2.180 + GraphNode from() const {
2.181 + if( ! front.empty() )
2.182 + return P.gr->tail(front[front.size()-1]);
2.183 + else if( ! P.empty() )
2.184 + return P.gr->tail(P.edges[0]);
2.185 + else if( ! back.empty() )
2.186 + return P.gr->tail(back[0]);
2.187 + else
2.188 + return INVALID;
2.189 + }
2.190 + GraphNode to() const {
2.191 + if( ! back.empty() )
2.192 + return P.gr->head(back[back.size()-1]);
2.193 + else if( ! P.empty() )
2.194 + return P.gr->head(P.edges[P.length()-1]);
2.195 + else if( ! front.empty() )
2.196 + return P.gr->head(front[0]);
2.197 + else
2.198 + return INVALID;
2.199 + }
2.200 +
2.201 + };
2.202 +
2.203 + };
2.204 +
2.205 +
2.206 +
2.207 +
2.208 +
2.209 +
2.210 +
2.211 +
2.212 +
2.213 +
2.214 + /**********************************************************************/
2.215 +
2.216 +
2.217 + //! \brief A structure for representing undirected path in a graph.
2.218 + //!
2.219 + //! A structure for representing undirected path in a graph. Ie. this is
2.220 + //! a path in a \e directed graph but the edges should not be directed
2.221 + //! forward.
2.222 + //!
2.223 + //! \param Graph The graph type in which the path is.
2.224 + //! \param DM DebugMode, defaults to DefaultDebugMode.
2.225 + //!
2.226 + //! In a sense, the path can be treated as a graph, for is has \c NodeIt
2.227 + //! and \c EdgeIt with the same usage. These types converts to the \c Node
2.228 + //! and \c Edge of the original graph.
2.229 + //!
2.230 + //! \todo Thoroughfully check all the range and consistency tests.
2.231 + template<typename Graph, typename DM = DefaultDebugMode>
2.232 + class UndirPath {
2.233 + public:
2.234 + typedef typename Graph::Edge GraphEdge;
2.235 + typedef typename Graph::Node GraphNode;
2.236 + class NodeIt;
2.237 + class EdgeIt;
2.238 +
2.239 + protected:
2.240 + const Graph *gr;
2.241 + typedef std::vector<GraphEdge> Container;
2.242 + Container edges;
2.243 +
2.244 + public:
2.245 +
2.246 + /// \param _G The graph in which the path is.
2.247 + ///
2.248 + UndirPath(const Graph &_G) : gr(&_G) {}
2.249 +
2.250 + /// \brief Subpath constructor.
2.251 + ///
2.252 + /// Subpath defined by two nodes.
2.253 + /// \warning It is an error if the two edges are not in order!
2.254 + UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
2.255 + if( DM::range_check && (!a.valid() || !b.valid) ) {
2.256 + // FIXME: this check should be more elaborate...
2.257 + fault("UndirPath, subpath ctor: invalid bounding nodes");
2.258 + }
2.259 + gr = P.gr;
2.260 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.261 + }
2.262 +
2.263 + /// \brief Subpath constructor.
2.264 + ///
2.265 + /// Subpath defined by two edges. Contains edges in [a,b)
2.266 + /// \warning It is an error if the two edges are not in order!
2.267 + UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
2.268 + if( DM::range_check && (!a.valid() || !b.valid) ) {
2.269 + // FIXME: this check should be more elaborate...
2.270 + fault("UndirPath, subpath ctor: invalid bounding nodes");
2.271 + }
2.272 + gr = P.gr;
2.273 + edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.274 + }
2.275 +
2.276 + /// Length of the path.
2.277 + size_t length() const { return edges.size(); }
2.278 + /// Returns whether the path is empty.
2.279 + bool empty() const { return edges.empty(); }
2.280 +
2.281 + /// Resets the path to an empty path.
2.282 + void clear() { edges.clear(); }
2.283 +
2.284 + /// \brief Starting point of the path.
2.285 + ///
2.286 + /// Starting point of the path.
2.287 + /// Returns INVALID if the path is empty.
2.288 + GraphNode from() const {
2.289 + return empty() ? INVALID : gr->tail(edges[0]);
2.290 + }
2.291 + /// \brief End point of the path.
2.292 + ///
2.293 + /// End point of the path.
2.294 + /// Returns INVALID if the path is empty.
2.295 + GraphNode to() const {
2.296 + return empty() ? INVALID : gr->head(edges[length()-1]);
2.297 + }
2.298 +
2.299 + /// \brief Initializes node or edge iterator to point to the first
2.300 + /// node or edge.
2.301 + ///
2.302 + /// \sa nth
2.303 + template<typename It>
2.304 + It& first(It &i) const { return i=It(*this); }
2.305 +
2.306 + /// \brief Initializes node iterator to point to the node of a given index.
2.307 + NodeIt& nth(NodeIt &i, int n) const {
2.308 + if( DM::range_check && (n<0 || n>int(length())) )
2.309 + fault("UndirPath::nth: index out of range");
2.310 + return i=NodeIt(*this, n);
2.311 + }
2.312 +
2.313 + /// \brief Initializes edge iterator to point to the edge of a given index.
2.314 + EdgeIt& nth(EdgeIt &i, int n) const {
2.315 + if( DM::range_check && (n<0 || n>=int(length())) )
2.316 + fault("UndirPath::nth: index out of range");
2.317 + return i=EdgeIt(*this, n);
2.318 + }
2.319 +
2.320 + /// Checks validity of a node or edge iterator.
2.321 + template<typename It>
2.322 + static
2.323 + bool valid(const It &i) { return i.valid(); }
2.324 +
2.325 + /// Steps the given node or edge iterator.
2.326 + template<typename It>
2.327 + static
2.328 + It& next(It &e) {
2.329 + if( DM::range_check && !e.valid() )
2.330 + fault("UndirPath::next() on invalid iterator");
2.331 + return ++e;
2.332 + }
2.333 +
2.334 + /// \brief Returns node iterator pointing to the head node of the
2.335 + /// given edge iterator.
2.336 + NodeIt head(const EdgeIt& e) const {
2.337 + if( DM::range_check && !e.valid() )
2.338 + fault("UndirPath::head() on invalid iterator");
2.339 + return NodeIt(*this, e.idx+1);
2.340 + }
2.341 +
2.342 + /// \brief Returns node iterator pointing to the tail node of the
2.343 + /// given edge iterator.
2.344 + NodeIt tail(const EdgeIt& e) const {
2.345 + if( DM::range_check && !e.valid() )
2.346 + fault("UndirPath::tail() on invalid iterator");
2.347 + return NodeIt(*this, e.idx);
2.348 + }
2.349 +
2.350 +
2.351 + /*** Iterator classes ***/
2.352 + class EdgeIt {
2.353 + friend class UndirPath;
2.354 +
2.355 + int idx;
2.356 + const UndirPath *p;
2.357 + public:
2.358 + EdgeIt() {}
2.359 + EdgeIt(Invalid) : idx(-1), p(0) {}
2.360 + EdgeIt(const UndirPath &_p, int _idx = 0) :
2.361 + idx(_idx), p(&_p) { validate(); }
2.362 +
2.363 + bool valid() const { return idx!=-1; }
2.364 +
2.365 + operator GraphEdge () const {
2.366 + return valid() ? p->edges[idx] : INVALID;
2.367 + }
2.368 + EdgeIt& operator++() { ++idx; validate(); return *this; }
2.369 +
2.370 + bool operator==(const EdgeIt& e) const { return idx==e.idx; }
2.371 + bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
2.372 + bool operator<(const EdgeIt& e) const { return idx<e.idx; }
2.373 +
2.374 + private:
2.375 + // FIXME: comparison between signed and unsigned...
2.376 + // Jo ez igy? Vagy esetleg legyen a length() int?
2.377 + void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
2.378 + };
2.379 +
2.380 + class NodeIt {
2.381 + friend class UndirPath;
2.382 +
2.383 + int idx;
2.384 + const UndirPath *p;
2.385 + public:
2.386 + NodeIt() {}
2.387 + NodeIt(Invalid) : idx(-1), p(0) {}
2.388 + NodeIt(const UndirPath &_p, int _idx = 0) :
2.389 + idx(_idx), p(&_p) { validate(); }
2.390 +
2.391 + bool valid() const { return idx!=-1; }
2.392 +
2.393 + operator const GraphNode& () const {
2.394 + if(idx >= p->length())
2.395 + return p->to();
2.396 + else if(idx >= 0)
2.397 + return p->gr->tail(p->edges[idx]);
2.398 + else
2.399 + return INVALID;
2.400 + }
2.401 + NodeIt& operator++() { ++idx; validate(); return *this; }
2.402 +
2.403 + bool operator==(const NodeIt& e) const { return idx==e.idx; }
2.404 + bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
2.405 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.406 +
2.407 + private:
2.408 + void validate() { if( size_t(idx) > p->length() ) idx=-1; }
2.409 + };
2.410 +
2.411 + friend class Builder;
2.412 +
2.413 + /**
2.414 + * \brief Class to build paths
2.415 + *
2.416 + * \ingroup datas
2.417 + * This class is used to fill a path with edges.
2.418 + *
2.419 + * You can push new edges to the front and to the back of the path in
2.420 + * arbitrary order then you should commit these changes to the graph.
2.421 + *
2.422 + * Fundamentally, for most "Paths" (classes fulfilling the
2.423 + * PathConcept) while the builder is active (after the first modifying
2.424 + * operation and until the commit()) the original Path is in a
2.425 + * "transitional" state (operations ot it have undefined result). But
2.426 + * in the case of UndirPath the original path is unchanged until the
2.427 + * commit. However we don't recomend that you use this feature.
2.428 + */
2.429 + class Builder {
2.430 + UndirPath &P;
2.431 + Container front, back;
2.432 +
2.433 + public:
2.434 + ///\param _P the path you want to fill in.
2.435 + ///
2.436 + Builder(UndirPath &_P) : P(_P) {}
2.437 +
2.438 + /// Sets the starting node of the path.
2.439 +
2.440 + /// Sets the starting node of the path. Edge added to the path
2.441 + /// afterwards have to be incident to this node.
2.442 + /// It should be called iff the path is empty and before any call to
2.443 + /// \ref pushFront() or \ref pushBack()
2.444 + void setStart(const GraphNode &) {}
2.445 +
2.446 + ///Push a new edge to the front of the path
2.447 +
2.448 + ///Push a new edge to the front of the path.
2.449 + ///\sa setStart
2.450 + void pushFront(const GraphEdge& e) {
2.451 + if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
2.452 + fault("UndirPath::Builder::pushFront: nonincident edge");
2.453 + }
2.454 + front.push_back(e);
2.455 + }
2.456 +
2.457 + ///Push a new edge to the back of the path
2.458 +
2.459 + ///Push a new edge to the back of the path.
2.460 + ///\sa setStart
2.461 + void pushBack(const GraphEdge& e) {
2.462 + if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
2.463 + fault("UndirPath::Builder::pushBack: nonincident edge");
2.464 + }
2.465 + back.push_back(e);
2.466 + }
2.467 +
2.468 + ///Commit the changes to the path.
2.469 + void commit() {
2.470 + if( !(front.empty() && back.empty()) ) {
2.471 + Container tmp;
2.472 + tmp.reserve(front.size()+back.size()+P.length());
2.473 + tmp.insert(tmp.end(), front.rbegin(), front.rend());
2.474 + tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
2.475 + tmp.insert(tmp.end(), back.begin(), back.end());
2.476 + P.edges.swap(tmp);
2.477 + front.clear();
2.478 + back.clear();
2.479 + }
2.480 + }
2.481
2.482 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.483 // Hogy kenyelmes egy ilyet hasznalni?