Changeset 368:99f1bdf8f7db in lemon
- Timestamp:
- 11/04/08 11:21:22 (16 years ago)
- Branch:
- default
- Parents:
- 362:c6c6e1d863c4 (diff), 367:aa75d24ba7d0 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r361 r368 29 29 lemon/dim2.h \ 30 30 lemon/error.h \ 31 lemon/full_graph.h \ 31 32 lemon/graph_to_eps.h \ 32 33 lemon/grid_graph.h \ -
lemon/Makefile.am
r365 r368 13 13 lemon/random.cc 14 14 15 16 lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 17 lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 15 #lemon_libemon_la_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS) $(SOPLEX_CXXFLAGS) 16 #lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) 18 17 19 18 lemon_HEADERS += \ … … 32 31 lemon/full_graph.h \ 33 32 lemon/graph_to_eps.h \ 33 lemon/grid_graph.h \ 34 34 lemon/kruskal.h \ 35 35 lemon/lgf_reader.h \ … … 38 38 lemon/maps.h \ 39 39 lemon/math.h \ 40 lemon/max_matching.h \ 41 lemon/nauty_reader.h \ 40 42 lemon/path.h \ 41 43 lemon/random.h \ 42 44 lemon/smart_graph.h \ 45 lemon/suurballe.h \ 43 46 lemon/time_measure.h \ 44 47 lemon/tolerance.h \ -
test/graph_test.cc
r348 r368 20 20 #include <lemon/list_graph.h> 21 21 #include <lemon/smart_graph.h> 22 //#include <lemon/full_graph.h>22 #include <lemon/full_graph.h> 23 23 #include <lemon/grid_graph.h> 24 24 … … 96 96 } 97 97 98 void checkFullGraph(int num) { 99 typedef FullGraph Graph; 100 GRAPH_TYPEDEFS(Graph); 101 102 Graph G(num); 103 checkGraphNodeList(G, num); 104 checkGraphEdgeList(G, num * (num - 1) / 2); 105 106 for (NodeIt n(G); n != INVALID; ++n) { 107 checkGraphOutArcList(G, n, num - 1); 108 checkGraphInArcList(G, n, num - 1); 109 checkGraphIncEdgeList(G, n, num - 1); 110 } 111 112 checkGraphConArcList(G, num * (num - 1)); 113 checkGraphConEdgeList(G, num * (num - 1) / 2); 114 115 checkArcDirections(G); 116 117 checkNodeIds(G); 118 checkArcIds(G); 119 checkEdgeIds(G); 120 checkGraphNodeMap(G); 121 checkGraphArcMap(G); 122 checkGraphEdgeMap(G); 123 124 125 for (int i = 0; i < G.nodeNum(); ++i) { 126 check(G.index(G(i)) == i, "Wrong index"); 127 } 128 129 for (NodeIt u(G); u != INVALID; ++u) { 130 for (NodeIt v(G); v != INVALID; ++v) { 131 Edge e = G.edge(u, v); 132 Arc a = G.arc(u, v); 133 if (u == v) { 134 check(e == INVALID, "Wrong edge lookup"); 135 check(a == INVALID, "Wrong arc lookup"); 136 } else { 137 check((G.u(e) == u && G.v(e) == v) || 138 (G.u(e) == v && G.v(e) == u), "Wrong edge lookup"); 139 check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup"); 140 } 141 } 142 } 143 } 144 98 145 void checkConcepts() { 99 146 { // Checking graph components … … 125 172 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 126 173 } 127 // { // Checking FullGraph 128 // checkConcept<Graph, FullGraph>(); 129 // checkGraphIterators<FullGraph>(); 130 // } 174 { // Checking FullGraph 175 checkConcept<Graph, FullGraph>(); 176 } 131 177 { // Checking GridGraph 132 178 checkConcept<Graph, GridGraph>(); … … 276 322 checkGraphValidity<SmartGraph>(); 277 323 } 278 // { // Checking FullGraph 279 // FullGraph g(5); 280 // checkGraphNodeList(g, 5); 281 // checkGraphEdgeList(g, 10); 282 // } 324 { // Checking FullGraph 325 checkFullGraph(7); 326 checkFullGraph(8); 327 } 283 328 { // Checking GridGraph 284 329 checkGridGraph(5, 8); -
test/graph_test.cc
r365 r368 21 21 #include <lemon/smart_graph.h> 22 22 #include <lemon/full_graph.h> 23 //#include <lemon/grid_graph.h>23 #include <lemon/grid_graph.h> 24 24 25 25 #include "test_tools.h" … … 175 175 checkConcept<Graph, FullGraph>(); 176 176 } 177 //{ // Checking GridGraph178 //checkConcept<Graph, GridGraph>();179 //}177 { // Checking GridGraph 178 checkConcept<Graph, GridGraph>(); 179 } 180 180 } 181 181 … … 234 234 } 235 235 236 // void checkGridGraph(const GridGraph& g, int w, int h) { 237 // check(g.width() == w, "Wrong width"); 238 // check(g.height() == h, "Wrong height"); 239 240 // for (int i = 0; i < w; ++i) { 241 // for (int j = 0; j < h; ++j) { 242 // check(g.col(g(i, j)) == i, "Wrong col"); 243 // check(g.row(g(i, j)) == j, "Wrong row"); 244 // } 245 // } 246 247 // for (int i = 0; i < w; ++i) { 248 // for (int j = 0; j < h - 1; ++j) { 249 // check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); 250 // check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); 251 // } 252 // check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); 253 // } 254 255 // for (int i = 0; i < w; ++i) { 256 // for (int j = 1; j < h; ++j) { 257 // check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); 258 // check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); 259 // } 260 // check(g.up(g(i, 0)) == INVALID, "Wrong up"); 261 // } 262 263 // for (int j = 0; j < h; ++j) { 264 // for (int i = 0; i < w - 1; ++i) { 265 // check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); 266 // check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); 267 // } 268 // check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); 269 // } 270 271 // for (int j = 0; j < h; ++j) { 272 // for (int i = 1; i < w; ++i) { 273 // check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); 274 // check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); 275 // } 276 // check(g.left(g(0, j)) == INVALID, "Wrong left"); 277 // } 278 // } 236 void checkGridGraph(int width, int height) { 237 typedef GridGraph Graph; 238 GRAPH_TYPEDEFS(Graph); 239 Graph G(width, height); 240 241 check(G.width() == width, "Wrong column number"); 242 check(G.height() == height, "Wrong row number"); 243 244 for (int i = 0; i < width; ++i) { 245 for (int j = 0; j < height; ++j) { 246 check(G.col(G(i, j)) == i, "Wrong column"); 247 check(G.row(G(i, j)) == j, "Wrong row"); 248 check(G.pos(G(i, j)).x == i, "Wrong column"); 249 check(G.pos(G(i, j)).y == j, "Wrong row"); 250 } 251 } 252 253 for (int j = 0; j < height; ++j) { 254 for (int i = 0; i < width - 1; ++i) { 255 check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); 256 check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); 257 } 258 check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); 259 } 260 261 for (int j = 0; j < height; ++j) { 262 for (int i = 1; i < width; ++i) { 263 check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); 264 check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); 265 } 266 check(G.left(G(0, j)) == INVALID, "Wrong left"); 267 } 268 269 for (int i = 0; i < width; ++i) { 270 for (int j = 0; j < height - 1; ++j) { 271 check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); 272 check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); 273 } 274 check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); 275 } 276 277 for (int i = 0; i < width; ++i) { 278 for (int j = 1; j < height; ++j) { 279 check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); 280 check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); 281 } 282 check(G.down(G(i, 0)) == INVALID, "Wrong down"); 283 } 284 285 checkGraphNodeList(G, width * height); 286 checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); 287 checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 288 289 for (NodeIt n(G); n != INVALID; ++n) { 290 int nb = 4; 291 if (G.col(n) == 0) --nb; 292 if (G.col(n) == width - 1) --nb; 293 if (G.row(n) == 0) --nb; 294 if (G.row(n) == height - 1) --nb; 295 296 checkGraphOutArcList(G, n, nb); 297 checkGraphInArcList(G, n, nb); 298 checkGraphIncEdgeList(G, n, nb); 299 } 300 301 checkArcDirections(G); 302 303 checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); 304 checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); 305 306 checkNodeIds(G); 307 checkArcIds(G); 308 checkEdgeIds(G); 309 checkGraphNodeMap(G); 310 checkGraphArcMap(G); 311 checkGraphEdgeMap(G); 312 313 } 279 314 280 315 void checkGraphs() { … … 291 326 checkFullGraph(8); 292 327 } 293 // { // Checking GridGraph 294 // GridGraph g(5, 6); 295 // checkGraphNodeList(g, 30); 296 // checkGraphEdgeList(g, 49); 297 // checkGridGraph(g, 5, 6); 298 // } 328 { // Checking GridGraph 329 checkGridGraph(5, 8); 330 checkGridGraph(8, 5); 331 checkGridGraph(5, 5); 332 checkGridGraph(0, 0); 333 checkGridGraph(1, 1); 334 } 299 335 } 300 336
Note: See TracChangeset
for help on using the changeset viewer.