lemon-1.2: test/graph_adaptor_test.cc@4b6112235fad

     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 checkRevDigraphAdaptor() {

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

    43   typedef ListDigraph Digraph;

    44   typedef RevDigraphAdaptor<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, 0);

    62   checkGraphOutArcList(adaptor, n2, 1);

    63   checkGraphOutArcList(adaptor, n3, 2);

    65   checkGraphInArcList(adaptor, n1, 2);

    66   checkGraphInArcList(adaptor, n2, 1);

    67   checkGraphInArcList(adaptor, n3, 0);

    69   checkNodeIds(adaptor);

    70   checkArcIds(adaptor);

    72   checkGraphNodeMap(adaptor);

    73   checkGraphArcMap(adaptor);

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

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

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

    78   }

    79 }

    81 void checkSubDigraphAdaptor() {

    82   checkConcept<concepts::Digraph,

    83     SubDigraphAdaptor<concepts::Digraph,

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

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

    87   typedef ListDigraph Digraph;

    88   typedef Digraph::NodeMap<bool> NodeFilter;

    89   typedef Digraph::ArcMap<bool> ArcFilter;

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

    92   Digraph digraph;

    93   NodeFilter node_filter(digraph);

    94   ArcFilter arc_filter(digraph);

    95   Adaptor adaptor(digraph, node_filter, arc_filter);

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

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

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

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

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

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

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

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

   108   checkGraphNodeList(adaptor, 3);

   109   checkGraphArcList(adaptor, 3);

   110   checkGraphConArcList(adaptor, 3);

   112   checkGraphOutArcList(adaptor, n1, 2);

   113   checkGraphOutArcList(adaptor, n2, 1);

   114   checkGraphOutArcList(adaptor, n3, 0);

   116   checkGraphInArcList(adaptor, n1, 0);

   117   checkGraphInArcList(adaptor, n2, 1);

   118   checkGraphInArcList(adaptor, n3, 2);

   120   checkNodeIds(adaptor);

   121   checkArcIds(adaptor);

   123   checkGraphNodeMap(adaptor);

   124   checkGraphArcMap(adaptor);

   126   arc_filter[a2] = false;

   128   checkGraphNodeList(adaptor, 3);

   129   checkGraphArcList(adaptor, 2);

   130   checkGraphConArcList(adaptor, 2);

   132   checkGraphOutArcList(adaptor, n1, 1);

   133   checkGraphOutArcList(adaptor, n2, 1);

   134   checkGraphOutArcList(adaptor, n3, 0);

   136   checkGraphInArcList(adaptor, n1, 0);

   137   checkGraphInArcList(adaptor, n2, 1);

   138   checkGraphInArcList(adaptor, n3, 1);

   140   checkNodeIds(adaptor);

   141   checkArcIds(adaptor);

   143   checkGraphNodeMap(adaptor);

   144   checkGraphArcMap(adaptor);

   146   node_filter[n1] = false;

   148   checkGraphNodeList(adaptor, 2);

   149   checkGraphArcList(adaptor, 1);

   150   checkGraphConArcList(adaptor, 1);

   152   checkGraphOutArcList(adaptor, n2, 1);

   153   checkGraphOutArcList(adaptor, n3, 0);

   155   checkGraphInArcList(adaptor, n2, 0);

   156   checkGraphInArcList(adaptor, n3, 1);

   158   checkNodeIds(adaptor);

   159   checkArcIds(adaptor);

   161   checkGraphNodeMap(adaptor);

   162   checkGraphArcMap(adaptor);

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

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

   167   checkGraphNodeList(adaptor, 0);

   168   checkGraphArcList(adaptor, 0);

   169   checkGraphConArcList(adaptor, 0);

   171   checkNodeIds(adaptor);

   172   checkArcIds(adaptor);

   174   checkGraphNodeMap(adaptor);

   175   checkGraphArcMap(adaptor);

   176 }

   178 void checkNodeSubDigraphAdaptor() {

   179   checkConcept<concepts::Digraph,

   180     NodeSubDigraphAdaptor<concepts::Digraph,

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

   183   typedef ListDigraph Digraph;

   184   typedef Digraph::NodeMap<bool> NodeFilter;

   185   typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;

   187   Digraph digraph;

   188   NodeFilter node_filter(digraph);

   189   Adaptor adaptor(digraph, node_filter);

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

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

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

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

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

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

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

   201   checkGraphNodeList(adaptor, 3);

   202   checkGraphArcList(adaptor, 3);

   203   checkGraphConArcList(adaptor, 3);

   205   checkGraphOutArcList(adaptor, n1, 2);

   206   checkGraphOutArcList(adaptor, n2, 1);

   207   checkGraphOutArcList(adaptor, n3, 0);

   209   checkGraphInArcList(adaptor, n1, 0);

   210   checkGraphInArcList(adaptor, n2, 1);

   211   checkGraphInArcList(adaptor, n3, 2);

   213   checkNodeIds(adaptor);

   214   checkArcIds(adaptor);

   216   checkGraphNodeMap(adaptor);

   217   checkGraphArcMap(adaptor);

   219   node_filter[n1] = false;

   221   checkGraphNodeList(adaptor, 2);

   222   checkGraphArcList(adaptor, 1);

   223   checkGraphConArcList(adaptor, 1);

   225   checkGraphOutArcList(adaptor, n2, 1);

   226   checkGraphOutArcList(adaptor, n3, 0);

   228   checkGraphInArcList(adaptor, n2, 0);

   229   checkGraphInArcList(adaptor, n3, 1);

   231   checkNodeIds(adaptor);

   232   checkArcIds(adaptor);

   234   checkGraphNodeMap(adaptor);

   235   checkGraphArcMap(adaptor);

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

   239   checkGraphNodeList(adaptor, 0);

   240   checkGraphArcList(adaptor, 0);

   241   checkGraphConArcList(adaptor, 0);

   243   checkNodeIds(adaptor);

   244   checkArcIds(adaptor);

   246   checkGraphNodeMap(adaptor);

   247   checkGraphArcMap(adaptor);

   248 }

   250 void checkArcSubDigraphAdaptor() {

   251   checkConcept<concepts::Digraph,

   252     ArcSubDigraphAdaptor<concepts::Digraph,

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

   255   typedef ListDigraph Digraph;

   256   typedef Digraph::ArcMap<bool> ArcFilter;

   257   typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;

   259   Digraph digraph;

   260   ArcFilter arc_filter(digraph);

   261   Adaptor adaptor(digraph, arc_filter);

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

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

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

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

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

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

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

   273   checkGraphNodeList(adaptor, 3);

   274   checkGraphArcList(adaptor, 3);

   275   checkGraphConArcList(adaptor, 3);

   277   checkGraphOutArcList(adaptor, n1, 2);

   278   checkGraphOutArcList(adaptor, n2, 1);

   279   checkGraphOutArcList(adaptor, n3, 0);

   281   checkGraphInArcList(adaptor, n1, 0);

   282   checkGraphInArcList(adaptor, n2, 1);

   283   checkGraphInArcList(adaptor, n3, 2);

   285   checkNodeIds(adaptor);

   286   checkArcIds(adaptor);

   288   checkGraphNodeMap(adaptor);

   289   checkGraphArcMap(adaptor);

   291   arc_filter[a2] = false;

   293   checkGraphNodeList(adaptor, 3);

   294   checkGraphArcList(adaptor, 2);

   295   checkGraphConArcList(adaptor, 2);

   297   checkGraphOutArcList(adaptor, n1, 1);

   298   checkGraphOutArcList(adaptor, n2, 1);

   299   checkGraphOutArcList(adaptor, n3, 0);

   301   checkGraphInArcList(adaptor, n1, 0);

   302   checkGraphInArcList(adaptor, n2, 1);

   303   checkGraphInArcList(adaptor, n3, 1);

   305   checkNodeIds(adaptor);

   306   checkArcIds(adaptor);

   308   checkGraphNodeMap(adaptor);

   309   checkGraphArcMap(adaptor);

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

   313   checkGraphNodeList(adaptor, 3);

   314   checkGraphArcList(adaptor, 0);

   315   checkGraphConArcList(adaptor, 0);

   317   checkNodeIds(adaptor);

   318   checkArcIds(adaptor);

   320   checkGraphNodeMap(adaptor);

   321   checkGraphArcMap(adaptor);

   322 }

   324 void checkUndirDigraphAdaptor() {

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

   327   typedef ListDigraph Digraph;

   328   typedef UndirDigraphAdaptor<Digraph> Adaptor;

   330   Digraph digraph;

   331   Adaptor adaptor(digraph);

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

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

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

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

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

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

   341   checkGraphNodeList(adaptor, 3);

   342   checkGraphArcList(adaptor, 6);

   343   checkGraphEdgeList(adaptor, 3);

   344   checkGraphConArcList(adaptor, 6);

   345   checkGraphConEdgeList(adaptor, 3);

   347   checkGraphOutArcList(adaptor, n1, 2);

   348   checkGraphOutArcList(adaptor, n2, 2);

   349   checkGraphOutArcList(adaptor, n3, 2);

   351   checkGraphInArcList(adaptor, n1, 2);

   352   checkGraphInArcList(adaptor, n2, 2);

   353   checkGraphInArcList(adaptor, n3, 2);

   355   checkGraphIncEdgeList(adaptor, n1, 2);

   356   checkGraphIncEdgeList(adaptor, n2, 2);

   357   checkGraphIncEdgeList(adaptor, n3, 2);

   359   checkNodeIds(adaptor);

   360   checkArcIds(adaptor);

   361   checkEdgeIds(adaptor);

   363   checkGraphNodeMap(adaptor);

   364   checkGraphArcMap(adaptor);

   365   checkGraphEdgeMap(adaptor);

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

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

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

   370   }

   372 }

   374 void checkResDigraphAdaptor() {

   375   checkConcept<concepts::Digraph,

   376     ResDigraphAdaptor<concepts::Digraph,

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

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

   380   typedef ListDigraph Digraph;

   381   typedef Digraph::ArcMap<int> IntArcMap;

   382   typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;

   384   Digraph digraph;

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

   386   Adaptor adaptor(digraph, capacity, flow);

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

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

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

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

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

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

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

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

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

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

   400   capacity[a1] = 8;

   401   capacity[a2] = 6;

   402   capacity[a3] = 4;

   403   capacity[a4] = 4;

   404   capacity[a5] = 6;

   405   capacity[a6] = 10;

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

   408     flow[a] = 0;

   409   }

   411   checkGraphNodeList(adaptor, 4);

   412   checkGraphArcList(adaptor, 6);

   413   checkGraphConArcList(adaptor, 6);

   415   checkGraphOutArcList(adaptor, n1, 3);

   416   checkGraphOutArcList(adaptor, n2, 2);

   417   checkGraphOutArcList(adaptor, n3, 1);

   418   checkGraphOutArcList(adaptor, n4, 0);

   420   checkGraphInArcList(adaptor, n1, 0);

   421   checkGraphInArcList(adaptor, n2, 1);

   422   checkGraphInArcList(adaptor, n3, 2);

   423   checkGraphInArcList(adaptor, n4, 3);

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

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

   427   }

   429   checkGraphNodeList(adaptor, 4);

   430   checkGraphArcList(adaptor, 12);

   431   checkGraphConArcList(adaptor, 12);

   433   checkGraphOutArcList(adaptor, n1, 3);

   434   checkGraphOutArcList(adaptor, n2, 3);

   435   checkGraphOutArcList(adaptor, n3, 3);

   436   checkGraphOutArcList(adaptor, n4, 3);

   438   checkGraphInArcList(adaptor, n1, 3);

   439   checkGraphInArcList(adaptor, n2, 3);

   440   checkGraphInArcList(adaptor, n3, 3);

   441   checkGraphInArcList(adaptor, n4, 3);

   443   checkNodeIds(adaptor);

   444   checkArcIds(adaptor);

   446   checkGraphNodeMap(adaptor);

   447   checkGraphArcMap(adaptor);

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

   450     flow[a] = capacity[a];

   451   }

   453   checkGraphNodeList(adaptor, 4);

   454   checkGraphArcList(adaptor, 6);

   455   checkGraphConArcList(adaptor, 6);

   457   checkGraphOutArcList(adaptor, n1, 0);

   458   checkGraphOutArcList(adaptor, n2, 1);

   459   checkGraphOutArcList(adaptor, n3, 2);

   460   checkGraphOutArcList(adaptor, n4, 3);

   462   checkGraphInArcList(adaptor, n1, 3);

   463   checkGraphInArcList(adaptor, n2, 2);

   464   checkGraphInArcList(adaptor, n3, 1);

   465   checkGraphInArcList(adaptor, n4, 0);

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

   468     flow[a] = 0;

   469   }

   471   int flow_value = 0;

   472   while (true) {

   474     Bfs<Adaptor> bfs(adaptor);

   475     bfs.run(n1, n4);

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

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

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

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

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

   484     }

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

   487       adaptor.augment(a, min);

   488     }

   489     flow_value += min;

   490   }

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

   494 }

   496 void checkSplitDigraphAdaptor() {

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

   499   typedef ListDigraph Digraph;

   500   typedef SplitDigraphAdaptor<Digraph> Adaptor;

   502   Digraph digraph;

   503   Adaptor adaptor(digraph);

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

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

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

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

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

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

   513   checkGraphNodeList(adaptor, 6);

   514   checkGraphArcList(adaptor, 6);

   515   checkGraphConArcList(adaptor, 6);

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

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

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

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

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

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

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

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

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

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

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

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

   531   checkNodeIds(adaptor);

   532   checkArcIds(adaptor);

   534   checkGraphNodeMap(adaptor);

   535   checkGraphArcMap(adaptor);

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

   538     if (adaptor.origArc(a)) {

   539       Digraph::Arc oa = a;

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

   541 	    "Wrong split");

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

   543 	    "Wrong split");

   544     } else {

   545       Digraph::Node on = a;

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

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

   548     }

   549   }

   550 }

   552 void checkSubGraphAdaptor() {

   553   checkConcept<concepts::Graph,

   554     SubGraphAdaptor<concepts::Graph,

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

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

   558   typedef ListGraph Graph;

   559   typedef Graph::NodeMap<bool> NodeFilter;

   560   typedef Graph::EdgeMap<bool> EdgeFilter;

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

   563   Graph graph;

   564   NodeFilter node_filter(graph);

   565   EdgeFilter edge_filter(graph);

   566   Adaptor adaptor(graph, node_filter, edge_filter);

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

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

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

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

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

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

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

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

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

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

   581   checkGraphNodeList(adaptor, 4);

   582   checkGraphArcList(adaptor, 8);

   583   checkGraphEdgeList(adaptor, 4);

   584   checkGraphConArcList(adaptor, 8);

   585   checkGraphConEdgeList(adaptor, 4);

   587   checkGraphOutArcList(adaptor, n1, 2);

   588   checkGraphOutArcList(adaptor, n2, 2);

   589   checkGraphOutArcList(adaptor, n3, 3);

   590   checkGraphOutArcList(adaptor, n4, 1);

   592   checkGraphInArcList(adaptor, n1, 2);

   593   checkGraphInArcList(adaptor, n2, 2);

   594   checkGraphInArcList(adaptor, n3, 3);

   595   checkGraphInArcList(adaptor, n4, 1);

   597   checkGraphIncEdgeList(adaptor, n1, 2);

   598   checkGraphIncEdgeList(adaptor, n2, 2);

   599   checkGraphIncEdgeList(adaptor, n3, 3);

   600   checkGraphIncEdgeList(adaptor, n4, 1);

   602   checkNodeIds(adaptor);

   603   checkArcIds(adaptor);

   604   checkEdgeIds(adaptor);

   606   checkGraphNodeMap(adaptor);

   607   checkGraphArcMap(adaptor);

   608   checkGraphEdgeMap(adaptor);

   610   edge_filter[e2] = false;

   612   checkGraphNodeList(adaptor, 4);

   613   checkGraphArcList(adaptor, 6);

   614   checkGraphEdgeList(adaptor, 3);

   615   checkGraphConArcList(adaptor, 6);

   616   checkGraphConEdgeList(adaptor, 3);

   618   checkGraphOutArcList(adaptor, n1, 1);

   619   checkGraphOutArcList(adaptor, n2, 2);

   620   checkGraphOutArcList(adaptor, n3, 2);

   621   checkGraphOutArcList(adaptor, n4, 1);

   623   checkGraphInArcList(adaptor, n1, 1);

   624   checkGraphInArcList(adaptor, n2, 2);

   625   checkGraphInArcList(adaptor, n3, 2);

   626   checkGraphInArcList(adaptor, n4, 1);

   628   checkGraphIncEdgeList(adaptor, n1, 1);

   629   checkGraphIncEdgeList(adaptor, n2, 2);

   630   checkGraphIncEdgeList(adaptor, n3, 2);

   631   checkGraphIncEdgeList(adaptor, n4, 1);

   633   checkNodeIds(adaptor);

   634   checkArcIds(adaptor);

   635   checkEdgeIds(adaptor);

   637   checkGraphNodeMap(adaptor);

   638   checkGraphArcMap(adaptor);

   639   checkGraphEdgeMap(adaptor);

   641   node_filter[n1] = false;

   643   checkGraphNodeList(adaptor, 3);

   644   checkGraphArcList(adaptor, 4);

   645   checkGraphEdgeList(adaptor, 2);

   646   checkGraphConArcList(adaptor, 4);

   647   checkGraphConEdgeList(adaptor, 2);

   649   checkGraphOutArcList(adaptor, n2, 1);

   650   checkGraphOutArcList(adaptor, n3, 2);

   651   checkGraphOutArcList(adaptor, n4, 1);

   653   checkGraphInArcList(adaptor, n2, 1);

   654   checkGraphInArcList(adaptor, n3, 2);

   655   checkGraphInArcList(adaptor, n4, 1);

   657   checkGraphIncEdgeList(adaptor, n2, 1);

   658   checkGraphIncEdgeList(adaptor, n3, 2);

   659   checkGraphIncEdgeList(adaptor, n4, 1);

   661   checkNodeIds(adaptor);

   662   checkArcIds(adaptor);

   663   checkEdgeIds(adaptor);

   665   checkGraphNodeMap(adaptor);

   666   checkGraphArcMap(adaptor);

   667   checkGraphEdgeMap(adaptor);

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

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

   672   checkGraphNodeList(adaptor, 0);

   673   checkGraphArcList(adaptor, 0);

   674   checkGraphEdgeList(adaptor, 0);

   675   checkGraphConArcList(adaptor, 0);

   676   checkGraphConEdgeList(adaptor, 0);

   678   checkNodeIds(adaptor);

   679   checkArcIds(adaptor);

   680   checkEdgeIds(adaptor);

   682   checkGraphNodeMap(adaptor);

   683   checkGraphArcMap(adaptor);

   684   checkGraphEdgeMap(adaptor);

   685 }

   687 void checkNodeSubGraphAdaptor() {

   688   checkConcept<concepts::Graph,

   689     NodeSubGraphAdaptor<concepts::Graph,

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

   692   typedef ListGraph Graph;

   693   typedef Graph::NodeMap<bool> NodeFilter;

   694   typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;

   696   Graph graph;

   697   NodeFilter node_filter(graph);

   698   Adaptor adaptor(graph, node_filter);

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

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

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

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

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

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

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

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

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

   712   checkGraphNodeList(adaptor, 4);

   713   checkGraphArcList(adaptor, 8);

   714   checkGraphEdgeList(adaptor, 4);

   715   checkGraphConArcList(adaptor, 8);

   716   checkGraphConEdgeList(adaptor, 4);

   718   checkGraphOutArcList(adaptor, n1, 2);

   719   checkGraphOutArcList(adaptor, n2, 2);

   720   checkGraphOutArcList(adaptor, n3, 3);

   721   checkGraphOutArcList(adaptor, n4, 1);

   723   checkGraphInArcList(adaptor, n1, 2);

   724   checkGraphInArcList(adaptor, n2, 2);

   725   checkGraphInArcList(adaptor, n3, 3);

   726   checkGraphInArcList(adaptor, n4, 1);

   728   checkGraphIncEdgeList(adaptor, n1, 2);

   729   checkGraphIncEdgeList(adaptor, n2, 2);

   730   checkGraphIncEdgeList(adaptor, n3, 3);

   731   checkGraphIncEdgeList(adaptor, n4, 1);

   733   checkNodeIds(adaptor);

   734   checkArcIds(adaptor);

   735   checkEdgeIds(adaptor);

   737   checkGraphNodeMap(adaptor);

   738   checkGraphArcMap(adaptor);

   739   checkGraphEdgeMap(adaptor);

   741   node_filter[n1] = false;

   743   checkGraphNodeList(adaptor, 3);

   744   checkGraphArcList(adaptor, 4);

   745   checkGraphEdgeList(adaptor, 2);

   746   checkGraphConArcList(adaptor, 4);

   747   checkGraphConEdgeList(adaptor, 2);

   749   checkGraphOutArcList(adaptor, n2, 1);

   750   checkGraphOutArcList(adaptor, n3, 2);

   751   checkGraphOutArcList(adaptor, n4, 1);

   753   checkGraphInArcList(adaptor, n2, 1);

   754   checkGraphInArcList(adaptor, n3, 2);

   755   checkGraphInArcList(adaptor, n4, 1);

   757   checkGraphIncEdgeList(adaptor, n2, 1);

   758   checkGraphIncEdgeList(adaptor, n3, 2);

   759   checkGraphIncEdgeList(adaptor, n4, 1);

   761   checkNodeIds(adaptor);

   762   checkArcIds(adaptor);

   763   checkEdgeIds(adaptor);

   765   checkGraphNodeMap(adaptor);

   766   checkGraphArcMap(adaptor);

   767   checkGraphEdgeMap(adaptor);

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

   771   checkGraphNodeList(adaptor, 0);

   772   checkGraphArcList(adaptor, 0);

   773   checkGraphEdgeList(adaptor, 0);

   774   checkGraphConArcList(adaptor, 0);

   775   checkGraphConEdgeList(adaptor, 0);

   777   checkNodeIds(adaptor);

   778   checkArcIds(adaptor);

   779   checkEdgeIds(adaptor);

   781   checkGraphNodeMap(adaptor);

   782   checkGraphArcMap(adaptor);

   783   checkGraphEdgeMap(adaptor);

   784 }

   786 void checkEdgeSubGraphAdaptor() {

   787   checkConcept<concepts::Graph,

   788     EdgeSubGraphAdaptor<concepts::Graph,

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

   791   typedef ListGraph Graph;

   792   typedef Graph::EdgeMap<bool> EdgeFilter;

   793   typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;

   795   Graph graph;

   796   EdgeFilter edge_filter(graph);

   797   Adaptor adaptor(graph, edge_filter);

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

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

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

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

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

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

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

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

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

   811   checkGraphNodeList(adaptor, 4);

   812   checkGraphArcList(adaptor, 8);

   813   checkGraphEdgeList(adaptor, 4);

   814   checkGraphConArcList(adaptor, 8);

   815   checkGraphConEdgeList(adaptor, 4);

   817   checkGraphOutArcList(adaptor, n1, 2);

   818   checkGraphOutArcList(adaptor, n2, 2);

   819   checkGraphOutArcList(adaptor, n3, 3);

   820   checkGraphOutArcList(adaptor, n4, 1);

   822   checkGraphInArcList(adaptor, n1, 2);

   823   checkGraphInArcList(adaptor, n2, 2);

   824   checkGraphInArcList(adaptor, n3, 3);

   825   checkGraphInArcList(adaptor, n4, 1);

   827   checkGraphIncEdgeList(adaptor, n1, 2);

   828   checkGraphIncEdgeList(adaptor, n2, 2);

   829   checkGraphIncEdgeList(adaptor, n3, 3);

   830   checkGraphIncEdgeList(adaptor, n4, 1);

   832   checkNodeIds(adaptor);

   833   checkArcIds(adaptor);

   834   checkEdgeIds(adaptor);

   836   checkGraphNodeMap(adaptor);

   837   checkGraphArcMap(adaptor);

   838   checkGraphEdgeMap(adaptor);

   840   edge_filter[e2] = false;

   842   checkGraphNodeList(adaptor, 4);

   843   checkGraphArcList(adaptor, 6);

   844   checkGraphEdgeList(adaptor, 3);

   845   checkGraphConArcList(adaptor, 6);

   846   checkGraphConEdgeList(adaptor, 3);

   848   checkGraphOutArcList(adaptor, n1, 1);

   849   checkGraphOutArcList(adaptor, n2, 2);

   850   checkGraphOutArcList(adaptor, n3, 2);

   851   checkGraphOutArcList(adaptor, n4, 1);

   853   checkGraphInArcList(adaptor, n1, 1);

   854   checkGraphInArcList(adaptor, n2, 2);

   855   checkGraphInArcList(adaptor, n3, 2);

   856   checkGraphInArcList(adaptor, n4, 1);

   858   checkGraphIncEdgeList(adaptor, n1, 1);

   859   checkGraphIncEdgeList(adaptor, n2, 2);

   860   checkGraphIncEdgeList(adaptor, n3, 2);

   861   checkGraphIncEdgeList(adaptor, n4, 1);

   863   checkNodeIds(adaptor);

   864   checkArcIds(adaptor);

   865   checkEdgeIds(adaptor);

   867   checkGraphNodeMap(adaptor);

   868   checkGraphArcMap(adaptor);

   869   checkGraphEdgeMap(adaptor);

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

   873   checkGraphNodeList(adaptor, 4);

   874   checkGraphArcList(adaptor, 0);

   875   checkGraphEdgeList(adaptor, 0);

   876   checkGraphConArcList(adaptor, 0);

   877   checkGraphConEdgeList(adaptor, 0);

   879   checkNodeIds(adaptor);

   880   checkArcIds(adaptor);

   881   checkEdgeIds(adaptor);

   883   checkGraphNodeMap(adaptor);

   884   checkGraphArcMap(adaptor);

   885   checkGraphEdgeMap(adaptor);

   886 }

   888 void checkDirGraphAdaptor() {

   889   checkConcept<concepts::Digraph,

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

   892   typedef ListGraph Graph;

   893   typedef ListGraph::EdgeMap<bool> DirMap;

   894   typedef DirGraphAdaptor<Graph> Adaptor;

   896   Graph graph;

   897   DirMap dir(graph, true);

   898   Adaptor adaptor(graph, dir);

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

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

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

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

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

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

   908   checkGraphNodeList(adaptor, 3);

   909   checkGraphArcList(adaptor, 3);

   910   checkGraphConArcList(adaptor, 3);

   912   {

   913     dir[e1] = true;

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

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

   917     dir[e1] = false;

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

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

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

   922     dir[e1] = n1 == u;

   923   }

   925   {

   926     dir[e2] = true;

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

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

   930     dir[e2] = false;

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

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

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

   935     dir[e2] = n3 == u;

   936   }

   938   {

   939     dir[e3] = true;

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

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

   943     dir[e3] = false;

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

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

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

   948     dir[e3] = n2 == u;

   949   }

   951   checkGraphOutArcList(adaptor, n1, 1);

   952   checkGraphOutArcList(adaptor, n2, 1);

   953   checkGraphOutArcList(adaptor, n3, 1);

   955   checkGraphInArcList(adaptor, n1, 1);

   956   checkGraphInArcList(adaptor, n2, 1);

   957   checkGraphInArcList(adaptor, n3, 1);

   959   checkNodeIds(adaptor);

   960   checkArcIds(adaptor);

   962   checkGraphNodeMap(adaptor);

   963   checkGraphArcMap(adaptor);

   965 }

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

   970   checkRevDigraphAdaptor();

   971   checkSubDigraphAdaptor();

   972   checkNodeSubDigraphAdaptor();

   973   checkArcSubDigraphAdaptor();

   974   checkUndirDigraphAdaptor();

   975   checkResDigraphAdaptor();

   976   checkSplitDigraphAdaptor();

   978   checkSubGraphAdaptor();

   979   checkNodeSubGraphAdaptor();

   980   checkEdgeSubGraphAdaptor();

   981   checkDirGraphAdaptor();

   983   return 0;

   984 }

author	Balazs Dezso <deba@inf.elte.hu>
	Sun, 30 Nov 2008 19:00:30 +0100
changeset 415	4b6112235fad
parent 414	05357da973ce
child 416	76287c8caa26
permissions	-rw-r--r--