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 / [339:a0b5131b958e:336:cada82273723] in lemon-1.0


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • lemon/smart_graph.h

    r337 r335  
    731731        dir.push_back(arcFromId(n-1));
    732732        Parent::notifier(Arc()).erase(dir);
    733         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
    734         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
     733        nodes[arcs[n].target].first_out=arcs[n].next_out;
     734        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
    735735        arcs.pop_back();
    736736        arcs.pop_back();

  • test/digraph_test.cc

    r338 r228  
    3030
    3131template <class Digraph>
    32 void checkDigraphBuild() {
     32void checkDigraph() {
    3333  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3434  Digraph G;
    … …  
    5959  checkGraphConArcList(G, 1);
    6060
    61   Arc a2 = G.addArc(n2, n1),
    62       a3 = G.addArc(n2, n3),
    63       a4 = G.addArc(n2, n3);
    64 
    65   checkGraphNodeList(G, 3);
    66   checkGraphArcList(G, 4);
    67 
    68   checkGraphOutArcList(G, n1, 1);
    69   checkGraphOutArcList(G, n2, 3);
    70   checkGraphOutArcList(G, n3, 0);
    71 
    72   checkGraphInArcList(G, n1, 1);
    73   checkGraphInArcList(G, n2, 1);
    74   checkGraphInArcList(G, n3, 2);
    75 
    76   checkGraphConArcList(G, 4);
    77 
    78   checkNodeIds(G);
    79   checkArcIds(G);
    80   checkGraphNodeMap(G);
    81   checkGraphArcMap(G);
    82 }
    83 
    84 template <class Digraph>
    85 void 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 
    115 template <class Digraph>
    116 void 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 
    194 template <class Digraph>
    195 void 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 
    243 template <class Digraph>
    244 void 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 
     61  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    26362  checkGraphNodeList(G, 3);
    26463  checkGraphArcList(G, 4);
    … …  
    27978  checkGraphArcMap(G);
    28079
    281   G.addNode();
    282   snapshot.save(G);
     80}
    28381
    284   G.addArc(G.addNode(), G.addNode());
    285 
    286   snapshot.restore();
    287 
    288   checkGraphNodeList(G, 4);
    289   checkGraphArcList(G, 4);
    290 }
    29182
    29283void checkConcepts() {
    … …  
    379170void checkDigraphs() {
    380171  { // Checking ListDigraph
    381     checkDigraphBuild<ListDigraph>();
    382     checkDigraphSplit<ListDigraph>();
    383     checkDigraphAlter<ListDigraph>();
    384     checkDigraphErase<ListDigraph>();
    385     checkDigraphSnapshot<ListDigraph>();
     172    checkDigraph<ListDigraph>();
    386173    checkDigraphValidityErase<ListDigraph>();
    387174  }
    388175  { // Checking SmartDigraph
    389     checkDigraphBuild<SmartDigraph>();
    390     checkDigraphSplit<SmartDigraph>();
    391     checkDigraphSnapshot<SmartDigraph>();
     176    checkDigraph<SmartDigraph>();
    392177    checkDigraphValidity<SmartDigraph>();
    393178  }

  • test/graph_test.cc

    r338 r228  
    3030
    3131template <class Graph>
    32 void checkGraphBuild() {
     32void checkGraph() {
    3333  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3434
    … …  
    3636  checkGraphNodeList(G, 0);
    3737  checkGraphEdgeList(G, 0);
    38   checkGraphArcList(G, 0);
    3938
    4039  Node
    … …  
    4443  checkGraphNodeList(G, 3);
    4544  checkGraphEdgeList(G, 0);
    46   checkGraphArcList(G, 0);
    4745
    4846  Edge e1 = G.addEdge(n1, n2);
    4947  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    5048        "Wrong edge");
    51 
    5249  checkGraphNodeList(G, 3);
     50  checkGraphArcList(G, 2);
    5351  checkGraphEdgeList(G, 1);
    54   checkGraphArcList(G, 2);
    55 
    56   checkGraphIncEdgeArcLists(G, n1, 1);
    57   checkGraphIncEdgeArcLists(G, n2, 1);
    58   checkGraphIncEdgeArcLists(G, n3, 0);
    59 
     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
     65  checkGraphConArcList(G, 2);
    6066  checkGraphConEdgeList(G, 1);
    61   checkGraphConArcList(G, 2);
    62 
    63   Edge e2 = G.addEdge(n2, n1),
    64        e3 = G.addEdge(n2, n3);
    65 
     67
     68  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    6669  checkGraphNodeList(G, 3);
     70  checkGraphArcList(G, 6);
    6771  checkGraphEdgeList(G, 3);
    68   checkGraphArcList(G, 6);
    69 
    70   checkGraphIncEdgeArcLists(G, n1, 2);
    71   checkGraphIncEdgeArcLists(G, n2, 3);
    72   checkGraphIncEdgeArcLists(G, n3, 1);
    73 
     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
     85  checkGraphConArcList(G, 6);
    7486  checkGraphConEdgeList(G, 3);
    75   checkGraphConArcList(G, 6);
    7687
    7788  checkArcDirections(G);
    … …  
    8394  checkGraphArcMap(G);
    8495  checkGraphEdgeMap(G);
    85 }
    86 
    87 template <class Graph>
    88 void 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 
    166 template <class Graph>
    167 void 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 
    208 template <class Graph>
    209 void 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);
    26296}
    26397
    … …  
    401235void checkGraphs() {
    402236  { // Checking ListGraph
    403     checkGraphBuild<ListGraph>();
    404     checkGraphAlter<ListGraph>();
    405     checkGraphErase<ListGraph>();
    406     checkGraphSnapshot<ListGraph>();
     237    checkGraph<ListGraph>();
    407238    checkGraphValidityErase<ListGraph>();
    408239  }
    409240  { // Checking SmartGraph
    410     checkGraphBuild<SmartGraph>();
    411     checkGraphSnapshot<SmartGraph>();
     241    checkGraph<SmartGraph>();
    412242    checkGraphValidity<SmartGraph>();
    413243  }

  • test/graph_test.h

    r338 r263  
    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);
    126117  }
    127118
Note: See TracChangeset for help on using the changeset viewer.