Mercuriallemon / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
test/digraph_test.cc
branch1.0
changeset 506 7e0d5d971bab
parent 228 b6732e0d38c5
child 388 2d87dbd7f8c8
equal deleted inserted replaced
4:db88099cfdc8 9: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() {
lemon