1.1 --- a/src/work/johanna/kruskal_test.cc Sun Sep 19 12:45:35 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,154 +0,0 @@
1.4 -#include <string>
1.5 -#include <iostream>
1.6 -#include <map>
1.7 -#include <vector>
1.8 -
1.9 -#include <kruskal.h>
1.10 -#include <hugo/list_graph.h>
1.11 -
1.12 -
1.13 -using namespace std;
1.14 -using namespace hugo;
1.15 -
1.16 -class string_int_map : public map<string,int> {
1.17 -public:
1.18 - int get(const string &s) {
1.19 - // Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
1.20 - // hogy is mukodik ez a map :)
1.21 - if( count(s) == 0 ) {
1.22 - operator[](s) = -1;
1.23 - }
1.24 - return operator[](s);
1.25 - }
1.26 - void set(const string &s, int i) {
1.27 - operator[](s) = i;
1.28 - }
1.29 -};
1.30 -
1.31 -
1.32 -// Egy olyan "map", ami nem tud semmit, csak a typedef-eket.
1.33 -// Valami elegansabb megoldas kene a Kruskalban...
1.34 -
1.35 -template <typename K, typename V>
1.36 -class DummyMap {
1.37 -public:
1.38 - typedef K KeyType;
1.39 - typedef V ValueType;
1.40 -};
1.41 -
1.42 -int main() {
1.43 -
1.44 - typedef ListGraph::Node Node;
1.45 - typedef ListGraph::Edge Edge;
1.46 - typedef ListGraph::NodeIt NodeIt;
1.47 - typedef ListGraph::EdgeIt EdgeIt;
1.48 -
1.49 - ListGraph G;
1.50 -
1.51 - Node s=G.addNode();
1.52 - Node v1=G.addNode();
1.53 - Node v2=G.addNode();
1.54 - Node v3=G.addNode();
1.55 - Node v4=G.addNode();
1.56 - Node t=G.addNode();
1.57 -
1.58 - Edge e1 = G.addEdge(s, v1);
1.59 - Edge e2 = G.addEdge(s, v2);
1.60 - Edge e3 = G.addEdge(v1, v2);
1.61 - Edge e4 = G.addEdge(v2, v1);
1.62 - Edge e5 = G.addEdge(v1, v3);
1.63 - Edge e6 = G.addEdge(v3, v2);
1.64 - Edge e7 = G.addEdge(v2, v4);
1.65 - Edge e8 = G.addEdge(v4, v3);
1.66 - Edge e9 = G.addEdge(v3, t);
1.67 - Edge e10 = G.addEdge(v4, t);
1.68 -
1.69 - typedef ListGraph::EdgeMap<double> ECostMap;
1.70 - typedef ListGraph::EdgeMap<bool> EBoolMap;
1.71 -
1.72 - ECostMap edge_cost_map(G, 2);
1.73 - EBoolMap tree_map(G);
1.74 -
1.75 -
1.76 - cout << "Uniform 2-es koltseggel: "
1.77 - << kruskalEdgeMap(G, edge_cost_map, tree_map)
1.78 - << endl;
1.79 -
1.80 -
1.81 - edge_cost_map.set(e1, -10);
1.82 - edge_cost_map.set(e2, -9);
1.83 - edge_cost_map.set(e3, -8);
1.84 - edge_cost_map.set(e4, -7);
1.85 - edge_cost_map.set(e5, -6);
1.86 - edge_cost_map.set(e6, -5);
1.87 - edge_cost_map.set(e7, -4);
1.88 - edge_cost_map.set(e8, -3);
1.89 - edge_cost_map.set(e9, -2);
1.90 - edge_cost_map.set(e10, -1);
1.91 -
1.92 - vector<Edge> tree_edge_vec;
1.93 -
1.94 - cout << "Nemkonst koltseggel (-31): "
1.95 - << kruskalEdgeMap_IteratorOut(G, edge_cost_map,
1.96 - back_inserter(tree_edge_vec))
1.97 - << endl;
1.98 -
1.99 - int i = 1;
1.100 - for(vector<Edge>::iterator e = tree_edge_vec.begin();
1.101 - e != tree_edge_vec.end(); ++e, ++i) {
1.102 - cout << i << ". el: " << G.id(*e) << endl;
1.103 - }
1.104 -
1.105 - tree_edge_vec.clear();
1.106 -// SequenceOutput< back_insert_iterator< vector<Edge> > >
1.107 -// vec_filler(back_inserter(tree_edge_vec));
1.108 -// cout << "Nemkonst koltseggel tarhatekonyabban: "
1.109 -// << Kruskal(G,
1.110 -// KruskalMapVec<ECostMap>(G, edge_cost_map),
1.111 -// vec_filler)
1.112 -// << endl;
1.113 -
1.114 -// cout << "Nemkonst koltseggel tarhatekonyabban: "
1.115 -// << kruskal(G,
1.116 -// KruskalMapVec<ECostMap>(G, edge_cost_map),
1.117 -// makeSequenceOutput(back_inserter(tree_edge_vec))
1.118 -// )
1.119 -// << endl;
1.120 -
1.121 -// i = 1;
1.122 -// for(vector<Edge>::iterator e = tree_edge_vec.begin();
1.123 -// e != tree_edge_vec.end(); ++e, ++i) {
1.124 -// cout << i << ". el: " << *e << endl;
1.125 -// }
1.126 -
1.127 -// **********************************************************************
1.128 -
1.129 -// typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
1.130 -
1.131 -// MCTK mctk(G, edge_cost_map, tree_map);
1.132 -// double k0lts = mctk.run();
1.133 -
1.134 -// cout << "Uniform 2-es koltseggel: " << k0lts << endl;
1.135 -
1.136 -// // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
1.137 -// typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
1.138 -// MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
1.139 -// MCTK2::EdgeCostVector ecv;
1.140 -// ecv.push_back(make_pair(e1, 10));
1.141 -// ecv.push_back(make_pair(e2, 9));
1.142 -// ecv.push_back(make_pair(e3, 8));
1.143 -// ecv.push_back(make_pair(e4, 7));
1.144 -// ecv.push_back(make_pair(e5, 6));
1.145 -// ecv.push_back(make_pair(e6, 5));
1.146 -// ecv.push_back(make_pair(e7, 4));
1.147 -// ecv.push_back(make_pair(e8, 3));
1.148 -// ecv.push_back(make_pair(e9, 2));
1.149 -// ecv.push_back(make_pair(e10, 1));
1.150 -
1.151 -// k0lts = mctk2.run(ecv);
1.152 -// cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
1.153 -// << k0lts << endl;
1.154 -
1.155 -
1.156 - return 0;
1.157 -}
2.1 --- a/src/work/klao/path.h Sun Sep 19 12:45:35 2004 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,1174 +0,0 @@
2.4 -// -*- c++ -*- //
2.5 -
2.6 -/**
2.7 -@defgroup paths Path Structures
2.8 -@ingroup datas
2.9 -\brief Path structures implemented in Hugo.
2.10 -
2.11 -Hugolib provides flexible data structures
2.12 -to work with paths.
2.13 -
2.14 -All of them have the same interface, especially they can be built or extended
2.15 -using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
2.16 -algorithm to store its result in any kind of path structure.
2.17 -
2.18 -\sa hugo::skeleton::Path
2.19 -
2.20 -*/
2.21 -
2.22 -///\ingroup paths
2.23 -///\file
2.24 -///\brief Classes for representing paths in graphs.
2.25 -
2.26 -#ifndef HUGO_PATH_H
2.27 -#define HUGO_PATH_H
2.28 -
2.29 -#include <deque>
2.30 -#include <vector>
2.31 -#include <algorithm>
2.32 -
2.33 -#include <hugo/invalid.h>
2.34 -#include <hugo/error.h>
2.35 -#include <debug.h>
2.36 -
2.37 -namespace hugo {
2.38 -
2.39 - /// \addtogroup paths
2.40 - /// @{
2.41 -
2.42 -
2.43 - //! \brief A structure for representing directed paths in a graph.
2.44 - //!
2.45 - //! A structure for representing directed path in a graph.
2.46 - //! \param Graph The graph type in which the path is.
2.47 - //! \param DM DebugMode, defaults to DefaultDebugMode.
2.48 - //!
2.49 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
2.50 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
2.51 - //! and \c Edge of the original graph.
2.52 - //!
2.53 - //! \todo Thoroughfully check all the range and consistency tests.
2.54 - template<typename Graph, typename DM = DefaultDebugMode>
2.55 - class DirPath {
2.56 - public:
2.57 - /// Edge type of the underlying graph.
2.58 - typedef typename Graph::Edge GraphEdge;
2.59 - /// Node type of the underlying graph.
2.60 - typedef typename Graph::Node GraphNode;
2.61 - class NodeIt;
2.62 - class EdgeIt;
2.63 -
2.64 - protected:
2.65 - const Graph *gr;
2.66 - typedef std::vector<GraphEdge> Container;
2.67 - Container edges;
2.68 -
2.69 - public:
2.70 -
2.71 - /// \param _G The graph in which the path is.
2.72 - ///
2.73 - DirPath(const Graph &_G) : gr(&_G) {}
2.74 -
2.75 - /// \brief Subpath constructor.
2.76 - ///
2.77 - /// Subpath defined by two nodes.
2.78 - /// \warning It is an error if the two edges are not in order!
2.79 - DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
2.80 - if( DM::range_check && (!a.valid() || !b.valid) ) {
2.81 - // FIXME: this check should be more elaborate...
2.82 - fault("DirPath, subpath ctor: invalid bounding nodes");
2.83 - }
2.84 - gr = P.gr;
2.85 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.86 - }
2.87 -
2.88 - /// \brief Subpath constructor.
2.89 - ///
2.90 - /// Subpath defined by two edges. Contains edges in [a,b)
2.91 - /// \warning It is an error if the two edges are not in order!
2.92 - DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
2.93 - if( DM::range_check && (!a.valid() || !b.valid) ) {
2.94 - // FIXME: this check should be more elaborate...
2.95 - fault("DirPath, subpath ctor: invalid bounding nodes");
2.96 - }
2.97 - gr = P.gr;
2.98 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.99 - }
2.100 -
2.101 - /// Length of the path.
2.102 - size_t length() const { return edges.size(); }
2.103 - /// Returns whether the path is empty.
2.104 - bool empty() const { return edges.empty(); }
2.105 -
2.106 - /// Resets the path to an empty path.
2.107 - void clear() { edges.clear(); }
2.108 -
2.109 - /// \brief Starting point of the path.
2.110 - ///
2.111 - /// Starting point of the path.
2.112 - /// Returns INVALID if the path is empty.
2.113 - GraphNode from() const {
2.114 - return empty() ? INVALID : gr->tail(edges[0]);
2.115 - }
2.116 - /// \brief End point of the path.
2.117 - ///
2.118 - /// End point of the path.
2.119 - /// Returns INVALID if the path is empty.
2.120 - GraphNode to() const {
2.121 - return empty() ? INVALID : gr->head(edges[length()-1]);
2.122 - }
2.123 -
2.124 - /// \brief Initializes node or edge iterator to point to the first
2.125 - /// node or edge.
2.126 - ///
2.127 - /// \sa nth
2.128 - template<typename It>
2.129 - It& first(It &i) const { return i=It(*this); }
2.130 -
2.131 - /// \brief Initializes node iterator to point to the node of a given index.
2.132 - NodeIt& nth(NodeIt &i, int n) const {
2.133 - if( DM::range_check && (n<0 || n>int(length())) )
2.134 - fault("DirPath::nth: index out of range");
2.135 - return i=NodeIt(*this, n);
2.136 - }
2.137 -
2.138 - /// \brief Initializes edge iterator to point to the edge of a given index.
2.139 - EdgeIt& nth(EdgeIt &i, int n) const {
2.140 - if( DM::range_check && (n<0 || n>=int(length())) )
2.141 - fault("DirPath::nth: index out of range");
2.142 - return i=EdgeIt(*this, n);
2.143 - }
2.144 -
2.145 - /// Checks validity of a node or edge iterator.
2.146 - template<typename It>
2.147 - static
2.148 - bool valid(const It &i) { return i.valid(); }
2.149 -
2.150 - /// Steps the given node or edge iterator.
2.151 - template<typename It>
2.152 - static
2.153 - It& next(It &e) {
2.154 - if( DM::range_check && !e.valid() )
2.155 - fault("DirPath::next() on invalid iterator");
2.156 - return ++e;
2.157 - }
2.158 -
2.159 - /// \brief Returns node iterator pointing to the head node of the
2.160 - /// given edge iterator.
2.161 - NodeIt head(const EdgeIt& e) const {
2.162 - if( DM::range_check && !e.valid() )
2.163 - fault("DirPath::head() on invalid iterator");
2.164 - return NodeIt(*this, e.idx+1);
2.165 - }
2.166 -
2.167 - /// \brief Returns node iterator pointing to the tail node of the
2.168 - /// given edge iterator.
2.169 - NodeIt tail(const EdgeIt& e) const {
2.170 - if( DM::range_check && !e.valid() )
2.171 - fault("DirPath::tail() on invalid iterator");
2.172 - return NodeIt(*this, e.idx);
2.173 - }
2.174 -
2.175 -
2.176 - /* Iterator classes */
2.177 -
2.178 - /**
2.179 - * \brief Iterator class to iterate on the edges of the paths
2.180 - *
2.181 - * \ingroup paths
2.182 - * This class is used to iterate on the edges of the paths
2.183 - *
2.184 - * Of course it converts to Graph::Edge
2.185 - *
2.186 - * \todo Its interface differs from the standard edge iterator.
2.187 - * Yes, it shouldn't.
2.188 - */
2.189 - class EdgeIt {
2.190 - friend class DirPath;
2.191 -
2.192 - int idx;
2.193 - const DirPath *p;
2.194 - public:
2.195 - /// Default constructor
2.196 - EdgeIt() {}
2.197 - /// Invalid constructor
2.198 - EdgeIt(Invalid) : idx(-1), p(0) {}
2.199 - /// Constructor with starting point
2.200 - EdgeIt(const DirPath &_p, int _idx = 0) :
2.201 - idx(_idx), p(&_p) { validate(); }
2.202 -
2.203 - ///Validity check
2.204 - bool valid() const { return idx!=-1; }
2.205 -
2.206 - ///Conversion to Graph::Edge
2.207 - operator GraphEdge () const {
2.208 - return valid() ? p->edges[idx] : INVALID;
2.209 - }
2.210 -
2.211 - /// Next edge
2.212 - EdgeIt& operator++() { ++idx; validate(); return *this; }
2.213 -
2.214 - /// Comparison operator
2.215 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
2.216 - /// Comparison operator
2.217 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
2.218 - /// Comparison operator
2.219 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
2.220 -
2.221 - private:
2.222 - // FIXME: comparison between signed and unsigned...
2.223 - // Jo ez igy? Vagy esetleg legyen a length() int?
2.224 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
2.225 - };
2.226 -
2.227 - /**
2.228 - * \brief Iterator class to iterate on the nodes of the paths
2.229 - *
2.230 - * \ingroup paths
2.231 - * This class is used to iterate on the nodes of the paths
2.232 - *
2.233 - * Of course it converts to Graph::Node
2.234 - *
2.235 - * \todo Its interface differs from the standard node iterator.
2.236 - * Yes, it shouldn't.
2.237 - */
2.238 - class NodeIt {
2.239 - friend class DirPath;
2.240 -
2.241 - int idx;
2.242 - const DirPath *p;
2.243 - public:
2.244 - /// Default constructor
2.245 - NodeIt() {}
2.246 - /// Invalid constructor
2.247 - NodeIt(Invalid) : idx(-1), p(0) {}
2.248 - /// Constructor with starting point
2.249 - NodeIt(const DirPath &_p, int _idx = 0) :
2.250 - idx(_idx), p(&_p) { validate(); }
2.251 -
2.252 - ///Validity check
2.253 - bool valid() const { return idx!=-1; }
2.254 -
2.255 - ///Conversion to Graph::Node
2.256 - operator const GraphNode& () const {
2.257 - if(idx >= p->length())
2.258 - return p->to();
2.259 - else if(idx >= 0)
2.260 - return p->gr->tail(p->edges[idx]);
2.261 - else
2.262 - return INVALID;
2.263 - }
2.264 - /// Next node
2.265 - NodeIt& operator++() { ++idx; validate(); return *this; }
2.266 -
2.267 - /// Comparison operator
2.268 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
2.269 - /// Comparison operator
2.270 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
2.271 - /// Comparison operator
2.272 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.273 -
2.274 - private:
2.275 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
2.276 - };
2.277 -
2.278 - friend class Builder;
2.279 -
2.280 - /**
2.281 - * \brief Class to build paths
2.282 - *
2.283 - * \ingroup paths
2.284 - * This class is used to fill a path with edges.
2.285 - *
2.286 - * You can push new edges to the front and to the back of the path in
2.287 - * arbitrary order then you should commit these changes to the graph.
2.288 - *
2.289 - * Fundamentally, for most "Paths" (classes fulfilling the
2.290 - * PathConcept) while the builder is active (after the first modifying
2.291 - * operation and until the commit()) the original Path is in a
2.292 - * "transitional" state (operations on it have undefined result). But
2.293 - * in the case of DirPath the original path remains unchanged until the
2.294 - * commit. However we don't recomend that you use this feature.
2.295 - */
2.296 - class Builder {
2.297 - DirPath &P;
2.298 - Container front, back;
2.299 -
2.300 - public:
2.301 - ///\param _P the path you want to fill in.
2.302 - ///
2.303 - Builder(DirPath &_P) : P(_P) {}
2.304 -
2.305 - /// Sets the starting node of the path.
2.306 -
2.307 - /// Sets the starting node of the path. Edge added to the path
2.308 - /// afterwards have to be incident to this node.
2.309 - /// It should be called iff the path is empty and before any call to
2.310 - /// \ref pushFront() or \ref pushBack()
2.311 - void setStartNode(const GraphNode &) {}
2.312 -
2.313 - ///Push a new edge to the front of the path
2.314 -
2.315 - ///Push a new edge to the front of the path.
2.316 - ///\sa setStartNode
2.317 - void pushFront(const GraphEdge& e) {
2.318 - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
2.319 - fault("DirPath::Builder::pushFront: nonincident edge");
2.320 - }
2.321 - front.push_back(e);
2.322 - }
2.323 -
2.324 - ///Push a new edge to the back of the path
2.325 -
2.326 - ///Push a new edge to the back of the path.
2.327 - ///\sa setStartNode
2.328 - void pushBack(const GraphEdge& e) {
2.329 - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
2.330 - fault("DirPath::Builder::pushBack: nonincident edge");
2.331 - }
2.332 - back.push_back(e);
2.333 - }
2.334 -
2.335 - ///Commit the changes to the path.
2.336 - void commit() {
2.337 - if( !(front.empty() && back.empty()) ) {
2.338 - Container tmp;
2.339 - tmp.reserve(front.size()+back.size()+P.length());
2.340 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
2.341 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
2.342 - tmp.insert(tmp.end(), back.begin(), back.end());
2.343 - P.edges.swap(tmp);
2.344 - front.clear();
2.345 - back.clear();
2.346 - }
2.347 - }
2.348 -
2.349 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.350 - // Hogy kenyelmes egy ilyet hasznalni?
2.351 -
2.352 - ///Reserve storage for the builder in advance.
2.353 -
2.354 - ///If you know an reasonable upper bound of the number of the edges
2.355 - ///to add, using this function you can speed up the building.
2.356 - void reserve(size_t r) {
2.357 - front.reserve(r);
2.358 - back.reserve(r);
2.359 - }
2.360 -
2.361 - private:
2.362 - bool empty() {
2.363 - return front.empty() && back.empty() && P.empty();
2.364 - }
2.365 -
2.366 - GraphNode from() const {
2.367 - if( ! front.empty() )
2.368 - return P.gr->tail(front[front.size()-1]);
2.369 - else if( ! P.empty() )
2.370 - return P.gr->tail(P.edges[0]);
2.371 - else if( ! back.empty() )
2.372 - return P.gr->tail(back[0]);
2.373 - else
2.374 - return INVALID;
2.375 - }
2.376 - GraphNode to() const {
2.377 - if( ! back.empty() )
2.378 - return P.gr->head(back[back.size()-1]);
2.379 - else if( ! P.empty() )
2.380 - return P.gr->head(P.edges[P.length()-1]);
2.381 - else if( ! front.empty() )
2.382 - return P.gr->head(front[0]);
2.383 - else
2.384 - return INVALID;
2.385 - }
2.386 -
2.387 - };
2.388 -
2.389 - };
2.390 -
2.391 -
2.392 -
2.393 -
2.394 -
2.395 -
2.396 -
2.397 -
2.398 -
2.399 -
2.400 - /**********************************************************************/
2.401 -
2.402 -
2.403 - //! \brief A structure for representing undirected path in a graph.
2.404 - //!
2.405 - //! A structure for representing undirected path in a graph. Ie. this is
2.406 - //! a path in a \e directed graph but the edges should not be directed
2.407 - //! forward.
2.408 - //!
2.409 - //! \param Graph The graph type in which the path is.
2.410 - //! \param DM DebugMode, defaults to DefaultDebugMode.
2.411 - //!
2.412 - //! In a sense, the path can be treated as a graph, for is has \c NodeIt
2.413 - //! and \c EdgeIt with the same usage. These types converts to the \c Node
2.414 - //! and \c Edge of the original graph.
2.415 - //!
2.416 - //! \todo Thoroughfully check all the range and consistency tests.
2.417 - template<typename Graph, typename DM = DefaultDebugMode>
2.418 - class UndirPath {
2.419 - public:
2.420 - /// Edge type of the underlying graph.
2.421 - typedef typename Graph::Edge GraphEdge;
2.422 - /// Node type of the underlying graph.
2.423 - typedef typename Graph::Node GraphNode;
2.424 - class NodeIt;
2.425 - class EdgeIt;
2.426 -
2.427 - protected:
2.428 - const Graph *gr;
2.429 - typedef std::vector<GraphEdge> Container;
2.430 - Container edges;
2.431 -
2.432 - public:
2.433 -
2.434 - /// \param _G The graph in which the path is.
2.435 - ///
2.436 - UndirPath(const Graph &_G) : gr(&_G) {}
2.437 -
2.438 - /// \brief Subpath constructor.
2.439 - ///
2.440 - /// Subpath defined by two nodes.
2.441 - /// \warning It is an error if the two edges are not in order!
2.442 - UndirPath(const UndirPath &P, const NodeIt &a, const NodeIt &b) {
2.443 - if( DM::range_check && (!a.valid() || !b.valid) ) {
2.444 - // FIXME: this check should be more elaborate...
2.445 - fault("UndirPath, subpath ctor: invalid bounding nodes");
2.446 - }
2.447 - gr = P.gr;
2.448 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.449 - }
2.450 -
2.451 - /// \brief Subpath constructor.
2.452 - ///
2.453 - /// Subpath defined by two edges. Contains edges in [a,b)
2.454 - /// \warning It is an error if the two edges are not in order!
2.455 - UndirPath(const UndirPath &P, const EdgeIt &a, const EdgeIt &b) {
2.456 - if( DM::range_check && (!a.valid() || !b.valid) ) {
2.457 - // FIXME: this check should be more elaborate...
2.458 - fault("UndirPath, subpath ctor: invalid bounding nodes");
2.459 - }
2.460 - gr = P.gr;
2.461 - edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
2.462 - }
2.463 -
2.464 - /// Length of the path.
2.465 - size_t length() const { return edges.size(); }
2.466 - /// Returns whether the path is empty.
2.467 - bool empty() const { return edges.empty(); }
2.468 -
2.469 - /// Resets the path to an empty path.
2.470 - void clear() { edges.clear(); }
2.471 -
2.472 - /// \brief Starting point of the path.
2.473 - ///
2.474 - /// Starting point of the path.
2.475 - /// Returns INVALID if the path is empty.
2.476 - GraphNode from() const {
2.477 - return empty() ? INVALID : gr->tail(edges[0]);
2.478 - }
2.479 - /// \brief End point of the path.
2.480 - ///
2.481 - /// End point of the path.
2.482 - /// Returns INVALID if the path is empty.
2.483 - GraphNode to() const {
2.484 - return empty() ? INVALID : gr->head(edges[length()-1]);
2.485 - }
2.486 -
2.487 - /// \brief Initializes node or edge iterator to point to the first
2.488 - /// node or edge.
2.489 - ///
2.490 - /// \sa nth
2.491 - template<typename It>
2.492 - It& first(It &i) const { return i=It(*this); }
2.493 -
2.494 - /// \brief Initializes node iterator to point to the node of a given index.
2.495 - NodeIt& nth(NodeIt &i, int n) const {
2.496 - if( DM::range_check && (n<0 || n>int(length())) )
2.497 - fault("UndirPath::nth: index out of range");
2.498 - return i=NodeIt(*this, n);
2.499 - }
2.500 -
2.501 - /// \brief Initializes edge iterator to point to the edge of a given index.
2.502 - EdgeIt& nth(EdgeIt &i, int n) const {
2.503 - if( DM::range_check && (n<0 || n>=int(length())) )
2.504 - fault("UndirPath::nth: index out of range");
2.505 - return i=EdgeIt(*this, n);
2.506 - }
2.507 -
2.508 - /// Checks validity of a node or edge iterator.
2.509 - template<typename It>
2.510 - static
2.511 - bool valid(const It &i) { return i.valid(); }
2.512 -
2.513 - /// Steps the given node or edge iterator.
2.514 - template<typename It>
2.515 - static
2.516 - It& next(It &e) {
2.517 - if( DM::range_check && !e.valid() )
2.518 - fault("UndirPath::next() on invalid iterator");
2.519 - return ++e;
2.520 - }
2.521 -
2.522 - /// \brief Returns node iterator pointing to the head node of the
2.523 - /// given edge iterator.
2.524 - NodeIt head(const EdgeIt& e) const {
2.525 - if( DM::range_check && !e.valid() )
2.526 - fault("UndirPath::head() on invalid iterator");
2.527 - return NodeIt(*this, e.idx+1);
2.528 - }
2.529 -
2.530 - /// \brief Returns node iterator pointing to the tail node of the
2.531 - /// given edge iterator.
2.532 - NodeIt tail(const EdgeIt& e) const {
2.533 - if( DM::range_check && !e.valid() )
2.534 - fault("UndirPath::tail() on invalid iterator");
2.535 - return NodeIt(*this, e.idx);
2.536 - }
2.537 -
2.538 -
2.539 -
2.540 - /**
2.541 - * \brief Iterator class to iterate on the edges of the paths
2.542 - *
2.543 - * \ingroup paths
2.544 - * This class is used to iterate on the edges of the paths
2.545 - *
2.546 - * Of course it converts to Graph::Edge
2.547 - *
2.548 - * \todo Its interface differs from the standard edge iterator.
2.549 - * Yes, it shouldn't.
2.550 - */
2.551 - class EdgeIt {
2.552 - friend class UndirPath;
2.553 -
2.554 - int idx;
2.555 - const UndirPath *p;
2.556 - public:
2.557 - /// Default constructor
2.558 - EdgeIt() {}
2.559 - /// Invalid constructor
2.560 - EdgeIt(Invalid) : idx(-1), p(0) {}
2.561 - /// Constructor with starting point
2.562 - EdgeIt(const UndirPath &_p, int _idx = 0) :
2.563 - idx(_idx), p(&_p) { validate(); }
2.564 -
2.565 - ///Validity check
2.566 - bool valid() const { return idx!=-1; }
2.567 -
2.568 - ///Conversion to Graph::Edge
2.569 - operator GraphEdge () const {
2.570 - return valid() ? p->edges[idx] : INVALID;
2.571 - }
2.572 - /// Next edge
2.573 - EdgeIt& operator++() { ++idx; validate(); return *this; }
2.574 -
2.575 - /// Comparison operator
2.576 - bool operator==(const EdgeIt& e) const { return idx==e.idx; }
2.577 - /// Comparison operator
2.578 - bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
2.579 - /// Comparison operator
2.580 - bool operator<(const EdgeIt& e) const { return idx<e.idx; }
2.581 -
2.582 - private:
2.583 - // FIXME: comparison between signed and unsigned...
2.584 - // Jo ez igy? Vagy esetleg legyen a length() int?
2.585 - void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
2.586 - };
2.587 -
2.588 - /**
2.589 - * \brief Iterator class to iterate on the nodes of the paths
2.590 - *
2.591 - * \ingroup paths
2.592 - * This class is used to iterate on the nodes of the paths
2.593 - *
2.594 - * Of course it converts to Graph::Node
2.595 - *
2.596 - * \todo Its interface differs from the standard node iterator.
2.597 - * Yes, it shouldn't.
2.598 - */
2.599 - class NodeIt {
2.600 - friend class UndirPath;
2.601 -
2.602 - int idx;
2.603 - const UndirPath *p;
2.604 - public:
2.605 - /// Default constructor
2.606 - NodeIt() {}
2.607 - /// Invalid constructor
2.608 - NodeIt(Invalid) : idx(-1), p(0) {}
2.609 - /// Constructor with starting point
2.610 - NodeIt(const UndirPath &_p, int _idx = 0) :
2.611 - idx(_idx), p(&_p) { validate(); }
2.612 -
2.613 - ///Validity check
2.614 - bool valid() const { return idx!=-1; }
2.615 -
2.616 - ///Conversion to Graph::Node
2.617 - operator const GraphNode& () const {
2.618 - if(idx >= p->length())
2.619 - return p->to();
2.620 - else if(idx >= 0)
2.621 - return p->gr->tail(p->edges[idx]);
2.622 - else
2.623 - return INVALID;
2.624 - }
2.625 - /// Next node
2.626 - NodeIt& operator++() { ++idx; validate(); return *this; }
2.627 -
2.628 - /// Comparison operator
2.629 - bool operator==(const NodeIt& e) const { return idx==e.idx; }
2.630 - /// Comparison operator
2.631 - bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
2.632 - /// Comparison operator
2.633 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
2.634 -
2.635 - private:
2.636 - void validate() { if( size_t(idx) > p->length() ) idx=-1; }
2.637 - };
2.638 -
2.639 - friend class Builder;
2.640 -
2.641 - /**
2.642 - * \brief Class to build paths
2.643 - *
2.644 - * \ingroup paths
2.645 - * This class is used to fill a path with edges.
2.646 - *
2.647 - * You can push new edges to the front and to the back of the path in
2.648 - * arbitrary order then you should commit these changes to the graph.
2.649 - *
2.650 - * Fundamentally, for most "Paths" (classes fulfilling the
2.651 - * PathConcept) while the builder is active (after the first modifying
2.652 - * operation and until the commit()) the original Path is in a
2.653 - * "transitional" state (operations ot it have undefined result). But
2.654 - * in the case of UndirPath the original path is unchanged until the
2.655 - * commit. However we don't recomend that you use this feature.
2.656 - */
2.657 - class Builder {
2.658 - UndirPath &P;
2.659 - Container front, back;
2.660 -
2.661 - public:
2.662 - ///\param _P the path you want to fill in.
2.663 - ///
2.664 - Builder(UndirPath &_P) : P(_P) {}
2.665 -
2.666 - /// Sets the starting node of the path.
2.667 -
2.668 - /// Sets the starting node of the path. Edge added to the path
2.669 - /// afterwards have to be incident to this node.
2.670 - /// It should be called iff the path is empty and before any call to
2.671 - /// \ref pushFront() or \ref pushBack()
2.672 - void setStartNode(const GraphNode &) {}
2.673 -
2.674 - ///Push a new edge to the front of the path
2.675 -
2.676 - ///Push a new edge to the front of the path.
2.677 - ///\sa setStartNode
2.678 - void pushFront(const GraphEdge& e) {
2.679 - if( DM::consistensy_check && !empty() && P.gr->head(e)!=from() ) {
2.680 - fault("UndirPath::Builder::pushFront: nonincident edge");
2.681 - }
2.682 - front.push_back(e);
2.683 - }
2.684 -
2.685 - ///Push a new edge to the back of the path
2.686 -
2.687 - ///Push a new edge to the back of the path.
2.688 - ///\sa setStartNode
2.689 - void pushBack(const GraphEdge& e) {
2.690 - if( DM::consistensy_check && !empty() && P.gr->tail(e)!=to() ) {
2.691 - fault("UndirPath::Builder::pushBack: nonincident edge");
2.692 - }
2.693 - back.push_back(e);
2.694 - }
2.695 -
2.696 - ///Commit the changes to the path.
2.697 - void commit() {
2.698 - if( !(front.empty() && back.empty()) ) {
2.699 - Container tmp;
2.700 - tmp.reserve(front.size()+back.size()+P.length());
2.701 - tmp.insert(tmp.end(), front.rbegin(), front.rend());
2.702 - tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
2.703 - tmp.insert(tmp.end(), back.begin(), back.end());
2.704 - P.edges.swap(tmp);
2.705 - front.clear();
2.706 - back.clear();
2.707 - }
2.708 - }
2.709 -
2.710 - // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
2.711 - // Hogy kenyelmes egy ilyet hasznalni?
2.712 -
2.713 - ///Reserve storage for the builder in advance.
2.714 -
2.715 - ///If you know an reasonable upper bound of the number of the edges
2.716 - ///to add, using this function you can speed up the building.
2.717 - void reserve(size_t r) {
2.718 - front.reserve(r);
2.719 - back.reserve(r);
2.720 - }
2.721 -
2.722 - private:
2.723 - bool empty() {
2.724 - return front.empty() && back.empty() && P.empty();
2.725 - }
2.726 -
2.727 - GraphNode from() const {
2.728 - if( ! front.empty() )
2.729 - return P.gr->tail(front[front.size()-1]);
2.730 - else if( ! P.empty() )
2.731 - return P.gr->tail(P.edges[0]);
2.732 - else if( ! back.empty() )
2.733 - return P.gr->tail(back[0]);
2.734 - else
2.735 - return INVALID;
2.736 - }
2.737 - GraphNode to() const {
2.738 - if( ! back.empty() )
2.739 - return P.gr->head(back[back.size()-1]);
2.740 - else if( ! P.empty() )
2.741 - return P.gr->head(P.edges[P.length()-1]);
2.742 - else if( ! front.empty() )
2.743 - return P.gr->head(front[0]);
2.744 - else
2.745 - return INVALID;
2.746 - }
2.747 -
2.748 - };
2.749 -
2.750 - };
2.751 -
2.752 -
2.753 -
2.754 -
2.755 -
2.756 -
2.757 -
2.758 -
2.759 -
2.760 -
2.761 - /**********************************************************************/
2.762 -
2.763 -
2.764 - /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata
2.765 - elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */
2.766 -
2.767 - template<typename Graph>
2.768 - class DynamicPath {
2.769 -
2.770 - public:
2.771 - typedef typename Graph::Edge GraphEdge;
2.772 - typedef typename Graph::Node GraphNode;
2.773 - class NodeIt;
2.774 - class EdgeIt;
2.775 -
2.776 - protected:
2.777 - Graph& G;
2.778 - // FIXME: ehelyett eleg lenne tarolni ket boolt: a ket szelso el
2.779 - // iranyitasat:
2.780 - GraphNode _first, _last;
2.781 - typedef std::deque<GraphEdge> Container;
2.782 - Container edges;
2.783 -
2.784 - public:
2.785 -
2.786 - DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {}
2.787 -
2.788 - /// Subpath defined by two nodes.
2.789 - /// Nodes may be in reversed order, then
2.790 - /// we contstruct the reversed path.
2.791 - DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b);
2.792 - /// Subpath defined by two edges. Contains edges in [a,b)
2.793 - /// It is an error if the two edges are not in order!
2.794 - DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b);
2.795 -
2.796 - size_t length() const { return edges.size(); }
2.797 - GraphNode from() const { return _first; }
2.798 - GraphNode to() const { return _last; }
2.799 -
2.800 - NodeIt& first(NodeIt &n) const { return nth(n, 0); }
2.801 - EdgeIt& first(EdgeIt &e) const { return nth(e, 0); }
2.802 - template<typename It>
2.803 - It first() const {
2.804 - It e;
2.805 - first(e);
2.806 - return e;
2.807 - }
2.808 -
2.809 - NodeIt& nth(NodeIt &, size_t) const;
2.810 - EdgeIt& nth(EdgeIt &, size_t) const;
2.811 - template<typename It>
2.812 - It nth(size_t n) const {
2.813 - It e;
2.814 - nth(e, n);
2.815 - return e;
2.816 - }
2.817 -
2.818 - bool valid(const NodeIt &n) const { return n.idx <= length(); }
2.819 - bool valid(const EdgeIt &e) const { return e.it < edges.end(); }
2.820 -
2.821 - bool isForward(const EdgeIt &e) const { return e.forw; }
2.822 -
2.823 - /// index of a node on the path. Returns length+2 for the invalid NodeIt
2.824 - int index(const NodeIt &n) const { return n.idx; }
2.825 - /// index of an edge on the path. Returns length+1 for the invalid EdgeIt
2.826 - int index(const EdgeIt &e) const { return e.it - edges.begin(); }
2.827 -
2.828 - EdgeIt& next(EdgeIt &e) const;
2.829 - NodeIt& next(NodeIt &n) const;
2.830 - template <typename It>
2.831 - It getNext(It it) const {
2.832 - It tmp(it); return next(tmp);
2.833 - }
2.834 -
2.835 - // A path is constructed using the following four functions.
2.836 - // They return false if the requested operation is inconsistent
2.837 - // with the path constructed so far.
2.838 - // If your path has only one edge you MUST set either "from" or "to"!
2.839 - // So you probably SHOULD call it in any case to be safe (and check the
2.840 - // returned value to check if your path is consistent with your idea).
2.841 - bool pushFront(const GraphEdge &e);
2.842 - bool pushBack(const GraphEdge &e);
2.843 - bool setFrom(const GraphNode &n);
2.844 - bool setTo(const GraphNode &n);
2.845 -
2.846 - // WARNING: these two functions return the head/tail of an edge with
2.847 - // respect to the direction of the path!
2.848 - // So G.head(P.graphEdge(e)) == P.graphNode(P.head(e)) holds only if
2.849 - // P.forward(e) is true (or the edge is a loop)!
2.850 - NodeIt head(const EdgeIt& e) const;
2.851 - NodeIt tail(const EdgeIt& e) const;
2.852 -
2.853 - // FIXME: ezeknek valami jobb nev kellene!!!
2.854 - GraphEdge graphEdge(const EdgeIt& e) const;
2.855 - GraphNode graphNode(const NodeIt& n) const;
2.856 -
2.857 -
2.858 - /*** Iterator classes ***/
2.859 - class EdgeIt {
2.860 - friend class DynamicPath;
2.861 -
2.862 - typename Container::const_iterator it;
2.863 - bool forw;
2.864 - public:
2.865 - // FIXME: jarna neki ilyen is...
2.866 - // EdgeIt(Invalid);
2.867 -
2.868 - bool forward() const { return forw; }
2.869 -
2.870 - bool operator==(const EdgeIt& e) const { return it==e.it; }
2.871 - bool operator!=(const EdgeIt& e) const { return it!=e.it; }
2.872 - bool operator<(const EdgeIt& e) const { return it<e.it; }
2.873 - };
2.874 -
2.875 - class NodeIt {
2.876 - friend class DynamicPath;
2.877 -
2.878 - size_t idx;
2.879 - bool tail; // Is this node the tail of the edge with same idx?
2.880 -
2.881 - public:
2.882 - // FIXME: jarna neki ilyen is...
2.883 - // NodeIt(Invalid);
2.884 -
2.885 - bool operator==(const NodeIt& n) const { return idx==n.idx; }
2.886 - bool operator!=(const NodeIt& n) const { return idx!=n.idx; }
2.887 - bool operator<(const NodeIt& n) const { return idx<n.idx; }
2.888 - };
2.889 -
2.890 - private:
2.891 - bool edgeIncident(const GraphEdge &e, const GraphNode &a,
2.892 - GraphNode &b);
2.893 - bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f);
2.894 - };
2.895 -
2.896 - template<typename Gr>
2.897 - typename DynamicPath<Gr>::EdgeIt&
2.898 - DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const {
2.899 - if( e.it == edges.end() )
2.900 - return e;
2.901 -
2.902 - GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) );
2.903 - ++e.it;
2.904 -
2.905 - // Invalid edgeit is always forward :)
2.906 - if( e.it == edges.end() ) {
2.907 - e.forw = true;
2.908 - return e;
2.909 - }
2.910 -
2.911 - e.forw = ( G.tail(*e.it) == common_node );
2.912 - return e;
2.913 - }
2.914 -
2.915 - template<typename Gr>
2.916 - typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const {
2.917 - if( n.idx >= length() ) {
2.918 - // FIXME: invalid
2.919 - n.idx = length()+1;
2.920 - return n;
2.921 - }
2.922 -
2.923 -
2.924 - GraphNode next_node = ( n.tail ? G.head(edges[n.idx]) :
2.925 - G.tail(edges[n.idx]) );
2.926 - ++n.idx;
2.927 - if( n.idx < length() ) {
2.928 - n.tail = ( next_node == G.tail(edges[n.idx]) );
2.929 - }
2.930 - else {
2.931 - n.tail = true;
2.932 - }
2.933 -
2.934 - return n;
2.935 - }
2.936 -
2.937 - template<typename Gr>
2.938 - bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a,
2.939 - GraphNode &b) {
2.940 - if( G.tail(e) == a ) {
2.941 - b=G.head(e);
2.942 - return true;
2.943 - }
2.944 - if( G.head(e) == a ) {
2.945 - b=G.tail(e);
2.946 - return true;
2.947 - }
2.948 - return false;
2.949 - }
2.950 -
2.951 - template<typename Gr>
2.952 - bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e,
2.953 - const GraphEdge &f) {
2.954 - if( edgeIncident(f, G.tail(e), _last) ) {
2.955 - _first = G.head(e);
2.956 - return true;
2.957 - }
2.958 - if( edgeIncident(f, G.head(e), _last) ) {
2.959 - _first = G.tail(e);
2.960 - return true;
2.961 - }
2.962 - return false;
2.963 - }
2.964 -
2.965 - template<typename Gr>
2.966 - bool DynamicPath<Gr>::pushFront(const GraphEdge &e) {
2.967 - if( G.valid(_first) ) {
2.968 - if( edgeIncident(e, _first, _first) ) {
2.969 - edges.push_front(e);
2.970 - return true;
2.971 - }
2.972 - else
2.973 - return false;
2.974 - }
2.975 - else if( length() < 1 || connectTwoEdges(e, edges[0]) ) {
2.976 - edges.push_front(e);
2.977 - return true;
2.978 - }
2.979 - else
2.980 - return false;
2.981 - }
2.982 -
2.983 - template<typename Gr>
2.984 - bool DynamicPath<Gr>::pushBack(const GraphEdge &e) {
2.985 - if( G.valid(_last) ) {
2.986 - if( edgeIncident(e, _last, _last) ) {
2.987 - edges.push_back(e);
2.988 - return true;
2.989 - }
2.990 - else
2.991 - return false;
2.992 - }
2.993 - else if( length() < 1 || connectTwoEdges(edges[0], e) ) {
2.994 - edges.push_back(e);
2.995 - return true;
2.996 - }
2.997 - else
2.998 - return false;
2.999 - }
2.1000 -
2.1001 -
2.1002 - template<typename Gr>
2.1003 - bool DynamicPath<Gr>::setFrom(const GraphNode &n) {
2.1004 - if( G.valid(_first) ) {
2.1005 - return _first == n;
2.1006 - }
2.1007 - else {
2.1008 - if( length() > 0) {
2.1009 - if( edgeIncident(edges[0], n, _last) ) {
2.1010 - _first = n;
2.1011 - return true;
2.1012 - }
2.1013 - else return false;
2.1014 - }
2.1015 - else {
2.1016 - _first = _last = n;
2.1017 - return true;
2.1018 - }
2.1019 - }
2.1020 - }
2.1021 -
2.1022 - template<typename Gr>
2.1023 - bool DynamicPath<Gr>::setTo(const GraphNode &n) {
2.1024 - if( G.valid(_last) ) {
2.1025 - return _last == n;
2.1026 - }
2.1027 - else {
2.1028 - if( length() > 0) {
2.1029 - if( edgeIncident(edges[0], n, _first) ) {
2.1030 - _last = n;
2.1031 - return true;
2.1032 - }
2.1033 - else return false;
2.1034 - }
2.1035 - else {
2.1036 - _first = _last = n;
2.1037 - return true;
2.1038 - }
2.1039 - }
2.1040 - }
2.1041 -
2.1042 -
2.1043 - template<typename Gr>
2.1044 - typename DynamicPath<Gr>::NodeIt
2.1045 - DynamicPath<Gr>::tail(const EdgeIt& e) const {
2.1046 - NodeIt n;
2.1047 -
2.1048 - if( e.it == edges.end() ) {
2.1049 - // FIXME: invalid-> invalid
2.1050 - n.idx = length() + 1;
2.1051 - n.tail = true;
2.1052 - return n;
2.1053 - }
2.1054 -
2.1055 - n.idx = e.it-edges.begin();
2.1056 - n.tail = e.forw;
2.1057 - return n;
2.1058 - }
2.1059 -
2.1060 - template<typename Gr>
2.1061 - typename DynamicPath<Gr>::NodeIt
2.1062 - DynamicPath<Gr>::head(const EdgeIt& e) const {
2.1063 - if( e.it == edges.end()-1 ) {
2.1064 - return _last;
2.1065 - }
2.1066 -
2.1067 - EdgeIt next_edge = e;
2.1068 - next(next_edge);
2.1069 - return tail(next_edge);
2.1070 - }
2.1071 -
2.1072 - template<typename Gr>
2.1073 - typename DynamicPath<Gr>::GraphEdge
2.1074 - DynamicPath<Gr>::graphEdge(const EdgeIt& e) const {
2.1075 - if( e.it != edges.end() ) {
2.1076 - return *e.it;
2.1077 - }
2.1078 - else {
2.1079 - return INVALID;
2.1080 - }
2.1081 - }
2.1082 -
2.1083 - template<typename Gr>
2.1084 - typename DynamicPath<Gr>::GraphNode
2.1085 - DynamicPath<Gr>::graphNode(const NodeIt& n) const {
2.1086 - if( n.idx < length() ) {
2.1087 - return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]);
2.1088 - }
2.1089 - else if( n.idx == length() ) {
2.1090 - return _last;
2.1091 - }
2.1092 - else {
2.1093 - return INVALID;
2.1094 - }
2.1095 - }
2.1096 -
2.1097 - template<typename Gr>
2.1098 - typename DynamicPath<Gr>::EdgeIt&
2.1099 - DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const {
2.1100 - if( k>=length() ) {
2.1101 - // FIXME: invalid EdgeIt
2.1102 - e.it = edges.end();
2.1103 - e.forw = true;
2.1104 - return e;
2.1105 - }
2.1106 -
2.1107 - e.it = edges.begin()+k;
2.1108 - if(k==0) {
2.1109 - e.forw = ( G.tail(*e.it) == _first );
2.1110 - }
2.1111 - else {
2.1112 - e.forw = ( G.tail(*e.it) == G.tail(edges[k-1]) ||
2.1113 - G.tail(*e.it) == G.head(edges[k-1]) );
2.1114 - }
2.1115 - return e;
2.1116 - }
2.1117 -
2.1118 - template<typename Gr>
2.1119 - typename DynamicPath<Gr>::NodeIt&
2.1120 - DynamicPath<Gr>::nth(NodeIt &n, size_t k) const {
2.1121 - if( k>length() ) {
2.1122 - // FIXME: invalid NodeIt
2.1123 - n.idx = length()+1;
2.1124 - n.tail = true;
2.1125 - return n;
2.1126 - }
2.1127 - if( k==length() ) {
2.1128 - n.idx = length();
2.1129 - n.tail = true;
2.1130 - return n;
2.1131 - }
2.1132 - n = tail(nth<EdgeIt>(k));
2.1133 - return n;
2.1134 - }
2.1135 -
2.1136 - // Reszut konstruktorok:
2.1137 -
2.1138 -
2.1139 - template<typename Gr>
2.1140 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a,
2.1141 - const EdgeIt &b) :
2.1142 - G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up!
2.1143 - {
2.1144 - if( G.valid(P._first) && a.it < P.edges.end() ) {
2.1145 - _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) );
2.1146 - if( b.it < P.edges.end() ) {
2.1147 - _last = ( b.forw ? G.tail(*b.it) : G.head(*b.it) );
2.1148 - }
2.1149 - else {
2.1150 - _last = P._last;
2.1151 - }
2.1152 - }
2.1153 - }
2.1154 -
2.1155 - template<typename Gr>
2.1156 - DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a,
2.1157 - const NodeIt &b) : G(P.G)
2.1158 - {
2.1159 - if( !P.valid(a) || !P.valid(b) )
2.1160 - return;
2.1161 -
2.1162 - int ai = a.idx, bi = b.idx;
2.1163 - if( bi<ai )
2.1164 - std::swap(ai,bi);
2.1165 -
2.1166 - edges.resize(bi-ai);
2.1167 - copy(P.edges.begin()+ai, P.edges.begin()+bi, edges.begin());
2.1168 -
2.1169 - _first = P.graphNode(a);
2.1170 - _last = P.graphNode(b);
2.1171 - }
2.1172 -
2.1173 - ///@}
2.1174 -
2.1175 -} // namespace hugo
2.1176 -
2.1177 -#endif // HUGO_PATH_H
3.1 --- a/src/work/klao/path_test.cc Sun Sep 19 12:45:35 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,160 +0,0 @@
3.4 -#include <string>
3.5 -#include <iostream>
3.6 -
3.7 -#include <path.h>
3.8 -#include <list_graph.h>
3.9 -
3.10 -using namespace std;
3.11 -using namespace hugo;
3.12 -
3.13 -bool passed = true;
3.14 -
3.15 -void check(bool rc) {
3.16 - passed = passed && rc;
3.17 - if(!rc) {
3.18 - cout << "Test failed!" << endl;
3.19 - }
3.20 -}
3.21 -
3.22 -#ifdef DEBUG
3.23 -const bool debug = true;
3.24 -#else
3.25 -const bool debug = false;
3.26 -#endif
3.27 -
3.28 -
3.29 -int main() {
3.30 -
3.31 - try {
3.32 -
3.33 - typedef ListGraph::Node Node;
3.34 - typedef ListGraph::Edge Edge;
3.35 -
3.36 - ListGraph G;
3.37 -
3.38 - Node s=G.addNode();
3.39 - Node v1=G.addNode();
3.40 - Node v2=G.addNode();
3.41 - Node v3=G.addNode();
3.42 - Node v4=G.addNode();
3.43 - Node t=G.addNode();
3.44 -
3.45 - Edge e1 = G.addEdge(s, v1);
3.46 - Edge e2 = G.addEdge(s, v2);
3.47 - Edge e3 = G.addEdge(v1, v2);
3.48 - Edge e4 = G.addEdge(v2, v1);
3.49 - Edge e5 = G.addEdge(v1, v3);
3.50 - Edge e6 = G.addEdge(v3, v2);
3.51 - Edge e7 = G.addEdge(v2, v4);
3.52 - Edge e8 = G.addEdge(v4, v3);
3.53 - Edge e9 = G.addEdge(v3, t);
3.54 - Edge e10 = G.addEdge(v4, t);
3.55 -
3.56 - bool rc;
3.57 -
3.58 - {
3.59 - cout << "\n\n\nDirPath tesztelese...\n";
3.60 -
3.61 -
3.62 - cout << "Ures path letrehozasa" << endl;
3.63 - typedef DirPath<ListGraph> DPath;
3.64 - DPath P(G);
3.65 -
3.66 - cout << "P.length() == " << P.length() << endl;
3.67 - check(P.length() == 0);
3.68 -
3.69 - cout << "P.from() valid? " << G.valid(P.from()) << endl;
3.70 - check(! G.valid(P.from()));
3.71 -
3.72 - {
3.73 - cout << "Builder objektum letrehozasa" << endl;
3.74 - DPath::Builder B(P);
3.75 -
3.76 - cout << "Hozzaadunk az elejehez ket elet..." << endl;
3.77 - B.pushFront(e6);
3.78 - B.pushFront(e5);
3.79 - cout << "P.length() == " << P.length() << endl;
3.80 - check(P.length() == 0);
3.81 -
3.82 - cout << "Commitolunk..." << endl;
3.83 - B.commit();
3.84 -
3.85 - cout << "P.length() == " << P.length() << endl;
3.86 - check(P.length() == 2);
3.87 - cout << "P.from() valid? " << G.valid(P.from()) << endl;
3.88 - check(G.valid(P.from()));
3.89 - cout << "P.from()==v1 ? " << (P.from()==v1) << endl;
3.90 - check(P.from() == v1);
3.91 -
3.92 - // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
3.93 - // de legalabb valami:
3.94 -#ifdef DEBUG
3.95 - cout << "Hozzaadunk az elejehez egy nem illeszkedo elet..." << endl;
3.96 - rc = false;
3.97 - try {
3.98 - B.pushFront(e3);
3.99 - }
3.100 - catch(const Exception &e) {
3.101 - cout << "E: " << e.what() << endl;
3.102 - rc = true;
3.103 - }
3.104 - check(rc);
3.105 -#endif
3.106 -
3.107 - cout << "Hozzaadunk a vegehez ket elet..." << endl;
3.108 - B.pushBack(e7);
3.109 - B.pushBack(e8);
3.110 - cout << "P.length() == " << P.length() << endl;
3.111 - check(P.length() == 2);
3.112 -
3.113 - cout << "Es commitolunk...\n";
3.114 - B.commit();
3.115 - }
3.116 - cout << "P.length() == " << P.length() << endl;
3.117 - check(P.length() == 4);
3.118 - cout << "P.to()==v3 ? " << (P.to()==v3) << endl;
3.119 - check(P.to() == v3);
3.120 -
3.121 - cout << "Vegigiteralunk az eleken." << endl;
3.122 - typedef DPath::NodeIt NodeIt;
3.123 - typedef DPath::EdgeIt EdgeIt;
3.124 - EdgeIt e;
3.125 - int i=1;
3.126 - for(P.first(e); P.valid(e); P.next(e), ++i) {
3.127 - cout << i << ". el: " << e << endl;
3.128 - }
3.129 -
3.130 -
3.131 - // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni,
3.132 - // de legalabb valami:
3.133 - rc = false;
3.134 - try {
3.135 - cout << "Setting an edgeiter to a nonexistant edge." << endl;
3.136 - P.nth(e,134);
3.137 - rc = !debug;
3.138 - }
3.139 - catch(const Exception &e) {
3.140 - cout << "E: " << e.what() << endl;
3.141 - rc = debug;
3.142 - }
3.143 - check(rc);
3.144 - }
3.145 -
3.146 -
3.147 - }
3.148 - catch(const std::exception &e) {
3.149 - cout << "Uncaught exception: " << e.what() << endl;
3.150 - return 1;
3.151 - }
3.152 - catch(...) {
3.153 - cout << "Something horrible happened: an exception which isn't "
3.154 - << "std::exception" << endl;
3.155 - return 2;
3.156 - }
3.157 -
3.158 -
3.159 - cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
3.160 - << endl;
3.161 -
3.162 - return passed ? 0 : 1;
3.163 -}