COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [372:7b6466ed488a:375:2d87dbd7f8c8] in lemon-1.2


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • lemon/smart_graph.h

    r371 r375  
    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();

  • test/digraph_test.cc

    r365 r375  
    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/graph_test.cc

    r372 r375  
    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.h

    r263 r374  
    115115    check(e==INVALID,"Wrong IncEdge list linking.");
    116116    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
     117  }
     118
     119  template <class Graph>
     120  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
     121                                 int cnt)
     122  {
     123    checkGraphIncEdgeList(G, n, cnt);
     124    checkGraphOutArcList(G, n, cnt);
     125    checkGraphInArcList(G, n, cnt);
    117126  }
    118127
Note: See TracChangeset for help on using the changeset viewer.