COIN-OR::LEMON - Graph Library

Changeset 356:99f1bdf8f7db in lemon-main


Ignore:
Timestamp:
11/04/08 11:21:22 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
350:c6c6e1d863c4 (diff), 355: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
Message:

Merge

Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r349 r356  
    2929        lemon/dim2.h \
    3030        lemon/error.h \
     31        lemon/full_graph.h \
    3132        lemon/graph_to_eps.h \
    3233        lemon/grid_graph.h \
  • lemon/Makefile.am

    r353 r356  
    1313        lemon/random.cc
    1414
    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)
    1817
    1918lemon_HEADERS += \
     
    3231        lemon/full_graph.h \
    3332        lemon/graph_to_eps.h \
     33        lemon/grid_graph.h \
    3434        lemon/kruskal.h \
    3535        lemon/lgf_reader.h \
     
    3838        lemon/maps.h \
    3939        lemon/math.h \
     40        lemon/max_matching.h \
     41        lemon/nauty_reader.h \
    4042        lemon/path.h \
    4143        lemon/random.h \
    4244        lemon/smart_graph.h \
     45        lemon/suurballe.h \
    4346        lemon/time_measure.h \
    4447        lemon/tolerance.h \
  • test/graph_test.cc

    r336 r356  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 // #include <lemon/full_graph.h>
     22#include <lemon/full_graph.h>
    2323#include <lemon/grid_graph.h>
    2424
     
    9696}
    9797
     98void 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
    98145void checkConcepts() {
    99146  { // Checking graph components
     
    125172    checkConcept<ClearableGraphComponent<>, SmartGraph>();
    126173  }
    127 //  { // Checking FullGraph
    128 //    checkConcept<Graph, FullGraph>();
    129 //    checkGraphIterators<FullGraph>();
    130 //  }
     174  { // Checking FullGraph
     175    checkConcept<Graph, FullGraph>();
     176  }
    131177  { // Checking GridGraph
    132178    checkConcept<Graph, GridGraph>();
     
    276322    checkGraphValidity<SmartGraph>();
    277323  }
    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  }
    283328  { // Checking GridGraph
    284329    checkGridGraph(5, 8);
  • test/graph_test.cc

    r353 r356  
    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"
     
    175175    checkConcept<Graph, FullGraph>();
    176176  }
    177 //   { // Checking GridGraph
    178 //     checkConcept<Graph, GridGraph>();
    179 //   }
     177  { // Checking GridGraph
     178    checkConcept<Graph, GridGraph>();
     179  }
    180180}
    181181
     
    234234}
    235235
    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 // }
     236void 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}
    279314
    280315void checkGraphs() {
     
    291326    checkFullGraph(8);
    292327  }
    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  }
    299335}
    300336
Note: See TracChangeset for help on using the changeset viewer.