Changeset 149:2f7ae34e1333 in lemon1.0
 Timestamp:
 04/24/08 14:53:09 (14 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

lemon/list_graph.h
r73 r149 153 153 static Arc arcFromId(int id) { return Arc(id);} 154 154 155 bool valid(Node n) const { 156 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 157 nodes[n.id].prev != 2; 158 } 159 160 bool valid(Arc a) const { 161 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 162 arcs[a.id].prev_in != 2; 163 } 164 155 165 Node addNode() { 156 166 int n; … … 220 230 nodes[n].next = first_free_node; 221 231 first_free_node = n; 232 nodes[n].prev = 2; 222 233 223 234 } … … 248 259 249 260 arcs[n].next_in = first_free_arc; 250 first_free_arc = n; 251 261 first_free_arc = n; 262 arcs[n].prev_in = 2; 252 263 } 253 264 … … 350 361 return Parent::addArc(s, t); 351 362 } 363 364 /// Node validity check 365 366 /// This function gives back true if the given node is valid, 367 /// ie. it is a real node of the graph. 368 /// 369 /// \warning A Node pointing to a removed item 370 /// could become valid again later if new nodes are 371 /// added to the graph. 372 bool valid(Node n) const { return Parent::valid(n); } 373 374 /// Arc validity check 375 376 /// This function gives back true if the given arc is valid, 377 /// ie. it is a real arc of the graph. 378 /// 379 /// \warning An Arc pointing to a removed item 380 /// could become valid again later if new nodes are 381 /// added to the graph. 382 bool valid(Arc a) const { return Parent::valid(a); } 352 383 353 384 /// Change the target of \c e to \c n … … 946 977 static Edge edgeFromId(int id) { return Edge(id);} 947 978 979 bool valid(Node n) const { 980 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) && 981 nodes[n.id].prev != 2; 982 } 983 984 bool valid(Arc a) const { 985 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) && 986 arcs[a.id].prev_out != 2; 987 } 988 989 bool valid(Edge e) const { 990 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) && 991 arcs[2 * e.id].prev_out != 2; 992 } 993 948 994 Node addNode() { 949 995 int n; … … 1014 1060 nodes[n].next = first_free_node; 1015 1061 first_free_node = n; 1016 1062 nodes[n].prev = 2; 1017 1063 } 1018 1064 … … 1042 1088 arcs[n].next_out = first_free_arc; 1043 1089 first_free_arc = n; 1090 arcs[n].prev_out = 2; 1091 arcs[n  1].prev_out = 2; 1044 1092 1045 1093 } … … 1158 1206 return Parent::addEdge(s, t); 1159 1207 } 1208 /// Node validity check 1209 1210 /// This function gives back true if the given node is valid, 1211 /// ie. it is a real node of the graph. 1212 /// 1213 /// \warning A Node pointing to a removed item 1214 /// could become valid again later if new nodes are 1215 /// added to the graph. 1216 bool valid(Node n) const { return Parent::valid(n); } 1217 /// Arc validity check 1218 1219 /// This function gives back true if the given arc is valid, 1220 /// ie. it is a real arc of the graph. 1221 /// 1222 /// \warning An Arc pointing to a removed item 1223 /// could become valid again later if new edges are 1224 /// added to the graph. 1225 bool valid(Arc a) const { return Parent::valid(a); } 1226 /// Edge validity check 1227 1228 /// This function gives back true if the given edge is valid, 1229 /// ie. it is a real arc of the graph. 1230 /// 1231 /// \warning A Edge pointing to a removed item 1232 /// could become valid again later if new edges are 1233 /// added to the graph. 1234 bool valid(Edge e) const { return Parent::valid(e); } 1160 1235 /// \brief Change the source of \c e to \c n 1161 1236 /// 
lemon/smart_graph.h
r139 r149 116 116 static Arc arcFromId(int id) { return Arc(id);} 117 117 118 bool valid(Node n) const { 119 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 120 } 121 bool valid(Arc a) const { 122 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 123 } 124 118 125 class Node { 119 126 friend class SmartDigraphBase; … … 261 268 /// \sa reserveNode 262 269 void reserveArc(int m) { arcs.reserve(m); }; 270 271 /// \brief Node validity check 272 /// 273 /// This function gives back true if the given node is valid, 274 /// ie. it is a real node of the graph. 275 /// 276 /// \warning A removed node (using Snapshot) could become valid again 277 /// when new nodes are added to the graph. 278 bool valid(Node n) const { return Parent::valid(n); } 279 280 /// \brief Arc validity check 281 /// 282 /// This function gives back true if the given arc is valid, 283 /// ie. it is a real arc of the graph. 284 /// 285 /// \warning A removed arc (using Snapshot) could become valid again 286 /// when new arcs are added to the graph. 287 bool valid(Arc a) const { return Parent::valid(a); } 263 288 264 289 ///Clear the digraph. … … 551 576 static Edge edgeFromId(int id) { return Edge(id);} 552 577 578 bool valid(Node n) const { 579 return n._id >= 0 && n._id < static_cast<int>(nodes.size()); 580 } 581 bool valid(Arc a) const { 582 return a._id >= 0 && a._id < static_cast<int>(arcs.size()); 583 } 584 bool valid(Edge e) const { 585 return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); 586 } 587 553 588 Node addNode() { 554 589 int n = nodes.size(); … … 642 677 return Parent::addEdge(s, t); 643 678 } 679 680 /// \brief Node validity check 681 /// 682 /// This function gives back true if the given node is valid, 683 /// ie. it is a real node of the graph. 684 /// 685 /// \warning A removed node (using Snapshot) could become valid again 686 /// when new nodes are added to the graph. 687 bool valid(Node n) const { return Parent::valid(n); } 688 689 /// \brief Arc validity check 690 /// 691 /// This function gives back true if the given arc is valid, 692 /// ie. it is a real arc of the graph. 693 /// 694 /// \warning A removed arc (using Snapshot) could become valid again 695 /// when new edges are added to the graph. 696 bool valid(Arc a) const { return Parent::valid(a); } 697 698 /// \brief Edge validity check 699 /// 700 /// This function gives back true if the given edge is valid, 701 /// ie. it is a real edge of the graph. 702 /// 703 /// \warning A removed edge (using Snapshot) could become valid again 704 /// when new edges are added to the graph. 705 bool valid(Edge e) const { return Parent::valid(e); } 644 706 645 707 ///Clear the graph. 
test/graph_test.cc
r109 r149 23 23 // #include <lemon/grid_graph.h> 24 24 25 //#include <lemon/graph_utils.h>25 #include <lemon/graph_utils.h> 26 26 27 27 #include "test_tools.h" … … 83 83 84 84 template <typename Graph> 85 void print_items(Graph &g) { 86 87 typedef typename Graph::NodeIt NodeIt; 88 typedef typename Graph::EdgeIt EdgeIt; 89 typedef typename Graph::ArcIt ArcIt; 90 91 std::cout << "Nodes" << std::endl; 92 int i=0; 93 for(NodeIt it(g); it!=INVALID; ++it, ++i) { 94 std::cout << " " << i << ": " << g.id(it) << std::endl; 95 } 96 97 std::cout << "Edge" << std::endl; 98 i=0; 99 for(EdgeIt it(g); it!=INVALID; ++it, ++i) { 100 std::cout << " " << i << ": " << g.id(it) 101 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 102 << ")" << std::endl; 103 } 104 105 std::cout << "Arc" << std::endl; 106 i=0; 107 for(ArcIt it(g); it!=INVALID; ++it, ++i) { 108 std::cout << " " << i << ": " << g.id(it) 109 << " (" << g.id(g.source(it)) << ", " << g.id(g.target(it)) 110 << ")" << std::endl; 111 } 112 113 } 114 115 template <typename Graph> 116 void check_graph() { 117 118 typedef typename Graph::Node Node; 119 typedef typename Graph::Edge Edge; 120 typedef typename Graph::Arc Arc; 121 typedef typename Graph::NodeIt NodeIt; 122 typedef typename Graph::EdgeIt EdgeIt; 123 typedef typename Graph::ArcIt ArcIt; 124 85 void check_graph_counts() { 86 87 TEMPLATE_GRAPH_TYPEDEFS(Graph); 125 88 Graph g; 126 89 … … 136 99 e2 = g.addEdge(n2, n3); 137 100 138 // print_items(g);139 140 101 check_item_counts(g,3,2); 141 102 } 103 104 template <typename Graph> 105 void check_graph_validity() { 106 107 TEMPLATE_GRAPH_TYPEDEFS(Graph); 108 Graph g; 109 110 check_item_counts(g,0,0); 111 112 Node 113 n1 = g.addNode(), 114 n2 = g.addNode(), 115 n3 = g.addNode(); 116 117 Edge 118 e1 = g.addEdge(n1, n2), 119 e2 = g.addEdge(n2, n3); 120 121 check(g.valid(n1), "Validity check"); 122 check(g.valid(e1), "Validity check"); 123 check(g.valid(g.direct(e1, true)), "Validity check"); 124 125 check(!g.valid(g.nodeFromId(1)), "Validity check"); 126 check(!g.valid(g.edgeFromId(1)), "Validity check"); 127 check(!g.valid(g.arcFromId(1)), "Validity check"); 128 129 } 130 131 template <typename Graph> 132 void check_graph_validity_erase() { 133 134 TEMPLATE_GRAPH_TYPEDEFS(Graph); 135 Graph g; 136 137 check_item_counts(g,0,0); 138 139 Node 140 n1 = g.addNode(), 141 n2 = g.addNode(), 142 n3 = g.addNode(); 143 144 Edge 145 e1 = g.addEdge(n1, n2), 146 e2 = g.addEdge(n2, n3); 147 148 check(g.valid(n1), "Validity check"); 149 check(g.valid(e1), "Validity check"); 150 check(g.valid(g.direct(e1, true)), "Validity check"); 151 152 g.erase(n1); 153 154 check(!g.valid(n1), "Validity check"); 155 check(g.valid(n2), "Validity check"); 156 check(g.valid(n3), "Validity check"); 157 check(!g.valid(e1), "Validity check"); 158 check(g.valid(e2), "Validity check"); 159 160 check(!g.valid(g.nodeFromId(1)), "Validity check"); 161 check(!g.valid(g.edgeFromId(1)), "Validity check"); 162 check(!g.valid(g.arcFromId(1)), "Validity check"); 163 164 } 165 166 142 167 143 168 // void checkGridGraph(const GridGraph& g, int w, int h) { … … 188 213 check_concepts(); 189 214 190 check_graph<ListGraph>(); 191 check_graph<SmartGraph>(); 215 check_graph_counts<ListGraph>(); 216 check_graph_counts<SmartGraph>(); 217 218 check_graph_validity_erase<ListGraph>(); 219 check_graph_validity<SmartGraph>(); 192 220 193 221 // {
Note: See TracChangeset
for help on using the changeset viewer.