test/graph_test.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 08 Mar 2013 01:13:54 +0100
changeset 1046 387483bf0a56
parent 1026 699c7eac2c6d
child 1092 dceba191c00d
permissions -rw-r--r--
Adjust image sizes in the documentation (#411)
     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  */
    18 
    19 #ifndef LEMON_TEST_GRAPH_TEST_H
    20 #define LEMON_TEST_GRAPH_TEST_H
    21 
    22 #include <set>
    23 
    24 #include <lemon/core.h>
    25 #include <lemon/maps.h>
    26 
    27 #include "test_tools.h"
    28 
    29 namespace lemon {
    30 
    31   template<class Graph>
    32   void checkGraphNodeList(const Graph &G, int cnt)
    33   {
    34     typename Graph::NodeIt n(G);
    35     for(int i=0;i<cnt;i++) {
    36       check(n!=INVALID,"Wrong Node list linking.");
    37       ++n;
    38     }
    39     check(n==INVALID,"Wrong Node list linking.");
    40     check(countNodes(G)==cnt,"Wrong Node number.");
    41   }
    42 
    43   template<class Graph>
    44   void checkGraphRedNodeList(const Graph &G, int cnt)
    45   {
    46     typename Graph::RedNodeIt n(G);
    47     for(int i=0;i<cnt;i++) {
    48       check(n!=INVALID,"Wrong red Node list linking.");
    49       check(G.red(n),"Wrong node set check.");
    50       check(!G.blue(n),"Wrong node set check.");
    51       typename Graph::Node nn = n;
    52       check(G.asRedNodeUnsafe(nn) == n,"Wrong node conversion.");
    53       check(G.asRedNode(nn) == n,"Wrong node conversion.");
    54       check(G.asBlueNode(nn) == INVALID,"Wrong node conversion.");
    55       ++n;
    56     }
    57     check(n==INVALID,"Wrong red Node list linking.");
    58     check(countRedNodes(G)==cnt,"Wrong red Node number.");
    59   }
    60 
    61   template<class Graph>
    62   void checkGraphBlueNodeList(const Graph &G, int cnt)
    63   {
    64     typename Graph::BlueNodeIt n(G);
    65     for(int i=0;i<cnt;i++) {
    66       check(n!=INVALID,"Wrong blue Node list linking.");
    67       check(G.blue(n),"Wrong node set check.");
    68       check(!G.red(n),"Wrong node set check.");
    69       typename Graph::Node nn = n;
    70       check(G.asBlueNodeUnsafe(nn) == n,"Wrong node conversion.");
    71       check(G.asBlueNode(nn) == n,"Wrong node conversion.");
    72       check(G.asRedNode(nn) == INVALID,"Wrong node conversion.");
    73       ++n;
    74     }
    75     check(n==INVALID,"Wrong blue Node list linking.");
    76     check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
    77   }
    78 
    79   template<class Graph>
    80   void checkGraphArcList(const Graph &G, int cnt)
    81   {
    82     typename Graph::ArcIt e(G);
    83     for(int i=0;i<cnt;i++) {
    84       check(e!=INVALID,"Wrong Arc list linking.");
    85       check(G.oppositeNode(G.source(e), e) == G.target(e),
    86             "Wrong opposite node");
    87       check(G.oppositeNode(G.target(e), e) == G.source(e),
    88             "Wrong opposite node");
    89       ++e;
    90     }
    91     check(e==INVALID,"Wrong Arc list linking.");
    92     check(countArcs(G)==cnt,"Wrong Arc number.");
    93   }
    94 
    95   template<class Graph>
    96   void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
    97   {
    98     typename Graph::OutArcIt e(G,n);
    99     for(int i=0;i<cnt;i++) {
   100       check(e!=INVALID,"Wrong OutArc list linking.");
   101       check(n==G.source(e),"Wrong OutArc list linking.");
   102       check(n==G.baseNode(e),"Wrong OutArc list linking.");
   103       check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
   104       ++e;
   105     }
   106     check(e==INVALID,"Wrong OutArc list linking.");
   107     check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
   108   }
   109 
   110   template<class Graph>
   111   void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
   112   {
   113     typename Graph::InArcIt e(G,n);
   114     for(int i=0;i<cnt;i++) {
   115       check(e!=INVALID,"Wrong InArc list linking.");
   116       check(n==G.target(e),"Wrong InArc list linking.");
   117       check(n==G.baseNode(e),"Wrong OutArc list linking.");
   118       check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
   119       ++e;
   120     }
   121     check(e==INVALID,"Wrong InArc list linking.");
   122     check(countInArcs(G,n)==cnt,"Wrong InArc number.");
   123   }
   124 
   125   template<class Graph>
   126   void checkGraphEdgeList(const Graph &G, int cnt)
   127   {
   128     typename Graph::EdgeIt e(G);
   129     for(int i=0;i<cnt;i++) {
   130       check(e!=INVALID,"Wrong Edge list linking.");
   131       check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
   132       check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
   133       ++e;
   134     }
   135     check(e==INVALID,"Wrong Edge list linking.");
   136     check(countEdges(G)==cnt,"Wrong Edge number.");
   137   }
   138 
   139   template<class Graph>
   140   void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
   141   {
   142     typename Graph::IncEdgeIt e(G,n);
   143     for(int i=0;i<cnt;i++) {
   144       check(e!=INVALID,"Wrong IncEdge list linking.");
   145       check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
   146       check(n==G.baseNode(e),"Wrong OutArc list linking.");
   147       check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
   148             "Wrong OutArc list linking.");
   149       ++e;
   150     }
   151     check(e==INVALID,"Wrong IncEdge list linking.");
   152     check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
   153   }
   154 
   155   template <class Graph>
   156   void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
   157                                  int cnt)
   158   {
   159     checkGraphIncEdgeList(G, n, cnt);
   160     checkGraphOutArcList(G, n, cnt);
   161     checkGraphInArcList(G, n, cnt);
   162   }
   163 
   164   template <class Graph>
   165   void checkGraphConArcList(const Graph &G, int cnt) {
   166     int i = 0;
   167     for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
   168       for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
   169         for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
   170           check(G.source(a) == u, "Wrong iterator.");
   171           check(G.target(a) == v, "Wrong iterator.");
   172           ++i;
   173         }
   174       }
   175     }
   176     check(cnt == i, "Wrong iterator.");
   177   }
   178 
   179   template <class Graph>
   180   void checkGraphConEdgeList(const Graph &G, int cnt) {
   181     int i = 0;
   182     for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
   183       for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
   184         for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
   185           check((G.u(e) == u && G.v(e) == v) ||
   186                 (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
   187           i += u == v ? 2 : 1;
   188         }
   189       }
   190     }
   191     check(2 * cnt == i, "Wrong iterator.");
   192   }
   193 
   194   template <typename Graph>
   195   void checkArcDirections(const Graph& G) {
   196     for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
   197       check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
   198       check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
   199       check(G.direct(a, G.direction(a)) == a, "Wrong direction");
   200     }
   201   }
   202 
   203   template <typename Graph>
   204   void checkNodeIds(const Graph& G) {
   205     typedef typename Graph::Node Node;
   206     std::set<int> values;
   207     for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
   208       check(G.nodeFromId(G.id(n)) == n, "Wrong id");
   209       check(values.find(G.id(n)) == values.end(), "Wrong id");
   210       check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
   211       values.insert(G.id(n));
   212     }
   213     check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id");
   214   }
   215 
   216   template <typename Graph>
   217   void checkRedNodeIds(const Graph& G) {
   218     typedef typename Graph::RedNode RedNode;
   219     std::set<int> values;
   220     for (typename Graph::RedNodeIt n(G); n != INVALID; ++n) {
   221       check(G.red(n), "Wrong partition");
   222       check(values.find(G.id(n)) == values.end(), "Wrong id");
   223       check(G.id(n) <= G.maxRedId(), "Wrong maximum id");
   224       values.insert(G.id(n));
   225     }
   226     check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
   227   }
   228 
   229   template <typename Graph>
   230   void checkBlueNodeIds(const Graph& G) {
   231     typedef typename Graph::BlueNode BlueNode;
   232     std::set<int> values;
   233     for (typename Graph::BlueNodeIt n(G); n != INVALID; ++n) {
   234       check(G.blue(n), "Wrong partition");
   235       check(values.find(G.id(n)) == values.end(), "Wrong id");
   236       check(G.id(n) <= G.maxBlueId(), "Wrong maximum id");
   237       values.insert(G.id(n));
   238     }
   239     check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");
   240   }
   241 
   242   template <typename Graph>
   243   void checkArcIds(const Graph& G) {
   244     typedef typename Graph::Arc Arc;
   245     std::set<int> values;
   246     for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
   247       check(G.arcFromId(G.id(a)) == a, "Wrong id");
   248       check(values.find(G.id(a)) == values.end(), "Wrong id");
   249       check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
   250       values.insert(G.id(a));
   251     }
   252     check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
   253   }
   254 
   255   template <typename Graph>
   256   void checkEdgeIds(const Graph& G) {
   257     typedef typename Graph::Edge Edge;
   258     std::set<int> values;
   259     for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
   260       check(G.edgeFromId(G.id(e)) == e, "Wrong id");
   261       check(values.find(G.id(e)) == values.end(), "Wrong id");
   262       check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
   263       values.insert(G.id(e));
   264     }
   265     check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
   266   }
   267 
   268   template <typename Graph>
   269   void checkGraphNodeMap(const Graph& G) {
   270     typedef typename Graph::Node Node;
   271     typedef typename Graph::NodeIt NodeIt;
   272 
   273     typedef typename Graph::template NodeMap<int> IntNodeMap;
   274     IntNodeMap map(G, 42);
   275     for (NodeIt it(G); it != INVALID; ++it) {
   276       check(map[it] == 42, "Wrong map constructor.");
   277     }
   278     int s = 0;
   279     for (NodeIt it(G); it != INVALID; ++it) {
   280       map[it] = 0;
   281       check(map[it] == 0, "Wrong operator[].");
   282       map.set(it, s);
   283       check(map[it] == s, "Wrong set.");
   284       ++s;
   285     }
   286     s = s * (s - 1) / 2;
   287     for (NodeIt it(G); it != INVALID; ++it) {
   288       s -= map[it];
   289     }
   290     check(s == 0, "Wrong sum.");
   291 
   292     // map = constMap<Node>(12);
   293     // for (NodeIt it(G); it != INVALID; ++it) {
   294     //   check(map[it] == 12, "Wrong operator[].");
   295     // }
   296   }
   297 
   298   template <typename Graph>
   299   void checkGraphRedNodeMap(const Graph& G) {
   300     typedef typename Graph::Node Node;
   301     typedef typename Graph::RedNodeIt RedNodeIt;
   302 
   303     typedef typename Graph::template RedNodeMap<int> IntRedNodeMap;
   304     IntRedNodeMap map(G, 42);
   305     for (RedNodeIt it(G); it != INVALID; ++it) {
   306       check(map[it] == 42, "Wrong map constructor.");
   307     }
   308     int s = 0;
   309     for (RedNodeIt it(G); it != INVALID; ++it) {
   310       map[it] = 0;
   311       check(map[it] == 0, "Wrong operator[].");
   312       map.set(it, s);
   313       check(map[it] == s, "Wrong set.");
   314       ++s;
   315     }
   316     s = s * (s - 1) / 2;
   317     for (RedNodeIt it(G); it != INVALID; ++it) {
   318       s -= map[it];
   319     }
   320     check(s == 0, "Wrong sum.");
   321 
   322     // map = constMap<Node>(12);
   323     // for (NodeIt it(G); it != INVALID; ++it) {
   324     //   check(map[it] == 12, "Wrong operator[].");
   325     // }
   326   }
   327 
   328   template <typename Graph>
   329   void checkGraphBlueNodeMap(const Graph& G) {
   330     typedef typename Graph::Node Node;
   331     typedef typename Graph::BlueNodeIt BlueNodeIt;
   332 
   333     typedef typename Graph::template BlueNodeMap<int> IntBlueNodeMap;
   334     IntBlueNodeMap map(G, 42);
   335     for (BlueNodeIt it(G); it != INVALID; ++it) {
   336       check(map[it] == 42, "Wrong map constructor.");
   337     }
   338     int s = 0;
   339     for (BlueNodeIt it(G); it != INVALID; ++it) {
   340       map[it] = 0;
   341       check(map[it] == 0, "Wrong operator[].");
   342       map.set(it, s);
   343       check(map[it] == s, "Wrong set.");
   344       ++s;
   345     }
   346     s = s * (s - 1) / 2;
   347     for (BlueNodeIt it(G); it != INVALID; ++it) {
   348       s -= map[it];
   349     }
   350     check(s == 0, "Wrong sum.");
   351 
   352     // map = constMap<Node>(12);
   353     // for (NodeIt it(G); it != INVALID; ++it) {
   354     //   check(map[it] == 12, "Wrong operator[].");
   355     // }
   356   }
   357 
   358   template <typename Graph>
   359   void checkGraphArcMap(const Graph& G) {
   360     typedef typename Graph::Arc Arc;
   361     typedef typename Graph::ArcIt ArcIt;
   362 
   363     typedef typename Graph::template ArcMap<int> IntArcMap;
   364     IntArcMap map(G, 42);
   365     for (ArcIt it(G); it != INVALID; ++it) {
   366       check(map[it] == 42, "Wrong map constructor.");
   367     }
   368     int s = 0;
   369     for (ArcIt it(G); it != INVALID; ++it) {
   370       map[it] = 0;
   371       check(map[it] == 0, "Wrong operator[].");
   372       map.set(it, s);
   373       check(map[it] == s, "Wrong set.");
   374       ++s;
   375     }
   376     s = s * (s - 1) / 2;
   377     for (ArcIt it(G); it != INVALID; ++it) {
   378       s -= map[it];
   379     }
   380     check(s == 0, "Wrong sum.");
   381 
   382     // map = constMap<Arc>(12);
   383     // for (ArcIt it(G); it != INVALID; ++it) {
   384     //   check(map[it] == 12, "Wrong operator[].");
   385     // }
   386   }
   387 
   388   template <typename Graph>
   389   void checkGraphEdgeMap(const Graph& G) {
   390     typedef typename Graph::Edge Edge;
   391     typedef typename Graph::EdgeIt EdgeIt;
   392 
   393     typedef typename Graph::template EdgeMap<int> IntEdgeMap;
   394     IntEdgeMap map(G, 42);
   395     for (EdgeIt it(G); it != INVALID; ++it) {
   396       check(map[it] == 42, "Wrong map constructor.");
   397     }
   398     int s = 0;
   399     for (EdgeIt it(G); it != INVALID; ++it) {
   400       map[it] = 0;
   401       check(map[it] == 0, "Wrong operator[].");
   402       map.set(it, s);
   403       check(map[it] == s, "Wrong set.");
   404       ++s;
   405     }
   406     s = s * (s - 1) / 2;
   407     for (EdgeIt it(G); it != INVALID; ++it) {
   408       s -= map[it];
   409     }
   410     check(s == 0, "Wrong sum.");
   411 
   412     // map = constMap<Edge>(12);
   413     // for (EdgeIt it(G); it != INVALID; ++it) {
   414     //   check(map[it] == 12, "Wrong operator[].");
   415     // }
   416   }
   417 
   418 
   419 } //namespace lemon
   420 
   421 #endif