gravatar
deba@inf.elte.hu
deba@inf.elte.hu
Item validity checking for ListGraph and SmartGraph
0 3 0
default
3 files changed with 212 insertions and 47 deletions:
↑ Collapse diff ↑
Ignore white space 6 line context
... ...
@@ -149,12 +149,22 @@
149 149
    static int id(Node v) { return v.id; }
150 150
    static int id(Arc e) { return e.id; }
151 151

	
152 152
    static Node nodeFromId(int id) { return Node(id);}
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;
157 167
      
158 168
      if(first_free_node==-1) {
159 169
	n = nodes.size();
160 170
	nodes.push_back(NodeT());
... ...
@@ -216,12 +226,13 @@
216 226
      } else {
217 227
	first_node = nodes[n].next;
218 228
      }
219 229
      
220 230
      nodes[n].next = first_free_node;
221 231
      first_free_node = n;
232
      nodes[n].prev = -2;
222 233

	
223 234
    }
224 235
    
225 236
    void erase(const Arc& arc) {
226 237
      int n = arc.id;
227 238
      
... ...
@@ -244,14 +255,14 @@
244 255
	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
245 256
      } else {
246 257
	nodes[arcs[n].source].first_out = arcs[n].next_out;
247 258
      }
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

	
254 265
    void clear() {
255 266
      arcs.clear();
256 267
      nodes.clear();
257 268
      first_node = first_free_node = first_free_arc = -1;
... ...
@@ -347,12 +358,32 @@
347 358
    ///and target node \c t.
348 359
    ///\return the new arc.
349 360
    Arc addArc(const Node& s, const Node& t) { 
350 361
      return Parent::addArc(s, t); 
351 362
    }
352 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); }
383

	
353 384
    /// Change the target of \c e to \c n
354 385

	
355 386
    /// Change the target of \c e to \c n
356 387
    ///
357 388
    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
358 389
    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
... ...
@@ -942,12 +973,27 @@
942 973
    static int id(Edge e) { return e.id; }
943 974

	
944 975
    static Node nodeFromId(int id) { return Node(id);}
945 976
    static Arc arcFromId(int id) { return Arc(id);}
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;
950 996
      
951 997
      if(first_free_node==-1) {
952 998
	n = nodes.size();
953 999
	nodes.push_back(NodeT());
... ...
@@ -1010,13 +1056,13 @@
1010 1056
      } else {
1011 1057
	first_node = nodes[n].next;
1012 1058
      }
1013 1059
      
1014 1060
      nodes[n].next = first_free_node;
1015 1061
      first_free_node = n;
1016

	
1062
      nodes[n].prev = -2;
1017 1063
    }
1018 1064
    
1019 1065
    void erase(const Edge& edge) {
1020 1066
      int n = edge.id * 2;
1021 1067
      
1022 1068
      if (arcs[n].next_out != -1) {
... ...
@@ -1038,12 +1084,14 @@
1038 1084
      } else {
1039 1085
	nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1040 1086
      }
1041 1087
      
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
    }
1046 1094

	
1047 1095
    void clear() {
1048 1096
      arcs.clear();
1049 1097
      nodes.clear();
... ...
@@ -1154,12 +1202,39 @@
1154 1202
    /// Add a new edge to the graph with source node \c s
1155 1203
    /// and target node \c t.
1156 1204
    /// \return the new edge.
1157 1205
    Edge addEdge(const Node& s, const Node& t) { 
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
    ///
1162 1237
    /// This function changes the source of \c e to \c n.
1163 1238
    ///
1164 1239
    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1165 1240
    ///referencing the changed arc remain
Ignore white space 12 line context
... ...
@@ -112,12 +112,19 @@
112 112
    static int id(Node v) { return v._id; }
113 113
    static int id(Arc a) { return a._id; }
114 114

	
115 115
    static Node nodeFromId(int id) { return Node(id);}
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;
120 127
      friend class SmartDigraph;
121 128

	
122 129
    protected:
123 130
      int _id;
... ...
@@ -258,12 +265,30 @@
258 265
    /// be very large (e.g. it will contain millions of nodes and/or arcs)
259 266
    /// then it is worth reserving space for this amount before starting
260 267
    /// to build the digraph.
261 268
    /// \sa reserveNode
262 269
    void reserveArc(int m) { arcs.reserve(m); };
263 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); }
288

	
264 289
    ///Clear the digraph.
265 290
    
266 291
    ///Erase all the nodes and arcs from the digraph.
267 292
    ///
268 293
    void clear() {
269 294
      Parent::clear();
... ...
@@ -547,12 +572,22 @@
547 572
    static int id(Edge e) { return e._id; }
548 573

	
549 574
    static Node nodeFromId(int id) { return Node(id);}
550 575
    static Arc arcFromId(int id) { return Arc(id);}
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();
555 590
      nodes.push_back(NodeT());
556 591
      nodes[n].first_out = -1;
557 592
      
558 593
      return Node(n);
... ...
@@ -639,12 +674,39 @@
639 674
    ///and \c t.
640 675
    ///\return the new edge.
641 676
    Edge addEdge(const Node& s, const Node& t) { 
642 677
      return Parent::addEdge(s, t); 
643 678
    }
644 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); }
706

	
645 707
    ///Clear the graph.
646 708
    
647 709
    ///Erase all the nodes and edges from the graph.
648 710
    ///
649 711
    void clear() {
650 712
      Parent::clear();
Ignore white space 6 line context
... ...
@@ -19,13 +19,13 @@
19 19
#include <lemon/concepts/graph.h>
20 20
#include <lemon/list_graph.h>
21 21
#include <lemon/smart_graph.h>
22 22
// #include <lemon/full_graph.h>
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"
28 28

	
29 29

	
30 30
using namespace lemon;
31 31
using namespace lemon::concepts;
... ...
@@ -79,52 +79,15 @@
79 79

	
80 80
  check(uee == e, "Wrong edge number.");
81 81
  //  check(countEdges(g) == e, "Wrong edge number.");
82 82
}
83 83

	
84 84
template <typename Graph>
85
void print_items(Graph &g) {
85
void check_graph_counts() {
86 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

	
87
  TEMPLATE_GRAPH_TYPEDEFS(Graph);
125 88
  Graph g;
126 89

	
127 90
  check_item_counts(g,0,0);
128 91

	
129 92
  Node
130 93
    n1 = g.addNode(),
... ...
@@ -132,17 +95,79 @@
132 95
    n3 = g.addNode();
133 96

	
134 97
  Edge
135 98
    e1 = g.addEdge(n1, n2),
136 99
    e2 = g.addEdge(n2, n3);
137 100

	
138
  // print_items(g);
139

	
140 101
  check_item_counts(g,3,2);
141 102
}
142 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

	
167

	
143 168
// void checkGridGraph(const GridGraph& g, int w, int h) {
144 169
//   check(g.width() == w, "Wrong width");
145 170
//   check(g.height() == h, "Wrong height");
146 171

	
147 172
//   for (int i = 0; i < w; ++i) {
148 173
//     for (int j = 0; j < h; ++j) {
... ...
@@ -184,14 +209,17 @@
184 209
//   }
185 210
// }
186 211

	
187 212
int main() {
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
//   {
194 222
//     FullGraph g(5);
195 223
//     check_item_counts(g, 5, 10);
196 224
//   }
197 225

	
0 comments (0 inline)