COIN-OR::LEMON - Graph Library

Changeset 388:2d87dbd7f8c8 in lemon


Ignore:
Timestamp:
11/07/08 14:14:22 (15 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:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/smart_graph.h

    r384 r388  
    738738        dir.push_back(arcFromId(n-1));
    739739        Parent::notifier(Arc()).erase(dir);
    740         nodes[arcs[n].target].first_out=arcs[n].next_out;
    741         nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
     740        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
     741        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
    742742        arcs.pop_back();
    743743        arcs.pop_back();
  • lemon/smart_graph.h

    r386 r388  
    6868
    6969    typedef True NodeNumTag;
    70     typedef True EdgeNumTag;
     70    typedef True ArcNumTag;
    7171
    7272    int nodeNum() const { return nodes.size(); }
     
    467467
    468468    public:
    469       operator Edge() const { 
    470         return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
     469      operator Edge() const {
     470        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
    471471      }
    472472
     
    483483      : nodes(), arcs() {}
    484484
     485    typedef True NodeNumTag;
     486    typedef True EdgeNumTag;
     487    typedef True ArcNumTag;
     488
     489    int nodeNum() const { return nodes.size(); }
     490    int edgeNum() const { return arcs.size() / 2; }
     491    int arcNum() const { return arcs.size(); }
    485492
    486493    int maxNodeId() const { return nodes.size()-1; }
  • 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
  • test/graph_test.cc

    r385 r388  
    3131
    3232template <class Graph>
    33 void checkGraph() {
     33void checkGraphBuild() {
    3434  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3535
     
    3737  checkGraphNodeList(G, 0);
    3838  checkGraphEdgeList(G, 0);
     39  checkGraphArcList(G, 0);
    3940
    4041  Node
     
    4445  checkGraphNodeList(G, 3);
    4546  checkGraphEdgeList(G, 0);
     47  checkGraphArcList(G, 0);
    4648
    4749  Edge e1 = G.addEdge(n1, n2);
    4850  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    4951        "Wrong edge");
    50   checkGraphNodeList(G, 3);
     52
     53  checkGraphNodeList(G, 3);
     54  checkGraphEdgeList(G, 1);
    5155  checkGraphArcList(G, 2);
    52   checkGraphEdgeList(G, 1);
    53 
    54   checkGraphOutArcList(G, n1, 1);
    55   checkGraphOutArcList(G, n2, 1);
    56   checkGraphOutArcList(G, n3, 0);
    57 
    58   checkGraphInArcList(G, n1, 1);
    59   checkGraphInArcList(G, n2, 1);
    60   checkGraphInArcList(G, n3, 0);
    61 
    62   checkGraphIncEdgeList(G, n1, 1);
    63   checkGraphIncEdgeList(G, n2, 1);
    64   checkGraphIncEdgeList(G, n3, 0);
    65 
     56
     57  checkGraphIncEdgeArcLists(G, n1, 1);
     58  checkGraphIncEdgeArcLists(G, n2, 1);
     59  checkGraphIncEdgeArcLists(G, n3, 0);
     60
     61  checkGraphConEdgeList(G, 1);
    6662  checkGraphConArcList(G, 2);
    67   checkGraphConEdgeList(G, 1);
    68 
    69   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    70   checkGraphNodeList(G, 3);
     63
     64  Edge e2 = G.addEdge(n2, n1),
     65       e3 = G.addEdge(n2, n3);
     66
     67  checkGraphNodeList(G, 3);
     68  checkGraphEdgeList(G, 3);
    7169  checkGraphArcList(G, 6);
    72   checkGraphEdgeList(G, 3);
    73 
    74   checkGraphOutArcList(G, n1, 2);
    75   checkGraphOutArcList(G, n2, 3);
    76   checkGraphOutArcList(G, n3, 1);
    77 
    78   checkGraphInArcList(G, n1, 2);
    79   checkGraphInArcList(G, n2, 3);
    80   checkGraphInArcList(G, n3, 1);
    81 
    82   checkGraphIncEdgeList(G, n1, 2);
    83   checkGraphIncEdgeList(G, n2, 3);
    84   checkGraphIncEdgeList(G, n3, 1);
    85 
     70
     71  checkGraphIncEdgeArcLists(G, n1, 2);
     72  checkGraphIncEdgeArcLists(G, n2, 3);
     73  checkGraphIncEdgeArcLists(G, n3, 1);
     74
     75  checkGraphConEdgeList(G, 3);
    8676  checkGraphConArcList(G, 6);
    87   checkGraphConEdgeList(G, 3);
    8877
    8978  checkArcDirections(G);
     
    9584  checkGraphArcMap(G);
    9685  checkGraphEdgeMap(G);
     86}
     87
     88template <class Graph>
     89void checkGraphAlter() {
     90  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     91
     92  Graph G;
     93  Node n1 = G.addNode(), n2 = G.addNode(),
     94       n3 = G.addNode(), n4 = G.addNode();
     95  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     96       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
     97       e5 = G.addEdge(n4, n3);
     98
     99  checkGraphNodeList(G, 4);
     100  checkGraphEdgeList(G, 5);
     101  checkGraphArcList(G, 10);
     102
     103  // Check changeU() and changeV()
     104  if (G.u(e2) == n2) {
     105    G.changeU(e2, n3);
     106  } else {
     107    G.changeV(e2, n3);
     108  }
     109
     110  checkGraphNodeList(G, 4);
     111  checkGraphEdgeList(G, 5);
     112  checkGraphArcList(G, 10);
     113
     114  checkGraphIncEdgeArcLists(G, n1, 3);
     115  checkGraphIncEdgeArcLists(G, n2, 2);
     116  checkGraphIncEdgeArcLists(G, n3, 3);
     117  checkGraphIncEdgeArcLists(G, n4, 2);
     118
     119  checkGraphConEdgeList(G, 5);
     120  checkGraphConArcList(G, 10);
     121
     122  if (G.u(e2) == n1) {
     123    G.changeU(e2, n2);
     124  } else {
     125    G.changeV(e2, n2);
     126  }
     127
     128  checkGraphNodeList(G, 4);
     129  checkGraphEdgeList(G, 5);
     130  checkGraphArcList(G, 10);
     131
     132  checkGraphIncEdgeArcLists(G, n1, 2);
     133  checkGraphIncEdgeArcLists(G, n2, 3);
     134  checkGraphIncEdgeArcLists(G, n3, 3);
     135  checkGraphIncEdgeArcLists(G, n4, 2);
     136
     137  checkGraphConEdgeList(G, 5);
     138  checkGraphConArcList(G, 10);
     139
     140  // Check contract()
     141  G.contract(n1, n4, false);
     142
     143  checkGraphNodeList(G, 3);
     144  checkGraphEdgeList(G, 5);
     145  checkGraphArcList(G, 10);
     146
     147  checkGraphIncEdgeArcLists(G, n1, 4);
     148  checkGraphIncEdgeArcLists(G, n2, 3);
     149  checkGraphIncEdgeArcLists(G, n3, 3);
     150
     151  checkGraphConEdgeList(G, 5);
     152  checkGraphConArcList(G, 10);
     153
     154  G.contract(n2, n3);
     155
     156  checkGraphNodeList(G, 2);
     157  checkGraphEdgeList(G, 3);
     158  checkGraphArcList(G, 6);
     159
     160  checkGraphIncEdgeArcLists(G, n1, 4);
     161  checkGraphIncEdgeArcLists(G, n2, 2);
     162
     163  checkGraphConEdgeList(G, 3);
     164  checkGraphConArcList(G, 6);
     165}
     166
     167template <class Graph>
     168void checkGraphErase() {
     169  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     170
     171  Graph G;
     172  Node n1 = G.addNode(), n2 = G.addNode(),
     173       n3 = G.addNode(), n4 = G.addNode();
     174  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     175       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
     176       e5 = G.addEdge(n4, n3);
     177
     178  // Check edge deletion
     179  G.erase(e2);
     180
     181  checkGraphNodeList(G, 4);
     182  checkGraphEdgeList(G, 4);
     183  checkGraphArcList(G, 8);
     184
     185  checkGraphIncEdgeArcLists(G, n1, 2);
     186  checkGraphIncEdgeArcLists(G, n2, 2);
     187  checkGraphIncEdgeArcLists(G, n3, 2);
     188  checkGraphIncEdgeArcLists(G, n4, 2);
     189
     190  checkGraphConEdgeList(G, 4);
     191  checkGraphConArcList(G, 8);
     192
     193  // Check node deletion
     194  G.erase(n3);
     195
     196  checkGraphNodeList(G, 3);
     197  checkGraphEdgeList(G, 2);
     198  checkGraphArcList(G, 4);
     199
     200  checkGraphIncEdgeArcLists(G, n1, 2);
     201  checkGraphIncEdgeArcLists(G, n2, 1);
     202  checkGraphIncEdgeArcLists(G, n4, 1);
     203
     204  checkGraphConEdgeList(G, 2);
     205  checkGraphConArcList(G, 4);
     206}
     207
     208
     209template <class Graph>
     210void checkGraphSnapshot() {
     211  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     212
     213  Graph G;
     214  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
     215  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     216       e3 = G.addEdge(n2, n3);
     217
     218  checkGraphNodeList(G, 3);
     219  checkGraphEdgeList(G, 3);
     220  checkGraphArcList(G, 6);
     221
     222  typename Graph::Snapshot snapshot(G);
     223
     224  Node n = G.addNode();
     225  G.addEdge(n3, n);
     226  G.addEdge(n, n3);
     227  G.addEdge(n3, n2);
     228
     229  checkGraphNodeList(G, 4);
     230  checkGraphEdgeList(G, 6);
     231  checkGraphArcList(G, 12);
     232
     233  snapshot.restore();
     234
     235  checkGraphNodeList(G, 3);
     236  checkGraphEdgeList(G, 3);
     237  checkGraphArcList(G, 6);
     238
     239  checkGraphIncEdgeArcLists(G, n1, 2);
     240  checkGraphIncEdgeArcLists(G, n2, 3);
     241  checkGraphIncEdgeArcLists(G, n3, 1);
     242
     243  checkGraphConEdgeList(G, 3);
     244  checkGraphConArcList(G, 6);
     245
     246  checkNodeIds(G);
     247  checkEdgeIds(G);
     248  checkArcIds(G);
     249  checkGraphNodeMap(G);
     250  checkGraphEdgeMap(G);
     251  checkGraphArcMap(G);
     252
     253  G.addNode();
     254  snapshot.save(G);
     255
     256  G.addEdge(G.addNode(), G.addNode());
     257
     258  snapshot.restore();
     259
     260  checkGraphNodeList(G, 4);
     261  checkGraphEdgeList(G, 3);
     262  checkGraphArcList(G, 6);
    97263}
    98264
     
    367533void checkGraphs() {
    368534  { // Checking ListGraph
    369     checkGraph<ListGraph>();
     535    checkGraphBuild<ListGraph>();
     536    checkGraphAlter<ListGraph>();
     537    checkGraphErase<ListGraph>();
     538    checkGraphSnapshot<ListGraph>();
    370539    checkGraphValidityErase<ListGraph>();
    371540  }
    372541  { // Checking SmartGraph
    373     checkGraph<SmartGraph>();
     542    checkGraphBuild<SmartGraph>();
     543    checkGraphSnapshot<SmartGraph>();
    374544    checkGraphValidity<SmartGraph>();
    375545  }
  • test/graph_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/grid_graph.h>
     22#include <lemon/full_graph.h>
     23#include <lemon/grid_graph.h>
     24#include <lemon/hypercube_graph.h>
    2425
    2526#include "test_tools.h"
     
    262263}
    263264
     265void checkFullGraph(int num) {
     266  typedef FullGraph Graph;
     267  GRAPH_TYPEDEFS(Graph);
     268
     269  Graph G(num);
     270  checkGraphNodeList(G, num);
     271  checkGraphEdgeList(G, num * (num - 1) / 2);
     272
     273  for (NodeIt n(G); n != INVALID; ++n) {
     274    checkGraphOutArcList(G, n, num - 1);
     275    checkGraphInArcList(G, n, num - 1);
     276    checkGraphIncEdgeList(G, n, num - 1);
     277  }
     278
     279  checkGraphConArcList(G, num * (num - 1));
     280  checkGraphConEdgeList(G, num * (num - 1) / 2);
     281
     282  checkArcDirections(G);
     283
     284  checkNodeIds(G);
     285  checkArcIds(G);
     286  checkEdgeIds(G);
     287  checkGraphNodeMap(G);
     288  checkGraphArcMap(G);
     289  checkGraphEdgeMap(G);
     290
     291
     292  for (int i = 0; i < G.nodeNum(); ++i) {
     293    check(G.index(G(i)) == i, "Wrong index");
     294  }
     295
     296  for (NodeIt u(G); u != INVALID; ++u) {
     297    for (NodeIt v(G); v != INVALID; ++v) {
     298      Edge e = G.edge(u, v);
     299      Arc a = G.arc(u, v);
     300      if (u == v) {
     301        check(e == INVALID, "Wrong edge lookup");
     302        check(a == INVALID, "Wrong arc lookup");
     303      } else {
     304        check((G.u(e) == u && G.v(e) == v) ||
     305              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");
     306        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");
     307      }
     308    }
     309  }
     310}
     311
    264312void checkConcepts() {
    265313  { // Checking graph components
     
    291339    checkConcept<ClearableGraphComponent<>, SmartGraph>();
    292340  }
    293 //  { // Checking FullGraph
    294 //    checkConcept<Graph, FullGraph>();
    295 //    checkGraphIterators<FullGraph>();
    296 //  }
    297 //  { // Checking GridGraph
    298 //    checkConcept<Graph, GridGraph>();
    299 //    checkGraphIterators<GridGraph>();
    300 //  }
     341  { // Checking FullGraph
     342    checkConcept<Graph, FullGraph>();
     343  }
     344  { // Checking GridGraph
     345    checkConcept<Graph, GridGraph>();
     346  }
     347  { // Checking HypercubeGraph
     348    checkConcept<Graph, HypercubeGraph>();
     349  }
    301350}
    302351
     
    355404}
    356405
    357 // void checkGridGraph(const GridGraph& g, int w, int h) {
    358 //   check(g.width() == w, "Wrong width");
    359 //   check(g.height() == h, "Wrong height");
    360 
    361 //   for (int i = 0; i < w; ++i) {
    362 //     for (int j = 0; j < h; ++j) {
    363 //       check(g.col(g(i, j)) == i, "Wrong col");
    364 //       check(g.row(g(i, j)) == j, "Wrong row");
    365 //     }
    366 //   }
    367 
    368 //   for (int i = 0; i < w; ++i) {
    369 //     for (int j = 0; j < h - 1; ++j) {
    370 //       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    371 //       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    372 //     }
    373 //     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    374 //   }
    375 
    376 //   for (int i = 0; i < w; ++i) {
    377 //     for (int j = 1; j < h; ++j) {
    378 //       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    379 //       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    380 //     }
    381 //     check(g.up(g(i, 0)) == INVALID, "Wrong up");
    382 //   }
    383 
    384 //   for (int j = 0; j < h; ++j) {
    385 //     for (int i = 0; i < w - 1; ++i) {
    386 //       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    387 //       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    388 //     }
    389 //     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    390 //   }
    391 
    392 //   for (int j = 0; j < h; ++j) {
    393 //     for (int i = 1; i < w; ++i) {
    394 //       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
    395 //       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
    396 //     }
    397 //     check(g.left(g(0, j)) == INVALID, "Wrong left");
    398 //   }
    399 // }
     406void checkGridGraph(int width, int height) {
     407  typedef GridGraph Graph;
     408  GRAPH_TYPEDEFS(Graph);
     409  Graph G(width, height);
     410
     411  check(G.width() == width, "Wrong column number");
     412  check(G.height() == height, "Wrong row number");
     413
     414  for (int i = 0; i < width; ++i) {
     415    for (int j = 0; j < height; ++j) {
     416      check(G.col(G(i, j)) == i, "Wrong column");
     417      check(G.row(G(i, j)) == j, "Wrong row");
     418      check(G.pos(G(i, j)).x == i, "Wrong column");
     419      check(G.pos(G(i, j)).y == j, "Wrong row");
     420    }
     421  }
     422
     423  for (int j = 0; j < height; ++j) {
     424    for (int i = 0; i < width - 1; ++i) {
     425      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
     426      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
     427    }
     428    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
     429  }
     430
     431  for (int j = 0; j < height; ++j) {
     432    for (int i = 1; i < width; ++i) {
     433      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
     434      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
     435    }
     436    check(G.left(G(0, j)) == INVALID, "Wrong left");
     437  }
     438
     439  for (int i = 0; i < width; ++i) {
     440    for (int j = 0; j < height - 1; ++j) {
     441      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
     442      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
     443    }
     444    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
     445  }
     446
     447  for (int i = 0; i < width; ++i) {
     448    for (int j = 1; j < height; ++j) {
     449      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
     450      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
     451    }
     452    check(G.down(G(i, 0)) == INVALID, "Wrong down");
     453  }
     454
     455  checkGraphNodeList(G, width * height);
     456  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
     457  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     458
     459  for (NodeIt n(G); n != INVALID; ++n) {
     460    int nb = 4;
     461    if (G.col(n) == 0) --nb;
     462    if (G.col(n) == width - 1) --nb;
     463    if (G.row(n) == 0) --nb;
     464    if (G.row(n) == height - 1) --nb;
     465
     466    checkGraphOutArcList(G, n, nb);
     467    checkGraphInArcList(G, n, nb);
     468    checkGraphIncEdgeList(G, n, nb);
     469  }
     470
     471  checkArcDirections(G);
     472
     473  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     474  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
     475
     476  checkNodeIds(G);
     477  checkArcIds(G);
     478  checkEdgeIds(G);
     479  checkGraphNodeMap(G);
     480  checkGraphArcMap(G);
     481  checkGraphEdgeMap(G);
     482
     483}
     484
     485void checkHypercubeGraph(int dim) {
     486  GRAPH_TYPEDEFS(HypercubeGraph);
     487
     488  HypercubeGraph G(dim);
     489  checkGraphNodeList(G, 1 << dim);
     490  checkGraphEdgeList(G, dim * (1 << (dim-1)));
     491  checkGraphArcList(G, dim * (1 << dim));
     492
     493  Node n = G.nodeFromId(dim);
     494
     495  for (NodeIt n(G); n != INVALID; ++n) {
     496    checkGraphIncEdgeList(G, n, dim);
     497    for (IncEdgeIt e(G, n); e != INVALID; ++e) {
     498      check( (G.u(e) == n &&
     499              G.id(G.v(e)) == (G.id(n) ^ (1 << G.dimension(e)))) ||
     500             (G.v(e) == n &&
     501              G.id(G.u(e)) == (G.id(n) ^ (1 << G.dimension(e)))),
     502             "Wrong edge or wrong dimension");
     503    }
     504
     505    checkGraphOutArcList(G, n, dim);
     506    for (OutArcIt a(G, n); a != INVALID; ++a) {
     507      check(G.source(a) == n &&
     508            G.id(G.target(a)) == (G.id(n) ^ (1 << G.dimension(a))),
     509            "Wrong arc or wrong dimension");
     510    }
     511
     512    checkGraphInArcList(G, n, dim);
     513    for (InArcIt a(G, n); a != INVALID; ++a) {
     514      check(G.target(a) == n &&
     515            G.id(G.source(a)) == (G.id(n) ^ (1 << G.dimension(a))),
     516            "Wrong arc or wrong dimension");
     517    }
     518  }
     519
     520  checkGraphConArcList(G, (1 << dim) * dim);
     521  checkGraphConEdgeList(G, dim * (1 << (dim-1)));
     522
     523  checkArcDirections(G);
     524
     525  checkNodeIds(G);
     526  checkArcIds(G);
     527  checkEdgeIds(G);
     528  checkGraphNodeMap(G);
     529  checkGraphArcMap(G);
     530  checkGraphEdgeMap(G);
     531}
    400532
    401533void checkGraphs() {
     
    412544    checkGraphValidity<SmartGraph>();
    413545  }
    414 //   { // Checking FullGraph
    415 //     FullGraph g(5);
    416 //     checkGraphNodeList(g, 5);
    417 //     checkGraphEdgeList(g, 10);
    418 //   }
    419 //   { // Checking GridGraph
    420 //     GridGraph g(5, 6);
    421 //     checkGraphNodeList(g, 30);
    422 //     checkGraphEdgeList(g, 49);
    423 //     checkGridGraph(g, 5, 6);
    424 //   }
     546  { // Checking FullGraph
     547    checkFullGraph(7);
     548    checkFullGraph(8);
     549  }
     550  { // Checking GridGraph
     551    checkGridGraph(5, 8);
     552    checkGridGraph(8, 5);
     553    checkGridGraph(5, 5);
     554    checkGridGraph(0, 0);
     555    checkGridGraph(1, 1);
     556  }
     557  { // Checking HypercubeGraph
     558    checkHypercubeGraph(1);
     559    checkHypercubeGraph(2);
     560    checkHypercubeGraph(3);
     561    checkHypercubeGraph(4);
     562  }
    425563}
    426564
Note: See TracChangeset for help on using the changeset viewer.