test/graph_test.h
 changeset 171 02f4d5d9bfd7 child 209 765619b7cbb2
```     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/graph_test.h	Sun Jun 15 22:05:23 2008 +0200
1.3 @@ -0,0 +1,262 @@
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 +namespace lemon {
1.29 +
1.30 +  template<class Graph>
1.31 +  void checkGraphNodeList(const Graph &G, int cnt)
1.32 +  {
1.33 +    typename Graph::NodeIt n(G);
1.34 +    for(int i=0;i<cnt;i++) {
1.35 +      check(n!=INVALID,"Wrong Node list linking.");
1.36 +      ++n;
1.37 +    }
1.38 +    check(n==INVALID,"Wrong Node list linking.");
1.39 +    check(countNodes(G)==cnt,"Wrong Node number.");
1.40 +  }
1.41 +
1.42 +  template<class Graph>
1.43 +  void checkGraphArcList(const Graph &G, int cnt)
1.44 +  {
1.45 +    typename Graph::ArcIt e(G);
1.46 +    for(int i=0;i<cnt;i++) {
1.47 +      check(e!=INVALID,"Wrong Arc list linking.");
1.48 +      ++e;
1.49 +    }
1.50 +    check(e==INVALID,"Wrong Arc list linking.");
1.51 +    check(countArcs(G)==cnt,"Wrong Arc number.");
1.52 +  }
1.53 +
1.54 +  template<class Graph>
1.55 +  void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
1.56 +  {
1.57 +    typename Graph::OutArcIt e(G,n);
1.58 +    for(int i=0;i<cnt;i++) {
1.59 +      check(e!=INVALID,"Wrong OutArc list linking.");
1.60 +      check(n==G.source(e),"Wrong OutArc list linking.");
1.61 +      ++e;
1.62 +    }
1.63 +    check(e==INVALID,"Wrong OutArc list linking.");
1.64 +    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
1.65 +  }
1.66 +
1.67 +  template<class Graph>
1.68 +  void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
1.69 +  {
1.70 +    typename Graph::InArcIt e(G,n);
1.71 +    for(int i=0;i<cnt;i++) {
1.72 +      check(e!=INVALID,"Wrong InArc list linking.");
1.73 +      check(n==G.target(e),"Wrong InArc list linking.");
1.74 +      ++e;
1.75 +    }
1.76 +    check(e==INVALID,"Wrong InArc list linking.");
1.77 +    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
1.78 +  }
1.79 +
1.80 +  template<class Graph>
1.81 +  void checkGraphEdgeList(const Graph &G, int cnt)
1.82 +  {
1.83 +    typename Graph::EdgeIt e(G);
1.84 +    for(int i=0;i<cnt;i++) {
1.85 +      check(e!=INVALID,"Wrong Edge list linking.");
1.86 +      ++e;
1.87 +    }
1.88 +    check(e==INVALID,"Wrong Edge list linking.");
1.89 +    check(countEdges(G)==cnt,"Wrong Edge number.");
1.90 +  }
1.91 +
1.92 +  template<class Graph>
1.93 +  void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
1.94 +  {
1.95 +    typename Graph::IncEdgeIt e(G,n);
1.96 +    for(int i=0;i<cnt;i++) {
1.97 +      check(e!=INVALID,"Wrong IncEdge list linking.");
1.98 +      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
1.99 +      ++e;
1.100 +    }
1.101 +    check(e==INVALID,"Wrong IncEdge list linking.");
1.102 +    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
1.103 +  }
1.104 +
1.105 +  template <class Digraph>
1.106 +  void checkDigraphIterators() {
1.107 +    typedef typename Digraph::Node Node;
1.108 +    typedef typename Digraph::NodeIt NodeIt;
1.109 +    typedef typename Digraph::Arc Arc;
1.110 +    typedef typename Digraph::ArcIt ArcIt;
1.111 +    typedef typename Digraph::InArcIt InArcIt;
1.112 +    typedef typename Digraph::OutArcIt OutArcIt;
1.113 +  }
1.114 +
1.115 +  template <class Graph>
1.116 +  void checkGraphIterators() {
1.117 +    checkDigraphIterators<Graph>();
1.118 +    typedef typename Graph::Edge Edge;
1.119 +    typedef typename Graph::EdgeIt EdgeIt;
1.120 +    typedef typename Graph::IncEdgeIt IncEdgeIt;
1.121 +  }
1.122 +
1.123 +  // Structure returned by addPetersen()
1.124 +  template<class Digraph>
1.125 +  struct PetStruct
1.126 +  {
1.127 +    // Vector containing the outer nodes
1.128 +    std::vector<typename Digraph::Node> outer;
1.129 +    // Vector containing the inner nodes
1.130 +    std::vector<typename Digraph::Node> inner;
1.131 +    // Vector containing the arcs of the inner circle
1.132 +    std::vector<typename Digraph::Arc> incir;
1.133 +    // Vector containing the arcs of the outer circle
1.134 +    std::vector<typename Digraph::Arc> outcir;
1.135 +    // Vector containing the chord arcs
1.136 +    std::vector<typename Digraph::Arc> chords;
1.137 +  };
1.138 +
1.139 +  // Adds the reverse pair of all arcs to a digraph
1.140 +  template<class Digraph>
1.141 +  void bidirDigraph(Digraph &G)
1.142 +  {
1.143 +    typedef typename Digraph::Arc Arc;
1.144 +    typedef typename Digraph::ArcIt ArcIt;
1.145 +
1.146 +    std::vector<Arc> ee;
1.147 +
1.148 +    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
1.149 +
1.150 +    for(int i=0;i<int(ee.size());++i)
1.152 +  }
1.153 +
1.154 +  // Adds a Petersen digraph to G.
1.155 +  // Returns the nodes and arcs of the generated digraph.
1.156 +  template<typename Digraph>
1.157 +  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
1.158 +  {
1.159 +    PetStruct<Digraph> n;
1.160 +
1.161 +    for(int i=0;i<num;i++) {
1.164 +    }
1.165 +
1.166 +    for(int i=0;i<num;i++) {
1.170 +    }
1.171 +
1.172 +    return n;
1.173 +  }
1.174 +
1.175 +  // Checks the bidirectioned Petersen digraph
1.176 +  template<class Digraph>
1.177 +  void checkBidirPetersen(const Digraph &G, int num = 5)
1.178 +  {
1.179 +    typedef typename Digraph::NodeIt NodeIt;
1.180 +
1.181 +    checkGraphNodeList(G, 2 * num);
1.182 +    checkGraphArcList(G, 6 * num);
1.183 +
1.184 +    for(NodeIt n(G);n!=INVALID;++n) {
1.185 +      checkGraphInArcList(G, n, 3);
1.186 +      checkGraphOutArcList(G, n, 3);
1.187 +    }
1.188 +  }
1.189 +
1.190 +  // Structure returned by addUPetersen()
1.191 +  template<class Graph>
1.192 +  struct UPetStruct
1.193 +  {
1.194 +    // Vector containing the outer nodes
1.195 +    std::vector<typename Graph::Node> outer;
1.196 +    // Vector containing the inner nodes
1.197 +    std::vector<typename Graph::Node> inner;
1.198 +    // Vector containing the edges of the inner circle
1.199 +    std::vector<typename Graph::Edge> incir;
1.200 +    // Vector containing the edges of the outer circle
1.201 +    std::vector<typename Graph::Edge> outcir;
1.202 +    // Vector containing the chord edges
1.203 +    std::vector<typename Graph::Edge> chords;
1.204 +  };
1.205 +
1.206 +  // Adds a Petersen graph to \c G.
1.207 +  // Returns the nodes and edges of the generated graph.
1.208 +  template<typename Graph>
1.209 +  UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
1.210 +  {
1.211 +    UPetStruct<Graph> n;
1.212 +
1.213 +    for(int i=0;i<num;i++) {
1.216 +    }
1.217 +
1.218 +    for(int i=0;i<num;i++) {
1.222 +    }
1.223 +
1.224 +    return n;
1.225 +  }
1.226 +
1.227 +  // Checks the undirected Petersen graph
1.228 +  template<class Graph>
1.229 +  void checkUndirPetersen(const Graph &G, int num = 5)
1.230 +  {
1.231 +    typedef typename Graph::NodeIt NodeIt;
1.232 +
1.233 +    checkGraphNodeList(G, 2 * num);
1.234 +    checkGraphEdgeList(G, 3 * num);
1.235 +    checkGraphArcList(G, 6 * num);
1.236 +
1.237 +    for(NodeIt n(G);n!=INVALID;++n) {
1.238 +      checkGraphIncEdgeList(G, n, 3);
1.239 +    }
1.240 +  }
1.241 +
1.242 +  template <class Digraph>
1.243 +  void checkDigraph() {
1.244 +    const int num = 5;
1.245 +    Digraph G;
1.246 +    checkGraphNodeList(G, 0);
1.247 +    checkGraphArcList(G, 0);
1.249 +    bidirDigraph(G);
1.250 +    checkBidirPetersen(G, num);
1.251 +  }
1.252 +
1.253 +  template <class Graph>
1.254 +  void checkGraph() {
1.255 +    const int num = 5;
1.256 +    Graph G;
1.257 +    checkGraphNodeList(G, 0);
1.258 +    checkGraphEdgeList(G, 0);