test/test_tools.h
author Balazs Dezso <deba@inf.elte.hu>
Mon, 14 Apr 2008 17:37:18 +0100
changeset 125 19e82bda606a
parent 39 0a01d811071f
child 171 02f4d5d9bfd7
permissions -rw-r--r--
Fix bug #83 in graph concept, extender and smart graph
alpar@4
     1
/* -*- C++ -*-
alpar@4
     2
 *
alpar@4
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@4
     4
 *
alpar@39
     5
 * Copyright (C) 2003-2008
alpar@4
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@4
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@4
     8
 *
alpar@4
     9
 * Permission to use, modify and distribute this software is granted
alpar@4
    10
 * provided that this copyright notice appears in all copies. For
alpar@4
    11
 * precise terms see the accompanying LICENSE file.
alpar@4
    12
 *
alpar@4
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@4
    14
 * express or implied, and with no claim as to its suitability for any
alpar@4
    15
 * purpose.
alpar@4
    16
 *
alpar@4
    17
 */
alpar@4
    18
alpar@4
    19
#ifndef LEMON_TEST_TEST_TOOLS_H
alpar@4
    20
#define LEMON_TEST_TEST_TOOLS_H
alpar@4
    21
alpar@4
    22
#include <iostream>
alpar@100
    23
#include <vector>
alpar@100
    24
alpar@100
    25
#include <cstdlib>
alpar@100
    26
#include <ctime>
alpar@100
    27
alpar@100
    28
#include <lemon/concept_check.h>
alpar@100
    29
#include <lemon/concepts/digraph.h>
alpar@100
    30
alpar@100
    31
#include <lemon/random.h>
alpar@100
    32
alpar@100
    33
using namespace lemon;
alpar@4
    34
alpar@4
    35
//! \ingroup misc
alpar@4
    36
//! \file
alpar@4
    37
//! \brief Some utilities to write test programs.
alpar@4
    38
alpar@4
    39
alpar@4
    40
///If \c rc is fail, writes an error message end exit.
alpar@4
    41
alpar@4
    42
///If \c rc is fail, writes an error message end exit.
alpar@4
    43
///The error message contains the file name and the line number of the
alpar@4
    44
///source code in a standard from, which makes it possible to go there
alpar@4
    45
///using good source browsers like e.g. \c emacs.
alpar@4
    46
///
alpar@4
    47
///For example
alpar@4
    48
///\code check(0==1,"This is obviously false.");\endcode will
alpar@4
    49
///print this (and then exits).
alpar@100
    50
///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
alpar@4
    51
///
alpar@4
    52
///\todo It should be in \c error.h
alpar@4
    53
#define check(rc, msg) \
alpar@4
    54
  if(!(rc)) { \
alpar@4
    55
    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
alpar@4
    56
    abort(); \
alpar@4
    57
  } else { } \
alpar@4
    58
alpar@100
    59
///Structure returned by \ref addPetersen().
alpar@100
    60
alpar@100
    61
///Structure returned by \ref addPetersen().
alpar@100
    62
///
alpar@100
    63
template<class Digraph> struct PetStruct
alpar@100
    64
{
alpar@100
    65
  ///Vector containing the outer nodes.
alpar@100
    66
  std::vector<typename Digraph::Node> outer;
alpar@100
    67
  ///Vector containing the inner nodes.
alpar@100
    68
  std::vector<typename Digraph::Node> inner;
alpar@100
    69
  ///Vector containing the arcs of the inner circle.
alpar@100
    70
  std::vector<typename Digraph::Arc> incir;
alpar@100
    71
  ///Vector containing the arcs of the outer circle.
alpar@100
    72
  std::vector<typename Digraph::Arc> outcir;
alpar@100
    73
  ///Vector containing the chord arcs.
alpar@100
    74
  std::vector<typename Digraph::Arc> chords;
alpar@100
    75
};
alpar@100
    76
alpar@100
    77
alpar@100
    78
alpar@100
    79
///Adds a Petersen digraph to \c G.
alpar@100
    80
alpar@100
    81
///Adds a Petersen digraph to \c G.
alpar@100
    82
///\return The nodes and arcs of the generated digraph.
alpar@100
    83
alpar@100
    84
template<typename Digraph>
alpar@100
    85
PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
alpar@100
    86
{
alpar@100
    87
  PetStruct<Digraph> n;
alpar@100
    88
alpar@100
    89
  for(int i=0;i<num;i++) {
alpar@100
    90
    n.outer.push_back(G.addNode());
alpar@100
    91
    n.inner.push_back(G.addNode());
alpar@100
    92
  }
alpar@100
    93
alpar@100
    94
 for(int i=0;i<num;i++) {
alpar@100
    95
   n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
alpar@100
    96
   n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
alpar@100
    97
   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
alpar@100
    98
  }
alpar@100
    99
 return n;
alpar@100
   100
}
alpar@100
   101
alpar@100
   102
/// \brief Adds to the digraph the reverse pair of all arcs.
alpar@100
   103
///
alpar@100
   104
/// Adds to the digraph the reverse pair of all arcs.
alpar@100
   105
///
alpar@100
   106
template<class Digraph> void bidirDigraph(Digraph &G)
alpar@100
   107
{
alpar@100
   108
  typedef typename Digraph::Arc Arc;
alpar@100
   109
  typedef typename Digraph::ArcIt ArcIt;
alpar@100
   110
  
alpar@100
   111
  std::vector<Arc> ee;
alpar@100
   112
  
alpar@100
   113
  for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
alpar@100
   114
alpar@100
   115
  for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
alpar@100
   116
    G.addArc(G.target(*p),G.source(*p));
alpar@100
   117
}
alpar@100
   118
alpar@100
   119
alpar@100
   120
/// \brief Checks the bidirectioned Petersen digraph.
alpar@100
   121
///
alpar@100
   122
///  Checks the bidirectioned Petersen digraph.
alpar@100
   123
///
alpar@100
   124
template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
alpar@100
   125
{
alpar@100
   126
  typedef typename Digraph::Node Node;
alpar@100
   127
alpar@100
   128
  typedef typename Digraph::ArcIt ArcIt;
alpar@100
   129
  typedef typename Digraph::NodeIt NodeIt;
alpar@100
   130
alpar@100
   131
  checkDigraphNodeList(G, 2 * num);
alpar@100
   132
  checkDigraphArcList(G, 6 * num);
alpar@100
   133
alpar@100
   134
  for(NodeIt n(G);n!=INVALID;++n) {
alpar@100
   135
    checkDigraphInArcList(G, n, 3);
alpar@100
   136
    checkDigraphOutArcList(G, n, 3);
alpar@100
   137
  }  
alpar@100
   138
}
alpar@100
   139
alpar@100
   140
///Structure returned by \ref addUPetersen().
alpar@100
   141
alpar@100
   142
///Structure returned by \ref addUPetersen().
alpar@100
   143
///
alpar@100
   144
template<class Digraph> struct UPetStruct
alpar@100
   145
{
alpar@100
   146
  ///Vector containing the outer nodes.
alpar@100
   147
  std::vector<typename Digraph::Node> outer;
alpar@100
   148
  ///Vector containing the inner nodes.
alpar@100
   149
  std::vector<typename Digraph::Node> inner;
alpar@100
   150
  ///Vector containing the arcs of the inner circle.
alpar@100
   151
  std::vector<typename Digraph::Edge> incir;
alpar@100
   152
  ///Vector containing the arcs of the outer circle.
alpar@100
   153
  std::vector<typename Digraph::Edge> outcir;
alpar@100
   154
  ///Vector containing the chord arcs.
alpar@100
   155
  std::vector<typename Digraph::Edge> chords;
alpar@100
   156
};
alpar@100
   157
alpar@100
   158
///Adds a Petersen digraph to the undirected \c G.
alpar@100
   159
alpar@100
   160
///Adds a Petersen digraph to the undirected \c G.
alpar@100
   161
///\return The nodes and arcs of the generated digraph.
alpar@100
   162
alpar@100
   163
template<typename Digraph>
alpar@100
   164
UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
alpar@100
   165
{
alpar@100
   166
  UPetStruct<Digraph> n;
alpar@100
   167
alpar@100
   168
  for(int i=0;i<num;i++) {
alpar@100
   169
    n.outer.push_back(G.addNode());
alpar@100
   170
    n.inner.push_back(G.addNode());
alpar@100
   171
  }
alpar@100
   172
alpar@100
   173
 for(int i=0;i<num;i++) {
alpar@100
   174
   n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
alpar@100
   175
   n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));
alpar@100
   176
   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
alpar@100
   177
 }
alpar@100
   178
 return n;
alpar@100
   179
}
alpar@100
   180
alpar@4
   181
#endif