Changeset 493:bbd1db03f0fe in lemon0.x for src/work/klao
 Timestamp:
 04/30/04 03:59:15 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@651
 Location:
 src/work/klao
 Files:

 1 added
 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/klao/path.h
r450 r493 1 1 // * c++ * // 2 2 3 /// ingroup datas3 ///\ingroup datas 4 4 ///\file 5 ///\brief Class for representing paths in graphs.5 ///\brief Classes for representing paths in graphs. 6 6 7 7 #ifndef HUGO_PATH_H … … 13 13 14 14 #include <invalid.h> 15 #include <error.h> 16 #include <debug.h> 15 17 16 18 namespace hugo { … … 19 21 /// @{ 20 22 21 ///A container for directed paths 22 23 ///\param Graph The graph type in which the path is. 24 /// 25 ///In a sense, the path can be treated as a graph, for is has \c NodeIt 26 ///and \c EdgeIt with the same usage. These types converts to the \c Node 27 ///and \c Edge of the original graph. 28 ///\todo How to clear a path? 29 ///\todo Clarify the consistency checks to do. 30 template<typename Graph> 23 24 //! \brief A structure for representing directed path in a graph. 25 //! 26 //! \param Graph The graph type in which the path is. 27 //! \param DM DebugMode, defaults to DefaultDebugMode. 28 //! 29 //! In a sense, the path can be treated as a graph, for is has \c NodeIt 30 //! and \c EdgeIt with the same usage. These types converts to the \c Node 31 //! and \c Edge of the original graph. 32 //! 33 //! \todo Thoroughfully check all the range and consistency tests. 34 template<typename Graph, typename DM = DefaultDebugMode> 31 35 class DirPath { 32 36 public: … … 43 47 public: 44 48 45 /// Constructor46 47 49 /// \param _G The graph in which the path is. 48 50 /// 49 51 DirPath(const Graph &_G) : gr(&_G) {} 50 52 53 /// \brief Subpath constructor. 54 /// 51 55 /// Subpath defined by two nodes. 52 56 /// \warning It is an error if the two edges are not in order! 57 /// \todo Implement! 53 58 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); 59 /// \brief Subpath constructor. 60 /// 54 61 /// Subpath defined by two edges. Contains edges in [a,b) 55 62 /// \warning It is an error if the two edges are not in order! 63 /// \todo Implement! 56 64 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); 57 65 66 /// Length of the path. 58 67 size_t length() const { return edges.size(); } 68 /// Returns whether the path is empty. 59 69 bool empty() const { return edges.empty(); } 70 71 /// Resets the path to an empty path. 72 void clear() { edges.clear(); } 73 74 /// \brief Starting point of the path. 75 /// 76 /// Starting point of the path. 77 /// Returns INVALID if the path is empty. 60 78 GraphNode from() const { 61 79 return empty() ? INVALID : gr>tail(edges[0]); 62 80 } 81 /// \brief End point of the path. 82 /// 83 /// End point of the path. 84 /// Returns INVALID if the path is empty. 63 85 GraphNode to() const { 64 86 return empty() ? INVALID : gr>head(edges[length()1]); 65 87 } 66 88 89 /// \brief Initializes node or edge iterator to point to the first 90 /// node or edge. 91 /// 92 /// \sa nth 67 93 template<typename It> 68 94 It& first(It &i) const { return i=It(*this); } 69 95 96 /// \brief Initializes node or edge iterator to point to the node or edge 97 /// of a given index. 70 98 template<typename It> 71 It& nth(It &i, int n) const { return i=It(*this, n); } 72 99 It& nth(It &i, int n) const { 100 // FIXME: this test should be different for NodeIt and EdgeIt: 101 if( DM::range_check && (n<0  n>int(length())) ) 102 fault("DirPath::nth: index out of range"); 103 return i=It(*this, n); 104 } 105 106 /// Checks validity of a node or edge iterator. 73 107 template<typename It> 74 108 bool valid(const It &i) const { return i.valid(); } 75 109 110 /// Steps the given node or edge iterator. 76 111 template<typename It> 77 It& next(It &e) const { return ++e; } 78 79 /// \todo ! 80 NodeIt head(const EdgeIt& e) const; 81 NodeIt tail(const EdgeIt& e) const; 112 It& next(It &e) const { 113 if( DM::range_check && !e.valid() ) 114 fault("DirPath::next() on invalid iterator"); 115 return ++e; 116 } 117 118 /// \brief Returns node iterator pointing to the head node of the 119 /// given edge iterator. 120 NodeIt head(const EdgeIt& e) const { 121 return NodeIt(*this, e.idx+1); 122 } 123 124 /// \brief Returns node iterator pointing to the tail node of the 125 /// given edge iterator. 126 NodeIt tail(const EdgeIt& e) const { 127 return NodeIt(*this, e.idx); 128 } 82 129 83 130 … … 144 191 friend class Builder; 145 192 146 ///Class to build paths 147 148 ///\ingroup datas 149 ///This class is used to build new paths. 150 ///You can push new edges to the front and to the back of the path in 151 ///arbitrary order the you can commit these changes to the graph. 152 ///\todo We must clarify when the path will be in "transitional" state. 193 /** 194 * \brief Class to build paths 195 * 196 * \ingroup datas 197 * This class is used to fill a path with edges. 198 * 199 * You can push new edges to the front and to the back of the path in 200 * arbitrary order the you can commit these changes to the graph. 201 * 202 * Fundamentally, for most "Paths" (classes fulfilling the 203 * PathConcept) while the builder is active (after the first modifying 204 * operation and until the commit()) the original Path is in a 205 * "transitional" state (operations ot it have undefined result). But 206 * in the case of DirPath the original path is unchanged until the 207 * commit. However we don't recomend that you use this feature. 208 */ 153 209 class Builder { 154 210 DirPath &P; 155 Container d;211 Container front, back; 156 212 157 213 public: 158 ///Constructor 159 160 ///\param _P the path you want to build. 214 ///\param _P the path you want to fill in. 161 215 /// 162 216 Builder(DirPath &_P) : P(_P) {} 163 217 164 ///Set the first node of the path.218 ///Sets the first node of the path. 165 219 166 ///Set the first node of the path. 167 ///If the path is empty, this must be call before any call of 168 ///\ref pushFront() or \ref pushBack() 169 void setFirst(const GraphNode &) { } 220 ///Sets the first node of the path. If the path is empty, this 221 ///function or setTo() have to be called before any call to \ref 222 ///pushFront() or \ref pushBack() 223 void setFrom(const GraphNode &) {} 224 225 ///Sets the last node of the path. 226 227 ///Sets the last node of the path. If the path is empty, this 228 ///function or setFrom() have to be called before any call of \ref 229 ///pushFront() or \ref pushBack() 230 void setTo(const GraphNode &) {} 170 231 171 232 ///Push a new edge to the front of the path 172 233 173 234 ///Push a new edge to the front of the path. 174 ///\sa setFirst() 175 bool pushFront(const GraphEdge& e) { 176 if( empty()  P.gr>head(e)==from() ) { 177 d.push_back(e); 178 return true; 235 ///\sa setTo 236 void pushFront(const GraphEdge& e) { 237 if( DM::consistensy_check && !empty() && P.gr>head(e)!=from() ) { 238 fault("DirPath::Builder::pushFront: nonincident edge"); 179 239 } 180 return false; 181 } 240 front.push_back(e); 241 } 242 182 243 ///Push a new edge to the back of the path 183 244 184 245 ///Push a new edge to the back of the path. 185 ///\sa setFirst() 186 bool pushBack(const GraphEdge& e) { 187 if( empty()  P.gr>tail(e)==to() ) { 188 P.edges.push_back(e); 189 return true; 246 ///\sa setFrom 247 void pushBack(const GraphEdge& e) { 248 if( DM::consistensy_check && !empty() && P.gr>tail(e)!=to() ) { 249 fault("DirPath::Builder::pushBack: nonincident edge"); 190 250 } 191 return false;251 back.push_back(e); 192 252 } 193 253 194 254 ///Commit the changes to the path. 195 255 void commit() { 196 if( !d.empty() ) { 197 P.edges.insert(P.edges.begin(), d.rbegin(), d.rend()); 198 d.clear(); 256 if( !(front.empty() && back.empty()) ) { 257 Container tmp; 258 tmp.reserve(front.size()+back.size()+P.length()); 259 tmp.insert(tmp.end(), front.rbegin(), front.rend()); 260 tmp.insert(tmp.end(), P.edges.begin(), P.edges.end()); 261 tmp.insert(tmp.end(), back.begin(), back.end()); 262 P.edges.swap(tmp); 263 front.clear(); 264 back.clear(); 199 265 } 200 266 } 201 267 202 ///Desctuctor 203 204 ///The desctuctor. 205 ///It commit also commit the changes. 206 ///\todo Is this what we want? 207 ~Builder() { commit(); } 268 // ///Desctuctor 269 270 // ///The desctuctor. 271 // ///It commit also commit the changes. 272 // ///\todo Is this what we want? 273 // Nope. Let's use commit() explicitly. 274 // ~Builder() { commit(); } 208 275 209 276 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? 210 277 // Hogy kenyelmes egy ilyet hasznalni? 211 278 void reserve(size_t r) { 212 d.reserve(r);213 P.edges.reserve(P.length()+r);279 front.reserve(r); 280 back.reserve(r); 214 281 } 215 282 216 283 private: 217 bool empty() { return d.empty() && P.empty(); } 284 bool empty() { 285 return front.empty() && back.empty() && P.empty(); 286 } 218 287 219 288 GraphNode from() const { 220 if( ! d.empty() )221 return P.gr>tail( d[d.size()1]);289 if( ! front.empty() ) 290 return P.gr>tail(front[front.size()1]); 222 291 else if( ! P.empty() ) 223 292 return P.gr>tail(P.edges[0]); 293 else if( ! back.empty() ) 294 return P.gr>tail(back[0]); 224 295 else 225 296 return INVALID; 226 297 } 227 298 GraphNode to() const { 228 if( ! P.empty() ) 299 if( ! back.empty() ) 300 return P.gr>head(back[back.size()1]); 301 else if( ! P.empty() ) 229 302 return P.gr>head(P.edges[P.length()1]); 230 else if( ! d.empty() )231 return P.gr>head( d[0]);303 else if( ! front.empty() ) 304 return P.gr>head(front[0]); 232 305 else 233 306 return INVALID; 
src/work/klao/path_test.cc
r369 r493 17 17 } 18 18 19 #ifdef DEBUG 20 const bool debug = true; 21 #else 22 const bool debug = false; 23 #endif 24 25 19 26 int main() { 20 27 21 typedef ListGraph::Node Node; 22 typedef ListGraph::Edge Edge; 28 try { 23 29 24 ListGraph G; 30 typedef ListGraph::Node Node; 31 typedef ListGraph::Edge Edge; 25 32 26 Node s=G.addNode(); 27 Node v1=G.addNode(); 28 Node v2=G.addNode(); 29 Node v3=G.addNode(); 30 Node v4=G.addNode(); 31 Node t=G.addNode(); 33 ListGraph G; 34 35 Node s=G.addNode(); 36 Node v1=G.addNode(); 37 Node v2=G.addNode(); 38 Node v3=G.addNode(); 39 Node v4=G.addNode(); 40 Node t=G.addNode(); 32 41 33 Edge e1 = G.addEdge(s, v1);34 Edge e2 = G.addEdge(s, v2);35 Edge e3 = G.addEdge(v1, v2);36 Edge e4 = G.addEdge(v2, v1);37 Edge e5 = G.addEdge(v1, v3);38 Edge e6 = G.addEdge(v3, v2);39 Edge e7 = G.addEdge(v2, v4);40 Edge e8 = G.addEdge(v4, v3);41 Edge e9 = G.addEdge(v3, t);42 Edge e10 = G.addEdge(v4, t);42 Edge e1 = G.addEdge(s, v1); 43 Edge e2 = G.addEdge(s, v2); 44 Edge e3 = G.addEdge(v1, v2); 45 Edge e4 = G.addEdge(v2, v1); 46 Edge e5 = G.addEdge(v1, v3); 47 Edge e6 = G.addEdge(v3, v2); 48 Edge e7 = G.addEdge(v2, v4); 49 Edge e8 = G.addEdge(v4, v3); 50 Edge e9 = G.addEdge(v3, t); 51 Edge e10 = G.addEdge(v4, t); 43 52 44 bool rc;53 bool rc; 45 54 46 {47 cout << "DynamicPath tesztelese...\n";55 { 56 cout << "\n\n\nDirPath tesztelese...\n"; 48 57 49 cout << "Ures path letrehozasa" << endl;50 typedef DynamicPath<ListGraph> LPath;51 LPath P(G);52 58 53 cout << "P.length() == " << P.length() << endl; 54 check(P.length() == 0); 59 cout << "Ures path letrehozasa" << endl; 60 typedef DirPath<ListGraph> DPath; 61 DPath P(G); 55 62 56 cout << "P.from() valid? " << G.valid(P.from()) << endl;57 check(! G.valid(P.from()));63 cout << "P.length() == " << P.length() << endl; 64 check(P.length() == 0); 58 65 59 cout << "Hozzaadunk ket elet..." << endl; 60 check(P.pushBack(e1)); 61 check(P.pushBack(e3)); 62 cout << "P.length() == " << P.length() << endl; 63 check(P.length() == 2); 66 cout << "P.from() valid? " << G.valid(P.from()) << endl; 67 check(! G.valid(P.from())); 64 68 65 cout << "P.from() valid? " << G.valid(P.from()) << endl; 66 check(G.valid(P.from())); 67 68 cout << "P.from()==s ? " << (P.from()==s) << endl; 69 check(P.from() == s); 69 { 70 cout << "Builder objektum letrehozasa" << endl; 71 DPath::Builder B(P); 70 72 71 cout << "Hozzaadunk egy nem illeszkedo elt." << endl; 72 rc = P.pushBack(e8); 73 cout << "Sukerult: " << rc << endl; 74 check(!rc); 73 cout << "Hozzaadunk az elejehez ket elet..." << endl; 74 B.pushFront(e6); 75 B.pushFront(e5); 76 cout << "P.length() == " << P.length() << endl; 77 check(P.length() == 0); 78 79 cout << "Commitolunk..." << endl; 80 B.commit(); 75 81 76 cout << "Meg 3 el hozzaadasa, nem mind elore iranyu..." << endl; 77 check(P.pushBack(e6)); 78 check(P.pushBack(e8)); 79 check(P.pushBack(e10)); 82 cout << "P.length() == " << P.length() << endl; 83 check(P.length() == 2); 84 cout << "P.from() valid? " << G.valid(P.from()) << endl; 85 check(G.valid(P.from())); 86 cout << "P.from()==v1 ? " << (P.from()==v1) << endl; 87 check(P.from() == v1); 80 88 81 cout << "P.length() == " << P.length() << endl; 82 check(P.length() == 5); 89 // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni, 90 // de legalabb valami: 91 #ifdef DEBUG 92 cout << "Hozzaadunk az elejehez egy nem illeszkedo elet..." << endl; 93 rc = false; 94 try { 95 B.pushFront(e3); 96 } 97 catch(const Exception &e) { 98 cout << "E: " << e.what() << endl; 99 rc = true; 100 } 101 check(rc); 102 #endif 83 103 84 cout << "P.from()==s ? " << (P.from()==s) << endl; 85 check(P.from() == s); 86 cout << "P.to()==t ? " << (P.to()==t) << endl; 87 check(P.to() == t); 104 cout << "Hozzaadunk a vegehez ket elet..." << endl; 105 B.pushBack(e7); 106 B.pushBack(e8); 107 cout << "P.length() == " << P.length() << endl; 108 check(P.length() == 2); 109 110 cout << "Es commitolunk...\n"; 111 B.commit(); 112 } 113 cout << "P.length() == " << P.length() << endl; 114 check(P.length() == 4); 115 cout << "P.to()==v3 ? " << (P.to()==v3) << endl; 116 check(P.to() == v3); 88 117 89 cout << "Vegpont bellitasa: " << endl; 90 rc = P.setTo(v2); 91 cout << "Hibasra: " << rc << endl; 92 check(!rc); 93 rc = P.setTo(t); 94 cout << "Helyesre: " << rc << endl; 95 check(rc); 118 cout << "Vegigiteralunk az eleken." << endl; 119 typedef DPath::NodeIt NodeIt; 120 typedef DPath::EdgeIt EdgeIt; 121 EdgeIt e; 122 int i=1; 123 for(P.first(e); P.valid(e); P.next(e), ++i) { 124 cout << i << ". el: " << e << endl; 125 } 96 126 97 cout << "Elek iranyitasanak ellenorzese." << endl;98 cout << "El: " << e1 << ", G.tail(el): " << G.head(e1) << endl;99 check(G.tail(e1)==s);100 127 101 cout << "Vegigiteralunk az eleken." << endl; 102 typedef LPath::NodeIt NodeIt; 103 typedef LPath::EdgeIt EdgeIt; 104 EdgeIt e = P.first<EdgeIt>(); 105 int i=1; 106 for(; P.valid(e); P.next(e), ++i) { 107 cout << i << ". el: " << P.graphEdge(e) 108 << ", elore el? " << P.isForward(e) << endl; 109 if(i>=3 && i<5) 110 check(!P.isForward(e)); 111 else 112 check(P.isForward(e)); 128 // Na ja, ez igy nem igazi, mindket esetet le kene tesztelni, 129 // de legalabb valami: 130 rc = false; 131 try { 132 cout << "Setting an edgeiter to a nonexistant edge." << endl; 133 P.nth(e,134); 134 rc = !debug; 135 } 136 catch(const Exception &e) { 137 cout << "E: " << e.what() << endl; 138 rc = debug; 139 } 140 check(rc); 113 141 } 114 142 115 {116 cout << "Reszut letrehozasa: [2. el, 4. el)..." << endl;117 LPath P2(P, P.nth<EdgeIt>(1), P.nth<EdgeIt>(3));118 119 cout << "P2.length() == " << P2.length() << endl;120 check(P2.length() == 2);121 122 cout << "P2.from()==v1 ? " << (P2.from()==v1) << endl;123 check(P2.from() == v1);124 cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;125 check(P2.to() == v3);126 }127 {128 cout << "Reszut letrehozasa: [1. el, 6. el)..." << endl;129 LPath P2(P, P.nth<EdgeIt>(0), P.nth<EdgeIt>(5));130 131 cout << "P2.length() == " << P2.length() << endl;132 check(P2.length() == 5);133 134 cout << "P2.from()==s ? " << (P2.from()==s) << endl;135 check(P2.from() == s);136 cout << "P2.to()==t ? " << (P2.to()==t) << endl;137 check(P2.to() == t);138 }139 140 {141 cout << "Ket pont altal megadott reszut letrehozasa: [2. pont, 4. pont]..."142 << endl;143 LPath P2(P, P.nth<NodeIt>(1), P.nth<NodeIt>(3));144 145 cout << "P2.length() == " << P2.length() << endl;146 check(P2.length() == 2);147 148 cout << "P2.from()==v1 ? " << (P2.from()==v1) << endl;149 check(P2.from() == v1);150 cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;151 check(P2.to() == v3);152 }153 {154 cout << "Egy pontu reszut letrehozasa: [4. pont, 4. pont]..."155 << endl;156 LPath P2(P, P.nth<NodeIt>(3), P.nth<NodeIt>(3));157 158 cout << "P2.length() == " << P2.length() << endl;159 check(P2.length() == 0);160 161 cout << "P2.from()==v3 ? " << (P2.from()==v3) << endl;162 check(P2.from() == v3);163 cout << "P2.to()==v3 ? " << (P2.to()==v3) << endl;164 check(P2.to() == v3);165 }166 {167 cout << "Forditott ut letrehozasa: [6. pont, 1. pont]..."168 << endl;169 LPath P2(P, P.nth<NodeIt>(5), P.nth<NodeIt>(0));170 171 cout << "P2.length() == " << P2.length() << endl;172 check(P2.length() == 5);173 174 cout << "P2.from()==t ? " << (P2.from()==t) << endl;175 check(P2.from() == t);176 cout << "P2.to()==s ? " << (P2.to()==s) << endl;177 check(P2.to() == s);178 }179 143 180 144 } 145 catch(const std::exception &e) { 146 cout << "Uncaught exception: " << e.what() << endl; 147 return 1; 148 } 149 catch(...) { 150 cout << "Something horrible happened: an exception which isn't " 151 << "std::exception" << endl; 152 return 2; 153 } 181 154 182 {183 cout << "\n\n\nDirPath tesztelese...\n";184 185 186 cout << "Ures path letrehozasa" << endl;187 typedef DirPath<ListGraph> DPath;188 DPath P(G);189 190 cout << "P.length() == " << P.length() << endl;191 check(P.length() == 0);192 193 cout << "P.from() valid? " << G.valid(P.from()) << endl;194 check(! G.valid(P.from()));195 196 {197 cout << "Builder objektum letrehozasa" << endl;198 DPath::Builder B(P);199 200 cout << "Hozzaadunk az elejehez ket elet..." << endl;201 check(B.pushFront(e6));202 check(B.pushFront(e5));203 cout << "P.length() == " << P.length() << endl;204 check(P.length() == 0);205 206 cout << "Commitolunk..." << endl;207 B.commit();208 209 cout << "P.length() == " << P.length() << endl;210 check(P.length() == 2);211 cout << "P.from() valid? " << G.valid(P.from()) << endl;212 check(G.valid(P.from()));213 cout << "P.from()==v1 ? " << (P.from()==v1) << endl;214 check(P.from() == v1);215 216 cout << "Hozzaadunk az elejehez egy nem illeszkedo elet..." << endl;217 check(!B.pushFront(e3));218 219 cout << "Hozzaadunk a vegehez ket elet..." << endl;220 check(B.pushBack(e7));221 check(B.pushBack(e8));222 cout << "P.length() == " << P.length() << endl;223 check(P.length() == 4);224 225 cout << "Hozzaadunk az elejehez meg egy elet..." << endl;226 check(B.pushFront(e4));227 cout << "P.length() == " << P.length() << endl;228 check(P.length() == 4);229 230 cout << "Es megvarjuk, amig megszunik a Builder...\n";231 }232 cout << "P.length() == " << P.length() << endl;233 check(P.length() == 5);234 cout << "P.from()==v2 ? " << (P.from()==v2) << endl;235 check(P.from() == v2);236 237 cout << "Vegigiteralunk az eleken." << endl;238 typedef DPath::NodeIt NodeIt;239 typedef DPath::EdgeIt EdgeIt;240 EdgeIt e;241 int i=1;242 for(P.first(e); P.valid(e); P.next(e), ++i) {243 cout << i << ". el: " << e << endl;244 }245 }246 155 247 156 cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
Note: See TracChangeset
for help on using the changeset viewer.