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