COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
1 deleted
3 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r368 r361  
    2929        lemon/dim2.h \
    3030        lemon/error.h \
    31         lemon/full_graph.h \
    3231        lemon/graph_to_eps.h \
    3332        lemon/grid_graph.h \

  • test/digraph_test.cc

    r366 r228  
    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/hypercube_graph.h>
    2424
    … …  
    8080}
    8181
    82 void checkFullDigraph(int num) {
    83   typedef FullDigraph Digraph;
    84   DIGRAPH_TYPEDEFS(Digraph);
    85   Digraph G(num);
    86 
    87   checkGraphNodeList(G, num);
    88   checkGraphArcList(G, num * num);
    89 
    90   for (NodeIt n(G); n != INVALID; ++n) {
    91     checkGraphOutArcList(G, n, num);
    92     checkGraphInArcList(G, n, num);
    93   }
    94 
    95   checkGraphConArcList(G, num * num);
    96 
    97   checkNodeIds(G);
    98   checkArcIds(G);
    99   checkGraphNodeMap(G);
    100   checkGraphArcMap(G);
    101 
    102   for (int i = 0; i < G.nodeNum(); ++i) {
    103     check(G.index(G(i)) == i, "Wrong index");
    104   }
    105 
    106   for (NodeIt s(G); s != INVALID; ++s) {
    107     for (NodeIt t(G); t != INVALID; ++t) {
    108       Arc a = G.arc(s, t);
    109       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
    110     }
    111   }
    112 
    113 }
    114 
    11582
    11683void checkConcepts() {
    … …  
    143110    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    144111  }
    145   { // Checking FullDigraph
    146     checkConcept<Digraph, FullDigraph>();
    147   }
     112//  { // Checking FullDigraph
     113//    checkConcept<Digraph, FullDigraph>();
     114//  }
    148115//  { // Checking HyperCubeDigraph
    149116//    checkConcept<Digraph, HyperCubeDigraph>();
    … …  
    210177    checkDigraphValidity<SmartDigraph>();
    211178  }
    212   { // Checking FullDigraph
    213     checkFullDigraph(8);
    214   }
    215179}
    216180

  • test/graph_test.cc

    r368 r348  
    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
    98 void checkFullGraph(int num) {
    99   typedef FullGraph Graph;
     98void checkConcepts() {
     99  { // Checking graph components
     100    checkConcept<BaseGraphComponent, BaseGraphComponent >();
     101
     102    checkConcept<IDableGraphComponent<>,
     103      IDableGraphComponent<> >();
     104
     105    checkConcept<IterableGraphComponent<>,
     106      IterableGraphComponent<> >();
     107
     108    checkConcept<MappableGraphComponent<>,
     109      MappableGraphComponent<> >();
     110  }
     111  { // Checking skeleton graph
     112    checkConcept<Graph, Graph>();
     113  }
     114  { // Checking ListGraph
     115    checkConcept<Graph, ListGraph>();
     116    checkConcept<AlterableGraphComponent<>, ListGraph>();
     117    checkConcept<ExtendableGraphComponent<>, ListGraph>();
     118    checkConcept<ClearableGraphComponent<>, ListGraph>();
     119    checkConcept<ErasableGraphComponent<>, ListGraph>();
     120  }
     121  { // Checking SmartGraph
     122    checkConcept<Graph, SmartGraph>();
     123    checkConcept<AlterableGraphComponent<>, SmartGraph>();
     124    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
     125    checkConcept<ClearableGraphComponent<>, SmartGraph>();
     126  }
     127//  { // Checking FullGraph
     128//    checkConcept<Graph, FullGraph>();
     129//    checkGraphIterators<FullGraph>();
     130//  }
     131  { // Checking GridGraph
     132    checkConcept<Graph, GridGraph>();
     133  }
     134}
     135
     136template <typename Graph>
     137void checkGraphValidity() {
     138  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     139  Graph g;
     140
     141  Node
     142    n1 = g.addNode(),
     143    n2 = g.addNode(),
     144    n3 = g.addNode();
     145
     146  Edge
     147    e1 = g.addEdge(n1, n2),
     148    e2 = g.addEdge(n2, n3);
     149
     150  check(g.valid(n1), "Wrong validity check");
     151  check(g.valid(e1), "Wrong validity check");
     152  check(g.valid(g.direct(e1, true)), "Wrong validity check");
     153
     154  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     155  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
     156  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     157}
     158
     159template <typename Graph>
     160void checkGraphValidityErase() {
     161  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     162  Graph g;
     163
     164  Node
     165    n1 = g.addNode(),
     166    n2 = g.addNode(),
     167    n3 = g.addNode();
     168
     169  Edge
     170    e1 = g.addEdge(n1, n2),
     171    e2 = g.addEdge(n2, n3);
     172
     173  check(g.valid(n1), "Wrong validity check");
     174  check(g.valid(e1), "Wrong validity check");
     175  check(g.valid(g.direct(e1, true)), "Wrong validity check");
     176
     177  g.erase(n1);
     178
     179  check(!g.valid(n1), "Wrong validity check");
     180  check(g.valid(n2), "Wrong validity check");
     181  check(g.valid(n3), "Wrong validity check");
     182  check(!g.valid(e1), "Wrong validity check");
     183  check(g.valid(e2), "Wrong validity check");
     184
     185  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     186  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
     187  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     188}
     189
     190void checkGridGraph(int width, int height) {
     191  typedef GridGraph Graph;
    100192  GRAPH_TYPEDEFS(Graph);
    101 
    102   Graph G(num);
    103   checkGraphNodeList(G, num);
    104   checkGraphEdgeList(G, num * (num - 1) / 2);
     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));
    105242
    106243  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);
     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  }
    114254
    115255  checkArcDirections(G);
     256
     257  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     258  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
    116259
    117260  checkNodeIds(G);
    … …  
    122265  checkGraphEdgeMap(G);
    123266
    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 
    145 void checkConcepts() {
    146   { // Checking graph components
    147     checkConcept<BaseGraphComponent, BaseGraphComponent >();
    148 
    149     checkConcept<IDableGraphComponent<>,
    150       IDableGraphComponent<> >();
    151 
    152     checkConcept<IterableGraphComponent<>,
    153       IterableGraphComponent<> >();
    154 
    155     checkConcept<MappableGraphComponent<>,
    156       MappableGraphComponent<> >();
    157   }
    158   { // Checking skeleton graph
    159     checkConcept<Graph, Graph>();
    160   }
    161   { // Checking ListGraph
    162     checkConcept<Graph, ListGraph>();
    163     checkConcept<AlterableGraphComponent<>, ListGraph>();
    164     checkConcept<ExtendableGraphComponent<>, ListGraph>();
    165     checkConcept<ClearableGraphComponent<>, ListGraph>();
    166     checkConcept<ErasableGraphComponent<>, ListGraph>();
    167   }
    168   { // Checking SmartGraph
    169     checkConcept<Graph, SmartGraph>();
    170     checkConcept<AlterableGraphComponent<>, SmartGraph>();
    171     checkConcept<ExtendableGraphComponent<>, SmartGraph>();
    172     checkConcept<ClearableGraphComponent<>, SmartGraph>();
    173   }
    174   { // Checking FullGraph
    175     checkConcept<Graph, FullGraph>();
    176   }
    177   { // Checking GridGraph
    178     checkConcept<Graph, GridGraph>();
    179   }
    180 }
    181 
    182 template <typename Graph>
    183 void checkGraphValidity() {
    184   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    185   Graph g;
    186 
    187   Node
    188     n1 = g.addNode(),
    189     n2 = g.addNode(),
    190     n3 = g.addNode();
    191 
    192   Edge
    193     e1 = g.addEdge(n1, n2),
    194     e2 = g.addEdge(n2, n3);
    195 
    196   check(g.valid(n1), "Wrong validity check");
    197   check(g.valid(e1), "Wrong validity check");
    198   check(g.valid(g.direct(e1, true)), "Wrong validity check");
    199 
    200   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    201   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
    202   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    203 }
    204 
    205 template <typename Graph>
    206 void checkGraphValidityErase() {
    207   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    208   Graph g;
    209 
    210   Node
    211     n1 = g.addNode(),
    212     n2 = g.addNode(),
    213     n3 = g.addNode();
    214 
    215   Edge
    216     e1 = g.addEdge(n1, n2),
    217     e2 = g.addEdge(n2, n3);
    218 
    219   check(g.valid(n1), "Wrong validity check");
    220   check(g.valid(e1), "Wrong validity check");
    221   check(g.valid(g.direct(e1, true)), "Wrong validity check");
    222 
    223   g.erase(n1);
    224 
    225   check(!g.valid(n1), "Wrong validity check");
    226   check(g.valid(n2), "Wrong validity check");
    227   check(g.valid(n3), "Wrong validity check");
    228   check(!g.valid(e1), "Wrong validity check");
    229   check(g.valid(e2), "Wrong validity check");
    230 
    231   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    232   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
    233   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    234 }
    235 
    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 
    313267}
    314268
    … …  
    322276    checkGraphValidity<SmartGraph>();
    323277  }
    324   { // Checking FullGraph   
    325     checkFullGraph(7);
    326     checkFullGraph(8);
    327   }
     278//   { // Checking FullGraph
     279//     FullGraph g(5);
     280//     checkGraphNodeList(g, 5);
     281//     checkGraphEdgeList(g, 10);
     282//   }
    328283  { // Checking GridGraph
    329284    checkGridGraph(5, 8);
Note: See TracChangeset for help on using the changeset viewer.