COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
11/07/08 12:15:16 (11 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/graph_test.cc

    r228 r387  
    3030
    3131template <class Graph>
    32 void checkGraph() {
     32void checkGraphBuild() {
    3333  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3434
     
    3636  checkGraphNodeList(G, 0);
    3737  checkGraphEdgeList(G, 0);
     38  checkGraphArcList(G, 0);
    3839
    3940  Node
     
    4344  checkGraphNodeList(G, 3);
    4445  checkGraphEdgeList(G, 0);
     46  checkGraphArcList(G, 0);
    4547
    4648  Edge e1 = G.addEdge(n1, n2);
    4749  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    4850        "Wrong edge");
    49   checkGraphNodeList(G, 3);
     51
     52  checkGraphNodeList(G, 3);
     53  checkGraphEdgeList(G, 1);
    5054  checkGraphArcList(G, 2);
    51   checkGraphEdgeList(G, 1);
    52 
    53   checkGraphOutArcList(G, n1, 1);
    54   checkGraphOutArcList(G, n2, 1);
    55   checkGraphOutArcList(G, n3, 0);
    56 
    57   checkGraphInArcList(G, n1, 1);
    58   checkGraphInArcList(G, n2, 1);
    59   checkGraphInArcList(G, n3, 0);
    60 
    61   checkGraphIncEdgeList(G, n1, 1);
    62   checkGraphIncEdgeList(G, n2, 1);
    63   checkGraphIncEdgeList(G, n3, 0);
    64 
     55
     56  checkGraphIncEdgeArcLists(G, n1, 1);
     57  checkGraphIncEdgeArcLists(G, n2, 1);
     58  checkGraphIncEdgeArcLists(G, n3, 0);
     59
     60  checkGraphConEdgeList(G, 1);
    6561  checkGraphConArcList(G, 2);
    66   checkGraphConEdgeList(G, 1);
    67 
    68   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    69   checkGraphNodeList(G, 3);
     62
     63  Edge e2 = G.addEdge(n2, n1),
     64       e3 = G.addEdge(n2, n3);
     65
     66  checkGraphNodeList(G, 3);
     67  checkGraphEdgeList(G, 3);
    7068  checkGraphArcList(G, 6);
    71   checkGraphEdgeList(G, 3);
    72 
    73   checkGraphOutArcList(G, n1, 2);
    74   checkGraphOutArcList(G, n2, 3);
    75   checkGraphOutArcList(G, n3, 1);
    76 
    77   checkGraphInArcList(G, n1, 2);
    78   checkGraphInArcList(G, n2, 3);
    79   checkGraphInArcList(G, n3, 1);
    80 
    81   checkGraphIncEdgeList(G, n1, 2);
    82   checkGraphIncEdgeList(G, n2, 3);
    83   checkGraphIncEdgeList(G, n3, 1);
    84 
     69
     70  checkGraphIncEdgeArcLists(G, n1, 2);
     71  checkGraphIncEdgeArcLists(G, n2, 3);
     72  checkGraphIncEdgeArcLists(G, n3, 1);
     73
     74  checkGraphConEdgeList(G, 3);
    8575  checkGraphConArcList(G, 6);
    86   checkGraphConEdgeList(G, 3);
    8776
    8877  checkArcDirections(G);
     
    9483  checkGraphArcMap(G);
    9584  checkGraphEdgeMap(G);
     85}
     86
     87template <class Graph>
     88void checkGraphAlter() {
     89  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     90
     91  Graph G;
     92  Node n1 = G.addNode(), n2 = G.addNode(),
     93       n3 = G.addNode(), n4 = G.addNode();
     94  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     95       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
     96       e5 = G.addEdge(n4, n3);
     97
     98  checkGraphNodeList(G, 4);
     99  checkGraphEdgeList(G, 5);
     100  checkGraphArcList(G, 10);
     101
     102  // Check changeU() and changeV()
     103  if (G.u(e2) == n2) {
     104    G.changeU(e2, n3);
     105  } else {
     106    G.changeV(e2, n3);
     107  }
     108
     109  checkGraphNodeList(G, 4);
     110  checkGraphEdgeList(G, 5);
     111  checkGraphArcList(G, 10);
     112
     113  checkGraphIncEdgeArcLists(G, n1, 3);
     114  checkGraphIncEdgeArcLists(G, n2, 2);
     115  checkGraphIncEdgeArcLists(G, n3, 3);
     116  checkGraphIncEdgeArcLists(G, n4, 2);
     117
     118  checkGraphConEdgeList(G, 5);
     119  checkGraphConArcList(G, 10);
     120
     121  if (G.u(e2) == n1) {
     122    G.changeU(e2, n2);
     123  } else {
     124    G.changeV(e2, n2);
     125  }
     126
     127  checkGraphNodeList(G, 4);
     128  checkGraphEdgeList(G, 5);
     129  checkGraphArcList(G, 10);
     130
     131  checkGraphIncEdgeArcLists(G, n1, 2);
     132  checkGraphIncEdgeArcLists(G, n2, 3);
     133  checkGraphIncEdgeArcLists(G, n3, 3);
     134  checkGraphIncEdgeArcLists(G, n4, 2);
     135
     136  checkGraphConEdgeList(G, 5);
     137  checkGraphConArcList(G, 10);
     138
     139  // Check contract()
     140  G.contract(n1, n4, false);
     141
     142  checkGraphNodeList(G, 3);
     143  checkGraphEdgeList(G, 5);
     144  checkGraphArcList(G, 10);
     145
     146  checkGraphIncEdgeArcLists(G, n1, 4);
     147  checkGraphIncEdgeArcLists(G, n2, 3);
     148  checkGraphIncEdgeArcLists(G, n3, 3);
     149
     150  checkGraphConEdgeList(G, 5);
     151  checkGraphConArcList(G, 10);
     152
     153  G.contract(n2, n3);
     154
     155  checkGraphNodeList(G, 2);
     156  checkGraphEdgeList(G, 3);
     157  checkGraphArcList(G, 6);
     158
     159  checkGraphIncEdgeArcLists(G, n1, 4);
     160  checkGraphIncEdgeArcLists(G, n2, 2);
     161
     162  checkGraphConEdgeList(G, 3);
     163  checkGraphConArcList(G, 6);
     164}
     165
     166template <class Graph>
     167void checkGraphErase() {
     168  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     169
     170  Graph G;
     171  Node n1 = G.addNode(), n2 = G.addNode(),
     172       n3 = G.addNode(), n4 = G.addNode();
     173  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     174       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
     175       e5 = G.addEdge(n4, n3);
     176
     177  // Check edge deletion
     178  G.erase(e2);
     179
     180  checkGraphNodeList(G, 4);
     181  checkGraphEdgeList(G, 4);
     182  checkGraphArcList(G, 8);
     183
     184  checkGraphIncEdgeArcLists(G, n1, 2);
     185  checkGraphIncEdgeArcLists(G, n2, 2);
     186  checkGraphIncEdgeArcLists(G, n3, 2);
     187  checkGraphIncEdgeArcLists(G, n4, 2);
     188
     189  checkGraphConEdgeList(G, 4);
     190  checkGraphConArcList(G, 8);
     191
     192  // Check node deletion
     193  G.erase(n3);
     194
     195  checkGraphNodeList(G, 3);
     196  checkGraphEdgeList(G, 2);
     197  checkGraphArcList(G, 4);
     198
     199  checkGraphIncEdgeArcLists(G, n1, 2);
     200  checkGraphIncEdgeArcLists(G, n2, 1);
     201  checkGraphIncEdgeArcLists(G, n4, 1);
     202
     203  checkGraphConEdgeList(G, 2);
     204  checkGraphConArcList(G, 4);
     205}
     206
     207
     208template <class Graph>
     209void checkGraphSnapshot() {
     210  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     211
     212  Graph G;
     213  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
     214  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     215       e3 = G.addEdge(n2, n3);
     216
     217  checkGraphNodeList(G, 3);
     218  checkGraphEdgeList(G, 3);
     219  checkGraphArcList(G, 6);
     220
     221  typename Graph::Snapshot snapshot(G);
     222
     223  Node n = G.addNode();
     224  G.addEdge(n3, n);
     225  G.addEdge(n, n3);
     226  G.addEdge(n3, n2);
     227
     228  checkGraphNodeList(G, 4);
     229  checkGraphEdgeList(G, 6);
     230  checkGraphArcList(G, 12);
     231
     232  snapshot.restore();
     233
     234  checkGraphNodeList(G, 3);
     235  checkGraphEdgeList(G, 3);
     236  checkGraphArcList(G, 6);
     237
     238  checkGraphIncEdgeArcLists(G, n1, 2);
     239  checkGraphIncEdgeArcLists(G, n2, 3);
     240  checkGraphIncEdgeArcLists(G, n3, 1);
     241
     242  checkGraphConEdgeList(G, 3);
     243  checkGraphConArcList(G, 6);
     244
     245  checkNodeIds(G);
     246  checkEdgeIds(G);
     247  checkArcIds(G);
     248  checkGraphNodeMap(G);
     249  checkGraphEdgeMap(G);
     250  checkGraphArcMap(G);
     251
     252  G.addNode();
     253  snapshot.save(G);
     254
     255  G.addEdge(G.addNode(), G.addNode());
     256
     257  snapshot.restore();
     258
     259  checkGraphNodeList(G, 4);
     260  checkGraphEdgeList(G, 3);
     261  checkGraphArcList(G, 6);
    96262}
    97263
     
    235401void checkGraphs() {
    236402  { // Checking ListGraph
    237     checkGraph<ListGraph>();
     403    checkGraphBuild<ListGraph>();
     404    checkGraphAlter<ListGraph>();
     405    checkGraphErase<ListGraph>();
     406    checkGraphSnapshot<ListGraph>();
    238407    checkGraphValidityErase<ListGraph>();
    239408  }
    240409  { // Checking SmartGraph
    241     checkGraph<SmartGraph>();
     410    checkGraphBuild<SmartGraph>();
     411    checkGraphSnapshot<SmartGraph>();
    242412    checkGraphValidity<SmartGraph>();
    243413  }
Note: See TracChangeset for help on using the changeset viewer.