COIN-OR::LEMON - Graph Library

Changeset 388:2d87dbd7f8c8 in lemon for test/digraph_test.cc


Ignore:
Timestamp:
11/07/08 14:14:22 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
385:7b6466ed488a (diff), 387:49d9a36b3b84 (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:
2 edited

Legend:

Unmodified
Added
Removed
  • test/digraph_test.cc

    r377 r388  
    2929
    3030template <class Digraph>
    31 void checkDigraph() {
     31void checkDigraphBuild() {
    3232  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3333  Digraph G;
     
    5858  checkGraphConArcList(G, 1);
    5959
    60   Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     60  Arc a2 = G.addArc(n2, n1),
     61      a3 = G.addArc(n2, n3),
     62      a4 = G.addArc(n2, n3);
     63
    6164  checkGraphNodeList(G, 3);
    6265  checkGraphArcList(G, 4);
     
    7679  checkGraphNodeMap(G);
    7780  checkGraphArcMap(G);
    78 
    79 }
    80 
    81 void 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);
     81}
     82
     83template <class Digraph>
     84void 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
     114template <class Digraph>
     115void 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
     193template <class Digraph>
     194void 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
     242template <class Digraph>
     243void 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);
    95274
    96275  checkNodeIds(G);
     
    99278  checkGraphArcMap(G);
    100279
    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 
     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);
    112289}
    113290
     
    196373}
    197374
     375void 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
    198407void checkDigraphs() {
    199408  { // Checking ListDigraph
    200     checkDigraph<ListDigraph>();
     409    checkDigraphBuild<ListDigraph>();
     410    checkDigraphSplit<ListDigraph>();
     411    checkDigraphAlter<ListDigraph>();
     412    checkDigraphErase<ListDigraph>();
     413    checkDigraphSnapshot<ListDigraph>();
    201414    checkDigraphValidityErase<ListDigraph>();
    202415  }
    203416  { // Checking SmartDigraph
    204     checkDigraph<SmartDigraph>();
     417    checkDigraphBuild<SmartDigraph>();
     418    checkDigraphSplit<SmartDigraph>();
     419    checkDigraphSnapshot<SmartDigraph>();
    205420    checkDigraphValidity<SmartDigraph>();
    206421  }
  • test/digraph_test.cc

    r387 r388  
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
    22 //#include <lemon/full_graph.h>
    23 //#include <lemon/hypercube_graph.h>
     22#include <lemon/full_graph.h>
    2423
    2524#include "test_tools.h"
     
    319318    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    320319  }
    321 //  { // Checking FullDigraph
    322 //    checkConcept<Digraph, FullDigraph>();
    323 //  }
    324 //  { // Checking HyperCubeDigraph
    325 //    checkConcept<Digraph, HyperCubeDigraph>();
    326 //  }
     320  { // Checking FullDigraph
     321    checkConcept<Digraph, FullDigraph>();
     322  }
    327323}
    328324
     
    375371  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    376372  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     373}
     374
     375void 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  }
    377405}
    378406
     
    392420    checkDigraphValidity<SmartDigraph>();
    393421  }
     422  { // Checking FullDigraph
     423    checkFullDigraph(8);
     424  }
    394425}
    395426
Note: See TracChangeset for help on using the changeset viewer.