test/digraph_test.cc
 branch 1.0 changeset 350 d5cfcff85dfd parent 228 b6732e0d38c5
equal inserted replaced
4:db88099cfdc8 5:f38728e44c24
`    27 `
`    27 `
`    28 using namespace lemon;`
`    28 using namespace lemon;`
`    29 using namespace lemon::concepts;`
`    29 using namespace lemon::concepts;`
`    30 `
`    30 `
`    31 template <class Digraph>`
`    31 template <class Digraph>`
`    32 void checkDigraph() {`
`    32 void checkDigraphBuild() {`
`    33   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);`
`    33   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);`
`    34   Digraph G;`
`    34   Digraph G;`
`    35 `
`    35 `
`    36   checkGraphNodeList(G, 0);`
`    36   checkGraphNodeList(G, 0);`
`    37   checkGraphArcList(G, 0);`
`    37   checkGraphArcList(G, 0);`
`    56   checkGraphInArcList(G, n2, 1);`
`    56   checkGraphInArcList(G, n2, 1);`
`    57   checkGraphInArcList(G, n3, 0);`
`    57   checkGraphInArcList(G, n3, 0);`
`    58 `
`    58 `
`    59   checkGraphConArcList(G, 1);`
`    59   checkGraphConArcList(G, 1);`
`    60 `
`    60 `
`    61   Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);`
`    61   Arc a2 = G.addArc(n2, n1),`
`       `
`    62       a3 = G.addArc(n2, n3),`
`       `
`    63       a4 = G.addArc(n2, n3);`
`       `
`    64 `
`    62   checkGraphNodeList(G, 3);`
`    65   checkGraphNodeList(G, 3);`
`    63   checkGraphArcList(G, 4);`
`    66   checkGraphArcList(G, 4);`
`    64 `
`    67 `
`    65   checkGraphOutArcList(G, n1, 1);`
`    68   checkGraphOutArcList(G, n1, 1);`
`    66   checkGraphOutArcList(G, n2, 3);`
`    69   checkGraphOutArcList(G, n2, 3);`
`    74 `
`    77 `
`    75   checkNodeIds(G);`
`    78   checkNodeIds(G);`
`    76   checkArcIds(G);`
`    79   checkArcIds(G);`
`    77   checkGraphNodeMap(G);`
`    80   checkGraphNodeMap(G);`
`    78   checkGraphArcMap(G);`
`    81   checkGraphArcMap(G);`
`    79 `
`    82 }`
`    80 }`
`    83 `
`    81 `
`    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 `
`       `
`   263   checkGraphNodeList(G, 3);`
`       `
`   264   checkGraphArcList(G, 4);`
`       `
`   265 `
`       `
`   266   checkGraphOutArcList(G, n1, 1);`
`       `
`   267   checkGraphOutArcList(G, n2, 3);`
`       `
`   268   checkGraphOutArcList(G, n3, 0);`
`       `
`   269 `
`       `
`   270   checkGraphInArcList(G, n1, 1);`
`       `
`   271   checkGraphInArcList(G, n2, 1);`
`       `
`   272   checkGraphInArcList(G, n3, 2);`
`       `
`   273 `
`       `
`   274   checkGraphConArcList(G, 4);`
`       `
`   275 `
`       `
`   276   checkNodeIds(G);`
`       `
`   277   checkArcIds(G);`
`       `
`   278   checkGraphNodeMap(G);`
`       `
`   279   checkGraphArcMap(G);`
`       `
`   280 `
`       `
`   281   G.addNode();`
`       `
`   282   snapshot.save(G);`
`       `
`   283 `
`       `
`   284   G.addArc(G.addNode(), G.addNode());`
`       `
`   285 `
`       `
`   286   snapshot.restore();`
`       `
`   287 `
`       `
`   288   checkGraphNodeList(G, 4);`
`       `
`   289   checkGraphArcList(G, 4);`
`       `
`   290 }`
`    82 `
`   291 `
`    83 void checkConcepts() {`
`   292 void checkConcepts() {`
`    84   { // Checking digraph components`
`   293   { // Checking digraph components`
`    85     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();`
`   294     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();`
`    86 `
`   295 `
`   167   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");`
`   376   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");`
`   168 }`
`   377 }`
`   169 `
`   378 `
`   170 void checkDigraphs() {`
`   379 void checkDigraphs() {`
`   171   { // Checking ListDigraph`
`   380   { // Checking ListDigraph`
`   172     checkDigraph<ListDigraph>();`
`   381     checkDigraphBuild<ListDigraph>();`
`       `
`   382     checkDigraphSplit<ListDigraph>();`
`       `
`   383     checkDigraphAlter<ListDigraph>();`
`       `
`   384     checkDigraphErase<ListDigraph>();`
`       `
`   385     checkDigraphSnapshot<ListDigraph>();`
`   173     checkDigraphValidityErase<ListDigraph>();`
`   386     checkDigraphValidityErase<ListDigraph>();`
`   174   }`
`   387   }`
`   175   { // Checking SmartDigraph`
`   388   { // Checking SmartDigraph`
`   176     checkDigraph<SmartDigraph>();`
`   389     checkDigraphBuild<SmartDigraph>();`
`       `
`   390     checkDigraphSplit<SmartDigraph>();`
`       `
`   391     checkDigraphSnapshot<SmartDigraph>();`
`   177     checkDigraphValidity<SmartDigraph>();`
`   392     checkDigraphValidity<SmartDigraph>();`
`   178   }`
`   393   }`
`   179 }`
`   394 }`
`   180 `
`   395 `
`   181 int main() {`
`   396 int main() {`