COIN-OR::LEMON - Graph Library

Changeset 387:49d9a36b3b84 in lemon for test/digraph_test.cc


Ignore:
Timestamp:
11/07/08 12:15:16 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
388:2d87dbd7f8c8, 389:a0b5131b958e
Phase:
public
Message:

Extend test cases for graphs and digraphs (#172)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/digraph_test.cc

    r228 r387  
    3030
    3131template <class Digraph>
    32 void checkDigraph() {
     32void checkDigraphBuild() {
    3333  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3434  Digraph G;
     
    5959  checkGraphConArcList(G, 1);
    6060
    61   Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     61  Arc a2 = G.addArc(n2, n1),
     62      a3 = G.addArc(n2, n3),
     63      a4 = G.addArc(n2, n3);
     64
    6265  checkGraphNodeList(G, 3);
    6366  checkGraphArcList(G, 4);
     
    7780  checkGraphNodeMap(G);
    7881  checkGraphArcMap(G);
    79 
    80 }
    81 
     82}
     83
     84template <class Digraph>
     85void checkDigraphSplit() {
     86  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     87
     88  Digraph G;
     89  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
     90  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
     91      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     92
     93  Node n4 = G.split(n2);
     94
     95  check(G.target(OutArcIt(G, n2)) == n4 &&
     96        G.source(InArcIt(G, n4)) == n2,
     97        "Wrong split.");
     98
     99  checkGraphNodeList(G, 4);
     100  checkGraphArcList(G, 5);
     101
     102  checkGraphOutArcList(G, n1, 1);
     103  checkGraphOutArcList(G, n2, 1);
     104  checkGraphOutArcList(G, n3, 0);
     105  checkGraphOutArcList(G, n4, 3);
     106
     107  checkGraphInArcList(G, n1, 1);
     108  checkGraphInArcList(G, n2, 1);
     109  checkGraphInArcList(G, n3, 2);
     110  checkGraphInArcList(G, n4, 1);
     111
     112  checkGraphConArcList(G, 5);
     113}
     114
     115template <class Digraph>
     116void checkDigraphAlter() {
     117  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     118
     119  Digraph G;
     120  Node n1 = G.addNode(), n2 = G.addNode(),
     121       n3 = G.addNode(), n4 = G.addNode();
     122  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
     123      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
     124      a5 = G.addArc(n2, n4);
     125
     126  checkGraphNodeList(G, 4);
     127  checkGraphArcList(G, 5);
     128
     129  // Check changeSource() and changeTarget()
     130  G.changeTarget(a4, n1);
     131
     132  checkGraphNodeList(G, 4);
     133  checkGraphArcList(G, 5);
     134
     135  checkGraphOutArcList(G, n1, 1);
     136  checkGraphOutArcList(G, n2, 1);
     137  checkGraphOutArcList(G, n3, 0);
     138  checkGraphOutArcList(G, n4, 3);
     139
     140  checkGraphInArcList(G, n1, 2);
     141  checkGraphInArcList(G, n2, 1);
     142  checkGraphInArcList(G, n3, 1);
     143  checkGraphInArcList(G, n4, 1);
     144
     145  checkGraphConArcList(G, 5);
     146
     147  G.changeSource(a4, n3);
     148
     149  checkGraphNodeList(G, 4);
     150  checkGraphArcList(G, 5);
     151
     152  checkGraphOutArcList(G, n1, 1);
     153  checkGraphOutArcList(G, n2, 1);
     154  checkGraphOutArcList(G, n3, 1);
     155  checkGraphOutArcList(G, n4, 2);
     156
     157  checkGraphInArcList(G, n1, 2);
     158  checkGraphInArcList(G, n2, 1);
     159  checkGraphInArcList(G, n3, 1);
     160  checkGraphInArcList(G, n4, 1);
     161
     162  checkGraphConArcList(G, 5);
     163
     164  // Check contract()
     165  G.contract(n2, n4, false);
     166
     167  checkGraphNodeList(G, 3);
     168  checkGraphArcList(G, 5);
     169
     170  checkGraphOutArcList(G, n1, 1);
     171  checkGraphOutArcList(G, n2, 3);
     172  checkGraphOutArcList(G, n3, 1);
     173
     174  checkGraphInArcList(G, n1, 2);
     175  checkGraphInArcList(G, n2, 2);
     176  checkGraphInArcList(G, n3, 1);
     177
     178  checkGraphConArcList(G, 5);
     179
     180  G.contract(n2, n1);
     181
     182  checkGraphNodeList(G, 2);
     183  checkGraphArcList(G, 3);
     184
     185  checkGraphOutArcList(G, n2, 2);
     186  checkGraphOutArcList(G, n3, 1);
     187
     188  checkGraphInArcList(G, n2, 2);
     189  checkGraphInArcList(G, n3, 1);
     190
     191  checkGraphConArcList(G, 3);
     192}
     193
     194template <class Digraph>
     195void checkDigraphErase() {
     196  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     197
     198  Digraph G;
     199  Node n1 = G.addNode(), n2 = G.addNode(),
     200       n3 = G.addNode(), n4 = G.addNode();
     201  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
     202      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
     203      a5 = G.addArc(n2, n4);
     204
     205  // Check arc deletion
     206  G.erase(a1);
     207
     208  checkGraphNodeList(G, 4);
     209  checkGraphArcList(G, 4);
     210
     211  checkGraphOutArcList(G, n1, 0);
     212  checkGraphOutArcList(G, n2, 1);
     213  checkGraphOutArcList(G, n3, 1);
     214  checkGraphOutArcList(G, n4, 2);
     215
     216  checkGraphInArcList(G, n1, 2);
     217  checkGraphInArcList(G, n2, 0);
     218  checkGraphInArcList(G, n3, 1);
     219  checkGraphInArcList(G, n4, 1);
     220
     221  checkGraphConArcList(G, 4);
     222
     223  // Check node deletion
     224  G.erase(n4);
     225
     226  checkGraphNodeList(G, 3);
     227  checkGraphArcList(G, 1);
     228
     229  checkGraphOutArcList(G, n1, 0);
     230  checkGraphOutArcList(G, n2, 0);
     231  checkGraphOutArcList(G, n3, 1);
     232  checkGraphOutArcList(G, n4, 0);
     233
     234  checkGraphInArcList(G, n1, 1);
     235  checkGraphInArcList(G, n2, 0);
     236  checkGraphInArcList(G, n3, 0);
     237  checkGraphInArcList(G, n4, 0);
     238
     239  checkGraphConArcList(G, 1);
     240}
     241
     242
     243template <class Digraph>
     244void checkDigraphSnapshot() {
     245  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     246
     247  Digraph G;
     248  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
     249  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
     250      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     251
     252  typename Digraph::Snapshot snapshot(G);
     253
     254  Node n = G.addNode();
     255  G.addArc(n3, n);
     256  G.addArc(n, n3);
     257
     258  checkGraphNodeList(G, 4);
     259  checkGraphArcList(G, 6);
     260
     261  snapshot.restore();
     262
     263  checkGraphNodeList(G, 3);
     264  checkGraphArcList(G, 4);
     265
     266  checkGraphOutArcList(G, n1, 1);
     267  checkGraphOutArcList(G, n2, 3);
     268  checkGraphOutArcList(G, n3, 0);
     269
     270  checkGraphInArcList(G, n1, 1);
     271  checkGraphInArcList(G, n2, 1);
     272  checkGraphInArcList(G, n3, 2);
     273
     274  checkGraphConArcList(G, 4);
     275
     276  checkNodeIds(G);
     277  checkArcIds(G);
     278  checkGraphNodeMap(G);
     279  checkGraphArcMap(G);
     280
     281  G.addNode();
     282  snapshot.save(G);
     283
     284  G.addArc(G.addNode(), G.addNode());
     285
     286  snapshot.restore();
     287
     288  checkGraphNodeList(G, 4);
     289  checkGraphArcList(G, 4);
     290}
    82291
    83292void checkConcepts() {
     
    170379void checkDigraphs() {
    171380  { // Checking ListDigraph
    172     checkDigraph<ListDigraph>();
     381    checkDigraphBuild<ListDigraph>();
     382    checkDigraphSplit<ListDigraph>();
     383    checkDigraphAlter<ListDigraph>();
     384    checkDigraphErase<ListDigraph>();
     385    checkDigraphSnapshot<ListDigraph>();
    173386    checkDigraphValidityErase<ListDigraph>();
    174387  }
    175388  { // Checking SmartDigraph
    176     checkDigraph<SmartDigraph>();
     389    checkDigraphBuild<SmartDigraph>();
     390    checkDigraphSplit<SmartDigraph>();
     391    checkDigraphSnapshot<SmartDigraph>();
    177392    checkDigraphValidity<SmartDigraph>();
    178393  }
Note: See TracChangeset for help on using the changeset viewer.