lemon-1.2: test/graph_adaptor_test.cc@05357da973ce

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2008

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #include<iostream>

    20 #include<lemon/concept_check.h>

    22 #include<lemon/list_graph.h>

    23 #include<lemon/smart_graph.h>

    25 #include<lemon/concepts/digraph.h>

    26 #include<lemon/concepts/graph.h>

    28 #include<lemon/digraph_adaptor.h>

    29 #include<lemon/graph_adaptor.h>

    31 #include <limits>

    32 #include <lemon/bfs.h>

    33 #include <lemon/path.h>

    35 #include"test/test_tools.h"

    36 #include"test/graph_test.h"

    38 using namespace lemon;

    40 void checkDigraphAdaptor() {

    41   checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();

    43   typedef ListDigraph Digraph;

    44   typedef DigraphAdaptor<Digraph> Adaptor;

    46   Digraph digraph;

    47   Adaptor adaptor(digraph);

    49   Digraph::Node n1 = digraph.addNode();

    50   Digraph::Node n2 = digraph.addNode();

    51   Digraph::Node n3 = digraph.addNode();

    53   Digraph::Arc a1 = digraph.addArc(n1, n2);

    54   Digraph::Arc a2 = digraph.addArc(n1, n3);

    55   Digraph::Arc a3 = digraph.addArc(n2, n3);

    57   checkGraphNodeList(adaptor, 3);

    58   checkGraphArcList(adaptor, 3);

    59   checkGraphConArcList(adaptor, 3);

    61   checkGraphOutArcList(adaptor, n1, 2);

    62   checkGraphOutArcList(adaptor, n2, 1);

    63   checkGraphOutArcList(adaptor, n3, 0);

    65   checkGraphInArcList(adaptor, n1, 0);

    66   checkGraphInArcList(adaptor, n2, 1);

    67   checkGraphInArcList(adaptor, n3, 2);

    69   checkNodeIds(adaptor);

    70   checkArcIds(adaptor);

    72   checkGraphNodeMap(adaptor);

    73   checkGraphArcMap(adaptor);

    74 }

    76 void checkRevDigraphAdaptor() {

    77   checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();

    79   typedef ListDigraph Digraph;

    80   typedef RevDigraphAdaptor<Digraph> Adaptor;

    82   Digraph digraph;

    83   Adaptor adaptor(digraph);

    85   Digraph::Node n1 = digraph.addNode();

    86   Digraph::Node n2 = digraph.addNode();

    87   Digraph::Node n3 = digraph.addNode();

    89   Digraph::Arc a1 = digraph.addArc(n1, n2);

    90   Digraph::Arc a2 = digraph.addArc(n1, n3);

    91   Digraph::Arc a3 = digraph.addArc(n2, n3);

    93   checkGraphNodeList(adaptor, 3);

    94   checkGraphArcList(adaptor, 3);

    95   checkGraphConArcList(adaptor, 3);

    97   checkGraphOutArcList(adaptor, n1, 0);

    98   checkGraphOutArcList(adaptor, n2, 1);

    99   checkGraphOutArcList(adaptor, n3, 2);

   101   checkGraphInArcList(adaptor, n1, 2);

   102   checkGraphInArcList(adaptor, n2, 1);

   103   checkGraphInArcList(adaptor, n3, 0);

   105   checkNodeIds(adaptor);

   106   checkArcIds(adaptor);

   108   checkGraphNodeMap(adaptor);

   109   checkGraphArcMap(adaptor);

   111   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   112     check(adaptor.source(a) == digraph.target(a), "Wrong reverse");

   113     check(adaptor.target(a) == digraph.source(a), "Wrong reverse");

   114   }

   115 }

   117 void checkSubDigraphAdaptor() {

   118   checkConcept<concepts::Digraph,

   119     SubDigraphAdaptor<concepts::Digraph,

   120     concepts::Digraph::NodeMap<bool>,

   121     concepts::Digraph::ArcMap<bool> > >();

   123   typedef ListDigraph Digraph;

   124   typedef Digraph::NodeMap<bool> NodeFilter;

   125   typedef Digraph::ArcMap<bool> ArcFilter;

   126   typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;

   128   Digraph digraph;

   129   NodeFilter node_filter(digraph);

   130   ArcFilter arc_filter(digraph);

   131   Adaptor adaptor(digraph, node_filter, arc_filter);

   133   Digraph::Node n1 = digraph.addNode();

   134   Digraph::Node n2 = digraph.addNode();

   135   Digraph::Node n3 = digraph.addNode();

   137   Digraph::Arc a1 = digraph.addArc(n1, n2);

   138   Digraph::Arc a2 = digraph.addArc(n1, n3);

   139   Digraph::Arc a3 = digraph.addArc(n2, n3);

   141   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;

   142   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;

   144   checkGraphNodeList(adaptor, 3);

   145   checkGraphArcList(adaptor, 3);

   146   checkGraphConArcList(adaptor, 3);

   148   checkGraphOutArcList(adaptor, n1, 2);

   149   checkGraphOutArcList(adaptor, n2, 1);

   150   checkGraphOutArcList(adaptor, n3, 0);

   152   checkGraphInArcList(adaptor, n1, 0);

   153   checkGraphInArcList(adaptor, n2, 1);

   154   checkGraphInArcList(adaptor, n3, 2);

   156   checkNodeIds(adaptor);

   157   checkArcIds(adaptor);

   159   checkGraphNodeMap(adaptor);

   160   checkGraphArcMap(adaptor);

   162   arc_filter[a2] = false;

   164   checkGraphNodeList(adaptor, 3);

   165   checkGraphArcList(adaptor, 2);

   166   checkGraphConArcList(adaptor, 2);

   168   checkGraphOutArcList(adaptor, n1, 1);

   169   checkGraphOutArcList(adaptor, n2, 1);

   170   checkGraphOutArcList(adaptor, n3, 0);

   172   checkGraphInArcList(adaptor, n1, 0);

   173   checkGraphInArcList(adaptor, n2, 1);

   174   checkGraphInArcList(adaptor, n3, 1);

   176   checkNodeIds(adaptor);

   177   checkArcIds(adaptor);

   179   checkGraphNodeMap(adaptor);

   180   checkGraphArcMap(adaptor);

   182   node_filter[n1] = false;

   184   checkGraphNodeList(adaptor, 2);

   185   checkGraphArcList(adaptor, 1);

   186   checkGraphConArcList(adaptor, 1);

   188   checkGraphOutArcList(adaptor, n2, 1);

   189   checkGraphOutArcList(adaptor, n3, 0);

   191   checkGraphInArcList(adaptor, n2, 0);

   192   checkGraphInArcList(adaptor, n3, 1);

   194   checkNodeIds(adaptor);

   195   checkArcIds(adaptor);

   197   checkGraphNodeMap(adaptor);

   198   checkGraphArcMap(adaptor);

   200   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;

   201   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;

   203   checkGraphNodeList(adaptor, 0);

   204   checkGraphArcList(adaptor, 0);

   205   checkGraphConArcList(adaptor, 0);

   207   checkNodeIds(adaptor);

   208   checkArcIds(adaptor);

   210   checkGraphNodeMap(adaptor);

   211   checkGraphArcMap(adaptor);

   212 }

   214 void checkNodeSubDigraphAdaptor() {

   215   checkConcept<concepts::Digraph,

   216     NodeSubDigraphAdaptor<concepts::Digraph,

   217       concepts::Digraph::NodeMap<bool> > >();

   219   typedef ListDigraph Digraph;

   220   typedef Digraph::NodeMap<bool> NodeFilter;

   221   typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;

   223   Digraph digraph;

   224   NodeFilter node_filter(digraph);

   225   Adaptor adaptor(digraph, node_filter);

   227   Digraph::Node n1 = digraph.addNode();

   228   Digraph::Node n2 = digraph.addNode();

   229   Digraph::Node n3 = digraph.addNode();

   231   Digraph::Arc a1 = digraph.addArc(n1, n2);

   232   Digraph::Arc a2 = digraph.addArc(n1, n3);

   233   Digraph::Arc a3 = digraph.addArc(n2, n3);

   235   node_filter[n1] = node_filter[n2] = node_filter[n3] = true;

   237   checkGraphNodeList(adaptor, 3);

   238   checkGraphArcList(adaptor, 3);

   239   checkGraphConArcList(adaptor, 3);

   241   checkGraphOutArcList(adaptor, n1, 2);

   242   checkGraphOutArcList(adaptor, n2, 1);

   243   checkGraphOutArcList(adaptor, n3, 0);

   245   checkGraphInArcList(adaptor, n1, 0);

   246   checkGraphInArcList(adaptor, n2, 1);

   247   checkGraphInArcList(adaptor, n3, 2);

   249   checkNodeIds(adaptor);

   250   checkArcIds(adaptor);

   252   checkGraphNodeMap(adaptor);

   253   checkGraphArcMap(adaptor);

   255   node_filter[n1] = false;

   257   checkGraphNodeList(adaptor, 2);

   258   checkGraphArcList(adaptor, 1);

   259   checkGraphConArcList(adaptor, 1);

   261   checkGraphOutArcList(adaptor, n2, 1);

   262   checkGraphOutArcList(adaptor, n3, 0);

   264   checkGraphInArcList(adaptor, n2, 0);

   265   checkGraphInArcList(adaptor, n3, 1);

   267   checkNodeIds(adaptor);

   268   checkArcIds(adaptor);

   270   checkGraphNodeMap(adaptor);

   271   checkGraphArcMap(adaptor);

   273   node_filter[n1] = node_filter[n2] = node_filter[n3] = false;

   275   checkGraphNodeList(adaptor, 0);

   276   checkGraphArcList(adaptor, 0);

   277   checkGraphConArcList(adaptor, 0);

   279   checkNodeIds(adaptor);

   280   checkArcIds(adaptor);

   282   checkGraphNodeMap(adaptor);

   283   checkGraphArcMap(adaptor);

   284 }

   286 void checkArcSubDigraphAdaptor() {

   287   checkConcept<concepts::Digraph,

   288     ArcSubDigraphAdaptor<concepts::Digraph,

   289     concepts::Digraph::ArcMap<bool> > >();

   291   typedef ListDigraph Digraph;

   292   typedef Digraph::ArcMap<bool> ArcFilter;

   293   typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;

   295   Digraph digraph;

   296   ArcFilter arc_filter(digraph);

   297   Adaptor adaptor(digraph, arc_filter);

   299   Digraph::Node n1 = digraph.addNode();

   300   Digraph::Node n2 = digraph.addNode();

   301   Digraph::Node n3 = digraph.addNode();

   303   Digraph::Arc a1 = digraph.addArc(n1, n2);

   304   Digraph::Arc a2 = digraph.addArc(n1, n3);

   305   Digraph::Arc a3 = digraph.addArc(n2, n3);

   307   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = true;

   309   checkGraphNodeList(adaptor, 3);

   310   checkGraphArcList(adaptor, 3);

   311   checkGraphConArcList(adaptor, 3);

   313   checkGraphOutArcList(adaptor, n1, 2);

   314   checkGraphOutArcList(adaptor, n2, 1);

   315   checkGraphOutArcList(adaptor, n3, 0);

   317   checkGraphInArcList(adaptor, n1, 0);

   318   checkGraphInArcList(adaptor, n2, 1);

   319   checkGraphInArcList(adaptor, n3, 2);

   321   checkNodeIds(adaptor);

   322   checkArcIds(adaptor);

   324   checkGraphNodeMap(adaptor);

   325   checkGraphArcMap(adaptor);

   327   arc_filter[a2] = false;

   329   checkGraphNodeList(adaptor, 3);

   330   checkGraphArcList(adaptor, 2);

   331   checkGraphConArcList(adaptor, 2);

   333   checkGraphOutArcList(adaptor, n1, 1);

   334   checkGraphOutArcList(adaptor, n2, 1);

   335   checkGraphOutArcList(adaptor, n3, 0);

   337   checkGraphInArcList(adaptor, n1, 0);

   338   checkGraphInArcList(adaptor, n2, 1);

   339   checkGraphInArcList(adaptor, n3, 1);

   341   checkNodeIds(adaptor);

   342   checkArcIds(adaptor);

   344   checkGraphNodeMap(adaptor);

   345   checkGraphArcMap(adaptor);

   347   arc_filter[a1] = arc_filter[a2] = arc_filter[a3] = false;

   349   checkGraphNodeList(adaptor, 3);

   350   checkGraphArcList(adaptor, 0);

   351   checkGraphConArcList(adaptor, 0);

   353   checkNodeIds(adaptor);

   354   checkArcIds(adaptor);

   356   checkGraphNodeMap(adaptor);

   357   checkGraphArcMap(adaptor);

   358 }

   360 void checkUndirDigraphAdaptor() {

   361   checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();

   363   typedef ListDigraph Digraph;

   364   typedef UndirDigraphAdaptor<Digraph> Adaptor;

   366   Digraph digraph;

   367   Adaptor adaptor(digraph);

   369   Digraph::Node n1 = digraph.addNode();

   370   Digraph::Node n2 = digraph.addNode();

   371   Digraph::Node n3 = digraph.addNode();

   373   Digraph::Arc a1 = digraph.addArc(n1, n2);

   374   Digraph::Arc a2 = digraph.addArc(n1, n3);

   375   Digraph::Arc a3 = digraph.addArc(n2, n3);

   377   checkGraphNodeList(adaptor, 3);

   378   checkGraphArcList(adaptor, 6);

   379   checkGraphEdgeList(adaptor, 3);

   380   checkGraphConArcList(adaptor, 6);

   381   checkGraphConEdgeList(adaptor, 3);

   383   checkGraphOutArcList(adaptor, n1, 2);

   384   checkGraphOutArcList(adaptor, n2, 2);

   385   checkGraphOutArcList(adaptor, n3, 2);

   387   checkGraphInArcList(adaptor, n1, 2);

   388   checkGraphInArcList(adaptor, n2, 2);

   389   checkGraphInArcList(adaptor, n3, 2);

   391   checkGraphIncEdgeList(adaptor, n1, 2);

   392   checkGraphIncEdgeList(adaptor, n2, 2);

   393   checkGraphIncEdgeList(adaptor, n3, 2);

   395   checkNodeIds(adaptor);

   396   checkArcIds(adaptor);

   397   checkEdgeIds(adaptor);

   399   checkGraphNodeMap(adaptor);

   400   checkGraphArcMap(adaptor);

   401   checkGraphEdgeMap(adaptor);

   403   for (Adaptor::EdgeIt e(adaptor); e != INVALID; ++e) {

   404     check(adaptor.u(e) == digraph.source(e), "Wrong undir");

   405     check(adaptor.v(e) == digraph.target(e), "Wrong undir");

   406   }

   408 }

   410 void checkResDigraphAdaptor() {

   411   checkConcept<concepts::Digraph,

   412     ResDigraphAdaptor<concepts::Digraph,

   413     concepts::Digraph::ArcMap<int>,

   414     concepts::Digraph::ArcMap<int> > >();

   416   typedef ListDigraph Digraph;

   417   typedef Digraph::ArcMap<int> IntArcMap;

   418   typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;

   420   Digraph digraph;

   421   IntArcMap capacity(digraph), flow(digraph);

   422   Adaptor adaptor(digraph, capacity, flow);

   424   Digraph::Node n1 = digraph.addNode();

   425   Digraph::Node n2 = digraph.addNode();

   426   Digraph::Node n3 = digraph.addNode();

   427   Digraph::Node n4 = digraph.addNode();

   429   Digraph::Arc a1 = digraph.addArc(n1, n2);

   430   Digraph::Arc a2 = digraph.addArc(n1, n3);

   431   Digraph::Arc a3 = digraph.addArc(n1, n4);

   432   Digraph::Arc a4 = digraph.addArc(n2, n3);

   433   Digraph::Arc a5 = digraph.addArc(n2, n4);

   434   Digraph::Arc a6 = digraph.addArc(n3, n4);

   436   capacity[a1] = 8;

   437   capacity[a2] = 6;

   438   capacity[a3] = 4;

   439   capacity[a4] = 4;

   440   capacity[a5] = 6;

   441   capacity[a6] = 10;

   443   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   444     flow[a] = 0;

   445   }

   447   checkGraphNodeList(adaptor, 4);

   448   checkGraphArcList(adaptor, 6);

   449   checkGraphConArcList(adaptor, 6);

   451   checkGraphOutArcList(adaptor, n1, 3);

   452   checkGraphOutArcList(adaptor, n2, 2);

   453   checkGraphOutArcList(adaptor, n3, 1);

   454   checkGraphOutArcList(adaptor, n4, 0);

   456   checkGraphInArcList(adaptor, n1, 0);

   457   checkGraphInArcList(adaptor, n2, 1);

   458   checkGraphInArcList(adaptor, n3, 2);

   459   checkGraphInArcList(adaptor, n4, 3);

   461   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   462     flow[a] = capacity[a] / 2;

   463   }

   465   checkGraphNodeList(adaptor, 4);

   466   checkGraphArcList(adaptor, 12);

   467   checkGraphConArcList(adaptor, 12);

   469   checkGraphOutArcList(adaptor, n1, 3);

   470   checkGraphOutArcList(adaptor, n2, 3);

   471   checkGraphOutArcList(adaptor, n3, 3);

   472   checkGraphOutArcList(adaptor, n4, 3);

   474   checkGraphInArcList(adaptor, n1, 3);

   475   checkGraphInArcList(adaptor, n2, 3);

   476   checkGraphInArcList(adaptor, n3, 3);

   477   checkGraphInArcList(adaptor, n4, 3);

   479   checkNodeIds(adaptor);

   480   checkArcIds(adaptor);

   482   checkGraphNodeMap(adaptor);

   483   checkGraphArcMap(adaptor);

   485   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   486     flow[a] = capacity[a];

   487   }

   489   checkGraphNodeList(adaptor, 4);

   490   checkGraphArcList(adaptor, 6);

   491   checkGraphConArcList(adaptor, 6);

   493   checkGraphOutArcList(adaptor, n1, 0);

   494   checkGraphOutArcList(adaptor, n2, 1);

   495   checkGraphOutArcList(adaptor, n3, 2);

   496   checkGraphOutArcList(adaptor, n4, 3);

   498   checkGraphInArcList(adaptor, n1, 3);

   499   checkGraphInArcList(adaptor, n2, 2);

   500   checkGraphInArcList(adaptor, n3, 1);

   501   checkGraphInArcList(adaptor, n4, 0);

   503   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   504     flow[a] = 0;

   505   }

   507   int flow_value = 0;

   508   while (true) {

   510     Bfs<Adaptor> bfs(adaptor);

   511     bfs.run(n1, n4);

   513     if (!bfs.reached(n4)) break;

   515     Path<Adaptor> p = bfs.path(n4);

   517     int min = std::numeric_limits<int>::max();

   518     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {

   519       if (adaptor.rescap(a) < min) min = adaptor.rescap(a);

   520     }

   522     for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) {

   523       adaptor.augment(a, min);

   524     }

   525     flow_value += min;

   526   }

   528   check(flow_value == 18, "Wrong flow with res graph adaptor");

   530 }

   532 void checkSplitDigraphAdaptor() {

   533   checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();

   535   typedef ListDigraph Digraph;

   536   typedef SplitDigraphAdaptor<Digraph> Adaptor;

   538   Digraph digraph;

   539   Adaptor adaptor(digraph);

   541   Digraph::Node n1 = digraph.addNode();

   542   Digraph::Node n2 = digraph.addNode();

   543   Digraph::Node n3 = digraph.addNode();

   545   Digraph::Arc a1 = digraph.addArc(n1, n2);

   546   Digraph::Arc a2 = digraph.addArc(n1, n3);

   547   Digraph::Arc a3 = digraph.addArc(n2, n3);

   549   checkGraphNodeList(adaptor, 6);

   550   checkGraphArcList(adaptor, 6);

   551   checkGraphConArcList(adaptor, 6);

   553   checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);

   554   checkGraphOutArcList(adaptor, adaptor.outNode(n1), 2);

   555   checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);

   556   checkGraphOutArcList(adaptor, adaptor.outNode(n2), 1);

   557   checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);

   558   checkGraphOutArcList(adaptor, adaptor.outNode(n3), 0);

   560   checkGraphInArcList(adaptor, adaptor.inNode(n1), 0);

   561   checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);

   562   checkGraphInArcList(adaptor, adaptor.inNode(n2), 1);

   563   checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);

   564   checkGraphInArcList(adaptor, adaptor.inNode(n3), 2);

   565   checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);

   567   checkNodeIds(adaptor);

   568   checkArcIds(adaptor);

   570   checkGraphNodeMap(adaptor);

   571   checkGraphArcMap(adaptor);

   573   for (Adaptor::ArcIt a(adaptor); a != INVALID; ++a) {

   574     if (adaptor.origArc(a)) {

   575       Digraph::Arc oa = a;

   576       check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)),

   577 	    "Wrong split");

   578       check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)),

   579 	    "Wrong split");

   580     } else {

   581       Digraph::Node on = a;

   582       check(adaptor.source(a) == adaptor.inNode(on), "Wrong split");

   583       check(adaptor.target(a) == adaptor.outNode(on), "Wrong split");

   584     }

   585   }

   586 }

   588 void checkGraphAdaptor() {

   589   checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();

   591   typedef ListGraph Graph;

   592   typedef GraphAdaptor<Graph> Adaptor;

   594   Graph graph;

   595   Adaptor adaptor(graph);

   597   Graph::Node n1 = graph.addNode();

   598   Graph::Node n2 = graph.addNode();

   599   Graph::Node n3 = graph.addNode();

   600   Graph::Node n4 = graph.addNode();

   602   Graph::Edge a1 = graph.addEdge(n1, n2);

   603   Graph::Edge a2 = graph.addEdge(n1, n3);

   604   Graph::Edge a3 = graph.addEdge(n2, n3);

   605   Graph::Edge a4 = graph.addEdge(n3, n4);

   607   checkGraphNodeList(adaptor, 4);

   608   checkGraphArcList(adaptor, 8);

   609   checkGraphEdgeList(adaptor, 4);

   610   checkGraphConArcList(adaptor, 8);

   611   checkGraphConEdgeList(adaptor, 4);

   613   checkGraphOutArcList(adaptor, n1, 2);

   614   checkGraphOutArcList(adaptor, n2, 2);

   615   checkGraphOutArcList(adaptor, n3, 3);

   616   checkGraphOutArcList(adaptor, n4, 1);

   618   checkGraphInArcList(adaptor, n1, 2);

   619   checkGraphInArcList(adaptor, n2, 2);

   620   checkGraphInArcList(adaptor, n3, 3);

   621   checkGraphInArcList(adaptor, n4, 1);

   623   checkGraphIncEdgeList(adaptor, n1, 2);

   624   checkGraphIncEdgeList(adaptor, n2, 2);

   625   checkGraphIncEdgeList(adaptor, n3, 3);

   626   checkGraphIncEdgeList(adaptor, n4, 1);

   629   checkNodeIds(adaptor);

   630   checkArcIds(adaptor);

   631   checkEdgeIds(adaptor);

   633   checkGraphNodeMap(adaptor);

   634   checkGraphArcMap(adaptor);

   635   checkGraphEdgeMap(adaptor);

   636 }

   638 void checkSubGraphAdaptor() {

   639   checkConcept<concepts::Graph,

   640     SubGraphAdaptor<concepts::Graph,

   641     concepts::Graph::NodeMap<bool>,

   642     concepts::Graph::EdgeMap<bool> > >();

   644   typedef ListGraph Graph;

   645   typedef Graph::NodeMap<bool> NodeFilter;

   646   typedef Graph::EdgeMap<bool> EdgeFilter;

   647   typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;

   649   Graph graph;

   650   NodeFilter node_filter(graph);

   651   EdgeFilter edge_filter(graph);

   652   Adaptor adaptor(graph, node_filter, edge_filter);

   654   Graph::Node n1 = graph.addNode();

   655   Graph::Node n2 = graph.addNode();

   656   Graph::Node n3 = graph.addNode();

   657   Graph::Node n4 = graph.addNode();

   659   Graph::Edge e1 = graph.addEdge(n1, n2);

   660   Graph::Edge e2 = graph.addEdge(n1, n3);

   661   Graph::Edge e3 = graph.addEdge(n2, n3);

   662   Graph::Edge e4 = graph.addEdge(n3, n4);

   664   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;

   665   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;

   667   checkGraphNodeList(adaptor, 4);

   668   checkGraphArcList(adaptor, 8);

   669   checkGraphEdgeList(adaptor, 4);

   670   checkGraphConArcList(adaptor, 8);

   671   checkGraphConEdgeList(adaptor, 4);

   673   checkGraphOutArcList(adaptor, n1, 2);

   674   checkGraphOutArcList(adaptor, n2, 2);

   675   checkGraphOutArcList(adaptor, n3, 3);

   676   checkGraphOutArcList(adaptor, n4, 1);

   678   checkGraphInArcList(adaptor, n1, 2);

   679   checkGraphInArcList(adaptor, n2, 2);

   680   checkGraphInArcList(adaptor, n3, 3);

   681   checkGraphInArcList(adaptor, n4, 1);

   683   checkGraphIncEdgeList(adaptor, n1, 2);

   684   checkGraphIncEdgeList(adaptor, n2, 2);

   685   checkGraphIncEdgeList(adaptor, n3, 3);

   686   checkGraphIncEdgeList(adaptor, n4, 1);

   688   checkNodeIds(adaptor);

   689   checkArcIds(adaptor);

   690   checkEdgeIds(adaptor);

   692   checkGraphNodeMap(adaptor);

   693   checkGraphArcMap(adaptor);

   694   checkGraphEdgeMap(adaptor);

   696   edge_filter[e2] = false;

   698   checkGraphNodeList(adaptor, 4);

   699   checkGraphArcList(adaptor, 6);

   700   checkGraphEdgeList(adaptor, 3);

   701   checkGraphConArcList(adaptor, 6);

   702   checkGraphConEdgeList(adaptor, 3);

   704   checkGraphOutArcList(adaptor, n1, 1);

   705   checkGraphOutArcList(adaptor, n2, 2);

   706   checkGraphOutArcList(adaptor, n3, 2);

   707   checkGraphOutArcList(adaptor, n4, 1);

   709   checkGraphInArcList(adaptor, n1, 1);

   710   checkGraphInArcList(adaptor, n2, 2);

   711   checkGraphInArcList(adaptor, n3, 2);

   712   checkGraphInArcList(adaptor, n4, 1);

   714   checkGraphIncEdgeList(adaptor, n1, 1);

   715   checkGraphIncEdgeList(adaptor, n2, 2);

   716   checkGraphIncEdgeList(adaptor, n3, 2);

   717   checkGraphIncEdgeList(adaptor, n4, 1);

   719   checkNodeIds(adaptor);

   720   checkArcIds(adaptor);

   721   checkEdgeIds(adaptor);

   723   checkGraphNodeMap(adaptor);

   724   checkGraphArcMap(adaptor);

   725   checkGraphEdgeMap(adaptor);

   727   node_filter[n1] = false;

   729   checkGraphNodeList(adaptor, 3);

   730   checkGraphArcList(adaptor, 4);

   731   checkGraphEdgeList(adaptor, 2);

   732   checkGraphConArcList(adaptor, 4);

   733   checkGraphConEdgeList(adaptor, 2);

   735   checkGraphOutArcList(adaptor, n2, 1);

   736   checkGraphOutArcList(adaptor, n3, 2);

   737   checkGraphOutArcList(adaptor, n4, 1);

   739   checkGraphInArcList(adaptor, n2, 1);

   740   checkGraphInArcList(adaptor, n3, 2);

   741   checkGraphInArcList(adaptor, n4, 1);

   743   checkGraphIncEdgeList(adaptor, n2, 1);

   744   checkGraphIncEdgeList(adaptor, n3, 2);

   745   checkGraphIncEdgeList(adaptor, n4, 1);

   747   checkNodeIds(adaptor);

   748   checkArcIds(adaptor);

   749   checkEdgeIds(adaptor);

   751   checkGraphNodeMap(adaptor);

   752   checkGraphArcMap(adaptor);

   753   checkGraphEdgeMap(adaptor);

   755   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;

   756   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;

   758   checkGraphNodeList(adaptor, 0);

   759   checkGraphArcList(adaptor, 0);

   760   checkGraphEdgeList(adaptor, 0);

   761   checkGraphConArcList(adaptor, 0);

   762   checkGraphConEdgeList(adaptor, 0);

   764   checkNodeIds(adaptor);

   765   checkArcIds(adaptor);

   766   checkEdgeIds(adaptor);

   768   checkGraphNodeMap(adaptor);

   769   checkGraphArcMap(adaptor);

   770   checkGraphEdgeMap(adaptor);

   771 }

   773 void checkNodeSubGraphAdaptor() {

   774   checkConcept<concepts::Graph,

   775     NodeSubGraphAdaptor<concepts::Graph,

   776       concepts::Graph::NodeMap<bool> > >();

   778   typedef ListGraph Graph;

   779   typedef Graph::NodeMap<bool> NodeFilter;

   780   typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;

   782   Graph graph;

   783   NodeFilter node_filter(graph);

   784   Adaptor adaptor(graph, node_filter);

   786   Graph::Node n1 = graph.addNode();

   787   Graph::Node n2 = graph.addNode();

   788   Graph::Node n3 = graph.addNode();

   789   Graph::Node n4 = graph.addNode();

   791   Graph::Edge e1 = graph.addEdge(n1, n2);

   792   Graph::Edge e2 = graph.addEdge(n1, n3);

   793   Graph::Edge e3 = graph.addEdge(n2, n3);

   794   Graph::Edge e4 = graph.addEdge(n3, n4);

   796   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = true;

   798   checkGraphNodeList(adaptor, 4);

   799   checkGraphArcList(adaptor, 8);

   800   checkGraphEdgeList(adaptor, 4);

   801   checkGraphConArcList(adaptor, 8);

   802   checkGraphConEdgeList(adaptor, 4);

   804   checkGraphOutArcList(adaptor, n1, 2);

   805   checkGraphOutArcList(adaptor, n2, 2);

   806   checkGraphOutArcList(adaptor, n3, 3);

   807   checkGraphOutArcList(adaptor, n4, 1);

   809   checkGraphInArcList(adaptor, n1, 2);

   810   checkGraphInArcList(adaptor, n2, 2);

   811   checkGraphInArcList(adaptor, n3, 3);

   812   checkGraphInArcList(adaptor, n4, 1);

   814   checkGraphIncEdgeList(adaptor, n1, 2);

   815   checkGraphIncEdgeList(adaptor, n2, 2);

   816   checkGraphIncEdgeList(adaptor, n3, 3);

   817   checkGraphIncEdgeList(adaptor, n4, 1);

   819   checkNodeIds(adaptor);

   820   checkArcIds(adaptor);

   821   checkEdgeIds(adaptor);

   823   checkGraphNodeMap(adaptor);

   824   checkGraphArcMap(adaptor);

   825   checkGraphEdgeMap(adaptor);

   827   node_filter[n1] = false;

   829   checkGraphNodeList(adaptor, 3);

   830   checkGraphArcList(adaptor, 4);

   831   checkGraphEdgeList(adaptor, 2);

   832   checkGraphConArcList(adaptor, 4);

   833   checkGraphConEdgeList(adaptor, 2);

   835   checkGraphOutArcList(adaptor, n2, 1);

   836   checkGraphOutArcList(adaptor, n3, 2);

   837   checkGraphOutArcList(adaptor, n4, 1);

   839   checkGraphInArcList(adaptor, n2, 1);

   840   checkGraphInArcList(adaptor, n3, 2);

   841   checkGraphInArcList(adaptor, n4, 1);

   843   checkGraphIncEdgeList(adaptor, n2, 1);

   844   checkGraphIncEdgeList(adaptor, n3, 2);

   845   checkGraphIncEdgeList(adaptor, n4, 1);

   847   checkNodeIds(adaptor);

   848   checkArcIds(adaptor);

   849   checkEdgeIds(adaptor);

   851   checkGraphNodeMap(adaptor);

   852   checkGraphArcMap(adaptor);

   853   checkGraphEdgeMap(adaptor);

   855   node_filter[n1] = node_filter[n2] = node_filter[n3] = node_filter[n4] = false;

   857   checkGraphNodeList(adaptor, 0);

   858   checkGraphArcList(adaptor, 0);

   859   checkGraphEdgeList(adaptor, 0);

   860   checkGraphConArcList(adaptor, 0);

   861   checkGraphConEdgeList(adaptor, 0);

   863   checkNodeIds(adaptor);

   864   checkArcIds(adaptor);

   865   checkEdgeIds(adaptor);

   867   checkGraphNodeMap(adaptor);

   868   checkGraphArcMap(adaptor);

   869   checkGraphEdgeMap(adaptor);

   870 }

   872 void checkEdgeSubGraphAdaptor() {

   873   checkConcept<concepts::Graph,

   874     EdgeSubGraphAdaptor<concepts::Graph,

   875     concepts::Graph::EdgeMap<bool> > >();

   877   typedef ListGraph Graph;

   878   typedef Graph::EdgeMap<bool> EdgeFilter;

   879   typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;

   881   Graph graph;

   882   EdgeFilter edge_filter(graph);

   883   Adaptor adaptor(graph, edge_filter);

   885   Graph::Node n1 = graph.addNode();

   886   Graph::Node n2 = graph.addNode();

   887   Graph::Node n3 = graph.addNode();

   888   Graph::Node n4 = graph.addNode();

   890   Graph::Edge e1 = graph.addEdge(n1, n2);

   891   Graph::Edge e2 = graph.addEdge(n1, n3);

   892   Graph::Edge e3 = graph.addEdge(n2, n3);

   893   Graph::Edge e4 = graph.addEdge(n3, n4);

   895   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = true;

   897   checkGraphNodeList(adaptor, 4);

   898   checkGraphArcList(adaptor, 8);

   899   checkGraphEdgeList(adaptor, 4);

   900   checkGraphConArcList(adaptor, 8);

   901   checkGraphConEdgeList(adaptor, 4);

   903   checkGraphOutArcList(adaptor, n1, 2);

   904   checkGraphOutArcList(adaptor, n2, 2);

   905   checkGraphOutArcList(adaptor, n3, 3);

   906   checkGraphOutArcList(adaptor, n4, 1);

   908   checkGraphInArcList(adaptor, n1, 2);

   909   checkGraphInArcList(adaptor, n2, 2);

   910   checkGraphInArcList(adaptor, n3, 3);

   911   checkGraphInArcList(adaptor, n4, 1);

   913   checkGraphIncEdgeList(adaptor, n1, 2);

   914   checkGraphIncEdgeList(adaptor, n2, 2);

   915   checkGraphIncEdgeList(adaptor, n3, 3);

   916   checkGraphIncEdgeList(adaptor, n4, 1);

   918   checkNodeIds(adaptor);

   919   checkArcIds(adaptor);

   920   checkEdgeIds(adaptor);

   922   checkGraphNodeMap(adaptor);

   923   checkGraphArcMap(adaptor);

   924   checkGraphEdgeMap(adaptor);

   926   edge_filter[e2] = false;

   928   checkGraphNodeList(adaptor, 4);

   929   checkGraphArcList(adaptor, 6);

   930   checkGraphEdgeList(adaptor, 3);

   931   checkGraphConArcList(adaptor, 6);

   932   checkGraphConEdgeList(adaptor, 3);

   934   checkGraphOutArcList(adaptor, n1, 1);

   935   checkGraphOutArcList(adaptor, n2, 2);

   936   checkGraphOutArcList(adaptor, n3, 2);

   937   checkGraphOutArcList(adaptor, n4, 1);

   939   checkGraphInArcList(adaptor, n1, 1);

   940   checkGraphInArcList(adaptor, n2, 2);

   941   checkGraphInArcList(adaptor, n3, 2);

   942   checkGraphInArcList(adaptor, n4, 1);

   944   checkGraphIncEdgeList(adaptor, n1, 1);

   945   checkGraphIncEdgeList(adaptor, n2, 2);

   946   checkGraphIncEdgeList(adaptor, n3, 2);

   947   checkGraphIncEdgeList(adaptor, n4, 1);

   949   checkNodeIds(adaptor);

   950   checkArcIds(adaptor);

   951   checkEdgeIds(adaptor);

   953   checkGraphNodeMap(adaptor);

   954   checkGraphArcMap(adaptor);

   955   checkGraphEdgeMap(adaptor);

   957   edge_filter[e1] = edge_filter[e2] = edge_filter[e3] = edge_filter[e4] = false;

   959   checkGraphNodeList(adaptor, 4);

   960   checkGraphArcList(adaptor, 0);

   961   checkGraphEdgeList(adaptor, 0);

   962   checkGraphConArcList(adaptor, 0);

   963   checkGraphConEdgeList(adaptor, 0);

   965   checkNodeIds(adaptor);

   966   checkArcIds(adaptor);

   967   checkEdgeIds(adaptor);

   969   checkGraphNodeMap(adaptor);

   970   checkGraphArcMap(adaptor);

   971   checkGraphEdgeMap(adaptor);

   972 }

   974 void checkDirGraphAdaptor() {

   975   checkConcept<concepts::Digraph,

   976     DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();

   978   typedef ListGraph Graph;

   979   typedef ListGraph::EdgeMap<bool> DirMap;

   980   typedef DirGraphAdaptor<Graph> Adaptor;

   982   Graph graph;

   983   DirMap dir(graph, true);

   984   Adaptor adaptor(graph, dir);

   986   Graph::Node n1 = graph.addNode();

   987   Graph::Node n2 = graph.addNode();

   988   Graph::Node n3 = graph.addNode();

   990   Graph::Edge e1 = graph.addEdge(n1, n2);

   991   Graph::Edge e2 = graph.addEdge(n1, n3);

   992   Graph::Edge e3 = graph.addEdge(n2, n3);

   994   checkGraphNodeList(adaptor, 3);

   995   checkGraphArcList(adaptor, 3);

   996   checkGraphConArcList(adaptor, 3);

   998   {

   999     dir[e1] = true;

  1000     Adaptor::Node u = adaptor.source(e1);

  1001     Adaptor::Node v = adaptor.target(e1);

  1003     dir[e1] = false;

  1004     check (u == adaptor.target(e1), "Wrong dir");

  1005     check (v == adaptor.source(e1), "Wrong dir");

  1007     check ((u == n1 && v == n2) || (u == n2 && v == n1), "Wrong dir");

  1008     dir[e1] = n1 == u;

  1009   }

  1011   {

  1012     dir[e2] = true;

  1013     Adaptor::Node u = adaptor.source(e2);

  1014     Adaptor::Node v = adaptor.target(e2);

  1016     dir[e2] = false;

  1017     check (u == adaptor.target(e2), "Wrong dir");

  1018     check (v == adaptor.source(e2), "Wrong dir");

  1020     check ((u == n1 && v == n3) || (u == n3 && v == n1), "Wrong dir");

  1021     dir[e2] = n3 == u;

  1022   }

  1024   {

  1025     dir[e3] = true;

  1026     Adaptor::Node u = adaptor.source(e3);

  1027     Adaptor::Node v = adaptor.target(e3);

  1029     dir[e3] = false;

  1030     check (u == adaptor.target(e3), "Wrong dir");

  1031     check (v == adaptor.source(e3), "Wrong dir");

  1033     check ((u == n2 && v == n3) || (u == n3 && v == n2), "Wrong dir");

  1034     dir[e3] = n2 == u;

  1035   }

  1037   checkGraphOutArcList(adaptor, n1, 1);

  1038   checkGraphOutArcList(adaptor, n2, 1);

  1039   checkGraphOutArcList(adaptor, n3, 1);

  1041   checkGraphInArcList(adaptor, n1, 1);

  1042   checkGraphInArcList(adaptor, n2, 1);

  1043   checkGraphInArcList(adaptor, n3, 1);

  1045   checkNodeIds(adaptor);

  1046   checkArcIds(adaptor);

  1048   checkGraphNodeMap(adaptor);

  1049   checkGraphArcMap(adaptor);

  1051 }

  1054 int main(int, const char **) {

  1056   checkDigraphAdaptor();

  1057   checkRevDigraphAdaptor();

  1058   checkSubDigraphAdaptor();

  1059   checkNodeSubDigraphAdaptor();

  1060   checkArcSubDigraphAdaptor();

  1061   checkUndirDigraphAdaptor();

  1062   checkResDigraphAdaptor();

  1063   checkSplitDigraphAdaptor();

  1065   checkGraphAdaptor();

  1066   checkSubGraphAdaptor();

  1067   checkNodeSubGraphAdaptor();

  1068   checkEdgeSubGraphAdaptor();

  1069   checkDirGraphAdaptor();

  1071   return 0;

  1072 }

author	Balazs Dezso <deba@inf.elte.hu>
	Sun, 30 Nov 2008 18:57:18 +0100
changeset 414	05357da973ce
child 415	4b6112235fad
permissions	-rw-r--r--