COIN-OR::LEMON - Graph Library

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


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/smart_graph.h

    r375 r371  
    738738        dir.push_back(arcFromId(n-1));
    739739        Parent::notifier(Arc()).erase(dir);
    740         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
    741         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
     740        nodes[arcs[n].target].first_out=arcs[n].next_out;
     741        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
    742742        arcs.pop_back();
    743743        arcs.pop_back();
  • test/digraph_test.cc

    r375 r365  
    2929
    3030template <class Digraph>
    31 void checkDigraphBuild() {
     31void checkDigraph() {
    3232  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3333  Digraph G;
     
    5858  checkGraphConArcList(G, 1);
    5959
    60   Arc a2 = G.addArc(n2, n1),
    61       a3 = G.addArc(n2, n3),
    62       a4 = G.addArc(n2, n3);
    63 
     60  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    6461  checkGraphNodeList(G, 3);
    6562  checkGraphArcList(G, 4);
     
    7976  checkGraphNodeMap(G);
    8077  checkGraphArcMap(G);
    81 }
    82 
    83 template <class Digraph>
    84 void 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 
    114 template <class Digraph>
    115 void 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 
    193 template <class Digraph>
    194 void 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 
    242 template <class Digraph>
    243 void 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);
     78
     79}
     80
     81void 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);
    27495
    27596  checkNodeIds(G);
     
    27899  checkGraphArcMap(G);
    279100
    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);
     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
    289112}
    290113
     
    373196}
    374197
    375 void 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 
    407198void checkDigraphs() {
    408199  { // Checking ListDigraph
    409     checkDigraphBuild<ListDigraph>();
    410     checkDigraphSplit<ListDigraph>();
    411     checkDigraphAlter<ListDigraph>();
    412     checkDigraphErase<ListDigraph>();
    413     checkDigraphSnapshot<ListDigraph>();
     200    checkDigraph<ListDigraph>();
    414201    checkDigraphValidityErase<ListDigraph>();
    415202  }
    416203  { // Checking SmartDigraph
    417     checkDigraphBuild<SmartDigraph>();
    418     checkDigraphSplit<SmartDigraph>();
    419     checkDigraphSnapshot<SmartDigraph>();
     204    checkDigraph<SmartDigraph>();
    420205    checkDigraphValidity<SmartDigraph>();
    421206  }
  • test/graph_test.cc

    r375 r372  
    3131
    3232template <class Graph>
    33 void checkGraphBuild() {
     33void checkGraph() {
    3434  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3535
     
    3737  checkGraphNodeList(G, 0);
    3838  checkGraphEdgeList(G, 0);
    39   checkGraphArcList(G, 0);
    4039
    4140  Node
     
    4544  checkGraphNodeList(G, 3);
    4645  checkGraphEdgeList(G, 0);
    47   checkGraphArcList(G, 0);
    4846
    4947  Edge e1 = G.addEdge(n1, n2);
    5048  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    5149        "Wrong edge");
    52 
    5350  checkGraphNodeList(G, 3);
     51  checkGraphArcList(G, 2);
    5452  checkGraphEdgeList(G, 1);
    55   checkGraphArcList(G, 2);
    56 
    57   checkGraphIncEdgeArcLists(G, n1, 1);
    58   checkGraphIncEdgeArcLists(G, n2, 1);
    59   checkGraphIncEdgeArcLists(G, n3, 0);
    60 
     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
     66  checkGraphConArcList(G, 2);
    6167  checkGraphConEdgeList(G, 1);
    62   checkGraphConArcList(G, 2);
    63 
    64   Edge e2 = G.addEdge(n2, n1),
    65        e3 = G.addEdge(n2, n3);
    66 
     68
     69  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    6770  checkGraphNodeList(G, 3);
     71  checkGraphArcList(G, 6);
    6872  checkGraphEdgeList(G, 3);
    69   checkGraphArcList(G, 6);
    70 
    71   checkGraphIncEdgeArcLists(G, n1, 2);
    72   checkGraphIncEdgeArcLists(G, n2, 3);
    73   checkGraphIncEdgeArcLists(G, n3, 1);
    74 
     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
     86  checkGraphConArcList(G, 6);
    7587  checkGraphConEdgeList(G, 3);
    76   checkGraphConArcList(G, 6);
    7788
    7889  checkArcDirections(G);
     
    8495  checkGraphArcMap(G);
    8596  checkGraphEdgeMap(G);
    86 }
    87 
    88 template <class Graph>
    89 void 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 
    167 template <class Graph>
    168 void 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 
    209 template <class Graph>
    210 void 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);
    26397}
    26498
     
    533367void checkGraphs() {
    534368  { // Checking ListGraph
    535     checkGraphBuild<ListGraph>();
    536     checkGraphAlter<ListGraph>();
    537     checkGraphErase<ListGraph>();
    538     checkGraphSnapshot<ListGraph>();
     369    checkGraph<ListGraph>();
    539370    checkGraphValidityErase<ListGraph>();
    540371  }
    541372  { // Checking SmartGraph
    542     checkGraphBuild<SmartGraph>();
    543     checkGraphSnapshot<SmartGraph>();
     373    checkGraph<SmartGraph>();
    544374    checkGraphValidity<SmartGraph>();
    545375  }
  • test/graph_test.h

    r374 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.