test/digraph_test.h
changeset 171 02f4d5d9bfd7
parent 170 91fb4372688f
child 172 c94a80f38d7f
child 173 b026e9779b28
child 175 4eb8900a865c
     1.1 --- a/test/digraph_test.h	Sun Jun 15 22:03:33 2008 +0200
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,188 +0,0 @@
     1.4 -/* -*- C++ -*-
     1.5 - *
     1.6 - * This file is a part of LEMON, a generic C++ optimization library
     1.7 - *
     1.8 - * Copyright (C) 2003-2008
     1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 - *
    1.12 - * Permission to use, modify and distribute this software is granted
    1.13 - * provided that this copyright notice appears in all copies. For
    1.14 - * precise terms see the accompanying LICENSE file.
    1.15 - *
    1.16 - * This software is provided "AS IS" with no warranty of any kind,
    1.17 - * express or implied, and with no claim as to its suitability for any
    1.18 - * purpose.
    1.19 - *
    1.20 - */
    1.21 -
    1.22 -#ifndef LEMON_TEST_GRAPH_TEST_H
    1.23 -#define LEMON_TEST_GRAPH_TEST_H
    1.24 -
    1.25 -//#include <lemon/graph_utils.h>
    1.26 -#include "test_tools.h"
    1.27 -
    1.28 -//! \ingroup misc
    1.29 -//! \file
    1.30 -//! \brief Some utility and test cases to test digraph classes.
    1.31 -namespace lemon {
    1.32 -
    1.33 -  ///Structure returned by \ref addPetersen().
    1.34 -
    1.35 -  ///Structure returned by \ref addPetersen().
    1.36 -  ///
    1.37 -  template<class Digraph> 
    1.38 -  struct PetStruct
    1.39 -  {
    1.40 -    ///Vector containing the outer nodes.
    1.41 -    std::vector<typename Digraph::Node> outer;
    1.42 -    ///Vector containing the inner nodes.
    1.43 -    std::vector<typename Digraph::Node> inner;
    1.44 -    ///Vector containing the edges of the inner circle.
    1.45 -    std::vector<typename Digraph::Arc> incir;
    1.46 -    ///Vector containing the edges of the outer circle.
    1.47 -    std::vector<typename Digraph::Arc> outcir;
    1.48 -    ///Vector containing the chord edges.
    1.49 -    std::vector<typename Digraph::Arc> chords;
    1.50 -  };
    1.51 -
    1.52 -
    1.53 -
    1.54 -  ///Adds a Petersen graph to \c G.
    1.55 -
    1.56 -  ///Adds a Petersen graph to \c G.
    1.57 -  ///\return The nodes and edges of the generated graph.
    1.58 -
    1.59 -  template<typename Digraph>
    1.60 -  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
    1.61 -  {
    1.62 -    PetStruct<Digraph> n;
    1.63 -
    1.64 -    for(int i=0;i<num;i++) {
    1.65 -      n.outer.push_back(G.addNode());
    1.66 -      n.inner.push_back(G.addNode());
    1.67 -    }
    1.68 -
    1.69 -    for(int i=0;i<num;i++) {
    1.70 -      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
    1.71 -      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
    1.72 -      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
    1.73 -    }
    1.74 -    return n;
    1.75 -  }
    1.76 -
    1.77 -  /// \brief Adds to the digraph the reverse pair of all edges.
    1.78 -  ///
    1.79 -  /// Adds to the digraph the reverse pair of all edges.
    1.80 -  ///
    1.81 -  template<class Digraph> 
    1.82 -  void bidirDigraph(Digraph &G)
    1.83 -  {
    1.84 -    typedef typename Digraph::Arc Arc;
    1.85 -    typedef typename Digraph::ArcIt ArcIt;
    1.86 -  
    1.87 -    std::vector<Arc> ee;
    1.88 -  
    1.89 -    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
    1.90 -
    1.91 -    for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
    1.92 -      G.addArc(G.target(*p),G.source(*p));
    1.93 -  }
    1.94 -
    1.95 -
    1.96 -  /// \brief Checks the bidirectioned Petersen graph.
    1.97 -  ///
    1.98 -  ///  Checks the bidirectioned Petersen graph.
    1.99 -  ///
   1.100 -  template<class Digraph> 
   1.101 -  void checkBidirPetersen(Digraph &G, int num = 5)
   1.102 -  {
   1.103 -    typedef typename Digraph::Node Node;
   1.104 -
   1.105 -    typedef typename Digraph::ArcIt ArcIt;
   1.106 -    typedef typename Digraph::NodeIt NodeIt;
   1.107 -
   1.108 -    checkDigraphNodeList(G, 2 * num);
   1.109 -    checkDigraphArcList(G, 6 * num);
   1.110 -
   1.111 -    for(NodeIt n(G);n!=INVALID;++n) {
   1.112 -      checkDigraphInArcList(G, n, 3);
   1.113 -      checkDigraphOutArcList(G, n, 3);
   1.114 -    }  
   1.115 -  }
   1.116 -
   1.117 -  template<class Digraph> void checkDigraphNodeList(Digraph &G, int nn)
   1.118 -  {
   1.119 -    typename Digraph::NodeIt n(G);
   1.120 -    for(int i=0;i<nn;i++) {
   1.121 -      check(n!=INVALID,"Wrong Node list linking.");
   1.122 -      ++n;
   1.123 -    }
   1.124 -    check(n==INVALID,"Wrong Node list linking.");
   1.125 -  }
   1.126 -
   1.127 -  template<class Digraph>
   1.128 -  void checkDigraphArcList(Digraph &G, int nn)
   1.129 -  {
   1.130 -    typedef typename Digraph::ArcIt ArcIt;
   1.131 -
   1.132 -    ArcIt e(G);
   1.133 -    for(int i=0;i<nn;i++) {
   1.134 -      check(e!=INVALID,"Wrong Arc list linking.");
   1.135 -      ++e;
   1.136 -    }
   1.137 -    check(e==INVALID,"Wrong Arc list linking.");
   1.138 -  }
   1.139 -
   1.140 -  template<class Digraph> 
   1.141 -  void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn)
   1.142 -  {
   1.143 -    typename Digraph::OutArcIt e(G,n);
   1.144 -    for(int i=0;i<nn;i++) {
   1.145 -      check(e!=INVALID,"Wrong OutArc list linking.");
   1.146 -      check(n==G.source(e), "Wrong OutArc list linking.");
   1.147 -      ++e;
   1.148 -    }
   1.149 -    check(e==INVALID,"Wrong OutArc list linking.");
   1.150 -  }
   1.151 -
   1.152 -  template<class Digraph> void 
   1.153 -  checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn)
   1.154 -  {
   1.155 -    typename Digraph::InArcIt e(G,n);
   1.156 -    for(int i=0;i<nn;i++) {
   1.157 -      check(e!=INVALID,"Wrong InArc list linking.");
   1.158 -      check(n==G.target(e), "Wrong InArc list linking.");
   1.159 -      ++e;
   1.160 -    }
   1.161 -    check(e==INVALID,"Wrong InArc list linking.");
   1.162 -  }
   1.163 -
   1.164 -  template <class Digraph> 
   1.165 -  void checkDigraph() {
   1.166 -    const int num = 5;
   1.167 -    Digraph G;
   1.168 -    addPetersen(G, num);
   1.169 -    bidirDigraph(G);
   1.170 -    checkBidirPetersen(G, num);
   1.171 -  }
   1.172 -
   1.173 -  template <class Digraph> 
   1.174 -  void checkDigraphIterators(const Digraph& digraph) {
   1.175 -    typedef typename Digraph::Node Node;
   1.176 -    typedef typename Digraph::NodeIt NodeIt;
   1.177 -    typedef typename Digraph::Arc Arc;
   1.178 -    typedef typename Digraph::ArcIt ArcIt;
   1.179 -    typedef typename Digraph::InArcIt InArcIt;
   1.180 -    typedef typename Digraph::OutArcIt OutArcIt;
   1.181 -    //    typedef ConArcIt<Digraph> ConArcIt;
   1.182 -  }
   1.183 -
   1.184 -  ///\file
   1.185 -  ///\todo Check target(), source() as well;
   1.186 -
   1.187 -  
   1.188 -} //namespace lemon
   1.189 -
   1.190 -
   1.191 -#endif