COIN-OR::LEMON - Graph Library

Changeset 335:160bf92c7cdc in lemon-1.2 for test


Ignore:
Timestamp:
10/20/08 12:36:02 (16 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Improvement on grid graphs

  • The indexing of matrix is changed according to integer points of the plane.
  • The graph type does not depend on the UndirGraphExtender?.
  • Improving documentation.
  • Improved image generation.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/graph_test.cc

    r334 r335  
    127127//  { // Checking FullGraph
    128128//    checkConcept<Graph, FullGraph>();
     129//    checkGraphIterators<FullGraph>();
    129130//  }
    130131  { // Checking GridGraph
     
    187188}
    188189
    189 void checkGridGraph(const GridGraph& g, int w, int h) {
    190   check(g.width() == w, "Wrong width");
    191   check(g.height() == h, "Wrong height");
    192 
    193   for (int i = 0; i < w; ++i) {
    194     for (int j = 0; j < h; ++j) {
    195       check(g.col(g(i, j)) == i, "Wrong col");
    196       check(g.row(g(i, j)) == j, "Wrong row");
    197     }
    198   }
    199 
    200   for (int i = 0; i < w; ++i) {
    201     for (int j = 0; j < h - 1; ++j) {
    202       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    203       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    204     }
    205     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    206   }
    207 
    208   for (int i = 0; i < w; ++i) {
    209     for (int j = 1; j < h; ++j) {
    210       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    211       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    212     }
    213     check(g.up(g(i, 0)) == INVALID, "Wrong up");
    214   }
    215 
    216   for (int j = 0; j < h; ++j) {
    217     for (int i = 0; i < w - 1; ++i) {
    218       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    219       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    220     }
    221     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    222   }
    223 
    224   for (int j = 0; j < h; ++j) {
    225     for (int i = 1; i < w; ++i) {
    226       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
    227       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
    228     }
    229     check(g.left(g(0, j)) == INVALID, "Wrong left");
    230   }
    231 
    232   checkGraphNodeList(g, w*h);
    233   checkGraphArcList(g, 2*(2*w*h-w-h));
    234   checkGraphEdgeList(g, 2*w*h-w-h);
    235 
    236   checkGraphOutArcList(g, g(0,0), 2);
    237   checkGraphOutArcList(g, g(0,1), 3);
    238   checkGraphOutArcList(g, g(w-2,h-2), 4);
    239 
    240   checkGraphInArcList(g, g(0,0), 2);
    241   checkGraphInArcList(g, g(0,1), 3);
    242   checkGraphInArcList(g, g(w-2,h-2), 4);
    243 
    244   checkGraphIncEdgeList(g, g(0,0), 2);
    245   checkGraphIncEdgeList(g, g(0,1), 3);
    246   checkGraphIncEdgeList(g, g(w-2,h-2), 4);
    247 
    248   checkGraphConArcList(g, 2*(2*w*h-w-h));
    249   checkGraphConEdgeList(g, 2*w*h-w-h);
    250 
    251   checkArcDirections(g);
    252 
    253   checkNodeIds(g);
    254   checkArcIds(g);
    255   checkEdgeIds(g);
    256   checkGraphNodeMap(g);
    257   checkGraphArcMap(g);
    258   checkGraphEdgeMap(g);
     190void checkGridGraph(int width, int height) {
     191  typedef GridGraph Graph;
     192  GRAPH_TYPEDEFS(Graph);
     193  Graph G(width, height);
     194
     195  check(G.width() == width, "Wrong row number");
     196  check(G.height() == height, "Wrong column number");
     197
     198  for (int i = 0; i < width; ++i) {
     199    for (int j = 0; j < height; ++j) {
     200      check(G.col(G(i, j)) == i, "Wrong column");
     201      check(G.row(G(i, j)) == j, "Wrong row");
     202      check(G.pos(G(i, j)).x == i, "Wrong column");
     203      check(G.pos(G(i, j)).y == j, "Wrong row");
     204    }
     205  }
     206
     207  for (int j = 0; j < height; ++j) {
     208    for (int i = 0; i < width - 1; ++i) {
     209      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
     210      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
     211    }
     212    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
     213  }
     214
     215  for (int j = 0; j < height; ++j) {
     216    for (int i = 1; i < width; ++i) {
     217      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
     218      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
     219    }
     220    check(G.left(G(0, j)) == INVALID, "Wrong left");
     221  }
     222
     223  for (int i = 0; i < width; ++i) {
     224    for (int j = 0; j < height - 1; ++j) {
     225      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
     226      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
     227    }
     228    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
     229  }
     230
     231  for (int i = 0; i < width; ++i) {
     232    for (int j = 1; j < height; ++j) {
     233      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
     234      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
     235    }
     236    check(G.down(G(i, 0)) == INVALID, "Wrong down");
     237  }
     238
     239  checkGraphNodeList(G, width * height);
     240  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
     241  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     242
     243  for (NodeIt n(G); n != INVALID; ++n) {
     244    int nb = 4;
     245    if (G.col(n) == 0) --nb;
     246    if (G.col(n) == width - 1) --nb;
     247    if (G.row(n) == 0) --nb;
     248    if (G.row(n) == height - 1) --nb;
     249
     250    checkGraphOutArcList(G, n, nb);
     251    checkGraphInArcList(G, n, nb);
     252    checkGraphIncEdgeList(G, n, nb);
     253  }
     254
     255  checkArcDirections(G);
     256
     257  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     258  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
     259
     260  checkNodeIds(G);
     261  checkArcIds(G);
     262  checkEdgeIds(G);
     263  checkGraphNodeMap(G);
     264  checkGraphArcMap(G);
     265  checkGraphEdgeMap(G);
     266
    259267}
    260268
     
    274282//   }
    275283  { // Checking GridGraph
    276     GridGraph g(5, 6);
    277     checkGridGraph(g, 5, 6);
     284    checkGridGraph(5, 8);
     285    checkGridGraph(8, 5);
     286    checkGridGraph(5, 5);
     287    checkGridGraph(0, 0);
     288    checkGridGraph(1, 1);
    278289  }
    279290}
Note: See TracChangeset for help on using the changeset viewer.