lemon-main: test/adaptors_test.cc@c6aa2cc1af04

     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2013

     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 <limits>

    22 #include <lemon/list_graph.h>

    23 #include <lemon/grid_graph.h>

    24 #include <lemon/bfs.h>

    25 #include <lemon/path.h>

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

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

    29 #include <lemon/concepts/graph_components.h>

    30 #include <lemon/concepts/maps.h>

    31 #include <lemon/concept_check.h>

    33 #include <lemon/adaptors.h>

    35 #include "test/test_tools.h"

    36 #include "test/graph_test.h"

    38 using namespace lemon;

    40 void checkReverseDigraph() {

    41   // Check concepts

    42   checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();

    43   checkConcept<concepts::Digraph, ReverseDigraph<ListDigraph> >();

    44   checkConcept<concepts::AlterableDigraphComponent<>,

    45                ReverseDigraph<ListDigraph> >();

    46   checkConcept<concepts::ExtendableDigraphComponent<>,

    47                ReverseDigraph<ListDigraph> >();

    48   checkConcept<concepts::ErasableDigraphComponent<>,

    49                ReverseDigraph<ListDigraph> >();

    50   checkConcept<concepts::ClearableDigraphComponent<>,

    51                ReverseDigraph<ListDigraph> >();

    53   // Create a digraph and an adaptor

    54   typedef ListDigraph Digraph;

    55   typedef ReverseDigraph<Digraph> Adaptor;

    57   Digraph digraph;

    58   Adaptor adaptor(digraph);

    60   // Add nodes and arcs to the original digraph

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

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

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

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

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

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

    68   ::lemon::ignore_unused_variable_warning(a3);

    70   // Check the adaptor

    71   checkGraphNodeList(adaptor, 3);

    72   checkGraphArcList(adaptor, 3);

    73   checkGraphConArcList(adaptor, 3);

    75   checkGraphOutArcList(adaptor, n1, 0);

    76   checkGraphOutArcList(adaptor, n2, 1);

    77   checkGraphOutArcList(adaptor, n3, 2);

    79   checkGraphInArcList(adaptor, n1, 2);

    80   checkGraphInArcList(adaptor, n2, 1);

    81   checkGraphInArcList(adaptor, n3, 0);

    83   checkNodeIds(adaptor);

    84   checkArcIds(adaptor);

    86   checkGraphNodeMap(adaptor);

    87   checkGraphArcMap(adaptor);

    89   // Check the orientation of the arcs

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

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

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

    93   }

    95   // Add and erase nodes and arcs in the digraph through the adaptor

    96   Adaptor::Node n4 = adaptor.addNode();

    98   Adaptor::Arc a4 = adaptor.addArc(n4, n3);

    99   Adaptor::Arc a5 = adaptor.addArc(n2, n4);

   100   Adaptor::Arc a6 = adaptor.addArc(n2, n4);

   101   Adaptor::Arc a7 = adaptor.addArc(n1, n4);

   102   Adaptor::Arc a8 = adaptor.addArc(n1, n2);

   103   ::lemon::ignore_unused_variable_warning(a6,a7,a8);

   105   adaptor.erase(a1);

   106   adaptor.erase(n3);

   108   // Check the adaptor

   109   checkGraphNodeList(adaptor, 3);

   110   checkGraphArcList(adaptor, 4);

   111   checkGraphConArcList(adaptor, 4);

   113   checkGraphOutArcList(adaptor, n1, 2);

   114   checkGraphOutArcList(adaptor, n2, 2);

   115   checkGraphOutArcList(adaptor, n4, 0);

   117   checkGraphInArcList(adaptor, n1, 0);

   118   checkGraphInArcList(adaptor, n2, 1);

   119   checkGraphInArcList(adaptor, n4, 3);

   121   checkNodeIds(adaptor);

   122   checkArcIds(adaptor);

   124   checkGraphNodeMap(adaptor);

   125   checkGraphArcMap(adaptor);

   127   // Check the digraph

   128   checkGraphNodeList(digraph, 3);

   129   checkGraphArcList(digraph, 4);

   130   checkGraphConArcList(digraph, 4);

   132   checkGraphOutArcList(digraph, n1, 0);

   133   checkGraphOutArcList(digraph, n2, 1);

   134   checkGraphOutArcList(digraph, n4, 3);

   136   checkGraphInArcList(digraph, n1, 2);

   137   checkGraphInArcList(digraph, n2, 2);

   138   checkGraphInArcList(digraph, n4, 0);

   140   checkNodeIds(digraph);

   141   checkArcIds(digraph);

   143   checkGraphNodeMap(digraph);

   144   checkGraphArcMap(digraph);

   146   // Check the conversion of nodes and arcs

   147   Digraph::Node nd = n4;

   148   ::lemon::ignore_unused_variable_warning(nd);

   149   nd = n4;

   150   Adaptor::Node na = n1;

   151   ::lemon::ignore_unused_variable_warning(na);

   152   na = n2;

   153   Digraph::Arc ad = a4;

   154   ::lemon::ignore_unused_variable_warning(ad);

   155   ad = a5;

   156   Adaptor::Arc aa = a1;

   157   ::lemon::ignore_unused_variable_warning(aa);

   158   aa = a2;

   159 }

   161 void checkSubDigraph() {

   162   // Check concepts

   163   checkConcept<concepts::Digraph, SubDigraph<concepts::Digraph> >();

   164   checkConcept<concepts::Digraph, SubDigraph<ListDigraph> >();

   165   checkConcept<concepts::AlterableDigraphComponent<>,

   166                SubDigraph<ListDigraph> >();

   167   checkConcept<concepts::ExtendableDigraphComponent<>,

   168                SubDigraph<ListDigraph> >();

   169   checkConcept<concepts::ErasableDigraphComponent<>,

   170                SubDigraph<ListDigraph> >();

   171   checkConcept<concepts::ClearableDigraphComponent<>,

   172                SubDigraph<ListDigraph> >();

   174   // Create a digraph and an adaptor

   175   typedef ListDigraph Digraph;

   176   typedef Digraph::NodeMap<bool> NodeFilter;

   177   typedef Digraph::ArcMap<bool> ArcFilter;

   178   typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;

   180   Digraph digraph;

   181   NodeFilter node_filter(digraph);

   182   ArcFilter arc_filter(digraph);

   183   Adaptor adaptor(digraph, node_filter, arc_filter);

   185   // Add nodes and arcs to the original digraph and the adaptor

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

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

   188   Adaptor::Node n3 = adaptor.addNode();

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

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

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

   194   Adaptor::Arc a3 = adaptor.addArc(n2, n3);

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

   198   checkGraphNodeList(adaptor, 3);

   199   checkGraphArcList(adaptor, 3);

   200   checkGraphConArcList(adaptor, 3);

   202   checkGraphOutArcList(adaptor, n1, 2);

   203   checkGraphOutArcList(adaptor, n2, 1);

   204   checkGraphOutArcList(adaptor, n3, 0);

   206   checkGraphInArcList(adaptor, n1, 0);

   207   checkGraphInArcList(adaptor, n2, 1);

   208   checkGraphInArcList(adaptor, n3, 2);

   210   checkNodeIds(adaptor);

   211   checkArcIds(adaptor);

   213   checkGraphNodeMap(adaptor);

   214   checkGraphArcMap(adaptor);

   216   // Hide an arc

   217   adaptor.status(a2, false);

   218   adaptor.disable(a3);

   219   if (!adaptor.status(a3)) adaptor.enable(a3);

   221   checkGraphNodeList(adaptor, 3);

   222   checkGraphArcList(adaptor, 2);

   223   checkGraphConArcList(adaptor, 2);

   225   checkGraphOutArcList(adaptor, n1, 1);

   226   checkGraphOutArcList(adaptor, n2, 1);

   227   checkGraphOutArcList(adaptor, n3, 0);

   229   checkGraphInArcList(adaptor, n1, 0);

   230   checkGraphInArcList(adaptor, n2, 1);

   231   checkGraphInArcList(adaptor, n3, 1);

   233   checkNodeIds(adaptor);

   234   checkArcIds(adaptor);

   236   checkGraphNodeMap(adaptor);

   237   checkGraphArcMap(adaptor);

   239   // Hide a node

   240   adaptor.status(n1, false);

   241   adaptor.disable(n3);

   242   if (!adaptor.status(n3)) adaptor.enable(n3);

   244   checkGraphNodeList(adaptor, 2);

   245   checkGraphArcList(adaptor, 1);

   246   checkGraphConArcList(adaptor, 1);

   248   checkGraphOutArcList(adaptor, n2, 1);

   249   checkGraphOutArcList(adaptor, n3, 0);

   251   checkGraphInArcList(adaptor, n2, 0);

   252   checkGraphInArcList(adaptor, n3, 1);

   254   checkNodeIds(adaptor);

   255   checkArcIds(adaptor);

   257   checkGraphNodeMap(adaptor);

   258   checkGraphArcMap(adaptor);

   260   // Hide all nodes and arcs

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

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

   264   checkGraphNodeList(adaptor, 0);

   265   checkGraphArcList(adaptor, 0);

   266   checkGraphConArcList(adaptor, 0);

   268   checkNodeIds(adaptor);

   269   checkArcIds(adaptor);

   271   checkGraphNodeMap(adaptor);

   272   checkGraphArcMap(adaptor);

   274   // Check the conversion of nodes and arcs

   275   Digraph::Node nd = n3;

   276   ::lemon::ignore_unused_variable_warning(nd);

   277   nd = n3;

   278   Adaptor::Node na = n1;

   279   ::lemon::ignore_unused_variable_warning(na);

   280   na = n2;

   281   Digraph::Arc ad = a3;

   282   ::lemon::ignore_unused_variable_warning(ad);

   283   ad = a3;

   284   Adaptor::Arc aa = a1;

   285   ::lemon::ignore_unused_variable_warning(aa);

   286   aa = a2;

   287 }

   289 void checkFilterNodes1() {

   290   // Check concepts

   291   checkConcept<concepts::Digraph, FilterNodes<concepts::Digraph> >();

   292   checkConcept<concepts::Digraph, FilterNodes<ListDigraph> >();

   293   checkConcept<concepts::AlterableDigraphComponent<>,

   294                FilterNodes<ListDigraph> >();

   295   checkConcept<concepts::ExtendableDigraphComponent<>,

   296                FilterNodes<ListDigraph> >();

   297   checkConcept<concepts::ErasableDigraphComponent<>,

   298                FilterNodes<ListDigraph> >();

   299   checkConcept<concepts::ClearableDigraphComponent<>,

   300                FilterNodes<ListDigraph> >();

   302   // Create a digraph and an adaptor

   303   typedef ListDigraph Digraph;

   304   typedef Digraph::NodeMap<bool> NodeFilter;

   305   typedef FilterNodes<Digraph, NodeFilter> Adaptor;

   307   Digraph digraph;

   308   NodeFilter node_filter(digraph);

   309   Adaptor adaptor(digraph, node_filter);

   311   // Add nodes and arcs to the original digraph and the adaptor

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

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

   314   Adaptor::Node n3 = adaptor.addNode();

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

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

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

   320   Adaptor::Arc a3 = adaptor.addArc(n2, n3);

   322   checkGraphNodeList(adaptor, 3);

   323   checkGraphArcList(adaptor, 3);

   324   checkGraphConArcList(adaptor, 3);

   326   checkGraphOutArcList(adaptor, n1, 2);

   327   checkGraphOutArcList(adaptor, n2, 1);

   328   checkGraphOutArcList(adaptor, n3, 0);

   330   checkGraphInArcList(adaptor, n1, 0);

   331   checkGraphInArcList(adaptor, n2, 1);

   332   checkGraphInArcList(adaptor, n3, 2);

   334   checkNodeIds(adaptor);

   335   checkArcIds(adaptor);

   337   checkGraphNodeMap(adaptor);

   338   checkGraphArcMap(adaptor);

   340   // Hide a node

   341   adaptor.status(n1, false);

   342   adaptor.disable(n3);

   343   if (!adaptor.status(n3)) adaptor.enable(n3);

   345   checkGraphNodeList(adaptor, 2);

   346   checkGraphArcList(adaptor, 1);

   347   checkGraphConArcList(adaptor, 1);

   349   checkGraphOutArcList(adaptor, n2, 1);

   350   checkGraphOutArcList(adaptor, n3, 0);

   352   checkGraphInArcList(adaptor, n2, 0);

   353   checkGraphInArcList(adaptor, n3, 1);

   355   checkNodeIds(adaptor);

   356   checkArcIds(adaptor);

   358   checkGraphNodeMap(adaptor);

   359   checkGraphArcMap(adaptor);

   361   // Hide all nodes

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

   364   checkGraphNodeList(adaptor, 0);

   365   checkGraphArcList(adaptor, 0);

   366   checkGraphConArcList(adaptor, 0);

   368   checkNodeIds(adaptor);

   369   checkArcIds(adaptor);

   371   checkGraphNodeMap(adaptor);

   372   checkGraphArcMap(adaptor);

   374   // Check the conversion of nodes and arcs

   375   Digraph::Node nd = n3;

   376   ::lemon::ignore_unused_variable_warning(nd);

   377   nd = n3;

   378   Adaptor::Node na = n1;

   379   ::lemon::ignore_unused_variable_warning(na);

   380   na = n2;

   381   Digraph::Arc ad = a3;

   382   ::lemon::ignore_unused_variable_warning(ad);

   383   ad = a3;

   384   Adaptor::Arc aa = a1;

   385   ::lemon::ignore_unused_variable_warning(aa);

   386   aa = a2;

   387 }

   389 void checkFilterArcs() {

   390   // Check concepts

   391   checkConcept<concepts::Digraph, FilterArcs<concepts::Digraph> >();

   392   checkConcept<concepts::Digraph, FilterArcs<ListDigraph> >();

   393   checkConcept<concepts::AlterableDigraphComponent<>,

   394                FilterArcs<ListDigraph> >();

   395   checkConcept<concepts::ExtendableDigraphComponent<>,

   396                FilterArcs<ListDigraph> >();

   397   checkConcept<concepts::ErasableDigraphComponent<>,

   398                FilterArcs<ListDigraph> >();

   399   checkConcept<concepts::ClearableDigraphComponent<>,

   400                FilterArcs<ListDigraph> >();

   402   // Create a digraph and an adaptor

   403   typedef ListDigraph Digraph;

   404   typedef Digraph::ArcMap<bool> ArcFilter;

   405   typedef FilterArcs<Digraph, ArcFilter> Adaptor;

   407   Digraph digraph;

   408   ArcFilter arc_filter(digraph);

   409   Adaptor adaptor(digraph, arc_filter);

   411   // Add nodes and arcs to the original digraph and the adaptor

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

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

   414   Adaptor::Node n3 = adaptor.addNode();

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

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

   418   Adaptor::Arc a3 = adaptor.addArc(n2, n3);

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

   422   checkGraphNodeList(adaptor, 3);

   423   checkGraphArcList(adaptor, 3);

   424   checkGraphConArcList(adaptor, 3);

   426   checkGraphOutArcList(adaptor, n1, 2);

   427   checkGraphOutArcList(adaptor, n2, 1);

   428   checkGraphOutArcList(adaptor, n3, 0);

   430   checkGraphInArcList(adaptor, n1, 0);

   431   checkGraphInArcList(adaptor, n2, 1);

   432   checkGraphInArcList(adaptor, n3, 2);

   434   checkNodeIds(adaptor);

   435   checkArcIds(adaptor);

   437   checkGraphNodeMap(adaptor);

   438   checkGraphArcMap(adaptor);

   440   // Hide an arc

   441   adaptor.status(a2, false);

   442   adaptor.disable(a3);

   443   if (!adaptor.status(a3)) adaptor.enable(a3);

   445   checkGraphNodeList(adaptor, 3);

   446   checkGraphArcList(adaptor, 2);

   447   checkGraphConArcList(adaptor, 2);

   449   checkGraphOutArcList(adaptor, n1, 1);

   450   checkGraphOutArcList(adaptor, n2, 1);

   451   checkGraphOutArcList(adaptor, n3, 0);

   453   checkGraphInArcList(adaptor, n1, 0);

   454   checkGraphInArcList(adaptor, n2, 1);

   455   checkGraphInArcList(adaptor, n3, 1);

   457   checkNodeIds(adaptor);

   458   checkArcIds(adaptor);

   460   checkGraphNodeMap(adaptor);

   461   checkGraphArcMap(adaptor);

   463   // Hide all arcs

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

   466   checkGraphNodeList(adaptor, 3);

   467   checkGraphArcList(adaptor, 0);

   468   checkGraphConArcList(adaptor, 0);

   470   checkNodeIds(adaptor);

   471   checkArcIds(adaptor);

   473   checkGraphNodeMap(adaptor);

   474   checkGraphArcMap(adaptor);

   476   // Check the conversion of nodes and arcs

   477   Digraph::Node nd = n3;

   478   ::lemon::ignore_unused_variable_warning(nd);

   479   nd = n3;

   480   Adaptor::Node na = n1;

   481   ::lemon::ignore_unused_variable_warning(na);

   482   na = n2;

   483   Digraph::Arc ad = a3;

   484   ::lemon::ignore_unused_variable_warning(ad);

   485   ad = a3;

   486   Adaptor::Arc aa = a1;

   487   ::lemon::ignore_unused_variable_warning(aa);

   488   aa = a2;

   489 }

   491 void checkUndirector() {

   492   // Check concepts

   493   checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();

   494   checkConcept<concepts::Graph, Undirector<ListDigraph> >();

   495   checkConcept<concepts::AlterableGraphComponent<>,

   496                Undirector<ListDigraph> >();

   497   checkConcept<concepts::ExtendableGraphComponent<>,

   498                Undirector<ListDigraph> >();

   499   checkConcept<concepts::ErasableGraphComponent<>,

   500                Undirector<ListDigraph> >();

   501   checkConcept<concepts::ClearableGraphComponent<>,

   502                Undirector<ListDigraph> >();

   505   // Create a digraph and an adaptor

   506   typedef ListDigraph Digraph;

   507   typedef Undirector<Digraph> Adaptor;

   509   Digraph digraph;

   510   Adaptor adaptor(digraph);

   512   // Add nodes and arcs/edges to the original digraph and the adaptor

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

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

   515   Adaptor::Node n3 = adaptor.addNode();

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

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

   519   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

   521   // Check the original digraph

   522   checkGraphNodeList(digraph, 3);

   523   checkGraphArcList(digraph, 3);

   524   checkGraphConArcList(digraph, 3);

   526   checkGraphOutArcList(digraph, n1, 2);

   527   checkGraphOutArcList(digraph, n2, 1);

   528   checkGraphOutArcList(digraph, n3, 0);

   530   checkGraphInArcList(digraph, n1, 0);

   531   checkGraphInArcList(digraph, n2, 1);

   532   checkGraphInArcList(digraph, n3, 2);

   534   checkNodeIds(digraph);

   535   checkArcIds(digraph);

   537   checkGraphNodeMap(digraph);

   538   checkGraphArcMap(digraph);

   540   // Check the adaptor

   541   checkGraphNodeList(adaptor, 3);

   542   checkGraphArcList(adaptor, 6);

   543   checkGraphEdgeList(adaptor, 3);

   544   checkGraphConArcList(adaptor, 6);

   545   checkGraphConEdgeList(adaptor, 3);

   547   checkGraphIncEdgeArcLists(adaptor, n1, 2);

   548   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   549   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   551   checkNodeIds(adaptor);

   552   checkArcIds(adaptor);

   553   checkEdgeIds(adaptor);

   555   checkGraphNodeMap(adaptor);

   556   checkGraphArcMap(adaptor);

   557   checkGraphEdgeMap(adaptor);

   559   // Check the edges of the adaptor

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

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

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

   563   }

   565   // Check CombinedArcMap

   566   typedef Adaptor::CombinedArcMap

   567     <Digraph::ArcMap<int>, Digraph::ArcMap<int> > IntCombinedMap;

   568   typedef Adaptor::CombinedArcMap

   569     <Digraph::ArcMap<bool>, Digraph::ArcMap<bool> > BoolCombinedMap;

   570   checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,

   571     IntCombinedMap>();

   572   checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,

   573     BoolCombinedMap>();

   575   Digraph::ArcMap<int> fw_map(digraph), bk_map(digraph);

   576   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   577     fw_map[a] = digraph.id(a);

   578     bk_map[a] = -digraph.id(a);

   579   }

   581   Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::ArcMap<int> >

   582     comb_map(fw_map, bk_map);

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

   584     if (adaptor.source(a) == digraph.source(a)) {

   585       check(comb_map[a] == fw_map[a], "Wrong combined map");

   586     } else {

   587       check(comb_map[a] == bk_map[a], "Wrong combined map");

   588     }

   589   }

   591   // Check the conversion of nodes and arcs/edges

   592   Digraph::Node nd = n3;

   593   ::lemon::ignore_unused_variable_warning(nd);

   594   nd = n3;

   595   Adaptor::Node na = n1;

   596   ::lemon::ignore_unused_variable_warning(na);

   597   na = n2;

   598   Digraph::Arc ad = e3;

   599   ::lemon::ignore_unused_variable_warning(ad);

   600   ad = e3;

   601   Adaptor::Edge ea = a1;

   602   ::lemon::ignore_unused_variable_warning(ea);

   603   ea = a2;

   604 }

   606 void checkResidualDigraph() {

   607   // Check concepts

   608   checkConcept<concepts::Digraph, ResidualDigraph<concepts::Digraph> >();

   609   checkConcept<concepts::Digraph, ResidualDigraph<ListDigraph> >();

   611   // Create a digraph and an adaptor

   612   typedef ListDigraph Digraph;

   613   typedef Digraph::ArcMap<int> IntArcMap;

   614   typedef ResidualDigraph<Digraph, IntArcMap> Adaptor;

   616   Digraph digraph;

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

   618   Adaptor adaptor(digraph, capacity, flow);

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

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

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

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

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

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

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

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

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

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

   632   capacity[a1] = 8;

   633   capacity[a2] = 6;

   634   capacity[a3] = 4;

   635   capacity[a4] = 4;

   636   capacity[a5] = 6;

   637   capacity[a6] = 10;

   639   // Check the adaptor with various flow values

   640   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   641     flow[a] = 0;

   642   }

   644   checkGraphNodeList(adaptor, 4);

   645   checkGraphArcList(adaptor, 6);

   646   checkGraphConArcList(adaptor, 6);

   648   checkGraphOutArcList(adaptor, n1, 3);

   649   checkGraphOutArcList(adaptor, n2, 2);

   650   checkGraphOutArcList(adaptor, n3, 1);

   651   checkGraphOutArcList(adaptor, n4, 0);

   653   checkGraphInArcList(adaptor, n1, 0);

   654   checkGraphInArcList(adaptor, n2, 1);

   655   checkGraphInArcList(adaptor, n3, 2);

   656   checkGraphInArcList(adaptor, n4, 3);

   658   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

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

   660   }

   662   checkGraphNodeList(adaptor, 4);

   663   checkGraphArcList(adaptor, 12);

   664   checkGraphConArcList(adaptor, 12);

   666   checkGraphOutArcList(adaptor, n1, 3);

   667   checkGraphOutArcList(adaptor, n2, 3);

   668   checkGraphOutArcList(adaptor, n3, 3);

   669   checkGraphOutArcList(adaptor, n4, 3);

   671   checkGraphInArcList(adaptor, n1, 3);

   672   checkGraphInArcList(adaptor, n2, 3);

   673   checkGraphInArcList(adaptor, n3, 3);

   674   checkGraphInArcList(adaptor, n4, 3);

   676   checkNodeIds(adaptor);

   677   checkArcIds(adaptor);

   679   checkGraphNodeMap(adaptor);

   680   checkGraphArcMap(adaptor);

   682   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   683     flow[a] = capacity[a];

   684   }

   686   checkGraphNodeList(adaptor, 4);

   687   checkGraphArcList(adaptor, 6);

   688   checkGraphConArcList(adaptor, 6);

   690   checkGraphOutArcList(adaptor, n1, 0);

   691   checkGraphOutArcList(adaptor, n2, 1);

   692   checkGraphOutArcList(adaptor, n3, 2);

   693   checkGraphOutArcList(adaptor, n4, 3);

   695   checkGraphInArcList(adaptor, n1, 3);

   696   checkGraphInArcList(adaptor, n2, 2);

   697   checkGraphInArcList(adaptor, n3, 1);

   698   checkGraphInArcList(adaptor, n4, 0);

   700   // Saturate all backward arcs

   701   // (set the flow to zero on all forward arcs)

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

   703     if (adaptor.backward(a))

   704       adaptor.augment(a, adaptor.residualCapacity(a));

   705   }

   707   checkGraphNodeList(adaptor, 4);

   708   checkGraphArcList(adaptor, 6);

   709   checkGraphConArcList(adaptor, 6);

   711   checkGraphOutArcList(adaptor, n1, 3);

   712   checkGraphOutArcList(adaptor, n2, 2);

   713   checkGraphOutArcList(adaptor, n3, 1);

   714   checkGraphOutArcList(adaptor, n4, 0);

   716   checkGraphInArcList(adaptor, n1, 0);

   717   checkGraphInArcList(adaptor, n2, 1);

   718   checkGraphInArcList(adaptor, n3, 2);

   719   checkGraphInArcList(adaptor, n4, 3);

   721   // Find maximum flow by augmenting along shortest paths

   722   int flow_value = 0;

   723   Adaptor::ResidualCapacity res_cap(adaptor);

   724   while (true) {

   726     Bfs<Adaptor> bfs(adaptor);

   727     bfs.run(n1, n4);

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

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

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

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

   735       if (res_cap[a] < min) min = res_cap[a];

   736     }

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

   739       adaptor.augment(a, min);

   740     }

   741     flow_value += min;

   742   }

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

   746   // Check forward() and backward()

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

   748     check(adaptor.forward(a) != adaptor.backward(a),

   749           "Wrong forward() or backward()");

   750     check((adaptor.forward(a) && adaptor.forward(Digraph::Arc(a)) == a) ||

   751           (adaptor.backward(a) && adaptor.backward(Digraph::Arc(a)) == a),

   752           "Wrong forward() or backward()");

   753   }

   755   // Check the conversion of nodes and arcs

   756   Digraph::Node nd = Adaptor::NodeIt(adaptor);

   757   ::lemon::ignore_unused_variable_warning(nd);

   758   nd = ++Adaptor::NodeIt(adaptor);

   759   Adaptor::Node na = n1;

   760   ::lemon::ignore_unused_variable_warning(na);

   761   na = n2;

   762   Digraph::Arc ad = Adaptor::ArcIt(adaptor);

   763   ::lemon::ignore_unused_variable_warning(ad);

   764   ad = ++Adaptor::ArcIt(adaptor);

   765 }

   767 void checkSplitNodes() {

   768   // Check concepts

   769   checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();

   770   checkConcept<concepts::Digraph, SplitNodes<ListDigraph> >();

   772   // Create a digraph and an adaptor

   773   typedef ListDigraph Digraph;

   774   typedef SplitNodes<Digraph> Adaptor;

   776   Digraph digraph;

   777   Adaptor adaptor(digraph);

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

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

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

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

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

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

   786   ::lemon::ignore_unused_variable_warning(a1,a2,a3);

   788   checkGraphNodeList(adaptor, 6);

   789   checkGraphArcList(adaptor, 6);

   790   checkGraphConArcList(adaptor, 6);

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

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

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

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

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

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

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

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

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

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

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

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

   806   checkNodeIds(adaptor);

   807   checkArcIds(adaptor);

   809   checkGraphNodeMap(adaptor);

   810   checkGraphArcMap(adaptor);

   812   // Check split

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

   814     if (adaptor.origArc(a)) {

   815       Digraph::Arc oa = a;

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

   817             "Wrong split");

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

   819             "Wrong split");

   820     } else {

   821       Digraph::Node on = a;

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

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

   824     }

   825   }

   827   // Check combined node map

   828   typedef Adaptor::CombinedNodeMap

   829     <Digraph::NodeMap<int>, Digraph::NodeMap<int> > IntCombinedNodeMap;

   830   typedef Adaptor::CombinedNodeMap

   831     <Digraph::NodeMap<bool>, Digraph::NodeMap<bool> > BoolCombinedNodeMap;

   832   checkConcept<concepts::ReferenceMap<Adaptor::Node, int, int&, const int&>,

   833     IntCombinedNodeMap>();

   834 //checkConcept<concepts::ReferenceMap<Adaptor::Node, bool, bool&, const bool&>,

   835 //  BoolCombinedNodeMap>();

   836   checkConcept<concepts::ReadWriteMap<Adaptor::Node, bool>,

   837     BoolCombinedNodeMap>();

   839   Digraph::NodeMap<int> in_map(digraph), out_map(digraph);

   840   for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {

   841     in_map[n] = digraph.id(n);

   842     out_map[n] = -digraph.id(n);

   843   }

   845   Adaptor::CombinedNodeMap<Digraph::NodeMap<int>, Digraph::NodeMap<int> >

   846     node_map(in_map, out_map);

   847   for (Adaptor::NodeIt n(adaptor); n != INVALID; ++n) {

   848     if (adaptor.inNode(n)) {

   849       check(node_map[n] == in_map[n], "Wrong combined node map");

   850     } else {

   851       check(node_map[n] == out_map[n], "Wrong combined node map");

   852     }

   853   }

   855   // Check combined arc map

   856   typedef Adaptor::CombinedArcMap

   857     <Digraph::ArcMap<int>, Digraph::NodeMap<int> > IntCombinedArcMap;

   858   typedef Adaptor::CombinedArcMap

   859     <Digraph::ArcMap<bool>, Digraph::NodeMap<bool> > BoolCombinedArcMap;

   860   checkConcept<concepts::ReferenceMap<Adaptor::Arc, int, int&, const int&>,

   861     IntCombinedArcMap>();

   862 //checkConcept<concepts::ReferenceMap<Adaptor::Arc, bool, bool&, const bool&>,

   863 //  BoolCombinedArcMap>();

   864   checkConcept<concepts::ReadWriteMap<Adaptor::Arc, bool>,

   865     BoolCombinedArcMap>();

   867   Digraph::ArcMap<int> a_map(digraph);

   868   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   869     a_map[a] = digraph.id(a);

   870   }

   872   Adaptor::CombinedArcMap<Digraph::ArcMap<int>, Digraph::NodeMap<int> >

   873     arc_map(a_map, out_map);

   874   for (Digraph::ArcIt a(digraph); a != INVALID; ++a) {

   875     check(arc_map[adaptor.arc(a)] == a_map[a],  "Wrong combined arc map");

   876   }

   877   for (Digraph::NodeIt n(digraph); n != INVALID; ++n) {

   878     check(arc_map[adaptor.arc(n)] == out_map[n],  "Wrong combined arc map");

   879   }

   881   // Check the conversion of nodes

   882   Digraph::Node nd = adaptor.inNode(n1);

   883   check (nd == n1, "Wrong node conversion");

   884   nd = adaptor.outNode(n2);

   885   check (nd == n2, "Wrong node conversion");

   886 }

   888 void checkSubGraph() {

   889   // Check concepts

   890   checkConcept<concepts::Graph, SubGraph<concepts::Graph> >();

   891   checkConcept<concepts::Graph, SubGraph<ListGraph> >();

   892   checkConcept<concepts::AlterableGraphComponent<>,

   893                SubGraph<ListGraph> >();

   894   checkConcept<concepts::ExtendableGraphComponent<>,

   895                SubGraph<ListGraph> >();

   896   checkConcept<concepts::ErasableGraphComponent<>,

   897                SubGraph<ListGraph> >();

   898   checkConcept<concepts::ClearableGraphComponent<>,

   899                SubGraph<ListGraph> >();

   901   // Create a graph and an adaptor

   902   typedef ListGraph Graph;

   903   typedef Graph::NodeMap<bool> NodeFilter;

   904   typedef Graph::EdgeMap<bool> EdgeFilter;

   905   typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;

   907   Graph graph;

   908   NodeFilter node_filter(graph);

   909   EdgeFilter edge_filter(graph);

   910   Adaptor adaptor(graph, node_filter, edge_filter);

   912   // Add nodes and edges to the original graph and the adaptor

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

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

   915   Adaptor::Node n3 = adaptor.addNode();

   916   Adaptor::Node n4 = adaptor.addNode();

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

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

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

   922   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

   923   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);

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

   927   checkGraphNodeList(adaptor, 4);

   928   checkGraphArcList(adaptor, 8);

   929   checkGraphEdgeList(adaptor, 4);

   930   checkGraphConArcList(adaptor, 8);

   931   checkGraphConEdgeList(adaptor, 4);

   933   checkGraphIncEdgeArcLists(adaptor, n1, 2);

   934   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   935   checkGraphIncEdgeArcLists(adaptor, n3, 3);

   936   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   938   checkNodeIds(adaptor);

   939   checkArcIds(adaptor);

   940   checkEdgeIds(adaptor);

   942   checkGraphNodeMap(adaptor);

   943   checkGraphArcMap(adaptor);

   944   checkGraphEdgeMap(adaptor);

   946   // Hide an edge

   947   adaptor.status(e2, false);

   948   adaptor.disable(e3);

   949   if (!adaptor.status(e3)) adaptor.enable(e3);

   951   checkGraphNodeList(adaptor, 4);

   952   checkGraphArcList(adaptor, 6);

   953   checkGraphEdgeList(adaptor, 3);

   954   checkGraphConArcList(adaptor, 6);

   955   checkGraphConEdgeList(adaptor, 3);

   957   checkGraphIncEdgeArcLists(adaptor, n1, 1);

   958   checkGraphIncEdgeArcLists(adaptor, n2, 2);

   959   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   960   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   962   checkNodeIds(adaptor);

   963   checkArcIds(adaptor);

   964   checkEdgeIds(adaptor);

   966   checkGraphNodeMap(adaptor);

   967   checkGraphArcMap(adaptor);

   968   checkGraphEdgeMap(adaptor);

   970   // Hide a node

   971   adaptor.status(n1, false);

   972   adaptor.disable(n3);

   973   if (!adaptor.status(n3)) adaptor.enable(n3);

   975   checkGraphNodeList(adaptor, 3);

   976   checkGraphArcList(adaptor, 4);

   977   checkGraphEdgeList(adaptor, 2);

   978   checkGraphConArcList(adaptor, 4);

   979   checkGraphConEdgeList(adaptor, 2);

   981   checkGraphIncEdgeArcLists(adaptor, n2, 1);

   982   checkGraphIncEdgeArcLists(adaptor, n3, 2);

   983   checkGraphIncEdgeArcLists(adaptor, n4, 1);

   985   checkNodeIds(adaptor);

   986   checkArcIds(adaptor);

   987   checkEdgeIds(adaptor);

   989   checkGraphNodeMap(adaptor);

   990   checkGraphArcMap(adaptor);

   991   checkGraphEdgeMap(adaptor);

   993   // Hide all nodes and edges

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

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

   997   checkGraphNodeList(adaptor, 0);

   998   checkGraphArcList(adaptor, 0);

   999   checkGraphEdgeList(adaptor, 0);

  1000   checkGraphConArcList(adaptor, 0);

  1001   checkGraphConEdgeList(adaptor, 0);

  1003   checkNodeIds(adaptor);

  1004   checkArcIds(adaptor);

  1005   checkEdgeIds(adaptor);

  1007   checkGraphNodeMap(adaptor);

  1008   checkGraphArcMap(adaptor);

  1009   checkGraphEdgeMap(adaptor);

  1011   // Check the conversion of nodes and edges

  1012   Graph::Node ng = n3;

  1013   ::lemon::ignore_unused_variable_warning(ng);

  1014   ng = n4;

  1015   Adaptor::Node na = n1;

  1016   ::lemon::ignore_unused_variable_warning(na);

  1017   na = n2;

  1018   Graph::Edge eg = e3;

  1019   ::lemon::ignore_unused_variable_warning(eg);

  1020   eg = e4;

  1021   Adaptor::Edge ea = e1;

  1022   ::lemon::ignore_unused_variable_warning(ea);

  1023   ea = e2;

  1024 }

  1026 void checkFilterNodes2() {

  1027   // Check concepts

  1028   checkConcept<concepts::Graph, FilterNodes<concepts::Graph> >();

  1029   checkConcept<concepts::Graph, FilterNodes<ListGraph> >();

  1030   checkConcept<concepts::AlterableGraphComponent<>,

  1031                FilterNodes<ListGraph> >();

  1032   checkConcept<concepts::ExtendableGraphComponent<>,

  1033                FilterNodes<ListGraph> >();

  1034   checkConcept<concepts::ErasableGraphComponent<>,

  1035                FilterNodes<ListGraph> >();

  1036   checkConcept<concepts::ClearableGraphComponent<>,

  1037                FilterNodes<ListGraph> >();

  1039   // Create a graph and an adaptor

  1040   typedef ListGraph Graph;

  1041   typedef Graph::NodeMap<bool> NodeFilter;

  1042   typedef FilterNodes<Graph, NodeFilter> Adaptor;

  1044   // Add nodes and edges to the original graph and the adaptor

  1045   Graph graph;

  1046   NodeFilter node_filter(graph);

  1047   Adaptor adaptor(graph, node_filter);

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

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

  1051   Adaptor::Node n3 = adaptor.addNode();

  1052   Adaptor::Node n4 = adaptor.addNode();

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

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

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

  1058   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

  1059   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);

  1061   checkGraphNodeList(adaptor, 4);

  1062   checkGraphArcList(adaptor, 8);

  1063   checkGraphEdgeList(adaptor, 4);

  1064   checkGraphConArcList(adaptor, 8);

  1065   checkGraphConEdgeList(adaptor, 4);

  1067   checkGraphIncEdgeArcLists(adaptor, n1, 2);

  1068   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1069   checkGraphIncEdgeArcLists(adaptor, n3, 3);

  1070   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1072   checkNodeIds(adaptor);

  1073   checkArcIds(adaptor);

  1074   checkEdgeIds(adaptor);

  1076   checkGraphNodeMap(adaptor);

  1077   checkGraphArcMap(adaptor);

  1078   checkGraphEdgeMap(adaptor);

  1080   // Hide a node

  1081   adaptor.status(n1, false);

  1082   adaptor.disable(n3);

  1083   if (!adaptor.status(n3)) adaptor.enable(n3);

  1085   checkGraphNodeList(adaptor, 3);

  1086   checkGraphArcList(adaptor, 4);

  1087   checkGraphEdgeList(adaptor, 2);

  1088   checkGraphConArcList(adaptor, 4);

  1089   checkGraphConEdgeList(adaptor, 2);

  1091   checkGraphIncEdgeArcLists(adaptor, n2, 1);

  1092   checkGraphIncEdgeArcLists(adaptor, n3, 2);

  1093   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1095   checkNodeIds(adaptor);

  1096   checkArcIds(adaptor);

  1097   checkEdgeIds(adaptor);

  1099   checkGraphNodeMap(adaptor);

  1100   checkGraphArcMap(adaptor);

  1101   checkGraphEdgeMap(adaptor);

  1103   // Hide all nodes

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

  1106   checkGraphNodeList(adaptor, 0);

  1107   checkGraphArcList(adaptor, 0);

  1108   checkGraphEdgeList(adaptor, 0);

  1109   checkGraphConArcList(adaptor, 0);

  1110   checkGraphConEdgeList(adaptor, 0);

  1112   checkNodeIds(adaptor);

  1113   checkArcIds(adaptor);

  1114   checkEdgeIds(adaptor);

  1116   checkGraphNodeMap(adaptor);

  1117   checkGraphArcMap(adaptor);

  1118   checkGraphEdgeMap(adaptor);

  1120   // Check the conversion of nodes and edges

  1121   Graph::Node ng = n3;

  1122   ::lemon::ignore_unused_variable_warning(ng);

  1123   ng = n4;

  1124   Adaptor::Node na = n1;

  1125   ::lemon::ignore_unused_variable_warning(na);

  1126   na = n2;

  1127   Graph::Edge eg = e3;

  1128   ::lemon::ignore_unused_variable_warning(eg);

  1129   eg = e4;

  1130   Adaptor::Edge ea = e1;

  1131   ::lemon::ignore_unused_variable_warning(ea);

  1132   ea = e2;

  1133 }

  1135 void checkFilterEdges() {

  1136   // Check concepts

  1137   checkConcept<concepts::Graph, FilterEdges<concepts::Graph> >();

  1138   checkConcept<concepts::Graph, FilterEdges<ListGraph> >();

  1139   checkConcept<concepts::AlterableGraphComponent<>,

  1140                FilterEdges<ListGraph> >();

  1141   checkConcept<concepts::ExtendableGraphComponent<>,

  1142                FilterEdges<ListGraph> >();

  1143   checkConcept<concepts::ErasableGraphComponent<>,

  1144                FilterEdges<ListGraph> >();

  1145   checkConcept<concepts::ClearableGraphComponent<>,

  1146                FilterEdges<ListGraph> >();

  1148   // Create a graph and an adaptor

  1149   typedef ListGraph Graph;

  1150   typedef Graph::EdgeMap<bool> EdgeFilter;

  1151   typedef FilterEdges<Graph, EdgeFilter> Adaptor;

  1153   Graph graph;

  1154   EdgeFilter edge_filter(graph);

  1155   Adaptor adaptor(graph, edge_filter);

  1157   // Add nodes and edges to the original graph and the adaptor

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

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

  1160   Adaptor::Node n3 = adaptor.addNode();

  1161   Adaptor::Node n4 = adaptor.addNode();

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

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

  1165   Adaptor::Edge e3 = adaptor.addEdge(n2, n3);

  1166   Adaptor::Edge e4 = adaptor.addEdge(n3, n4);

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

  1170   checkGraphNodeList(adaptor, 4);

  1171   checkGraphArcList(adaptor, 8);

  1172   checkGraphEdgeList(adaptor, 4);

  1173   checkGraphConArcList(adaptor, 8);

  1174   checkGraphConEdgeList(adaptor, 4);

  1176   checkGraphIncEdgeArcLists(adaptor, n1, 2);

  1177   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1178   checkGraphIncEdgeArcLists(adaptor, n3, 3);

  1179   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1181   checkNodeIds(adaptor);

  1182   checkArcIds(adaptor);

  1183   checkEdgeIds(adaptor);

  1185   checkGraphNodeMap(adaptor);

  1186   checkGraphArcMap(adaptor);

  1187   checkGraphEdgeMap(adaptor);

  1189   // Hide an edge

  1190   adaptor.status(e2, false);

  1191   adaptor.disable(e3);

  1192   if (!adaptor.status(e3)) adaptor.enable(e3);

  1194   checkGraphNodeList(adaptor, 4);

  1195   checkGraphArcList(adaptor, 6);

  1196   checkGraphEdgeList(adaptor, 3);

  1197   checkGraphConArcList(adaptor, 6);

  1198   checkGraphConEdgeList(adaptor, 3);

  1200   checkGraphIncEdgeArcLists(adaptor, n1, 1);

  1201   checkGraphIncEdgeArcLists(adaptor, n2, 2);

  1202   checkGraphIncEdgeArcLists(adaptor, n3, 2);

  1203   checkGraphIncEdgeArcLists(adaptor, n4, 1);

  1205   checkNodeIds(adaptor);

  1206   checkArcIds(adaptor);

  1207   checkEdgeIds(adaptor);

  1209   checkGraphNodeMap(adaptor);

  1210   checkGraphArcMap(adaptor);

  1211   checkGraphEdgeMap(adaptor);

  1213   // Hide all edges

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

  1216   checkGraphNodeList(adaptor, 4);

  1217   checkGraphArcList(adaptor, 0);

  1218   checkGraphEdgeList(adaptor, 0);

  1219   checkGraphConArcList(adaptor, 0);

  1220   checkGraphConEdgeList(adaptor, 0);

  1222   checkNodeIds(adaptor);

  1223   checkArcIds(adaptor);

  1224   checkEdgeIds(adaptor);

  1226   checkGraphNodeMap(adaptor);

  1227   checkGraphArcMap(adaptor);

  1228   checkGraphEdgeMap(adaptor);

  1230   // Check the conversion of nodes and edges

  1231   Graph::Node ng = n3;

  1232   ::lemon::ignore_unused_variable_warning(ng);

  1233   ng = n4;

  1234   Adaptor::Node na = n1;

  1235   ::lemon::ignore_unused_variable_warning(na);

  1236   na = n2;

  1237   Graph::Edge eg = e3;

  1238   ::lemon::ignore_unused_variable_warning(eg);

  1239   eg = e4;

  1240   Adaptor::Edge ea = e1;

  1241   ::lemon::ignore_unused_variable_warning(ea);

  1242   ea = e2;

  1243 }

  1245 void checkOrienter() {

  1246   // Check concepts

  1247   checkConcept<concepts::Digraph, Orienter<concepts::Graph> >();

  1248   checkConcept<concepts::Digraph, Orienter<ListGraph> >();

  1249   checkConcept<concepts::AlterableDigraphComponent<>,

  1250                Orienter<ListGraph> >();

  1251   checkConcept<concepts::ExtendableDigraphComponent<>,

  1252                Orienter<ListGraph> >();

  1253   checkConcept<concepts::ErasableDigraphComponent<>,

  1254                Orienter<ListGraph> >();

  1255   checkConcept<concepts::ClearableDigraphComponent<>,

  1256                Orienter<ListGraph> >();

  1258   // Create a graph and an adaptor

  1259   typedef ListGraph Graph;

  1260   typedef ListGraph::EdgeMap<bool> DirMap;

  1261   typedef Orienter<Graph> Adaptor;

  1263   Graph graph;

  1264   DirMap dir(graph);

  1265   Adaptor adaptor(graph, dir);

  1267   // Add nodes and edges to the original graph and the adaptor

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

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

  1270   Adaptor::Node n3 = adaptor.addNode();

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

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

  1274   Adaptor::Arc e3 = adaptor.addArc(n2, n3);

  1276   dir[e1] = dir[e2] = dir[e3] = true;

  1278   // Check the original graph

  1279   checkGraphNodeList(graph, 3);

  1280   checkGraphArcList(graph, 6);

  1281   checkGraphConArcList(graph, 6);

  1282   checkGraphEdgeList(graph, 3);

  1283   checkGraphConEdgeList(graph, 3);

  1285   checkGraphIncEdgeArcLists(graph, n1, 2);

  1286   checkGraphIncEdgeArcLists(graph, n2, 2);

  1287   checkGraphIncEdgeArcLists(graph, n3, 2);

  1289   checkNodeIds(graph);

  1290   checkArcIds(graph);

  1291   checkEdgeIds(graph);

  1293   checkGraphNodeMap(graph);

  1294   checkGraphArcMap(graph);

  1295   checkGraphEdgeMap(graph);

  1297   // Check the adaptor

  1298   checkGraphNodeList(adaptor, 3);

  1299   checkGraphArcList(adaptor, 3);

  1300   checkGraphConArcList(adaptor, 3);

  1302   checkGraphOutArcList(adaptor, n1, 2);

  1303   checkGraphOutArcList(adaptor, n2, 1);

  1304   checkGraphOutArcList(adaptor, n3, 0);

  1306   checkGraphInArcList(adaptor, n1, 0);

  1307   checkGraphInArcList(adaptor, n2, 1);

  1308   checkGraphInArcList(adaptor, n3, 2);

  1310   checkNodeIds(adaptor);

  1311   checkArcIds(adaptor);

  1313   checkGraphNodeMap(adaptor);

  1314   checkGraphArcMap(adaptor);

  1316   // Check direction changing

  1317   {

  1318     dir[e1] = true;

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

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

  1322     dir[e1] = false;

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

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

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

  1327     dir[e1] = n1 == u;

  1328   }

  1330   {

  1331     dir[e2] = true;

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

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

  1335     dir[e2] = false;

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

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

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

  1340     dir[e2] = n3 == u;

  1341   }

  1343   {

  1344     dir[e3] = true;

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

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

  1348     dir[e3] = false;

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

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

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

  1353     dir[e3] = n2 == u;

  1354   }

  1356   // Check the adaptor again

  1357   checkGraphNodeList(adaptor, 3);

  1358   checkGraphArcList(adaptor, 3);

  1359   checkGraphConArcList(adaptor, 3);

  1361   checkGraphOutArcList(adaptor, n1, 1);

  1362   checkGraphOutArcList(adaptor, n2, 1);

  1363   checkGraphOutArcList(adaptor, n3, 1);

  1365   checkGraphInArcList(adaptor, n1, 1);

  1366   checkGraphInArcList(adaptor, n2, 1);

  1367   checkGraphInArcList(adaptor, n3, 1);

  1369   checkNodeIds(adaptor);

  1370   checkArcIds(adaptor);

  1372   checkGraphNodeMap(adaptor);

  1373   checkGraphArcMap(adaptor);

  1375   // Check reverseArc()

  1376   adaptor.reverseArc(e2);

  1377   adaptor.reverseArc(e3);

  1378   adaptor.reverseArc(e2);

  1380   checkGraphNodeList(adaptor, 3);

  1381   checkGraphArcList(adaptor, 3);

  1382   checkGraphConArcList(adaptor, 3);

  1384   checkGraphOutArcList(adaptor, n1, 1);

  1385   checkGraphOutArcList(adaptor, n2, 0);

  1386   checkGraphOutArcList(adaptor, n3, 2);

  1388   checkGraphInArcList(adaptor, n1, 1);

  1389   checkGraphInArcList(adaptor, n2, 2);

  1390   checkGraphInArcList(adaptor, n3, 0);

  1392   // Check the conversion of nodes and arcs/edges

  1393   Graph::Node ng = n3;

  1394   ::lemon::ignore_unused_variable_warning(ng);

  1395   ng = n3;

  1396   Adaptor::Node na = n1;

  1397   ::lemon::ignore_unused_variable_warning(na);

  1398   na = n2;

  1399   Graph::Edge eg = e3;

  1400   ::lemon::ignore_unused_variable_warning(eg);

  1401   eg = e3;

  1402   Adaptor::Arc aa = e1;

  1403   ::lemon::ignore_unused_variable_warning(aa);

  1404   aa = e2;

  1405 }

  1407 void checkCombiningAdaptors() {

  1408   // Create a grid graph

  1409   GridGraph graph(2,2);

  1410   GridGraph::Node n1 = graph(0,0);

  1411   GridGraph::Node n2 = graph(0,1);

  1412   GridGraph::Node n3 = graph(1,0);

  1413   GridGraph::Node n4 = graph(1,1);

  1415   GridGraph::EdgeMap<bool> dir_map(graph);

  1416   dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;

  1417   dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;

  1418   dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;

  1419   dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;

  1421   // Apply several adaptors on the grid graph

  1422   typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> >

  1423     OrientedGridGraph;

  1424   typedef SplitNodes<OrientedGridGraph> SplitGridGraph;

  1425   typedef Undirector<const SplitGridGraph> USplitGridGraph;

  1426   checkConcept<concepts::Digraph, SplitGridGraph>();

  1427   checkConcept<concepts::Graph, USplitGridGraph>();

  1429   OrientedGridGraph oadaptor = orienter(graph, dir_map);

  1430   SplitGridGraph adaptor = splitNodes(oadaptor);

  1431   USplitGridGraph uadaptor = undirector(adaptor);

  1433   // Check adaptor

  1434   checkGraphNodeList(adaptor, 8);

  1435   checkGraphArcList(adaptor, 8);

  1436   checkGraphConArcList(adaptor, 8);

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

  1439   checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);

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

  1441   checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);

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

  1443   checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);

  1444   checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);

  1445   checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);

  1447   checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);

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

  1449   checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);

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

  1451   checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);

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

  1453   checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);

  1454   checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);

  1456   checkNodeIds(adaptor);

  1457   checkArcIds(adaptor);

  1459   checkGraphNodeMap(adaptor);

  1460   checkGraphArcMap(adaptor);

  1462   // Check uadaptor

  1463   checkGraphNodeList(uadaptor, 8);

  1464   checkGraphEdgeList(uadaptor, 8);

  1465   checkGraphArcList(uadaptor, 16);

  1466   checkGraphConEdgeList(uadaptor, 8);

  1467   checkGraphConArcList(uadaptor, 16);

  1469   checkNodeIds(uadaptor);

  1470   checkEdgeIds(uadaptor);

  1471   checkArcIds(uadaptor);

  1473   checkGraphNodeMap(uadaptor);

  1474   checkGraphEdgeMap(uadaptor);

  1475   checkGraphArcMap(uadaptor);

  1477   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);

  1478   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);

  1479   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);

  1480   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);

  1481   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);

  1482   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);

  1483   checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);

  1484   checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);

  1485 }

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

  1488   // Check the digraph adaptors (using ListDigraph)

  1489   checkReverseDigraph();

  1490   checkSubDigraph();

  1491   checkFilterNodes1();

  1492   checkFilterArcs();

  1493   checkUndirector();

  1494   checkResidualDigraph();

  1495   checkSplitNodes();

  1497   // Check the graph adaptors (using ListGraph)

  1498   checkSubGraph();

  1499   checkFilterNodes2();

  1500   checkFilterEdges();

  1501   checkOrienter();

  1503   // Combine adaptors (using GridGraph)

  1504   checkCombiningAdaptors();

  1506   return 0;

  1507 }

author	Balazs Dezso <deba@google.com>
	Fri, 22 Jan 2021 10:55:32 +0100
changeset 1208	c6aa2cc1af04
parent 1092	dceba191c00d
permissions	-rw-r--r--