lemon: test/graph_adaptor_test.cc@5a1e9fdcfd3a

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

     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/adaptors.h>

    30 #include <limits>

    31 #include <lemon/bfs.h>

    32 #include <lemon/path.h>

    34 #include"test/test_tools.h"

    35 #include"test/graph_test.h"

    37 using namespace lemon;

    39 void checkReverseDigraph() {

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

    42   typedef ListDigraph Digraph;

    43   typedef ReverseDigraph<Digraph> Adaptor;

    45   Digraph digraph;

    46   Adaptor adaptor(digraph);

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

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

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

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

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

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

    56   checkGraphNodeList(adaptor, 3);

    57   checkGraphArcList(adaptor, 3);

    58   checkGraphConArcList(adaptor, 3);

    60   checkGraphOutArcList(adaptor, n1, 0);

    61   checkGraphOutArcList(adaptor, n2, 1);

    62   checkGraphOutArcList(adaptor, n3, 2);

    64   checkGraphInArcList(adaptor, n1, 2);

    65   checkGraphInArcList(adaptor, n2, 1);

    66   checkGraphInArcList(adaptor, n3, 0);

    68   checkNodeIds(adaptor);

    69   checkArcIds(adaptor);

    71   checkGraphNodeMap(adaptor);

    72   checkGraphArcMap(adaptor);

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

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

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

    77   }

    78 }

    80 void checkSubDigraph() {

    81   checkConcept<concepts::Digraph,

    82     SubDigraph<concepts::Digraph,

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

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

    86   typedef ListDigraph Digraph;

    87   typedef Digraph::NodeMap<bool> NodeFilter;

    88   typedef Digraph::ArcMap<bool> ArcFilter;

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

    91   Digraph digraph;

    92   NodeFilter node_filter(digraph);

    93   ArcFilter arc_filter(digraph);

    94   Adaptor adaptor(digraph, node_filter, arc_filter);

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

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

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

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

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

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

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

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

   107   checkGraphNodeList(adaptor, 3);

   108   checkGraphArcList(adaptor, 3);

   109   checkGraphConArcList(adaptor, 3);

   111   checkGraphOutArcList(adaptor, n1, 2);

   112   checkGraphOutArcList(adaptor, n2, 1);

   113   checkGraphOutArcList(adaptor, n3, 0);

   115   checkGraphInArcList(adaptor, n1, 0);

   116   checkGraphInArcList(adaptor, n2, 1);

   117   checkGraphInArcList(adaptor, n3, 2);

   119   checkNodeIds(adaptor);

   120   checkArcIds(adaptor);

   122   checkGraphNodeMap(adaptor);

   123   checkGraphArcMap(adaptor);

   125   arc_filter[a2] = false;

   127   checkGraphNodeList(adaptor, 3);

   128   checkGraphArcList(adaptor, 2);

   129   checkGraphConArcList(adaptor, 2);

   131   checkGraphOutArcList(adaptor, n1, 1);

   132   checkGraphOutArcList(adaptor, n2, 1);

   133   checkGraphOutArcList(adaptor, n3, 0);

   135   checkGraphInArcList(adaptor, n1, 0);

   136   checkGraphInArcList(adaptor, n2, 1);

   137   checkGraphInArcList(adaptor, n3, 1);

   139   checkNodeIds(adaptor);

   140   checkArcIds(adaptor);

   142   checkGraphNodeMap(adaptor);

   143   checkGraphArcMap(adaptor);

   145   node_filter[n1] = false;

   147   checkGraphNodeList(adaptor, 2);

   148   checkGraphArcList(adaptor, 1);

   149   checkGraphConArcList(adaptor, 1);

   151   checkGraphOutArcList(adaptor, n2, 1);

   152   checkGraphOutArcList(adaptor, n3, 0);

   154   checkGraphInArcList(adaptor, n2, 0);

   155   checkGraphInArcList(adaptor, n3, 1);

   157   checkNodeIds(adaptor);

   158   checkArcIds(adaptor);

   160   checkGraphNodeMap(adaptor);

   161   checkGraphArcMap(adaptor);

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

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

   166   checkGraphNodeList(adaptor, 0);

   167   checkGraphArcList(adaptor, 0);

   168   checkGraphConArcList(adaptor, 0);

   170   checkNodeIds(adaptor);

   171   checkArcIds(adaptor);

   173   checkGraphNodeMap(adaptor);

   174   checkGraphArcMap(adaptor);

   175 }

   177 void checkFilterNodes1() {

   178   checkConcept<concepts::Digraph,

   179     FilterNodes<concepts::Digraph,

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

   182   typedef ListDigraph Digraph;

   183   typedef Digraph::NodeMap<bool> NodeFilter;

   184   typedef FilterNodes<Digraph, NodeFilter> Adaptor;

   186   Digraph digraph;

   187   NodeFilter node_filter(digraph);

   188   Adaptor adaptor(digraph, node_filter);

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

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

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

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

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

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

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

   200   checkGraphNodeList(adaptor, 3);

   201   checkGraphArcList(adaptor, 3);

   202   checkGraphConArcList(adaptor, 3);

   204   checkGraphOutArcList(adaptor, n1, 2);

   205   checkGraphOutArcList(adaptor, n2, 1);

   206   checkGraphOutArcList(adaptor, n3, 0);

   208   checkGraphInArcList(adaptor, n1, 0);

   209   checkGraphInArcList(adaptor, n2, 1);

   210   checkGraphInArcList(adaptor, n3, 2);

   212   checkNodeIds(adaptor);

   213   checkArcIds(adaptor);

   215   checkGraphNodeMap(adaptor);

   216   checkGraphArcMap(adaptor);

   218   node_filter[n1] = false;

   220   checkGraphNodeList(adaptor, 2);

   221   checkGraphArcList(adaptor, 1);

   222   checkGraphConArcList(adaptor, 1);

   224   checkGraphOutArcList(adaptor, n2, 1);

   225   checkGraphOutArcList(adaptor, n3, 0);

   227   checkGraphInArcList(adaptor, n2, 0);

   228   checkGraphInArcList(adaptor, n3, 1);

   230   checkNodeIds(adaptor);

   231   checkArcIds(adaptor);

   233   checkGraphNodeMap(adaptor);

   234   checkGraphArcMap(adaptor);

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

   238   checkGraphNodeList(adaptor, 0);

   239   checkGraphArcList(adaptor, 0);

   240   checkGraphConArcList(adaptor, 0);

   242   checkNodeIds(adaptor);

   243   checkArcIds(adaptor);

   245   checkGraphNodeMap(adaptor);

   246   checkGraphArcMap(adaptor);

   247 }

   249 void checkFilterArcs() {

   250   checkConcept<concepts::Digraph,

   251     FilterArcs<concepts::Digraph,

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

   254   typedef ListDigraph Digraph;

   255   typedef Digraph::ArcMap<bool> ArcFilter;

   256   typedef FilterArcs<Digraph, ArcFilter> Adaptor;

   258   Digraph digraph;

   259   ArcFilter arc_filter(digraph);

   260   Adaptor adaptor(digraph, arc_filter);

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

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

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

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

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

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

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

   272   checkGraphNodeList(adaptor, 3);

   273   checkGraphArcList(adaptor, 3);

   274   checkGraphConArcList(adaptor, 3);

   276   checkGraphOutArcList(adaptor, n1, 2);

   277   checkGraphOutArcList(adaptor, n2, 1);

   278   checkGraphOutArcList(adaptor, n3, 0);

   280   checkGraphInArcList(adaptor, n1, 0);

   281   checkGraphInArcList(adaptor, n2, 1);

   282   checkGraphInArcList(adaptor, n3, 2);

   284   checkNodeIds(adaptor);

   285   checkArcIds(adaptor);

   287   checkGraphNodeMap(adaptor);

   288   checkGraphArcMap(adaptor);

   290   arc_filter[a2] = false;

   292   checkGraphNodeList(adaptor, 3);

   293   checkGraphArcList(adaptor, 2);

   294   checkGraphConArcList(adaptor, 2);

   296   checkGraphOutArcList(adaptor, n1, 1);

   297   checkGraphOutArcList(adaptor, n2, 1);

   298   checkGraphOutArcList(adaptor, n3, 0);

   300   checkGraphInArcList(adaptor, n1, 0);

   301   checkGraphInArcList(adaptor, n2, 1);

   302   checkGraphInArcList(adaptor, n3, 1);

   304   checkNodeIds(adaptor);

   305   checkArcIds(adaptor);

   307   checkGraphNodeMap(adaptor);

   308   checkGraphArcMap(adaptor);

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

   312   checkGraphNodeList(adaptor, 3);

   313   checkGraphArcList(adaptor, 0);

   314   checkGraphConArcList(adaptor, 0);

   316   checkNodeIds(adaptor);

   317   checkArcIds(adaptor);

   319   checkGraphNodeMap(adaptor);

   320   checkGraphArcMap(adaptor);

   321 }

   323 void checkUndirector() {

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

   326   typedef ListDigraph Digraph;

   327   typedef Undirector<Digraph> Adaptor;

   329   Digraph digraph;

   330   Adaptor adaptor(digraph);

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

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

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

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

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

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

   340   checkGraphNodeList(adaptor, 3);

   341   checkGraphArcList(adaptor, 6);

   342   checkGraphEdgeList(adaptor, 3);

   343   checkGraphConArcList(adaptor, 6);

   344   checkGraphConEdgeList(adaptor, 3);

   346   checkGraphOutArcList(adaptor, n1, 2);

   347   checkGraphOutArcList(adaptor, n2, 2);

   348   checkGraphOutArcList(adaptor, n3, 2);

   350   checkGraphInArcList(adaptor, n1, 2);

   351   checkGraphInArcList(adaptor, n2, 2);

   352   checkGraphInArcList(adaptor, n3, 2);

   354   checkGraphIncEdgeList(adaptor, n1, 2);

   355   checkGraphIncEdgeList(adaptor, n2, 2);

   356   checkGraphIncEdgeList(adaptor, n3, 2);

   358   checkNodeIds(adaptor);

   359   checkArcIds(adaptor);

   360   checkEdgeIds(adaptor);

   362   checkGraphNodeMap(adaptor);

   363   checkGraphArcMap(adaptor);

   364   checkGraphEdgeMap(adaptor);

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

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

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

   369   }

   371 }

   373 void checkResidual() {

   374   checkConcept<concepts::Digraph,

   375     Residual<concepts::Digraph,

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

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

   379   typedef ListDigraph Digraph;

   380   typedef Digraph::ArcMap<int> IntArcMap;

   381   typedef Residual<Digraph, IntArcMap> Adaptor;

   383   Digraph digraph;

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

   385   Adaptor adaptor(digraph, capacity, flow);

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

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

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

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

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

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

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

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

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

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

   399   capacity[a1] = 8;

   400   capacity[a2] = 6;

   401   capacity[a3] = 4;

   402   capacity[a4] = 4;

   403   capacity[a5] = 6;

   404   capacity[a6] = 10;

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

   407     flow[a] = 0;

   408   }

   410   checkGraphNodeList(adaptor, 4);

   411   checkGraphArcList(adaptor, 6);

   412   checkGraphConArcList(adaptor, 6);

   414   checkGraphOutArcList(adaptor, n1, 3);

   415   checkGraphOutArcList(adaptor, n2, 2);

   416   checkGraphOutArcList(adaptor, n3, 1);

   417   checkGraphOutArcList(adaptor, n4, 0);

   419   checkGraphInArcList(adaptor, n1, 0);

   420   checkGraphInArcList(adaptor, n2, 1);

   421   checkGraphInArcList(adaptor, n3, 2);

   422   checkGraphInArcList(adaptor, n4, 3);

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

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

   426   }

   428   checkGraphNodeList(adaptor, 4);

   429   checkGraphArcList(adaptor, 12);

   430   checkGraphConArcList(adaptor, 12);

   432   checkGraphOutArcList(adaptor, n1, 3);

   433   checkGraphOutArcList(adaptor, n2, 3);

   434   checkGraphOutArcList(adaptor, n3, 3);

   435   checkGraphOutArcList(adaptor, n4, 3);

   437   checkGraphInArcList(adaptor, n1, 3);

   438   checkGraphInArcList(adaptor, n2, 3);

   439   checkGraphInArcList(adaptor, n3, 3);

   440   checkGraphInArcList(adaptor, n4, 3);

   442   checkNodeIds(adaptor);

   443   checkArcIds(adaptor);

   445   checkGraphNodeMap(adaptor);

   446   checkGraphArcMap(adaptor);

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

   449     flow[a] = capacity[a];

   450   }

   452   checkGraphNodeList(adaptor, 4);

   453   checkGraphArcList(adaptor, 6);

   454   checkGraphConArcList(adaptor, 6);

   456   checkGraphOutArcList(adaptor, n1, 0);

   457   checkGraphOutArcList(adaptor, n2, 1);

   458   checkGraphOutArcList(adaptor, n3, 2);

   459   checkGraphOutArcList(adaptor, n4, 3);

   461   checkGraphInArcList(adaptor, n1, 3);

   462   checkGraphInArcList(adaptor, n2, 2);

   463   checkGraphInArcList(adaptor, n3, 1);

   464   checkGraphInArcList(adaptor, n4, 0);

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

   467     flow[a] = 0;

   468   }

   470   int flow_value = 0;

   471   while (true) {

   473     Bfs<Adaptor> bfs(adaptor);

   474     bfs.run(n1, n4);

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

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

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

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

   482       if (adaptor.residualCapacity(a) < min)

   483         min = adaptor.residualCapacity(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 checkSplitNodes() {

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

   499   typedef ListDigraph Digraph;

   500   typedef SplitNodes<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 checkSubGraph() {

   553   checkConcept<concepts::Graph,

   554     SubGraph<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 SubGraph<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 checkFilterNodes2() {

   688   checkConcept<concepts::Graph,

   689     FilterNodes<concepts::Graph,

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

   692   typedef ListGraph Graph;

   693   typedef Graph::NodeMap<bool> NodeFilter;

   694   typedef FilterNodes<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 checkFilterEdges() {

   787   checkConcept<concepts::Graph,

   788     FilterEdges<concepts::Graph,

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

   791   typedef ListGraph Graph;

   792   typedef Graph::EdgeMap<bool> EdgeFilter;

   793   typedef FilterEdges<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 checkOrienter() {

   889   checkConcept<concepts::Digraph,

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

   892   typedef ListGraph Graph;

   893   typedef ListGraph::EdgeMap<bool> DirMap;

   894   typedef Orienter<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   checkReverseDigraph();

   971   checkSubDigraph();

   972   checkFilterNodes1();

   973   checkFilterArcs();

   974   checkUndirector();

   975   checkResidual();

   976   checkSplitNodes();

   978   checkSubGraph();

   979   checkFilterNodes2();

   980   checkFilterEdges();

   981   checkOrienter();

   983   return 0;

   984 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Sun, 11 Jan 2009 15:09:53 +0000
changeset 478	5a1e9fdcfd3a
parent 432	76287c8caa26
child 486	a2fd8b8d0b30
permissions	-rw-r--r--