COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/digraph_test.cc

    r375 r365  
    2929
    3030template <class Digraph>
    31 void checkDigraphBuild() {
     31void checkDigraph() {
    3232  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3333  Digraph G;
     
    5858  checkGraphConArcList(G, 1);
    5959
    60   Arc a2 = G.addArc(n2, n1),
    61       a3 = G.addArc(n2, n3),
    62       a4 = G.addArc(n2, n3);
    63 
     60  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    6461  checkGraphNodeList(G, 3);
    6562  checkGraphArcList(G, 4);
     
    7976  checkGraphNodeMap(G);
    8077  checkGraphArcMap(G);
    81 }
    82 
    83 template <class Digraph>
    84 void checkDigraphSplit() {
    85   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    86 
    87   Digraph G;
    88   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    89   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    90       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    91 
    92   Node n4 = G.split(n2);
    93 
    94   check(G.target(OutArcIt(G, n2)) == n4 &&
    95         G.source(InArcIt(G, n4)) == n2,
    96         "Wrong split.");
    97 
    98   checkGraphNodeList(G, 4);
    99   checkGraphArcList(G, 5);
    100 
    101   checkGraphOutArcList(G, n1, 1);
    102   checkGraphOutArcList(G, n2, 1);
    103   checkGraphOutArcList(G, n3, 0);
    104   checkGraphOutArcList(G, n4, 3);
    105 
    106   checkGraphInArcList(G, n1, 1);
    107   checkGraphInArcList(G, n2, 1);
    108   checkGraphInArcList(G, n3, 2);
    109   checkGraphInArcList(G, n4, 1);
    110 
    111   checkGraphConArcList(G, 5);
    112 }
    113 
    114 template <class Digraph>
    115 void checkDigraphAlter() {
    116   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    117 
    118   Digraph G;
    119   Node n1 = G.addNode(), n2 = G.addNode(),
    120        n3 = G.addNode(), n4 = G.addNode();
    121   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
    122       a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
    123       a5 = G.addArc(n2, n4);
    124 
    125   checkGraphNodeList(G, 4);
    126   checkGraphArcList(G, 5);
    127 
    128   // Check changeSource() and changeTarget()
    129   G.changeTarget(a4, n1);
    130 
    131   checkGraphNodeList(G, 4);
    132   checkGraphArcList(G, 5);
    133 
    134   checkGraphOutArcList(G, n1, 1);
    135   checkGraphOutArcList(G, n2, 1);
    136   checkGraphOutArcList(G, n3, 0);
    137   checkGraphOutArcList(G, n4, 3);
    138 
    139   checkGraphInArcList(G, n1, 2);
    140   checkGraphInArcList(G, n2, 1);
    141   checkGraphInArcList(G, n3, 1);
    142   checkGraphInArcList(G, n4, 1);
    143 
    144   checkGraphConArcList(G, 5);
    145 
    146   G.changeSource(a4, n3);
    147 
    148   checkGraphNodeList(G, 4);
    149   checkGraphArcList(G, 5);
    150 
    151   checkGraphOutArcList(G, n1, 1);
    152   checkGraphOutArcList(G, n2, 1);
    153   checkGraphOutArcList(G, n3, 1);
    154   checkGraphOutArcList(G, n4, 2);
    155 
    156   checkGraphInArcList(G, n1, 2);
    157   checkGraphInArcList(G, n2, 1);
    158   checkGraphInArcList(G, n3, 1);
    159   checkGraphInArcList(G, n4, 1);
    160 
    161   checkGraphConArcList(G, 5);
    162 
    163   // Check contract()
    164   G.contract(n2, n4, false);
    165 
    166   checkGraphNodeList(G, 3);
    167   checkGraphArcList(G, 5);
    168 
    169   checkGraphOutArcList(G, n1, 1);
    170   checkGraphOutArcList(G, n2, 3);
    171   checkGraphOutArcList(G, n3, 1);
    172 
    173   checkGraphInArcList(G, n1, 2);
    174   checkGraphInArcList(G, n2, 2);
    175   checkGraphInArcList(G, n3, 1);
    176 
    177   checkGraphConArcList(G, 5);
    178 
    179   G.contract(n2, n1);
    180 
    181   checkGraphNodeList(G, 2);
    182   checkGraphArcList(G, 3);
    183 
    184   checkGraphOutArcList(G, n2, 2);
    185   checkGraphOutArcList(G, n3, 1);
    186 
    187   checkGraphInArcList(G, n2, 2);
    188   checkGraphInArcList(G, n3, 1);
    189 
    190   checkGraphConArcList(G, 3);
    191 }
    192 
    193 template <class Digraph>
    194 void checkDigraphErase() {
    195   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    196 
    197   Digraph G;
    198   Node n1 = G.addNode(), n2 = G.addNode(),
    199        n3 = G.addNode(), n4 = G.addNode();
    200   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
    201       a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
    202       a5 = G.addArc(n2, n4);
    203 
    204   // Check arc deletion
    205   G.erase(a1);
    206 
    207   checkGraphNodeList(G, 4);
    208   checkGraphArcList(G, 4);
    209 
    210   checkGraphOutArcList(G, n1, 0);
    211   checkGraphOutArcList(G, n2, 1);
    212   checkGraphOutArcList(G, n3, 1);
    213   checkGraphOutArcList(G, n4, 2);
    214 
    215   checkGraphInArcList(G, n1, 2);
    216   checkGraphInArcList(G, n2, 0);
    217   checkGraphInArcList(G, n3, 1);
    218   checkGraphInArcList(G, n4, 1);
    219 
    220   checkGraphConArcList(G, 4);
    221 
    222   // Check node deletion
    223   G.erase(n4);
    224 
    225   checkGraphNodeList(G, 3);
    226   checkGraphArcList(G, 1);
    227 
    228   checkGraphOutArcList(G, n1, 0);
    229   checkGraphOutArcList(G, n2, 0);
    230   checkGraphOutArcList(G, n3, 1);
    231   checkGraphOutArcList(G, n4, 0);
    232 
    233   checkGraphInArcList(G, n1, 1);
    234   checkGraphInArcList(G, n2, 0);
    235   checkGraphInArcList(G, n3, 0);
    236   checkGraphInArcList(G, n4, 0);
    237 
    238   checkGraphConArcList(G, 1);
    239 }
    240 
    241 
    242 template <class Digraph>
    243 void checkDigraphSnapshot() {
    244   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    245 
    246   Digraph G;
    247   Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
    248   Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    249       a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    250 
    251   typename Digraph::Snapshot snapshot(G);
    252 
    253   Node n = G.addNode();
    254   G.addArc(n3, n);
    255   G.addArc(n, n3);
    256 
    257   checkGraphNodeList(G, 4);
    258   checkGraphArcList(G, 6);
    259 
    260   snapshot.restore();
    261 
    262   checkGraphNodeList(G, 3);
    263   checkGraphArcList(G, 4);
    264 
    265   checkGraphOutArcList(G, n1, 1);
    266   checkGraphOutArcList(G, n2, 3);
    267   checkGraphOutArcList(G, n3, 0);
    268 
    269   checkGraphInArcList(G, n1, 1);
    270   checkGraphInArcList(G, n2, 1);
    271   checkGraphInArcList(G, n3, 2);
    272 
    273   checkGraphConArcList(G, 4);
     78
     79}
     80
     81void checkFullDigraph(int num) {
     82  typedef FullDigraph Digraph;
     83  DIGRAPH_TYPEDEFS(Digraph);
     84  Digraph G(num);
     85
     86  checkGraphNodeList(G, num);
     87  checkGraphArcList(G, num * num);
     88
     89  for (NodeIt n(G); n != INVALID; ++n) {
     90    checkGraphOutArcList(G, n, num);
     91    checkGraphInArcList(G, n, num);
     92  }
     93
     94  checkGraphConArcList(G, num * num);
    27495
    27596  checkNodeIds(G);
     
    27899  checkGraphArcMap(G);
    279100
    280   G.addNode();
    281   snapshot.save(G);
    282 
    283   G.addArc(G.addNode(), G.addNode());
    284 
    285   snapshot.restore();
    286 
    287   checkGraphNodeList(G, 4);
    288   checkGraphArcList(G, 4);
     101  for (int i = 0; i < G.nodeNum(); ++i) {
     102    check(G.index(G(i)) == i, "Wrong index");
     103  }
     104
     105  for (NodeIt s(G); s != INVALID; ++s) {
     106    for (NodeIt t(G); t != INVALID; ++t) {
     107      Arc a = G.arc(s, t);
     108      check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
     109    }
     110  }
     111
    289112}
    290113
     
    373196}
    374197
    375 void checkFullDigraph(int num) {
    376   typedef FullDigraph Digraph;
    377   DIGRAPH_TYPEDEFS(Digraph);
    378   Digraph G(num);
    379 
    380   checkGraphNodeList(G, num);
    381   checkGraphArcList(G, num * num);
    382 
    383   for (NodeIt n(G); n != INVALID; ++n) {
    384     checkGraphOutArcList(G, n, num);
    385     checkGraphInArcList(G, n, num);
    386   }
    387 
    388   checkGraphConArcList(G, num * num);
    389 
    390   checkNodeIds(G);
    391   checkArcIds(G);
    392   checkGraphNodeMap(G);
    393   checkGraphArcMap(G);
    394 
    395   for (int i = 0; i < G.nodeNum(); ++i) {
    396     check(G.index(G(i)) == i, "Wrong index");
    397   }
    398 
    399   for (NodeIt s(G); s != INVALID; ++s) {
    400     for (NodeIt t(G); t != INVALID; ++t) {
    401       Arc a = G.arc(s, t);
    402       check(G.source(a) == s && G.target(a) == t, "Wrong arc lookup");
    403     }
    404   }
    405 }
    406 
    407198void checkDigraphs() {
    408199  { // Checking ListDigraph
    409     checkDigraphBuild<ListDigraph>();
    410     checkDigraphSplit<ListDigraph>();
    411     checkDigraphAlter<ListDigraph>();
    412     checkDigraphErase<ListDigraph>();
    413     checkDigraphSnapshot<ListDigraph>();
     200    checkDigraph<ListDigraph>();
    414201    checkDigraphValidityErase<ListDigraph>();
    415202  }
    416203  { // Checking SmartDigraph
    417     checkDigraphBuild<SmartDigraph>();
    418     checkDigraphSplit<SmartDigraph>();
    419     checkDigraphSnapshot<SmartDigraph>();
     204    checkDigraph<SmartDigraph>();
    420205    checkDigraphValidity<SmartDigraph>();
    421206  }
Note: See TracChangeset for help on using the changeset viewer.