COIN-OR::LEMON - Graph Library

Ignore:
Files:
2 added
4 edited

Legend:

Unmodified
Added
Removed
  • doc/CMakeLists.txt

    r225 r347  
    1414      COMMAND rm -rf gen-images
    1515      COMMAND mkdir gen-images
     16      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    1617      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    1718      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
  • doc/Makefile.am

    r317 r349  
    1515
    1616DOC_EPS_IMAGES18 = \
     17        grid_graph.eps \
    1718        nodeshape_0.eps \
    1819        nodeshape_1.eps \
  • lemon/Makefile.am

    r338 r349  
    3030        lemon/error.h \
    3131        lemon/graph_to_eps.h \
     32        lemon/grid_graph.h \
    3233        lemon/kruskal.h \
    3334        lemon/lgf_reader.h \
  • test/graph_test.cc

    r228 r348  
    2121#include <lemon/smart_graph.h>
    2222// #include <lemon/full_graph.h>
    23 // #include <lemon/grid_graph.h>
     23#include <lemon/grid_graph.h>
    2424
    2525#include "test_tools.h"
     
    129129//    checkGraphIterators<FullGraph>();
    130130//  }
    131 //  { // Checking GridGraph
    132 //    checkConcept<Graph, GridGraph>();
    133 //    checkGraphIterators<GridGraph>();
    134 //  }
     131  { // Checking GridGraph
     132    checkConcept<Graph, GridGraph>();
     133  }
    135134}
    136135
     
    189188}
    190189
    191 // void checkGridGraph(const GridGraph& g, int w, int h) {
    192 //   check(g.width() == w, "Wrong width");
    193 //   check(g.height() == h, "Wrong height");
    194 
    195 //   for (int i = 0; i < w; ++i) {
    196 //     for (int j = 0; j < h; ++j) {
    197 //       check(g.col(g(i, j)) == i, "Wrong col");
    198 //       check(g.row(g(i, j)) == j, "Wrong row");
    199 //     }
    200 //   }
    201 
    202 //   for (int i = 0; i < w; ++i) {
    203 //     for (int j = 0; j < h - 1; ++j) {
    204 //       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    205 //       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    206 //     }
    207 //     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    208 //   }
    209 
    210 //   for (int i = 0; i < w; ++i) {
    211 //     for (int j = 1; j < h; ++j) {
    212 //       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    213 //       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    214 //     }
    215 //     check(g.up(g(i, 0)) == INVALID, "Wrong up");
    216 //   }
    217 
    218 //   for (int j = 0; j < h; ++j) {
    219 //     for (int i = 0; i < w - 1; ++i) {
    220 //       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    221 //       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    222 //     }
    223 //     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    224 //   }
    225 
    226 //   for (int j = 0; j < h; ++j) {
    227 //     for (int i = 1; i < w; ++i) {
    228 //       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
    229 //       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
    230 //     }
    231 //     check(g.left(g(0, j)) == INVALID, "Wrong left");
    232 //   }
    233 // }
     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 column number");
     196  check(G.height() == height, "Wrong row 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
     267}
    234268
    235269void checkGraphs() {
     
    247281//     checkGraphEdgeList(g, 10);
    248282//   }
    249 //   { // Checking GridGraph
    250 //     GridGraph g(5, 6);
    251 //     checkGraphNodeList(g, 30);
    252 //     checkGraphEdgeList(g, 49);
    253 //     checkGridGraph(g, 5, 6);
    254 //   }
     283  { // Checking GridGraph
     284    checkGridGraph(5, 8);
     285    checkGridGraph(8, 5);
     286    checkGridGraph(5, 5);
     287    checkGridGraph(0, 0);
     288    checkGridGraph(1, 1);
     289  }
    255290}
    256291
Note: See TracChangeset for help on using the changeset viewer.