test/graph_test.h
author Balazs Dezso <deba@inf.elte.hu>
Fri, 11 Jul 2008 15:01:49 +0200
changeset 203 215bfc30b14f
child 209 765619b7cbb2
permissions -rw-r--r--
Cleaning of heap test and bug fix in heap concept check (ticket #100)

* The dijkstra heap test's digraph is inlined into the source file
* The random sequences are fixed
* The content of the header is moved to the source file
* Only the binary heap is checked
kpeter@171
     1
/* -*- C++ -*-
kpeter@171
     2
 *
kpeter@171
     3
 * This file is a part of LEMON, a generic C++ optimization library
kpeter@171
     4
 *
kpeter@171
     5
 * Copyright (C) 2003-2008
kpeter@171
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@171
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@171
     8
 *
kpeter@171
     9
 * Permission to use, modify and distribute this software is granted
kpeter@171
    10
 * provided that this copyright notice appears in all copies. For
kpeter@171
    11
 * precise terms see the accompanying LICENSE file.
kpeter@171
    12
 *
kpeter@171
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@171
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@171
    15
 * purpose.
kpeter@171
    16
 *
kpeter@171
    17
 */
kpeter@171
    18
kpeter@171
    19
#ifndef LEMON_TEST_GRAPH_TEST_H
kpeter@171
    20
#define LEMON_TEST_GRAPH_TEST_H
kpeter@171
    21
kpeter@171
    22
#include <lemon/graph_utils.h>
kpeter@171
    23
#include "test_tools.h"
kpeter@171
    24
kpeter@171
    25
namespace lemon {
kpeter@171
    26
kpeter@171
    27
  template<class Graph>
kpeter@171
    28
  void checkGraphNodeList(const Graph &G, int cnt)
kpeter@171
    29
  {
kpeter@171
    30
    typename Graph::NodeIt n(G);
kpeter@171
    31
    for(int i=0;i<cnt;i++) {
kpeter@171
    32
      check(n!=INVALID,"Wrong Node list linking.");
kpeter@171
    33
      ++n;
kpeter@171
    34
    }
kpeter@171
    35
    check(n==INVALID,"Wrong Node list linking.");
kpeter@171
    36
    check(countNodes(G)==cnt,"Wrong Node number.");
kpeter@171
    37
  }
kpeter@171
    38
kpeter@171
    39
  template<class Graph>
kpeter@171
    40
  void checkGraphArcList(const Graph &G, int cnt)
kpeter@171
    41
  {
kpeter@171
    42
    typename Graph::ArcIt e(G);
kpeter@171
    43
    for(int i=0;i<cnt;i++) {
kpeter@171
    44
      check(e!=INVALID,"Wrong Arc list linking.");
kpeter@171
    45
      ++e;
kpeter@171
    46
    }
kpeter@171
    47
    check(e==INVALID,"Wrong Arc list linking.");
kpeter@171
    48
    check(countArcs(G)==cnt,"Wrong Arc number.");
kpeter@171
    49
  }
kpeter@171
    50
kpeter@171
    51
  template<class Graph>
kpeter@171
    52
  void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
kpeter@171
    53
  {
kpeter@171
    54
    typename Graph::OutArcIt e(G,n);
kpeter@171
    55
    for(int i=0;i<cnt;i++) {
kpeter@171
    56
      check(e!=INVALID,"Wrong OutArc list linking.");
kpeter@171
    57
      check(n==G.source(e),"Wrong OutArc list linking.");
kpeter@171
    58
      ++e;
kpeter@171
    59
    }
kpeter@171
    60
    check(e==INVALID,"Wrong OutArc list linking.");
kpeter@171
    61
    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
kpeter@171
    62
  }
kpeter@171
    63
kpeter@171
    64
  template<class Graph>
kpeter@171
    65
  void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
kpeter@171
    66
  {
kpeter@171
    67
    typename Graph::InArcIt e(G,n);
kpeter@171
    68
    for(int i=0;i<cnt;i++) {
kpeter@171
    69
      check(e!=INVALID,"Wrong InArc list linking.");
kpeter@171
    70
      check(n==G.target(e),"Wrong InArc list linking.");
kpeter@171
    71
      ++e;
kpeter@171
    72
    }
kpeter@171
    73
    check(e==INVALID,"Wrong InArc list linking.");
kpeter@171
    74
    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
kpeter@171
    75
  }
kpeter@171
    76
kpeter@171
    77
  template<class Graph>
kpeter@171
    78
  void checkGraphEdgeList(const Graph &G, int cnt)
kpeter@171
    79
  {
kpeter@171
    80
    typename Graph::EdgeIt e(G);
kpeter@171
    81
    for(int i=0;i<cnt;i++) {
kpeter@171
    82
      check(e!=INVALID,"Wrong Edge list linking.");
kpeter@171
    83
      ++e;
kpeter@171
    84
    }
kpeter@171
    85
    check(e==INVALID,"Wrong Edge list linking.");
kpeter@171
    86
    check(countEdges(G)==cnt,"Wrong Edge number.");
kpeter@171
    87
  }
kpeter@171
    88
kpeter@171
    89
  template<class Graph>
kpeter@171
    90
  void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
kpeter@171
    91
  {
kpeter@171
    92
    typename Graph::IncEdgeIt e(G,n);
kpeter@171
    93
    for(int i=0;i<cnt;i++) {
kpeter@171
    94
      check(e!=INVALID,"Wrong IncEdge list linking.");
kpeter@171
    95
      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
kpeter@171
    96
      ++e;
kpeter@171
    97
    }
kpeter@171
    98
    check(e==INVALID,"Wrong IncEdge list linking.");
kpeter@171
    99
    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
kpeter@171
   100
  }
kpeter@171
   101
kpeter@171
   102
  template <class Digraph>
kpeter@171
   103
  void checkDigraphIterators() {
kpeter@171
   104
    typedef typename Digraph::Node Node;
kpeter@171
   105
    typedef typename Digraph::NodeIt NodeIt;
kpeter@171
   106
    typedef typename Digraph::Arc Arc;
kpeter@171
   107
    typedef typename Digraph::ArcIt ArcIt;
kpeter@171
   108
    typedef typename Digraph::InArcIt InArcIt;
kpeter@171
   109
    typedef typename Digraph::OutArcIt OutArcIt;
kpeter@171
   110
  }
kpeter@171
   111
kpeter@171
   112
  template <class Graph>
kpeter@171
   113
  void checkGraphIterators() {
kpeter@171
   114
    checkDigraphIterators<Graph>();
kpeter@171
   115
    typedef typename Graph::Edge Edge;
kpeter@171
   116
    typedef typename Graph::EdgeIt EdgeIt;
kpeter@171
   117
    typedef typename Graph::IncEdgeIt IncEdgeIt;
kpeter@171
   118
  }
kpeter@171
   119
kpeter@171
   120
  // Structure returned by addPetersen()
kpeter@171
   121
  template<class Digraph>
kpeter@171
   122
  struct PetStruct
kpeter@171
   123
  {
kpeter@171
   124
    // Vector containing the outer nodes
kpeter@171
   125
    std::vector<typename Digraph::Node> outer;
kpeter@171
   126
    // Vector containing the inner nodes
kpeter@171
   127
    std::vector<typename Digraph::Node> inner;
kpeter@171
   128
    // Vector containing the arcs of the inner circle
kpeter@171
   129
    std::vector<typename Digraph::Arc> incir;
kpeter@171
   130
    // Vector containing the arcs of the outer circle
kpeter@171
   131
    std::vector<typename Digraph::Arc> outcir;
kpeter@171
   132
    // Vector containing the chord arcs
kpeter@171
   133
    std::vector<typename Digraph::Arc> chords;
kpeter@171
   134
  };
kpeter@171
   135
kpeter@171
   136
  // Adds the reverse pair of all arcs to a digraph
kpeter@171
   137
  template<class Digraph>
kpeter@171
   138
  void bidirDigraph(Digraph &G)
kpeter@171
   139
  {
kpeter@171
   140
    typedef typename Digraph::Arc Arc;
kpeter@171
   141
    typedef typename Digraph::ArcIt ArcIt;
kpeter@171
   142
kpeter@171
   143
    std::vector<Arc> ee;
kpeter@171
   144
kpeter@171
   145
    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
kpeter@171
   146
kpeter@171
   147
    for(int i=0;i<int(ee.size());++i)
kpeter@171
   148
      G.addArc(G.target(ee[i]),G.source(ee[i]));
kpeter@171
   149
  }
kpeter@171
   150
kpeter@171
   151
  // Adds a Petersen digraph to G.
kpeter@171
   152
  // Returns the nodes and arcs of the generated digraph.
kpeter@171
   153
  template<typename Digraph>
kpeter@171
   154
  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
kpeter@171
   155
  {
kpeter@171
   156
    PetStruct<Digraph> n;
kpeter@171
   157
kpeter@171
   158
    for(int i=0;i<num;i++) {
kpeter@171
   159
      n.outer.push_back(G.addNode());
kpeter@171
   160
      n.inner.push_back(G.addNode());
kpeter@171
   161
    }
kpeter@171
   162
kpeter@171
   163
    for(int i=0;i<num;i++) {
kpeter@171
   164
      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
kpeter@171
   165
      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
kpeter@171
   166
      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
kpeter@171
   167
    }
kpeter@171
   168
kpeter@171
   169
    return n;
kpeter@171
   170
  }
kpeter@171
   171
kpeter@171
   172
  // Checks the bidirectioned Petersen digraph
kpeter@171
   173
  template<class Digraph>
kpeter@171
   174
  void checkBidirPetersen(const Digraph &G, int num = 5)
kpeter@171
   175
  {
kpeter@171
   176
    typedef typename Digraph::NodeIt NodeIt;
kpeter@171
   177
kpeter@171
   178
    checkGraphNodeList(G, 2 * num);
kpeter@171
   179
    checkGraphArcList(G, 6 * num);
kpeter@171
   180
kpeter@171
   181
    for(NodeIt n(G);n!=INVALID;++n) {
kpeter@171
   182
      checkGraphInArcList(G, n, 3);
kpeter@171
   183
      checkGraphOutArcList(G, n, 3);
kpeter@171
   184
    }
kpeter@171
   185
  }
kpeter@171
   186
kpeter@171
   187
  // Structure returned by addUPetersen()
kpeter@171
   188
  template<class Graph>
kpeter@171
   189
  struct UPetStruct
kpeter@171
   190
  {
kpeter@171
   191
    // Vector containing the outer nodes
kpeter@171
   192
    std::vector<typename Graph::Node> outer;
kpeter@171
   193
    // Vector containing the inner nodes
kpeter@171
   194
    std::vector<typename Graph::Node> inner;
kpeter@171
   195
    // Vector containing the edges of the inner circle
kpeter@171
   196
    std::vector<typename Graph::Edge> incir;
kpeter@171
   197
    // Vector containing the edges of the outer circle
kpeter@171
   198
    std::vector<typename Graph::Edge> outcir;
kpeter@171
   199
    // Vector containing the chord edges
kpeter@171
   200
    std::vector<typename Graph::Edge> chords;
kpeter@171
   201
  };
kpeter@171
   202
kpeter@171
   203
  // Adds a Petersen graph to \c G.
kpeter@171
   204
  // Returns the nodes and edges of the generated graph.
kpeter@171
   205
  template<typename Graph>
kpeter@171
   206
  UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
kpeter@171
   207
  {
kpeter@171
   208
    UPetStruct<Graph> n;
kpeter@171
   209
kpeter@171
   210
    for(int i=0;i<num;i++) {
kpeter@171
   211
      n.outer.push_back(G.addNode());
kpeter@171
   212
      n.inner.push_back(G.addNode());
kpeter@171
   213
    }
kpeter@171
   214
kpeter@171
   215
    for(int i=0;i<num;i++) {
kpeter@171
   216
      n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
kpeter@171
   217
      n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
kpeter@171
   218
      n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
kpeter@171
   219
    }
kpeter@171
   220
    
kpeter@171
   221
    return n;
kpeter@171
   222
  }
kpeter@171
   223
kpeter@171
   224
  // Checks the undirected Petersen graph
kpeter@171
   225
  template<class Graph>
kpeter@171
   226
  void checkUndirPetersen(const Graph &G, int num = 5)
kpeter@171
   227
  {
kpeter@171
   228
    typedef typename Graph::NodeIt NodeIt;
kpeter@171
   229
kpeter@171
   230
    checkGraphNodeList(G, 2 * num);
kpeter@171
   231
    checkGraphEdgeList(G, 3 * num);
kpeter@171
   232
    checkGraphArcList(G, 6 * num);
kpeter@171
   233
kpeter@171
   234
    for(NodeIt n(G);n!=INVALID;++n) {
kpeter@171
   235
      checkGraphIncEdgeList(G, n, 3);
kpeter@171
   236
    }
kpeter@171
   237
  }
kpeter@171
   238
kpeter@171
   239
  template <class Digraph>
kpeter@171
   240
  void checkDigraph() {
kpeter@171
   241
    const int num = 5;
kpeter@171
   242
    Digraph G;
kpeter@171
   243
    checkGraphNodeList(G, 0);
kpeter@171
   244
    checkGraphArcList(G, 0);
kpeter@171
   245
    addPetersen(G, num);
kpeter@171
   246
    bidirDigraph(G);
kpeter@171
   247
    checkBidirPetersen(G, num);
kpeter@171
   248
  }
kpeter@171
   249
  
kpeter@171
   250
  template <class Graph>
kpeter@171
   251
  void checkGraph() {
kpeter@171
   252
    const int num = 5;
kpeter@171
   253
    Graph G;
kpeter@171
   254
    checkGraphNodeList(G, 0);
kpeter@171
   255
    checkGraphEdgeList(G, 0);
kpeter@171
   256
    addUPetersen(G, num);
kpeter@171
   257
    checkUndirPetersen(G, num);
kpeter@171
   258
  }
kpeter@171
   259
kpeter@171
   260
} //namespace lemon
kpeter@171
   261
kpeter@171
   262
#endif