test/graph_test.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 374 49d9a36b3b84
child 1019 4c89e925cfe2
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     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 checkGraphArcList(const Graph &G, int cnt)
    45   {
    46     typename Graph::ArcIt e(G);
    47     for(int i=0;i<cnt;i++) {
    48       check(e!=INVALID,"Wrong Arc list linking.");
    49       check(G.oppositeNode(G.source(e), e) == G.target(e),
    50             "Wrong opposite node");
    51       check(G.oppositeNode(G.target(e), e) == G.source(e),
    52             "Wrong opposite node");
    53       ++e;
    54     }
    55     check(e==INVALID,"Wrong Arc list linking.");
    56     check(countArcs(G)==cnt,"Wrong Arc number.");
    57   }
    58 
    59   template<class Graph>
    60   void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
    61   {
    62     typename Graph::OutArcIt e(G,n);
    63     for(int i=0;i<cnt;i++) {
    64       check(e!=INVALID,"Wrong OutArc list linking.");
    65       check(n==G.source(e),"Wrong OutArc list linking.");
    66       check(n==G.baseNode(e),"Wrong OutArc list linking.");
    67       check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking.");
    68       ++e;
    69     }
    70     check(e==INVALID,"Wrong OutArc list linking.");
    71     check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
    72   }
    73 
    74   template<class Graph>
    75   void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
    76   {
    77     typename Graph::InArcIt e(G,n);
    78     for(int i=0;i<cnt;i++) {
    79       check(e!=INVALID,"Wrong InArc list linking.");
    80       check(n==G.target(e),"Wrong InArc list linking.");
    81       check(n==G.baseNode(e),"Wrong OutArc list linking.");
    82       check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking.");
    83       ++e;
    84     }
    85     check(e==INVALID,"Wrong InArc list linking.");
    86     check(countInArcs(G,n)==cnt,"Wrong InArc number.");
    87   }
    88 
    89   template<class Graph>
    90   void checkGraphEdgeList(const Graph &G, int cnt)
    91   {
    92     typename Graph::EdgeIt e(G);
    93     for(int i=0;i<cnt;i++) {
    94       check(e!=INVALID,"Wrong Edge list linking.");
    95       check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node");
    96       check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node");
    97       ++e;
    98     }
    99     check(e==INVALID,"Wrong Edge list linking.");
   100     check(countEdges(G)==cnt,"Wrong Edge number.");
   101   }
   102 
   103   template<class Graph>
   104   void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
   105   {
   106     typename Graph::IncEdgeIt e(G,n);
   107     for(int i=0;i<cnt;i++) {
   108       check(e!=INVALID,"Wrong IncEdge list linking.");
   109       check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
   110       check(n==G.baseNode(e),"Wrong OutArc list linking.");
   111       check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e),
   112             "Wrong OutArc list linking.");
   113       ++e;
   114     }
   115     check(e==INVALID,"Wrong IncEdge list linking.");
   116     check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
   117   }
   118 
   119   template <class Graph>
   120   void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
   121                                  int cnt)
   122   {
   123     checkGraphIncEdgeList(G, n, cnt);
   124     checkGraphOutArcList(G, n, cnt);
   125     checkGraphInArcList(G, n, cnt);
   126   }
   127 
   128   template <class Graph>
   129   void checkGraphConArcList(const Graph &G, int cnt) {
   130     int i = 0;
   131     for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
   132       for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
   133         for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) {
   134           check(G.source(a) == u, "Wrong iterator.");
   135           check(G.target(a) == v, "Wrong iterator.");
   136           ++i;
   137         }
   138       }
   139     }
   140     check(cnt == i, "Wrong iterator.");
   141   }
   142 
   143   template <class Graph>
   144   void checkGraphConEdgeList(const Graph &G, int cnt) {
   145     int i = 0;
   146     for (typename Graph::NodeIt u(G); u != INVALID; ++u) {
   147       for (typename Graph::NodeIt v(G); v != INVALID; ++v) {
   148         for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) {
   149           check((G.u(e) == u && G.v(e) == v) ||
   150                 (G.u(e) == v && G.v(e) == u), "Wrong iterator.");
   151           i += u == v ? 2 : 1;
   152         }
   153       }
   154     }
   155     check(2 * cnt == i, "Wrong iterator.");
   156   }
   157 
   158   template <typename Graph>
   159   void checkArcDirections(const Graph& G) {
   160     for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
   161       check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction");
   162       check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction");
   163       check(G.direct(a, G.direction(a)) == a, "Wrong direction");
   164     }
   165   }
   166 
   167   template <typename Graph>
   168   void checkNodeIds(const Graph& G) {
   169     std::set<int> values;
   170     for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
   171       check(G.nodeFromId(G.id(n)) == n, "Wrong id");
   172       check(values.find(G.id(n)) == values.end(), "Wrong id");
   173       check(G.id(n) <= G.maxNodeId(), "Wrong maximum id");
   174       values.insert(G.id(n));
   175     }
   176   }
   177 
   178   template <typename Graph>
   179   void checkArcIds(const Graph& G) {
   180     std::set<int> values;
   181     for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
   182       check(G.arcFromId(G.id(a)) == a, "Wrong id");
   183       check(values.find(G.id(a)) == values.end(), "Wrong id");
   184       check(G.id(a) <= G.maxArcId(), "Wrong maximum id");
   185       values.insert(G.id(a));
   186     }
   187   }
   188 
   189   template <typename Graph>
   190   void checkEdgeIds(const Graph& G) {
   191     std::set<int> values;
   192     for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
   193       check(G.edgeFromId(G.id(e)) == e, "Wrong id");
   194       check(values.find(G.id(e)) == values.end(), "Wrong id");
   195       check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id");
   196       values.insert(G.id(e));
   197     }
   198   }
   199 
   200   template <typename Graph>
   201   void checkGraphNodeMap(const Graph& G) {
   202     typedef typename Graph::Node Node;
   203     typedef typename Graph::NodeIt NodeIt;
   204 
   205     typedef typename Graph::template NodeMap<int> IntNodeMap;
   206     IntNodeMap map(G, 42);
   207     for (NodeIt it(G); it != INVALID; ++it) {
   208       check(map[it] == 42, "Wrong map constructor.");
   209     }
   210     int s = 0;
   211     for (NodeIt it(G); it != INVALID; ++it) {
   212       map[it] = 0;
   213       check(map[it] == 0, "Wrong operator[].");
   214       map.set(it, s);
   215       check(map[it] == s, "Wrong set.");
   216       ++s;
   217     }
   218     s = s * (s - 1) / 2;
   219     for (NodeIt it(G); it != INVALID; ++it) {
   220       s -= map[it];
   221     }
   222     check(s == 0, "Wrong sum.");
   223 
   224     // map = constMap<Node>(12);
   225     // for (NodeIt it(G); it != INVALID; ++it) {
   226     //   check(map[it] == 12, "Wrong operator[].");
   227     // }
   228   }
   229 
   230   template <typename Graph>
   231   void checkGraphArcMap(const Graph& G) {
   232     typedef typename Graph::Arc Arc;
   233     typedef typename Graph::ArcIt ArcIt;
   234 
   235     typedef typename Graph::template ArcMap<int> IntArcMap;
   236     IntArcMap map(G, 42);
   237     for (ArcIt it(G); it != INVALID; ++it) {
   238       check(map[it] == 42, "Wrong map constructor.");
   239     }
   240     int s = 0;
   241     for (ArcIt it(G); it != INVALID; ++it) {
   242       map[it] = 0;
   243       check(map[it] == 0, "Wrong operator[].");
   244       map.set(it, s);
   245       check(map[it] == s, "Wrong set.");
   246       ++s;
   247     }
   248     s = s * (s - 1) / 2;
   249     for (ArcIt it(G); it != INVALID; ++it) {
   250       s -= map[it];
   251     }
   252     check(s == 0, "Wrong sum.");
   253 
   254     // map = constMap<Arc>(12);
   255     // for (ArcIt it(G); it != INVALID; ++it) {
   256     //   check(map[it] == 12, "Wrong operator[].");
   257     // }
   258   }
   259 
   260   template <typename Graph>
   261   void checkGraphEdgeMap(const Graph& G) {
   262     typedef typename Graph::Edge Edge;
   263     typedef typename Graph::EdgeIt EdgeIt;
   264 
   265     typedef typename Graph::template EdgeMap<int> IntEdgeMap;
   266     IntEdgeMap map(G, 42);
   267     for (EdgeIt it(G); it != INVALID; ++it) {
   268       check(map[it] == 42, "Wrong map constructor.");
   269     }
   270     int s = 0;
   271     for (EdgeIt it(G); it != INVALID; ++it) {
   272       map[it] = 0;
   273       check(map[it] == 0, "Wrong operator[].");
   274       map.set(it, s);
   275       check(map[it] == s, "Wrong set.");
   276       ++s;
   277     }
   278     s = s * (s - 1) / 2;
   279     for (EdgeIt it(G); it != INVALID; ++it) {
   280       s -= map[it];
   281     }
   282     check(s == 0, "Wrong sum.");
   283 
   284     // map = constMap<Edge>(12);
   285     // for (EdgeIt it(G); it != INVALID; ++it) {
   286     //   check(map[it] == 12, "Wrong operator[].");
   287     // }
   288   }
   289 
   290 
   291 } //namespace lemon
   292 
   293 #endif