1.1 --- a/test/CMakeLists.txt Sun Jun 15 22:03:33 2008 +0200
1.2 +++ b/test/CMakeLists.txt Sun Jun 15 22:05:23 2008 +0200
1.3 @@ -11,10 +11,11 @@
1.4 dim_test
1.5 error_test
1.6 graph_test
1.7 + graph_utils_test
1.8 kruskal_test
1.9 maps_test
1.10 + path_test
1.11 random_test
1.12 - path_test
1.13 time_measure_test
1.14 unionfind_test)
1.15
2.1 --- a/test/Makefile.am Sun Jun 15 22:03:33 2008 +0200
2.2 +++ b/test/Makefile.am Sun Jun 15 22:05:23 2008 +0200
2.3 @@ -2,10 +2,9 @@
2.4 test/CMakeLists.txt
2.5
2.6 noinst_HEADERS += \
2.7 - test/digraph_test.h \
2.8 - test/graph_utils_test.h \
2.9 + test/graph_test.h \
2.10 test/heap_test.h \
2.11 - test/map_test.h \
2.12 + test/graph_maps_test.h \
2.13 test/test_tools.h
2.14
2.15 check_PROGRAMS += \
3.1 --- a/test/bfs_test.cc Sun Jun 15 22:03:33 2008 +0200
3.2 +++ b/test/bfs_test.cc Sun Jun 15 22:05:23 2008 +0200
3.3 @@ -16,32 +16,25 @@
3.4 *
3.5 */
3.6
3.7 -#include "test_tools.h"
3.8 -//#include <lemon/smart_graph.h>
3.9 +#include <lemon/concepts/digraph.h>
3.10 +#include <lemon/smart_graph.h>
3.11 #include <lemon/list_graph.h>
3.12 #include <lemon/bfs.h>
3.13 #include <lemon/path.h>
3.14 -#include<lemon/concepts/digraph.h>
3.15 +
3.16 +#include "graph_test.h"
3.17 +#include "test_tools.h"
3.18
3.19 using namespace lemon;
3.20
3.21 -const int PET_SIZE =5;
3.22 -
3.23 -
3.24 -void check_Bfs_Compile()
3.25 +void checkBfsCompile()
3.26 {
3.27 typedef concepts::Digraph Digraph;
3.28 -
3.29 - typedef Digraph::Arc Arc;
3.30 - typedef Digraph::Node Node;
3.31 - typedef Digraph::ArcIt ArcIt;
3.32 - typedef Digraph::NodeIt NodeIt;
3.33 -
3.34 typedef Bfs<Digraph> BType;
3.35
3.36 Digraph G;
3.37 - Node n;
3.38 - Arc e;
3.39 + Digraph::Node n;
3.40 + Digraph::Arc e;
3.41 int l;
3.42 bool b;
3.43 BType::DistMap d(G);
3.44 @@ -63,16 +56,12 @@
3.45 Path<Digraph> pp = bfs_test.path(n);
3.46 }
3.47
3.48 -void check_Bfs_Function_Compile()
3.49 +void checkBfsFunctionCompile()
3.50 {
3.51 typedef int VType;
3.52 typedef concepts::Digraph Digraph;
3.53 -
3.54 typedef Digraph::Arc Arc;
3.55 typedef Digraph::Node Node;
3.56 - typedef Digraph::ArcIt ArcIt;
3.57 - typedef Digraph::NodeIt NodeIt;
3.58 - typedef concepts::ReadMap<Arc,VType> LengthMap;
3.59
3.60 Digraph g;
3.61 bfs(g,Node()).run();
3.62 @@ -83,24 +72,15 @@
3.63 .reachedMap(concepts::ReadWriteMap<Node,bool>())
3.64 .processedMap(concepts::WriteMap<Node,bool>())
3.65 .run(Node());
3.66 -
3.67 }
3.68
3.69 -int main()
3.70 -{
3.71 -
3.72 - // typedef SmartDigraph Digraph;
3.73 - typedef ListDigraph Digraph;
3.74 -
3.75 - typedef Digraph::Arc Arc;
3.76 - typedef Digraph::Node Node;
3.77 - typedef Digraph::ArcIt ArcIt;
3.78 - typedef Digraph::NodeIt NodeIt;
3.79 - typedef Digraph::ArcMap<int> LengthMap;
3.80 +template <class Digraph>
3.81 +void checkBfs() {
3.82 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
3.83
3.84 Digraph G;
3.85 Node s, t;
3.86 - PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
3.87 + PetStruct<Digraph> ps = addPetersen(G, 5);
3.88
3.89 s=ps.outer[2];
3.90 t=ps.inner[0];
3.91 @@ -108,10 +88,10 @@
3.92 Bfs<Digraph> bfs_test(G);
3.93 bfs_test.run(s);
3.94
3.95 - check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
3.96 + check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
3.97
3.98 Path<Digraph> p = bfs_test.path(t);
3.99 - check(p.length()==3,"getPath() found a wrong path.");
3.100 + check(p.length()==3,"path() found a wrong path.");
3.101 check(checkPath(G, p),"path() found a wrong path.");
3.102 check(pathSource(G, p) == s,"path() found a wrong path.");
3.103 check(pathTarget(G, p) == t,"path() found a wrong path.");
3.104 @@ -139,3 +119,9 @@
3.105 }
3.106 }
3.107
3.108 +int main()
3.109 +{
3.110 + checkBfs<ListDigraph>();
3.111 + checkBfs<SmartDigraph>();
3.112 + return 0;
3.113 +}
4.1 --- a/test/counter_test.cc Sun Jun 15 22:03:33 2008 +0200
4.2 +++ b/test/counter_test.cc Sun Jun 15 22:05:23 2008 +0200
4.3 @@ -17,50 +17,75 @@
4.4 */
4.5
4.6 #include <lemon/counter.h>
4.7 +#include <vector>
4.8
4.9 -///\file \brief Test cases for time_measure.h
4.10 -///
4.11 -///\todo To be extended
4.12 +using namespace lemon;
4.13
4.14 +template <typename T>
4.15 +void bubbleSort(std::vector<T>& v) {
4.16 + Counter op("Bubble Sort - Operations: ");
4.17 + Counter::NoSubCounter as(op, "Assignments: ");
4.18 + Counter::NoSubCounter co(op, "Comparisons: ");
4.19 + for (int i = v.size()-1; i > 0; --i) {
4.20 + for (int j = 0; j < i; ++j) {
4.21 + if (v[j] > v[j+1]) {
4.22 + T tmp = v[j];
4.23 + v[j] = v[j+1];
4.24 + v[j+1] = tmp;
4.25 + as += 3;
4.26 + }
4.27 + ++co;
4.28 + }
4.29 + }
4.30 +}
4.31
4.32 -int fibonacci(int f)
4.33 -{
4.34 - static lemon::Counter count("Fibonacci steps: ");
4.35 - count++;
4.36 - if(f<1) return 0;
4.37 - else if(f==1) return 1;
4.38 - else return fibonacci(f-1)+fibonacci(f-2);
4.39 +template <typename T>
4.40 +void insertionSort(std::vector<T>& v) {
4.41 + Counter op("Insertion Sort - Operations: ");
4.42 + Counter::NoSubCounter as(op, "Assignments: ");
4.43 + Counter::NoSubCounter co(op, "Comparisons: ");
4.44 + for (int i = 1; i < int(v.size()); ++i) {
4.45 + T value = v[i];
4.46 + ++as;
4.47 + int j = i;
4.48 + while (j > 0 && v[j-1] > value) {
4.49 + v[j] = v[j-1];
4.50 + --j;
4.51 + ++co; ++as;
4.52 + }
4.53 + v[j] = value;
4.54 + ++as;
4.55 + }
4.56 +}
4.57 +
4.58 +template <typename MyCounter>
4.59 +void counterTest() {
4.60 + MyCounter c("Main Counter: ");
4.61 + c++;
4.62 + typename MyCounter::SubCounter d(c, "SubCounter: ");
4.63 + d++;
4.64 + typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ");
4.65 + e++;
4.66 + d+=3;
4.67 + c-=4;
4.68 + e-=2;
4.69 + c.reset(2);
4.70 + c.reset();
4.71 +}
4.72 +
4.73 +void init(std::vector<int>& v) {
4.74 + v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;
4.75 + v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70;
4.76 }
4.77
4.78 int main()
4.79 {
4.80 - fibonacci(10);
4.81 + counterTest<Counter>();
4.82 + counterTest<NoCounter>();
4.83
4.84 - {
4.85 - typedef lemon::Counter MyCounter;
4.86 - MyCounter c("Main counter: ");
4.87 - c++;
4.88 - c++;
4.89 - MyCounter::SubCounter d(c,"Subcounter: ");
4.90 - d++;
4.91 - d++;
4.92 - MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
4.93 - e++;
4.94 - e++;
4.95 - }
4.96 -
4.97 - {
4.98 - typedef lemon::NoCounter MyCounter;
4.99 - MyCounter c("Main counter: ");
4.100 - c++;
4.101 - c++;
4.102 - MyCounter::SubCounter d(c,"Subcounter: ");
4.103 - d++;
4.104 - d++;
4.105 - MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
4.106 - e++;
4.107 - e++;
4.108 - }
4.109 + std::vector<int> x(10);
4.110 + init(x); bubbleSort(x);
4.111 + init(x); insertionSort(x);
4.112
4.113 return 0;
4.114 }
5.1 --- a/test/dfs_test.cc Sun Jun 15 22:03:33 2008 +0200
5.2 +++ b/test/dfs_test.cc Sun Jun 15 22:05:23 2008 +0200
5.3 @@ -16,32 +16,25 @@
5.4 *
5.5 */
5.6
5.7 -#include "test_tools.h"
5.8 -// #include <lemon/smart_graph.h>
5.9 +#include <lemon/concepts/digraph.h>
5.10 +#include <lemon/smart_graph.h>
5.11 #include <lemon/list_graph.h>
5.12 #include <lemon/dfs.h>
5.13 #include <lemon/path.h>
5.14 -#include <lemon/concepts/digraph.h>
5.15 +
5.16 +#include "graph_test.h"
5.17 +#include "test_tools.h"
5.18
5.19 using namespace lemon;
5.20
5.21 -const int PET_SIZE =5;
5.22 -
5.23 -
5.24 -void check_Dfs_SmartDigraph_Compile()
5.25 +void checkDfsCompile()
5.26 {
5.27 typedef concepts::Digraph Digraph;
5.28 -
5.29 - typedef Digraph::Arc Arc;
5.30 - typedef Digraph::Node Node;
5.31 - typedef Digraph::ArcIt ArcIt;
5.32 - typedef Digraph::NodeIt NodeIt;
5.33 -
5.34 typedef Dfs<Digraph> DType;
5.35
5.36 Digraph G;
5.37 - Node n;
5.38 - Arc e;
5.39 + Digraph::Node n;
5.40 + Digraph::Arc e;
5.41 int l;
5.42 bool b;
5.43 DType::DistMap d(G);
5.44 @@ -63,17 +56,12 @@
5.45 Path<Digraph> pp = dfs_test.path(n);
5.46 }
5.47
5.48 -
5.49 -void check_Dfs_Function_Compile()
5.50 +void checkDfsFunctionCompile()
5.51 {
5.52 typedef int VType;
5.53 typedef concepts::Digraph Digraph;
5.54 -
5.55 typedef Digraph::Arc Arc;
5.56 typedef Digraph::Node Node;
5.57 - typedef Digraph::ArcIt ArcIt;
5.58 - typedef Digraph::NodeIt NodeIt;
5.59 - typedef concepts::ReadMap<Arc,VType> LengthMap;
5.60
5.61 Digraph g;
5.62 dfs(g,Node()).run();
5.63 @@ -83,25 +71,16 @@
5.64 .distMap(concepts::WriteMap<Node,VType>())
5.65 .reachedMap(concepts::ReadWriteMap<Node,bool>())
5.66 .processedMap(concepts::WriteMap<Node,bool>())
5.67 - .run(Node());
5.68 -
5.69 + .run(Node());
5.70 }
5.71
5.72 -int main()
5.73 -{
5.74 -
5.75 - // typedef SmartDigraph Digraph;
5.76 - typedef ListDigraph Digraph;
5.77 -
5.78 - typedef Digraph::Arc Arc;
5.79 - typedef Digraph::Node Node;
5.80 - typedef Digraph::ArcIt ArcIt;
5.81 - typedef Digraph::NodeIt NodeIt;
5.82 - typedef Digraph::ArcMap<int> LengthMap;
5.83 +template <class Digraph>
5.84 +void checkDfs() {
5.85 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
5.86
5.87 Digraph G;
5.88 Node s, t;
5.89 - PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
5.90 + PetStruct<Digraph> ps = addPetersen(G, 5);
5.91
5.92 s=ps.outer[2];
5.93 t=ps.inner[0];
5.94 @@ -110,7 +89,7 @@
5.95 dfs_test.run(s);
5.96
5.97 Path<Digraph> p = dfs_test.path(t);
5.98 - check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
5.99 + check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
5.100 check(checkPath(G, p),"path() found a wrong path.");
5.101 check(pathSource(G, p) == s,"path() found a wrong path.");
5.102 check(pathTarget(G, p) == t,"path() found a wrong path.");
5.103 @@ -128,3 +107,9 @@
5.104 }
5.105 }
5.106
5.107 +int main()
5.108 +{
5.109 + checkDfs<ListDigraph>();
5.110 + checkDfs<SmartDigraph>();
5.111 + return 0;
5.112 +}
6.1 --- a/test/digraph_test.cc Sun Jun 15 22:03:33 2008 +0200
6.2 +++ b/test/digraph_test.cc Sun Jun 15 22:05:23 2008 +0200
6.3 @@ -16,26 +16,21 @@
6.4 *
6.5 */
6.6
6.7 -#include <iostream>
6.8 -#include <vector>
6.9 -
6.10 #include <lemon/concepts/digraph.h>
6.11 #include <lemon/list_graph.h>
6.12 -//#include <lemon/smart_graph.h>
6.13 +#include <lemon/smart_graph.h>
6.14 //#include <lemon/full_graph.h>
6.15 //#include <lemon/hypercube_graph.h>
6.16
6.17 #include "test_tools.h"
6.18 -#include "digraph_test.h"
6.19 -#include "map_test.h"
6.20 -
6.21 +#include "graph_test.h"
6.22 +#include "graph_maps_test.h"
6.23
6.24 using namespace lemon;
6.25 using namespace lemon::concepts;
6.26
6.27 -
6.28 -int main() {
6.29 - { // checking digraph components
6.30 +void check_concepts() {
6.31 + { // Checking digraph components
6.32 checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
6.33
6.34 checkConcept<IDableDigraphComponent<>,
6.35 @@ -46,37 +41,104 @@
6.36
6.37 checkConcept<MappableDigraphComponent<>,
6.38 MappableDigraphComponent<> >();
6.39 -
6.40 }
6.41 - { // checking skeleton digraphs
6.42 + { // Checking skeleton digraph
6.43 checkConcept<Digraph, Digraph>();
6.44 }
6.45 - { // checking list digraph
6.46 - checkConcept<Digraph, ListDigraph >();
6.47 + { // Checking ListDigraph
6.48 + checkConcept<Digraph, ListDigraph>();
6.49 checkConcept<AlterableDigraphComponent<>, ListDigraph>();
6.50 checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
6.51 checkConcept<ClearableDigraphComponent<>, ListDigraph>();
6.52 checkConcept<ErasableDigraphComponent<>, ListDigraph>();
6.53 + checkDigraphIterators<ListDigraph>();
6.54 + }
6.55 + { // Checking SmartDigraph
6.56 + checkConcept<Digraph, SmartDigraph>();
6.57 + checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
6.58 + checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
6.59 + checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
6.60 + checkDigraphIterators<SmartDigraph>();
6.61 + }
6.62 +// { // Checking FullDigraph
6.63 +// checkConcept<Digraph, FullDigraph>();
6.64 +// checkDigraphIterators<FullDigraph>();
6.65 +// }
6.66 +// { // Checking HyperCubeDigraph
6.67 +// checkConcept<Digraph, HyperCubeDigraph>();
6.68 +// checkDigraphIterators<HyperCubeDigraph>();
6.69 +// }
6.70 +}
6.71
6.72 +template <typename Digraph>
6.73 +void check_graph_validity() {
6.74 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
6.75 + Digraph g;
6.76 +
6.77 + Node
6.78 + n1 = g.addNode(),
6.79 + n2 = g.addNode(),
6.80 + n3 = g.addNode();
6.81 +
6.82 + Arc
6.83 + e1 = g.addArc(n1, n2),
6.84 + e2 = g.addArc(n2, n3);
6.85 +
6.86 + check(g.valid(n1), "Wrong validity check");
6.87 + check(g.valid(e1), "Wrong validity check");
6.88 +
6.89 + check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
6.90 + check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
6.91 +}
6.92 +
6.93 +template <typename Digraph>
6.94 +void check_graph_validity_erase() {
6.95 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
6.96 + Digraph g;
6.97 +
6.98 + Node
6.99 + n1 = g.addNode(),
6.100 + n2 = g.addNode(),
6.101 + n3 = g.addNode();
6.102 +
6.103 + Arc
6.104 + e1 = g.addArc(n1, n2),
6.105 + e2 = g.addArc(n2, n3);
6.106 +
6.107 + check(g.valid(n1), "Wrong validity check");
6.108 + check(g.valid(e1), "Wrong validity check");
6.109 +
6.110 + g.erase(n1);
6.111 +
6.112 + check(!g.valid(n1), "Wrong validity check");
6.113 + check(g.valid(n2), "Wrong validity check");
6.114 + check(g.valid(n3), "Wrong validity check");
6.115 + check(!g.valid(e1), "Wrong validity check");
6.116 + check(g.valid(e2), "Wrong validity check");
6.117 +
6.118 + check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
6.119 + check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
6.120 +}
6.121 +
6.122 +void check_digraphs() {
6.123 + { // Checking ListDigraph
6.124 checkDigraph<ListDigraph>();
6.125 checkGraphNodeMap<ListDigraph>();
6.126 checkGraphArcMap<ListDigraph>();
6.127 +
6.128 + check_graph_validity_erase<ListDigraph>();
6.129 }
6.130 -// { // checking smart digraph
6.131 -// checkConcept<Digraph, SmartDigraph >();
6.132 + { // Checking SmartDigraph
6.133 + checkDigraph<SmartDigraph>();
6.134 + checkGraphNodeMap<SmartDigraph>();
6.135 + checkGraphArcMap<SmartDigraph>();
6.136
6.137 -// checkDigraph<SmartDigraph>();
6.138 -// checkDigraphNodeMap<SmartDigraph>();
6.139 -// checkDigraphArcMap<SmartDigraph>();
6.140 -// }
6.141 -// { // checking full digraph
6.142 -// checkConcept<Digraph, FullDigraph >();
6.143 -// }
6.144 -// { // checking full digraph
6.145 -// checkConcept<Digraph, HyperCubeDigraph >();
6.146 -// }
6.147 + check_graph_validity<SmartDigraph>();
6.148 + }
6.149 +}
6.150
6.151 - std::cout << __FILE__ ": All tests passed.\n";
6.152 -
6.153 +int main() {
6.154 + check_concepts();
6.155 + check_digraphs();
6.156 return 0;
6.157 }
7.1 --- a/test/digraph_test.h Sun Jun 15 22:03:33 2008 +0200
7.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
7.3 @@ -1,188 +0,0 @@
7.4 -/* -*- C++ -*-
7.5 - *
7.6 - * This file is a part of LEMON, a generic C++ optimization library
7.7 - *
7.8 - * Copyright (C) 2003-2008
7.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 - *
7.12 - * Permission to use, modify and distribute this software is granted
7.13 - * provided that this copyright notice appears in all copies. For
7.14 - * precise terms see the accompanying LICENSE file.
7.15 - *
7.16 - * This software is provided "AS IS" with no warranty of any kind,
7.17 - * express or implied, and with no claim as to its suitability for any
7.18 - * purpose.
7.19 - *
7.20 - */
7.21 -
7.22 -#ifndef LEMON_TEST_GRAPH_TEST_H
7.23 -#define LEMON_TEST_GRAPH_TEST_H
7.24 -
7.25 -//#include <lemon/graph_utils.h>
7.26 -#include "test_tools.h"
7.27 -
7.28 -//! \ingroup misc
7.29 -//! \file
7.30 -//! \brief Some utility and test cases to test digraph classes.
7.31 -namespace lemon {
7.32 -
7.33 - ///Structure returned by \ref addPetersen().
7.34 -
7.35 - ///Structure returned by \ref addPetersen().
7.36 - ///
7.37 - template<class Digraph>
7.38 - struct PetStruct
7.39 - {
7.40 - ///Vector containing the outer nodes.
7.41 - std::vector<typename Digraph::Node> outer;
7.42 - ///Vector containing the inner nodes.
7.43 - std::vector<typename Digraph::Node> inner;
7.44 - ///Vector containing the edges of the inner circle.
7.45 - std::vector<typename Digraph::Arc> incir;
7.46 - ///Vector containing the edges of the outer circle.
7.47 - std::vector<typename Digraph::Arc> outcir;
7.48 - ///Vector containing the chord edges.
7.49 - std::vector<typename Digraph::Arc> chords;
7.50 - };
7.51 -
7.52 -
7.53 -
7.54 - ///Adds a Petersen graph to \c G.
7.55 -
7.56 - ///Adds a Petersen graph to \c G.
7.57 - ///\return The nodes and edges of the generated graph.
7.58 -
7.59 - template<typename Digraph>
7.60 - PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
7.61 - {
7.62 - PetStruct<Digraph> n;
7.63 -
7.64 - for(int i=0;i<num;i++) {
7.65 - n.outer.push_back(G.addNode());
7.66 - n.inner.push_back(G.addNode());
7.67 - }
7.68 -
7.69 - for(int i=0;i<num;i++) {
7.70 - n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
7.71 - n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
7.72 - n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
7.73 - }
7.74 - return n;
7.75 - }
7.76 -
7.77 - /// \brief Adds to the digraph the reverse pair of all edges.
7.78 - ///
7.79 - /// Adds to the digraph the reverse pair of all edges.
7.80 - ///
7.81 - template<class Digraph>
7.82 - void bidirDigraph(Digraph &G)
7.83 - {
7.84 - typedef typename Digraph::Arc Arc;
7.85 - typedef typename Digraph::ArcIt ArcIt;
7.86 -
7.87 - std::vector<Arc> ee;
7.88 -
7.89 - for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
7.90 -
7.91 - for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
7.92 - G.addArc(G.target(*p),G.source(*p));
7.93 - }
7.94 -
7.95 -
7.96 - /// \brief Checks the bidirectioned Petersen graph.
7.97 - ///
7.98 - /// Checks the bidirectioned Petersen graph.
7.99 - ///
7.100 - template<class Digraph>
7.101 - void checkBidirPetersen(Digraph &G, int num = 5)
7.102 - {
7.103 - typedef typename Digraph::Node Node;
7.104 -
7.105 - typedef typename Digraph::ArcIt ArcIt;
7.106 - typedef typename Digraph::NodeIt NodeIt;
7.107 -
7.108 - checkDigraphNodeList(G, 2 * num);
7.109 - checkDigraphArcList(G, 6 * num);
7.110 -
7.111 - for(NodeIt n(G);n!=INVALID;++n) {
7.112 - checkDigraphInArcList(G, n, 3);
7.113 - checkDigraphOutArcList(G, n, 3);
7.114 - }
7.115 - }
7.116 -
7.117 - template<class Digraph> void checkDigraphNodeList(Digraph &G, int nn)
7.118 - {
7.119 - typename Digraph::NodeIt n(G);
7.120 - for(int i=0;i<nn;i++) {
7.121 - check(n!=INVALID,"Wrong Node list linking.");
7.122 - ++n;
7.123 - }
7.124 - check(n==INVALID,"Wrong Node list linking.");
7.125 - }
7.126 -
7.127 - template<class Digraph>
7.128 - void checkDigraphArcList(Digraph &G, int nn)
7.129 - {
7.130 - typedef typename Digraph::ArcIt ArcIt;
7.131 -
7.132 - ArcIt e(G);
7.133 - for(int i=0;i<nn;i++) {
7.134 - check(e!=INVALID,"Wrong Arc list linking.");
7.135 - ++e;
7.136 - }
7.137 - check(e==INVALID,"Wrong Arc list linking.");
7.138 - }
7.139 -
7.140 - template<class Digraph>
7.141 - void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn)
7.142 - {
7.143 - typename Digraph::OutArcIt e(G,n);
7.144 - for(int i=0;i<nn;i++) {
7.145 - check(e!=INVALID,"Wrong OutArc list linking.");
7.146 - check(n==G.source(e), "Wrong OutArc list linking.");
7.147 - ++e;
7.148 - }
7.149 - check(e==INVALID,"Wrong OutArc list linking.");
7.150 - }
7.151 -
7.152 - template<class Digraph> void
7.153 - checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn)
7.154 - {
7.155 - typename Digraph::InArcIt e(G,n);
7.156 - for(int i=0;i<nn;i++) {
7.157 - check(e!=INVALID,"Wrong InArc list linking.");
7.158 - check(n==G.target(e), "Wrong InArc list linking.");
7.159 - ++e;
7.160 - }
7.161 - check(e==INVALID,"Wrong InArc list linking.");
7.162 - }
7.163 -
7.164 - template <class Digraph>
7.165 - void checkDigraph() {
7.166 - const int num = 5;
7.167 - Digraph G;
7.168 - addPetersen(G, num);
7.169 - bidirDigraph(G);
7.170 - checkBidirPetersen(G, num);
7.171 - }
7.172 -
7.173 - template <class Digraph>
7.174 - void checkDigraphIterators(const Digraph& digraph) {
7.175 - typedef typename Digraph::Node Node;
7.176 - typedef typename Digraph::NodeIt NodeIt;
7.177 - typedef typename Digraph::Arc Arc;
7.178 - typedef typename Digraph::ArcIt ArcIt;
7.179 - typedef typename Digraph::InArcIt InArcIt;
7.180 - typedef typename Digraph::OutArcIt OutArcIt;
7.181 - // typedef ConArcIt<Digraph> ConArcIt;
7.182 - }
7.183 -
7.184 - ///\file
7.185 - ///\todo Check target(), source() as well;
7.186 -
7.187 -
7.188 -} //namespace lemon
7.189 -
7.190 -
7.191 -#endif
8.1 --- a/test/dijkstra_test.cc Sun Jun 15 22:03:33 2008 +0200
8.2 +++ b/test/dijkstra_test.cc Sun Jun 15 22:05:23 2008 +0200
8.3 @@ -16,9 +16,6 @@
8.4 *
8.5 */
8.6
8.7 -///\file
8.8 -///\brief Test cases for Dijkstra algorithm.
8.9 -
8.10 #include <lemon/concepts/digraph.h>
8.11 #include <lemon/smart_graph.h>
8.12 #include <lemon/list_graph.h>
8.13 @@ -26,6 +23,7 @@
8.14 #include <lemon/dijkstra.h>
8.15 #include <lemon/path.h>
8.16
8.17 +#include "graph_test.h"
8.18 #include "test_tools.h"
8.19
8.20 using namespace lemon;
9.1 --- a/test/dim_test.cc Sun Jun 15 22:03:33 2008 +0200
9.2 +++ b/test/dim_test.cc Sun Jun 15 22:05:23 2008 +0200
9.3 @@ -25,63 +25,59 @@
9.4
9.5 int main()
9.6 {
9.7 - cout << "Testing classes 'dim2::Point' and 'dim2::BoundingBox'." << endl;
9.8 -
9.9 typedef dim2::Point<int> Point;
9.10
9.11 Point p;
9.12 - check(p.size()==2, "Wrong vector initialization.");
9.13 + check(p.size()==2, "Wrong dim2::Point initialization.");
9.14
9.15 Point a(1,2);
9.16 Point b(3,4);
9.17 - check(a[0]==1 && a[1]==2, "Wrong vector initialization.");
9.18 + check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization.");
9.19
9.20 p = a+b;
9.21 - check(p.x==4 && p.y==6, "Wrong vector addition.");
9.22 + check(p.x==4 && p.y==6, "Wrong dim2::Point addition.");
9.23
9.24 p = a-b;
9.25 - check(p.x==-2 && p.y==-2, "Wrong vector subtraction.");
9.26 + check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction.");
9.27
9.28 - check(a.normSquare()==5,"Wrong vector norm calculation.");
9.29 - check(a*b==11, "Wrong vector scalar product.");
9.30 + check(a.normSquare()==5,"Wrong dim2::Point norm calculation.");
9.31 + check(a*b==11, "Wrong dim2::Point scalar product.");
9.32
9.33 int l=2;
9.34 p = a*l;
9.35 - check(p.x==2 && p.y==4, "Wrong vector multiplication by a scalar.");
9.36 + check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar.");
9.37
9.38 p = b/l;
9.39 - check(p.x==1 && p.y==2, "Wrong vector division by a scalar.");
9.40 + check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");
9.41
9.42 typedef dim2::BoundingBox<int> BB;
9.43 BB box1;
9.44 - check(box1.empty(), "It should be empty.");
9.45 + check(box1.empty(), "Wrong empty() in dim2::BoundingBox.");
9.46
9.47 box1.add(a);
9.48 - check(!box1.empty(), "It should not be empty.");
9.49 + check(!box1.empty(), "Wrong empty() in dim2::BoundingBox.");
9.50 box1.add(b);
9.51
9.52 check(box1.bottomLeft().x==1 &&
9.53 box1.bottomLeft().y==2 &&
9.54 box1.topRight().x==3 &&
9.55 box1.topRight().y==4,
9.56 - "Wrong addition of points to box.");
9.57 + "Wrong addition of points to dim2::BoundingBox.");
9.58
9.59 p.x=2; p.y=3;
9.60 - check(box1.inside(p), "It should be inside.");
9.61 + check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
9.62
9.63 p.x=1; p.y=3;
9.64 - check(box1.inside(p), "It should be inside.");
9.65 + check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
9.66
9.67 p.x=0; p.y=3;
9.68 - check(!box1.inside(p), "It should not be inside.");
9.69 + check(!box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
9.70
9.71 BB box2(p);
9.72 - check(!box2.empty(),
9.73 - "It should not be empty. Constructed from 1 point.");
9.74 + check(!box2.empty(), "Wrong empty() in dim2::BoundingBox.");
9.75
9.76 box2.add(box1);
9.77 - check(box2.inside(p),
9.78 - "It should be inside. Incremented a box with another one.");
9.79 + check(box2.inside(p), "Wrong inside() in dim2::BoundingBox.");
9.80
9.81 return 0;
9.82 }
10.1 --- a/test/error_test.cc Sun Jun 15 22:03:33 2008 +0200
10.2 +++ b/test/error_test.cc Sun Jun 15 22:05:23 2008 +0200
10.3 @@ -54,6 +54,7 @@
10.4 }
10.5 #undef LEMON_DISABLE_ASSERTS
10.6
10.7 +//checking custom assert handler
10.8 #define LEMON_ASSERT_CUSTOM
10.9
10.10 static int cnt = 0;
11.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
11.2 +++ b/test/graph_maps_test.h Sun Jun 15 22:05:23 2008 +0200
11.3 @@ -0,0 +1,144 @@
11.4 +/* -*- C++ -*-
11.5 + *
11.6 + * This file is a part of LEMON, a generic C++ optimization library
11.7 + *
11.8 + * Copyright (C) 2003-2008
11.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
11.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
11.11 + *
11.12 + * Permission to use, modify and distribute this software is granted
11.13 + * provided that this copyright notice appears in all copies. For
11.14 + * precise terms see the accompanying LICENSE file.
11.15 + *
11.16 + * This software is provided "AS IS" with no warranty of any kind,
11.17 + * express or implied, and with no claim as to its suitability for any
11.18 + * purpose.
11.19 + *
11.20 + */
11.21 +
11.22 +#ifndef LEMON_TEST_MAP_TEST_H
11.23 +#define LEMON_TEST_MAP_TEST_H
11.24 +
11.25 +#include <vector>
11.26 +#include <lemon/maps.h>
11.27 +
11.28 +#include "test_tools.h"
11.29 +
11.30 +namespace lemon {
11.31 +
11.32 + template <typename Graph>
11.33 + void checkGraphNodeMap() {
11.34 + Graph graph;
11.35 + const int num = 16;
11.36 +
11.37 + typedef typename Graph::Node Node;
11.38 +
11.39 + std::vector<Node> nodes;
11.40 + for (int i = 0; i < num; ++i) {
11.41 + nodes.push_back(graph.addNode());
11.42 + }
11.43 + typedef typename Graph::template NodeMap<int> IntNodeMap;
11.44 + IntNodeMap map(graph, 42);
11.45 + for (int i = 0; i < int(nodes.size()); ++i) {
11.46 + check(map[nodes[i]] == 42, "Wrong map constructor.");
11.47 + }
11.48 + for (int i = 0; i < num; ++i) {
11.49 + nodes.push_back(graph.addNode());
11.50 + map[nodes.back()] = 23;
11.51 + check(map[nodes.back()] == 23, "Wrong operator[].");
11.52 + }
11.53 + map = constMap<Node>(12);
11.54 + for (int i = 0; i < int(nodes.size()); ++i) {
11.55 + check(map[nodes[i]] == 12, "Wrong map constructor.");
11.56 + }
11.57 + graph.clear();
11.58 + nodes.clear();
11.59 + }
11.60 +
11.61 + template <typename Graph>
11.62 + void checkGraphArcMap() {
11.63 + Graph graph;
11.64 + const int num = 16;
11.65 +
11.66 + typedef typename Graph::Node Node;
11.67 + typedef typename Graph::Arc Arc;
11.68 +
11.69 + std::vector<Node> nodes;
11.70 + for (int i = 0; i < num; ++i) {
11.71 + nodes.push_back(graph.addNode());
11.72 + }
11.73 +
11.74 + std::vector<Arc> arcs;
11.75 + for (int i = 0; i < num; ++i) {
11.76 + for (int j = 0; j < i; ++j) {
11.77 + arcs.push_back(graph.addArc(nodes[i], nodes[j]));
11.78 + }
11.79 + }
11.80 +
11.81 + typedef typename Graph::template ArcMap<int> IntArcMap;
11.82 + IntArcMap map(graph, 42);
11.83 +
11.84 + for (int i = 0; i < int(arcs.size()); ++i) {
11.85 + check(map[arcs[i]] == 42, "Wrong map constructor.");
11.86 + }
11.87 +
11.88 + for (int i = 0; i < num; ++i) {
11.89 + for (int j = i + 1; j < num; ++j) {
11.90 + arcs.push_back(graph.addArc(nodes[i], nodes[j]));
11.91 + map[arcs.back()] = 23;
11.92 + check(map[arcs.back()] == 23, "Wrong operator[].");
11.93 + }
11.94 + }
11.95 + map = constMap<Arc>(12);
11.96 + for (int i = 0; i < int(arcs.size()); ++i) {
11.97 + check(map[arcs[i]] == 12, "Wrong map constructor.");
11.98 + }
11.99 + graph.clear();
11.100 + arcs.clear();
11.101 + }
11.102 +
11.103 + template <typename Graph>
11.104 + void checkGraphEdgeMap() {
11.105 + Graph graph;
11.106 + const int num = 16;
11.107 +
11.108 + typedef typename Graph::Node Node;
11.109 + typedef typename Graph::Edge Edge;
11.110 +
11.111 + std::vector<Node> nodes;
11.112 + for (int i = 0; i < num; ++i) {
11.113 + nodes.push_back(graph.addNode());
11.114 + }
11.115 +
11.116 + std::vector<Edge> edges;
11.117 + for (int i = 0; i < num; ++i) {
11.118 + for (int j = 0; j < i; ++j) {
11.119 + edges.push_back(graph.addEdge(nodes[i], nodes[j]));
11.120 + }
11.121 + }
11.122 +
11.123 + typedef typename Graph::template EdgeMap<int> IntEdgeMap;
11.124 + IntEdgeMap map(graph, 42);
11.125 +
11.126 + for (int i = 0; i < int(edges.size()); ++i) {
11.127 + check(map[edges[i]] == 42, "Wrong map constructor.");
11.128 + }
11.129 +
11.130 + for (int i = 0; i < num; ++i) {
11.131 + for (int j = i + 1; j < num; ++j) {
11.132 + edges.push_back(graph.addEdge(nodes[i], nodes[j]));
11.133 + map[edges.back()] = 23;
11.134 + check(map[edges.back()] == 23, "Wrong operator[].");
11.135 + }
11.136 + }
11.137 + map = constMap<Edge>(12);
11.138 + for (int i = 0; i < int(edges.size()); ++i) {
11.139 + check(map[edges[i]] == 12, "Wrong map constructor.");
11.140 + }
11.141 + graph.clear();
11.142 + edges.clear();
11.143 + }
11.144 +
11.145 +}
11.146 +
11.147 +#endif
12.1 --- a/test/graph_test.cc Sun Jun 15 22:03:33 2008 +0200
12.2 +++ b/test/graph_test.cc Sun Jun 15 22:05:23 2008 +0200
12.3 @@ -22,17 +22,15 @@
12.4 // #include <lemon/full_graph.h>
12.5 // #include <lemon/grid_graph.h>
12.6
12.7 -#include <lemon/graph_utils.h>
12.8 -
12.9 #include "test_tools.h"
12.10 -
12.11 +#include "graph_test.h"
12.12 +#include "graph_maps_test.h"
12.13
12.14 using namespace lemon;
12.15 using namespace lemon::concepts;
12.16
12.17 void check_concepts() {
12.18 -
12.19 - { // checking digraph components
12.20 + { // Checking graph components
12.21 checkConcept<BaseGraphComponent, BaseGraphComponent >();
12.22
12.23 checkConcept<IDableGraphComponent<>,
12.24 @@ -43,52 +41,40 @@
12.25
12.26 checkConcept<MappableGraphComponent<>,
12.27 MappableGraphComponent<> >();
12.28 -
12.29 }
12.30 - {
12.31 - checkConcept<Graph, ListGraph>();
12.32 - checkConcept<Graph, SmartGraph>();
12.33 -// checkConcept<Graph, FullGraph>();
12.34 -// checkConcept<Graph, Graph>();
12.35 -// checkConcept<Graph, GridGraph>();
12.36 + { // Checking skeleton graph
12.37 + checkConcept<Graph, Graph>();
12.38 }
12.39 + { // Checking ListGraph
12.40 + checkConcept<Graph, ListGraph>();
12.41 + checkConcept<AlterableGraphComponent<>, ListGraph>();
12.42 + checkConcept<ExtendableGraphComponent<>, ListGraph>();
12.43 + checkConcept<ClearableGraphComponent<>, ListGraph>();
12.44 + checkConcept<ErasableGraphComponent<>, ListGraph>();
12.45 + checkGraphIterators<ListGraph>();
12.46 + }
12.47 + { // Checking SmartGraph
12.48 + checkConcept<Graph, SmartGraph>();
12.49 + checkConcept<AlterableGraphComponent<>, SmartGraph>();
12.50 + checkConcept<ExtendableGraphComponent<>, SmartGraph>();
12.51 + checkConcept<ClearableGraphComponent<>, SmartGraph>();
12.52 + checkGraphIterators<SmartGraph>();
12.53 + }
12.54 +// { // Checking FullGraph
12.55 +// checkConcept<Graph, FullGraph>();
12.56 +// checkGraphIterators<FullGraph>();
12.57 +// }
12.58 +// { // Checking GridGraph
12.59 +// checkConcept<Graph, GridGraph>();
12.60 +// checkGraphIterators<GridGraph>();
12.61 +// }
12.62 }
12.63
12.64 template <typename Graph>
12.65 -void check_item_counts(Graph &g, int n, int e) {
12.66 - int nn = 0;
12.67 - for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
12.68 - ++nn;
12.69 - }
12.70 -
12.71 - check(nn == n, "Wrong node number.");
12.72 - // check(countNodes(g) == n, "Wrong node number.");
12.73 -
12.74 - int ee = 0;
12.75 - for (typename Graph::ArcIt it(g); it != INVALID; ++it) {
12.76 - ++ee;
12.77 - }
12.78 -
12.79 - check(ee == 2*e, "Wrong arc number.");
12.80 - // check(countArcs(g) == 2*e, "Wrong arc number.");
12.81 -
12.82 - int uee = 0;
12.83 - for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
12.84 - ++uee;
12.85 - }
12.86 -
12.87 - check(uee == e, "Wrong edge number.");
12.88 - // check(countEdges(g) == e, "Wrong edge number.");
12.89 -}
12.90 -
12.91 -template <typename Graph>
12.92 -void check_graph_counts() {
12.93 -
12.94 +void check_graph_validity() {
12.95 TEMPLATE_GRAPH_TYPEDEFS(Graph);
12.96 Graph g;
12.97
12.98 - check_item_counts(g,0,0);
12.99 -
12.100 Node
12.101 n1 = g.addNode(),
12.102 n2 = g.addNode(),
12.103 @@ -98,17 +84,20 @@
12.104 e1 = g.addEdge(n1, n2),
12.105 e2 = g.addEdge(n2, n3);
12.106
12.107 - check_item_counts(g,3,2);
12.108 + check(g.valid(n1), "Wrong validity check");
12.109 + check(g.valid(e1), "Wrong validity check");
12.110 + check(g.valid(g.direct(e1, true)), "Wrong validity check");
12.111 +
12.112 + check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
12.113 + check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
12.114 + check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
12.115 }
12.116
12.117 template <typename Graph>
12.118 -void check_graph_validity() {
12.119 -
12.120 +void check_graph_validity_erase() {
12.121 TEMPLATE_GRAPH_TYPEDEFS(Graph);
12.122 Graph g;
12.123
12.124 - check_item_counts(g,0,0);
12.125 -
12.126 Node
12.127 n1 = g.addNode(),
12.128 n2 = g.addNode(),
12.129 @@ -118,53 +107,23 @@
12.130 e1 = g.addEdge(n1, n2),
12.131 e2 = g.addEdge(n2, n3);
12.132
12.133 - check(g.valid(n1), "Validity check");
12.134 - check(g.valid(e1), "Validity check");
12.135 - check(g.valid(g.direct(e1, true)), "Validity check");
12.136 -
12.137 - check(!g.valid(g.nodeFromId(-1)), "Validity check");
12.138 - check(!g.valid(g.edgeFromId(-1)), "Validity check");
12.139 - check(!g.valid(g.arcFromId(-1)), "Validity check");
12.140 -
12.141 -}
12.142 -
12.143 -template <typename Graph>
12.144 -void check_graph_validity_erase() {
12.145 -
12.146 - TEMPLATE_GRAPH_TYPEDEFS(Graph);
12.147 - Graph g;
12.148 -
12.149 - check_item_counts(g,0,0);
12.150 -
12.151 - Node
12.152 - n1 = g.addNode(),
12.153 - n2 = g.addNode(),
12.154 - n3 = g.addNode();
12.155 -
12.156 - Edge
12.157 - e1 = g.addEdge(n1, n2),
12.158 - e2 = g.addEdge(n2, n3);
12.159 -
12.160 - check(g.valid(n1), "Validity check");
12.161 - check(g.valid(e1), "Validity check");
12.162 - check(g.valid(g.direct(e1, true)), "Validity check");
12.163 + check(g.valid(n1), "Wrong validity check");
12.164 + check(g.valid(e1), "Wrong validity check");
12.165 + check(g.valid(g.direct(e1, true)), "Wrong validity check");
12.166
12.167 g.erase(n1);
12.168
12.169 - check(!g.valid(n1), "Validity check");
12.170 - check(g.valid(n2), "Validity check");
12.171 - check(g.valid(n3), "Validity check");
12.172 - check(!g.valid(e1), "Validity check");
12.173 - check(g.valid(e2), "Validity check");
12.174 + check(!g.valid(n1), "Wrong validity check");
12.175 + check(g.valid(n2), "Wrong validity check");
12.176 + check(g.valid(n3), "Wrong validity check");
12.177 + check(!g.valid(e1), "Wrong validity check");
12.178 + check(g.valid(e2), "Wrong validity check");
12.179
12.180 - check(!g.valid(g.nodeFromId(-1)), "Validity check");
12.181 - check(!g.valid(g.edgeFromId(-1)), "Validity check");
12.182 - check(!g.valid(g.arcFromId(-1)), "Validity check");
12.183 -
12.184 + check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
12.185 + check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
12.186 + check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
12.187 }
12.188
12.189 -
12.190 -
12.191 // void checkGridGraph(const GridGraph& g, int w, int h) {
12.192 // check(g.width() == w, "Wrong width");
12.193 // check(g.height() == h, "Wrong height");
12.194 @@ -209,27 +168,36 @@
12.195 // }
12.196 // }
12.197
12.198 +void check_graphs() {
12.199 + { // Checking ListGraph
12.200 + checkGraph<ListGraph>();
12.201 + checkGraphNodeMap<ListGraph>();
12.202 + checkGraphEdgeMap<ListGraph>();
12.203 +
12.204 + check_graph_validity_erase<ListGraph>();
12.205 + }
12.206 + { // Checking SmartGraph
12.207 + checkGraph<SmartGraph>();
12.208 + checkGraphNodeMap<SmartGraph>();
12.209 + checkGraphEdgeMap<SmartGraph>();
12.210 +
12.211 + check_graph_validity<SmartGraph>();
12.212 + }
12.213 +// { // Checking FullGraph
12.214 +// FullGraph g(5);
12.215 +// checkGraphNodeList(g, 5);
12.216 +// checkGraphEdgeList(g, 10);
12.217 +// }
12.218 +// { // Checking GridGraph
12.219 +// GridGraph g(5, 6);
12.220 +// checkGraphNodeList(g, 30);
12.221 +// checkGraphEdgeList(g, 49);
12.222 +// checkGridGraph(g, 5, 6);
12.223 +// }
12.224 +}
12.225 +
12.226 int main() {
12.227 check_concepts();
12.228 -
12.229 - check_graph_counts<ListGraph>();
12.230 - check_graph_counts<SmartGraph>();
12.231 -
12.232 - check_graph_validity_erase<ListGraph>();
12.233 - check_graph_validity<SmartGraph>();
12.234 -
12.235 -// {
12.236 -// FullGraph g(5);
12.237 -// check_item_counts(g, 5, 10);
12.238 -// }
12.239 -
12.240 -// {
12.241 -// GridGraph g(5, 6);
12.242 -// check_item_counts(g, 30, 49);
12.243 -// checkGridGraph(g, 5, 6);
12.244 -// }
12.245 -
12.246 - std::cout << __FILE__ ": All tests passed.\n";
12.247 -
12.248 + check_graphs();
12.249 return 0;
12.250 }
13.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
13.2 +++ b/test/graph_test.h Sun Jun 15 22:05:23 2008 +0200
13.3 @@ -0,0 +1,262 @@
13.4 +/* -*- C++ -*-
13.5 + *
13.6 + * This file is a part of LEMON, a generic C++ optimization library
13.7 + *
13.8 + * Copyright (C) 2003-2008
13.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
13.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
13.11 + *
13.12 + * Permission to use, modify and distribute this software is granted
13.13 + * provided that this copyright notice appears in all copies. For
13.14 + * precise terms see the accompanying LICENSE file.
13.15 + *
13.16 + * This software is provided "AS IS" with no warranty of any kind,
13.17 + * express or implied, and with no claim as to its suitability for any
13.18 + * purpose.
13.19 + *
13.20 + */
13.21 +
13.22 +#ifndef LEMON_TEST_GRAPH_TEST_H
13.23 +#define LEMON_TEST_GRAPH_TEST_H
13.24 +
13.25 +#include <lemon/graph_utils.h>
13.26 +#include "test_tools.h"
13.27 +
13.28 +namespace lemon {
13.29 +
13.30 + template<class Graph>
13.31 + void checkGraphNodeList(const Graph &G, int cnt)
13.32 + {
13.33 + typename Graph::NodeIt n(G);
13.34 + for(int i=0;i<cnt;i++) {
13.35 + check(n!=INVALID,"Wrong Node list linking.");
13.36 + ++n;
13.37 + }
13.38 + check(n==INVALID,"Wrong Node list linking.");
13.39 + check(countNodes(G)==cnt,"Wrong Node number.");
13.40 + }
13.41 +
13.42 + template<class Graph>
13.43 + void checkGraphArcList(const Graph &G, int cnt)
13.44 + {
13.45 + typename Graph::ArcIt e(G);
13.46 + for(int i=0;i<cnt;i++) {
13.47 + check(e!=INVALID,"Wrong Arc list linking.");
13.48 + ++e;
13.49 + }
13.50 + check(e==INVALID,"Wrong Arc list linking.");
13.51 + check(countArcs(G)==cnt,"Wrong Arc number.");
13.52 + }
13.53 +
13.54 + template<class Graph>
13.55 + void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
13.56 + {
13.57 + typename Graph::OutArcIt e(G,n);
13.58 + for(int i=0;i<cnt;i++) {
13.59 + check(e!=INVALID,"Wrong OutArc list linking.");
13.60 + check(n==G.source(e),"Wrong OutArc list linking.");
13.61 + ++e;
13.62 + }
13.63 + check(e==INVALID,"Wrong OutArc list linking.");
13.64 + check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
13.65 + }
13.66 +
13.67 + template<class Graph>
13.68 + void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
13.69 + {
13.70 + typename Graph::InArcIt e(G,n);
13.71 + for(int i=0;i<cnt;i++) {
13.72 + check(e!=INVALID,"Wrong InArc list linking.");
13.73 + check(n==G.target(e),"Wrong InArc list linking.");
13.74 + ++e;
13.75 + }
13.76 + check(e==INVALID,"Wrong InArc list linking.");
13.77 + check(countInArcs(G,n)==cnt,"Wrong InArc number.");
13.78 + }
13.79 +
13.80 + template<class Graph>
13.81 + void checkGraphEdgeList(const Graph &G, int cnt)
13.82 + {
13.83 + typename Graph::EdgeIt e(G);
13.84 + for(int i=0;i<cnt;i++) {
13.85 + check(e!=INVALID,"Wrong Edge list linking.");
13.86 + ++e;
13.87 + }
13.88 + check(e==INVALID,"Wrong Edge list linking.");
13.89 + check(countEdges(G)==cnt,"Wrong Edge number.");
13.90 + }
13.91 +
13.92 + template<class Graph>
13.93 + void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
13.94 + {
13.95 + typename Graph::IncEdgeIt e(G,n);
13.96 + for(int i=0;i<cnt;i++) {
13.97 + check(e!=INVALID,"Wrong IncEdge list linking.");
13.98 + check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
13.99 + ++e;
13.100 + }
13.101 + check(e==INVALID,"Wrong IncEdge list linking.");
13.102 + check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
13.103 + }
13.104 +
13.105 + template <class Digraph>
13.106 + void checkDigraphIterators() {
13.107 + typedef typename Digraph::Node Node;
13.108 + typedef typename Digraph::NodeIt NodeIt;
13.109 + typedef typename Digraph::Arc Arc;
13.110 + typedef typename Digraph::ArcIt ArcIt;
13.111 + typedef typename Digraph::InArcIt InArcIt;
13.112 + typedef typename Digraph::OutArcIt OutArcIt;
13.113 + }
13.114 +
13.115 + template <class Graph>
13.116 + void checkGraphIterators() {
13.117 + checkDigraphIterators<Graph>();
13.118 + typedef typename Graph::Edge Edge;
13.119 + typedef typename Graph::EdgeIt EdgeIt;
13.120 + typedef typename Graph::IncEdgeIt IncEdgeIt;
13.121 + }
13.122 +
13.123 + // Structure returned by addPetersen()
13.124 + template<class Digraph>
13.125 + struct PetStruct
13.126 + {
13.127 + // Vector containing the outer nodes
13.128 + std::vector<typename Digraph::Node> outer;
13.129 + // Vector containing the inner nodes
13.130 + std::vector<typename Digraph::Node> inner;
13.131 + // Vector containing the arcs of the inner circle
13.132 + std::vector<typename Digraph::Arc> incir;
13.133 + // Vector containing the arcs of the outer circle
13.134 + std::vector<typename Digraph::Arc> outcir;
13.135 + // Vector containing the chord arcs
13.136 + std::vector<typename Digraph::Arc> chords;
13.137 + };
13.138 +
13.139 + // Adds the reverse pair of all arcs to a digraph
13.140 + template<class Digraph>
13.141 + void bidirDigraph(Digraph &G)
13.142 + {
13.143 + typedef typename Digraph::Arc Arc;
13.144 + typedef typename Digraph::ArcIt ArcIt;
13.145 +
13.146 + std::vector<Arc> ee;
13.147 +
13.148 + for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
13.149 +
13.150 + for(int i=0;i<int(ee.size());++i)
13.151 + G.addArc(G.target(ee[i]),G.source(ee[i]));
13.152 + }
13.153 +
13.154 + // Adds a Petersen digraph to G.
13.155 + // Returns the nodes and arcs of the generated digraph.
13.156 + template<typename Digraph>
13.157 + PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
13.158 + {
13.159 + PetStruct<Digraph> n;
13.160 +
13.161 + for(int i=0;i<num;i++) {
13.162 + n.outer.push_back(G.addNode());
13.163 + n.inner.push_back(G.addNode());
13.164 + }
13.165 +
13.166 + for(int i=0;i<num;i++) {
13.167 + n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
13.168 + n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
13.169 + n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
13.170 + }
13.171 +
13.172 + return n;
13.173 + }
13.174 +
13.175 + // Checks the bidirectioned Petersen digraph
13.176 + template<class Digraph>
13.177 + void checkBidirPetersen(const Digraph &G, int num = 5)
13.178 + {
13.179 + typedef typename Digraph::NodeIt NodeIt;
13.180 +
13.181 + checkGraphNodeList(G, 2 * num);
13.182 + checkGraphArcList(G, 6 * num);
13.183 +
13.184 + for(NodeIt n(G);n!=INVALID;++n) {
13.185 + checkGraphInArcList(G, n, 3);
13.186 + checkGraphOutArcList(G, n, 3);
13.187 + }
13.188 + }
13.189 +
13.190 + // Structure returned by addUPetersen()
13.191 + template<class Graph>
13.192 + struct UPetStruct
13.193 + {
13.194 + // Vector containing the outer nodes
13.195 + std::vector<typename Graph::Node> outer;
13.196 + // Vector containing the inner nodes
13.197 + std::vector<typename Graph::Node> inner;
13.198 + // Vector containing the edges of the inner circle
13.199 + std::vector<typename Graph::Edge> incir;
13.200 + // Vector containing the edges of the outer circle
13.201 + std::vector<typename Graph::Edge> outcir;
13.202 + // Vector containing the chord edges
13.203 + std::vector<typename Graph::Edge> chords;
13.204 + };
13.205 +
13.206 + // Adds a Petersen graph to \c G.
13.207 + // Returns the nodes and edges of the generated graph.
13.208 + template<typename Graph>
13.209 + UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
13.210 + {
13.211 + UPetStruct<Graph> n;
13.212 +
13.213 + for(int i=0;i<num;i++) {
13.214 + n.outer.push_back(G.addNode());
13.215 + n.inner.push_back(G.addNode());
13.216 + }
13.217 +
13.218 + for(int i=0;i<num;i++) {
13.219 + n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
13.220 + n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
13.221 + n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
13.222 + }
13.223 +
13.224 + return n;
13.225 + }
13.226 +
13.227 + // Checks the undirected Petersen graph
13.228 + template<class Graph>
13.229 + void checkUndirPetersen(const Graph &G, int num = 5)
13.230 + {
13.231 + typedef typename Graph::NodeIt NodeIt;
13.232 +
13.233 + checkGraphNodeList(G, 2 * num);
13.234 + checkGraphEdgeList(G, 3 * num);
13.235 + checkGraphArcList(G, 6 * num);
13.236 +
13.237 + for(NodeIt n(G);n!=INVALID;++n) {
13.238 + checkGraphIncEdgeList(G, n, 3);
13.239 + }
13.240 + }
13.241 +
13.242 + template <class Digraph>
13.243 + void checkDigraph() {
13.244 + const int num = 5;
13.245 + Digraph G;
13.246 + checkGraphNodeList(G, 0);
13.247 + checkGraphArcList(G, 0);
13.248 + addPetersen(G, num);
13.249 + bidirDigraph(G);
13.250 + checkBidirPetersen(G, num);
13.251 + }
13.252 +
13.253 + template <class Graph>
13.254 + void checkGraph() {
13.255 + const int num = 5;
13.256 + Graph G;
13.257 + checkGraphNodeList(G, 0);
13.258 + checkGraphEdgeList(G, 0);
13.259 + addUPetersen(G, num);
13.260 + checkUndirPetersen(G, num);
13.261 + }
13.262 +
13.263 +} //namespace lemon
13.264 +
13.265 +#endif
14.1 --- a/test/graph_utils_test.cc Sun Jun 15 22:03:33 2008 +0200
14.2 +++ b/test/graph_utils_test.cc Sun Jun 15 22:05:23 2008 +0200
14.3 @@ -16,41 +16,177 @@
14.4 *
14.5 */
14.6
14.7 -#include <iostream>
14.8 -#include <vector>
14.9 +#include <cstdlib>
14.10 +#include <ctime>
14.11
14.12 +#include <lemon/random.h>
14.13 #include <lemon/graph_utils.h>
14.14 -
14.15 #include <lemon/list_graph.h>
14.16 #include <lemon/smart_graph.h>
14.17
14.18 +#include "graph_test.h"
14.19 #include "test_tools.h"
14.20 -#include "graph_utils_test.h"
14.21 -
14.22
14.23 using namespace lemon;
14.24
14.25 -template <class Graph>
14.26 -void checkSnapDeg()
14.27 +template <typename Digraph>
14.28 +void checkFindArcs() {
14.29 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
14.30 +
14.31 + {
14.32 + Digraph digraph;
14.33 + for (int i = 0; i < 10; ++i) {
14.34 + digraph.addNode();
14.35 + }
14.36 + DescriptorMap<Digraph, Node> nodes(digraph);
14.37 + typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
14.38 + for (int i = 0; i < 100; ++i) {
14.39 + int src = rnd[invNodes.size()];
14.40 + int trg = rnd[invNodes.size()];
14.41 + digraph.addArc(invNodes[src], invNodes[trg]);
14.42 + }
14.43 + typename Digraph::template ArcMap<bool> found(digraph, false);
14.44 + DescriptorMap<Digraph, Arc> arcs(digraph);
14.45 + for (NodeIt src(digraph); src != INVALID; ++src) {
14.46 + for (NodeIt trg(digraph); trg != INVALID; ++trg) {
14.47 + for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
14.48 + check(digraph.source(con) == src, "Wrong source.");
14.49 + check(digraph.target(con) == trg, "Wrong target.");
14.50 + check(found[con] == false, "The arc found already.");
14.51 + found[con] = true;
14.52 + }
14.53 + }
14.54 + }
14.55 + for (ArcIt it(digraph); it != INVALID; ++it) {
14.56 + check(found[it] == true, "The arc is not found.");
14.57 + }
14.58 + }
14.59 +
14.60 + {
14.61 + int num = 5;
14.62 + Digraph fg;
14.63 + std::vector<Node> nodes;
14.64 + for (int i = 0; i < num; ++i) {
14.65 + nodes.push_back(fg.addNode());
14.66 + }
14.67 + for (int i = 0; i < num * num; ++i) {
14.68 + fg.addArc(nodes[i / num], nodes[i % num]);
14.69 + }
14.70 + check(countNodes(fg) == num, "Wrong node number.");
14.71 + check(countArcs(fg) == num*num, "Wrong arc number.");
14.72 + for (NodeIt src(fg); src != INVALID; ++src) {
14.73 + for (NodeIt trg(fg); trg != INVALID; ++trg) {
14.74 + ConArcIt<Digraph> con(fg, src, trg);
14.75 + check(con != INVALID, "There is no connecting arc.");
14.76 + check(fg.source(con) == src, "Wrong source.");
14.77 + check(fg.target(con) == trg, "Wrong target.");
14.78 + check(++con == INVALID, "There is more connecting arc.");
14.79 + }
14.80 + }
14.81 + ArcLookUp<Digraph> al1(fg);
14.82 + DynArcLookUp<Digraph> al2(fg);
14.83 + AllArcLookUp<Digraph> al3(fg);
14.84 + for (NodeIt src(fg); src != INVALID; ++src) {
14.85 + for (NodeIt trg(fg); trg != INVALID; ++trg) {
14.86 + Arc con1 = al1(src, trg);
14.87 + Arc con2 = al2(src, trg);
14.88 + Arc con3 = al3(src, trg);
14.89 + Arc con4 = findArc(fg, src, trg);
14.90 + check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.")
14.91 + check(con1 != INVALID, "There is no connecting arc.");
14.92 + check(fg.source(con1) == src, "Wrong source.");
14.93 + check(fg.target(con1) == trg, "Wrong target.");
14.94 + check(al3(src, trg, con3) == INVALID, "There is more connecting arc.");
14.95 + check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc.");
14.96 + }
14.97 + }
14.98 + }
14.99 +}
14.100 +
14.101 +template <typename Graph>
14.102 +void checkFindEdges() {
14.103 + TEMPLATE_GRAPH_TYPEDEFS(Graph);
14.104 + Graph graph;
14.105 + for (int i = 0; i < 10; ++i) {
14.106 + graph.addNode();
14.107 + }
14.108 + DescriptorMap<Graph, Node> nodes(graph);
14.109 + typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
14.110 + for (int i = 0; i < 100; ++i) {
14.111 + int src = rnd[invNodes.size()];
14.112 + int trg = rnd[invNodes.size()];
14.113 + graph.addEdge(invNodes[src], invNodes[trg]);
14.114 + }
14.115 + typename Graph::template EdgeMap<int> found(graph, 0);
14.116 + DescriptorMap<Graph, Edge> edges(graph);
14.117 + for (NodeIt src(graph); src != INVALID; ++src) {
14.118 + for (NodeIt trg(graph); trg != INVALID; ++trg) {
14.119 + for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
14.120 + check( (graph.u(con) == src && graph.v(con) == trg) ||
14.121 + (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes.");
14.122 + ++found[con];
14.123 + check(found[con] <= 2, "The edge found more than twice.");
14.124 + }
14.125 + }
14.126 + }
14.127 + for (EdgeIt it(graph); it != INVALID; ++it) {
14.128 + check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
14.129 + (graph.u(it) == graph.v(it) && found[it] == 1),
14.130 + "The edge is not found correctly.");
14.131 + }
14.132 +}
14.133 +
14.134 +template <class Digraph>
14.135 +void checkDeg()
14.136 {
14.137 - Graph g;
14.138 - typename Graph::Node n1=g.addNode();
14.139 - typename Graph::Node n2=g.addNode();
14.140 -
14.141 - InDegMap<Graph> ind(g);
14.142 -
14.143 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
14.144 +
14.145 + const int nodeNum = 10;
14.146 + const int arcNum = 100;
14.147 + Digraph digraph;
14.148 + InDegMap<Digraph> inDeg(digraph);
14.149 + OutDegMap<Digraph> outDeg(digraph);
14.150 + std::vector<Node> nodes(nodeNum);
14.151 + for (int i = 0; i < nodeNum; ++i) {
14.152 + nodes[i] = digraph.addNode();
14.153 + }
14.154 + std::vector<Arc> arcs(arcNum);
14.155 + for (int i = 0; i < arcNum; ++i) {
14.156 + arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
14.157 + }
14.158 + for (int i = 0; i < nodeNum; ++i) {
14.159 + check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
14.160 + "Wrong in degree map");
14.161 + }
14.162 + for (int i = 0; i < nodeNum; ++i) {
14.163 + check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
14.164 + "Wrong out degree map");
14.165 + }
14.166 +}
14.167 +
14.168 +template <class Digraph>
14.169 +void checkSnapDeg()
14.170 +{
14.171 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
14.172 +
14.173 + Digraph g;
14.174 + Node n1=g.addNode();
14.175 + Node n2=g.addNode();
14.176 +
14.177 + InDegMap<Digraph> ind(g);
14.178 +
14.179 g.addArc(n1,n2);
14.180
14.181 - typename Graph::Snapshot snap(g);
14.182 + typename Digraph::Snapshot snap(g);
14.183
14.184 - OutDegMap<Graph> outd(g);
14.185 + OutDegMap<Digraph> outd(g);
14.186
14.187 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
14.188 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
14.189
14.190 g.addArc(n1,n2);
14.191 g.addArc(n2,n1);
14.192 -
14.193 +
14.194 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
14.195 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
14.196
14.197 @@ -58,84 +194,20 @@
14.198
14.199 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
14.200 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
14.201 -
14.202 }
14.203
14.204 int main() {
14.205 - ///\file
14.206 - { // checking list graph
14.207 - checkDigraphCounters<ListDigraph>();
14.208 - checkFindArc<ListDigraph>();
14.209 - }
14.210 - { // checking smart graph
14.211 - checkDigraphCounters<SmartDigraph>();
14.212 - checkFindArc<SmartDigraph>();
14.213 - }
14.214 - {
14.215 - int num = 5;
14.216 - SmartDigraph fg;
14.217 - std::vector<SmartDigraph::Node> nodes;
14.218 - for (int i = 0; i < num; ++i) {
14.219 - nodes.push_back(fg.addNode());
14.220 - }
14.221 - for (int i = 0; i < num * num; ++i) {
14.222 - fg.addArc(nodes[i / num], nodes[i % num]);
14.223 - }
14.224 - check(countNodes(fg) == num, "FullGraph: wrong node number.");
14.225 - check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
14.226 - for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
14.227 - for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
14.228 - ConArcIt<SmartDigraph> con(fg, src, trg);
14.229 - check(con != INVALID, "There is no connecting arc.");
14.230 - check(fg.source(con) == src, "Wrong source.");
14.231 - check(fg.target(con) == trg, "Wrong target.");
14.232 - check(++con == INVALID, "There is more connecting arc.");
14.233 - }
14.234 - }
14.235 - AllArcLookUp<SmartDigraph> el(fg);
14.236 - for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
14.237 - for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
14.238 - SmartDigraph::Arc con = el(src, trg);
14.239 - check(con != INVALID, "There is no connecting arc.");
14.240 - check(fg.source(con) == src, "Wrong source.");
14.241 - check(fg.target(con) == trg, "Wrong target.");
14.242 - check(el(src,trg,con) == INVALID, "There is more connecting arc.");
14.243 - }
14.244 - }
14.245 - }
14.246 + // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
14.247 + checkFindArcs<ListDigraph>();
14.248 + checkFindArcs<SmartDigraph>();
14.249 + checkFindEdges<ListGraph>();
14.250 + checkFindEdges<SmartGraph>();
14.251
14.252 - //check In/OutDegMap (and Snapshot feature)
14.253 -
14.254 + // Checking In/OutDegMap (and Snapshot feature)
14.255 + checkDeg<ListDigraph>();
14.256 + checkDeg<SmartDigraph>();
14.257 checkSnapDeg<ListDigraph>();
14.258 checkSnapDeg<SmartDigraph>();
14.259 -
14.260 - {
14.261 - const int nodeNum = 10;
14.262 - const int arcNum = 100;
14.263 - ListDigraph digraph;
14.264 - InDegMap<ListDigraph> inDeg(digraph);
14.265 - OutDegMap<ListDigraph> outDeg(digraph);
14.266 - std::vector<ListDigraph::Node> nodes(nodeNum);
14.267 - for (int i = 0; i < nodeNum; ++i) {
14.268 - nodes[i] = digraph.addNode();
14.269 - }
14.270 - std::vector<ListDigraph::Arc> arcs(arcNum);
14.271 - for (int i = 0; i < arcNum; ++i) {
14.272 - arcs[i] =
14.273 - digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
14.274 - }
14.275 - for (int i = 0; i < nodeNum; ++i) {
14.276 - check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),
14.277 - "Wrong in degree map");
14.278 - }
14.279 - for (int i = 0; i < nodeNum; ++i) {
14.280 - check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),
14.281 - "Wrong in degree map");
14.282 - }
14.283 - }
14.284 -
14.285 - ///Everything is OK
14.286 - std::cout << __FILE__ ": All tests passed.\n";
14.287
14.288 return 0;
14.289 }
15.1 --- a/test/graph_utils_test.h Sun Jun 15 22:03:33 2008 +0200
15.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
15.3 @@ -1,83 +0,0 @@
15.4 -/* -*- C++ -*-
15.5 - *
15.6 - * This file is a part of LEMON, a generic C++ optimization library
15.7 - *
15.8 - * Copyright (C) 2003-2008
15.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
15.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
15.11 - *
15.12 - * Permission to use, modify and distribute this software is granted
15.13 - * provided that this copyright notice appears in all copies. For
15.14 - * precise terms see the accompanying LICENSE file.
15.15 - *
15.16 - * This software is provided "AS IS" with no warranty of any kind,
15.17 - * express or implied, and with no claim as to its suitability for any
15.18 - * purpose.
15.19 - *
15.20 - */
15.21 -
15.22 -#ifndef LEMON_TEST_GRAPH_UTILS_TEST_H
15.23 -#define LEMON_TEST_GRAPH_UTILS_TEST_H
15.24 -
15.25 -
15.26 -#include "test_tools.h"
15.27 -#include <cstdlib>
15.28 -#include <ctime>
15.29 -
15.30 -//! \ingroup misc
15.31 -//! \file
15.32 -//! \brief Test cases for graph utils.
15.33 -namespace lemon {
15.34 -
15.35 - template <typename Digraph>
15.36 - void checkDigraphCounters() {
15.37 - const int num = 5;
15.38 - Digraph digraph;
15.39 - addPetersen(digraph, num);
15.40 - bidirDigraph(digraph);
15.41 - check(countNodes(digraph) == 2*num, "Wrong node number.");
15.42 - check(countArcs(digraph) == 6*num, "Wrong arc number.");
15.43 - for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
15.44 - check(countOutArcs(digraph, it) == 3, "Wrong out degree number.");
15.45 - check(countInArcs(digraph, it) == 3, "Wrong in degree number.");
15.46 - }
15.47 - }
15.48 -
15.49 - template <typename Digraph>
15.50 - void checkFindArc() {
15.51 - typedef typename Digraph::Node Node;
15.52 - typedef typename Digraph::Arc Arc;
15.53 - typedef typename Digraph::NodeIt NodeIt;
15.54 - typedef typename Digraph::ArcIt ArcIt;
15.55 - Digraph digraph;
15.56 - for (int i = 0; i < 10; ++i) {
15.57 - digraph.addNode();
15.58 - }
15.59 - DescriptorMap<Digraph, Node> nodes(digraph);
15.60 - typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
15.61 - for (int i = 0; i < 100; ++i) {
15.62 - int src = rnd[invNodes.size()];
15.63 - int trg = rnd[invNodes.size()];
15.64 - digraph.addArc(invNodes[src], invNodes[trg]);
15.65 - }
15.66 - typename Digraph::template ArcMap<bool> found(digraph, false);
15.67 - DescriptorMap<Digraph, Arc> arcs(digraph);
15.68 - for (NodeIt src(digraph); src != INVALID; ++src) {
15.69 - for (NodeIt trg(digraph); trg != INVALID; ++trg) {
15.70 - for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
15.71 - check(digraph.source(con) == src, "Wrong source.");
15.72 - check(digraph.target(con) == trg, "Wrong target.");
15.73 - check(found[con] == false, "The arc found already.");
15.74 - found[con] = true;
15.75 - }
15.76 - }
15.77 - }
15.78 - for (ArcIt it(digraph); it != INVALID; ++it) {
15.79 - check(found[it] == true, "The arc is not found.");
15.80 - }
15.81 - }
15.82 -
15.83 -} //namespace lemon
15.84 -
15.85 -
15.86 -#endif
16.1 --- a/test/heap_test.cc Sun Jun 15 22:03:33 2008 +0200
16.2 +++ b/test/heap_test.cc Sun Jun 15 22:05:23 2008 +0200
16.3 @@ -42,7 +42,6 @@
16.4 using namespace lemon;
16.5 using namespace lemon::concepts;
16.6
16.7 -
16.8 int main() {
16.9
16.10 typedef int Item;
16.11 @@ -77,7 +76,7 @@
16.12 run();
16.13
16.14 {
16.15 - std::cerr << "Checking Bin Heap" << std::endl;
16.16 + std::cout << "Checking Bin Heap" << std::endl;
16.17
16.18 typedef BinHeap<Prio, ItemIntMap> IntHeap;
16.19 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
16.20 @@ -91,7 +90,7 @@
16.21 std::cout << timer << std::endl;
16.22 }
16.23 {
16.24 - std::cerr << "Checking Fib Heap" << std::endl;
16.25 + std::cout << "Checking Fib Heap" << std::endl;
16.26
16.27 typedef FibHeap<Prio, ItemIntMap> IntHeap;
16.28 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
16.29 @@ -105,7 +104,7 @@
16.30 std::cout << timer << std::endl;
16.31 }
16.32 {
16.33 - std::cerr << "Checking Radix Heap" << std::endl;
16.34 + std::cout << "Checking Radix Heap" << std::endl;
16.35
16.36 typedef RadixHeap<ItemIntMap> IntHeap;
16.37 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
16.38 @@ -120,7 +119,7 @@
16.39 }
16.40
16.41 {
16.42 - std::cerr << "Checking Bucket Heap" << std::endl;
16.43 + std::cout << "Checking Bucket Heap" << std::endl;
16.44
16.45 typedef BucketHeap<ItemIntMap> IntHeap;
16.46 checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
16.47 @@ -134,7 +133,5 @@
16.48 std::cout << timer << std::endl;
16.49 }
16.50
16.51 - std::cout << __FILE__ ": All tests passed.\n";
16.52 -
16.53 return 0;
16.54 }
17.1 --- a/test/kruskal_test.cc Sun Jun 15 22:03:33 2008 +0200
17.2 +++ b/test/kruskal_test.cc Sun Jun 15 22:05:23 2008 +0200
17.3 @@ -28,7 +28,6 @@
17.4 #include <lemon/concepts/digraph.h>
17.5 #include <lemon/concepts/graph.h>
17.6
17.7 -
17.8 using namespace std;
17.9 using namespace lemon;
17.10
17.11 @@ -57,7 +56,6 @@
17.12
17.13 kruskal(g, r, ws.begin());
17.14 kruskal(ug, ur, uws.begin());
17.15 -
17.16 }
17.17
17.18 int main() {
17.19 @@ -97,7 +95,7 @@
17.20 //Test with const map.
17.21 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
17.22 "Total cost should be 10");
17.23 - //Test with a edge map (filled with uniform costs).
17.24 + //Test with an edge map (filled with uniform costs).
17.25 check(kruskal(G, edge_cost_map, tree_map)==10,
17.26 "Total cost should be 10");
17.27
18.1 --- a/test/map_test.h Sun Jun 15 22:03:33 2008 +0200
18.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
18.3 @@ -1,149 +0,0 @@
18.4 -/* -*- C++ -*-
18.5 - *
18.6 - * This file is a part of LEMON, a generic C++ optimization library
18.7 - *
18.8 - * Copyright (C) 2003-2008
18.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
18.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
18.11 - *
18.12 - * Permission to use, modify and distribute this software is granted
18.13 - * provided that this copyright notice appears in all copies. For
18.14 - * precise terms see the accompanying LICENSE file.
18.15 - *
18.16 - * This software is provided "AS IS" with no warranty of any kind,
18.17 - * express or implied, and with no claim as to its suitability for any
18.18 - * purpose.
18.19 - *
18.20 - */
18.21 -
18.22 -#ifndef LEMON_TEST_MAP_TEST_H
18.23 -#define LEMON_TEST_MAP_TEST_H
18.24 -
18.25 -
18.26 -#include <vector>
18.27 -#include <lemon/maps.h>
18.28 -
18.29 -#include "test_tools.h"
18.30 -
18.31 -
18.32 -//! \ingroup misc
18.33 -//! \file
18.34 -//! \brief Some utilities to test map classes.
18.35 -
18.36 -namespace lemon {
18.37 -
18.38 -
18.39 -
18.40 - template <typename Graph>
18.41 - void checkGraphNodeMap() {
18.42 - Graph graph;
18.43 - const int num = 16;
18.44 -
18.45 - typedef typename Graph::Node Node;
18.46 -
18.47 - std::vector<Node> nodes;
18.48 - for (int i = 0; i < num; ++i) {
18.49 - nodes.push_back(graph.addNode());
18.50 - }
18.51 - typedef typename Graph::template NodeMap<int> IntNodeMap;
18.52 - IntNodeMap map(graph, 42);
18.53 - for (int i = 0; i < int(nodes.size()); ++i) {
18.54 - check(map[nodes[i]] == 42, "Wrong map constructor.");
18.55 - }
18.56 - for (int i = 0; i < num; ++i) {
18.57 - nodes.push_back(graph.addNode());
18.58 - map[nodes.back()] = 23;
18.59 - }
18.60 - map = constMap<Node>(12);
18.61 - for (int i = 0; i < int(nodes.size()); ++i) {
18.62 - check(map[nodes[i]] == 12, "Wrong map constructor.");
18.63 - }
18.64 - graph.clear();
18.65 - nodes.clear();
18.66 - }
18.67 -
18.68 - template <typename Graph>
18.69 - void checkGraphArcMap() {
18.70 - Graph graph;
18.71 - const int num = 16;
18.72 -
18.73 - typedef typename Graph::Node Node;
18.74 - typedef typename Graph::Arc Arc;
18.75 -
18.76 - std::vector<Node> nodes;
18.77 - for (int i = 0; i < num; ++i) {
18.78 - nodes.push_back(graph.addNode());
18.79 - }
18.80 -
18.81 - std::vector<Arc> edges;
18.82 - for (int i = 0; i < num; ++i) {
18.83 - for (int j = 0; j < i; ++j) {
18.84 - edges.push_back(graph.addArc(nodes[i], nodes[j]));
18.85 - }
18.86 - }
18.87 -
18.88 - typedef typename Graph::template ArcMap<int> IntArcMap;
18.89 - IntArcMap map(graph, 42);
18.90 -
18.91 - for (int i = 0; i < int(edges.size()); ++i) {
18.92 - check(map[edges[i]] == 42, "Wrong map constructor.");
18.93 - }
18.94 -
18.95 - for (int i = 0; i < num; ++i) {
18.96 - for (int j = i + 1; j < num; ++j) {
18.97 - edges.push_back(graph.addArc(nodes[i], nodes[j]));
18.98 - map[edges.back()] = 23;
18.99 - }
18.100 - }
18.101 - map = constMap<Arc>(12);
18.102 - for (int i = 0; i < int(edges.size()); ++i) {
18.103 - check(map[edges[i]] == 12, "Wrong map constructor.");
18.104 - }
18.105 - graph.clear();
18.106 - edges.clear();
18.107 - }
18.108 -
18.109 - template <typename Graph>
18.110 - void checkGraphEdgeMap() {
18.111 - Graph graph;
18.112 - const int num = 16;
18.113 -
18.114 - typedef typename Graph::Node Node;
18.115 - typedef typename Graph::Edge Edge;
18.116 -
18.117 - std::vector<Node> nodes;
18.118 - for (int i = 0; i < num; ++i) {
18.119 - nodes.push_back(graph.addNode());
18.120 - }
18.121 -
18.122 - std::vector<Edge> edges;
18.123 - for (int i = 0; i < num; ++i) {
18.124 - for (int j = 0; j < i; ++j) {
18.125 - edges.push_back(graph.addEdge(nodes[i], nodes[j]));
18.126 - }
18.127 - }
18.128 -
18.129 - typedef typename Graph::template EdgeMap<int> IntEdgeMap;
18.130 - IntEdgeMap map(graph, 42);
18.131 -
18.132 - for (int i = 0; i < int(edges.size()); ++i) {
18.133 - check(map[edges[i]] == 42, "Wrong map constructor.");
18.134 - }
18.135 -
18.136 - for (int i = 0; i < num; ++i) {
18.137 - for (int j = i + 1; j < num; ++j) {
18.138 - edges.push_back(graph.addEdge(nodes[i], nodes[j]));
18.139 - map[edges.back()] = 23;
18.140 - }
18.141 - }
18.142 - map = constMap<Edge>(12);
18.143 - for (int i = 0; i < int(edges.size()); ++i) {
18.144 - check(map[edges[i]] == 12, "Wrong map constructor.");
18.145 - }
18.146 - graph.clear();
18.147 - edges.clear();
18.148 - }
18.149 -
18.150 -}
18.151 -
18.152 -#endif
19.1 --- a/test/random_test.cc Sun Jun 15 22:03:33 2008 +0200
19.2 +++ b/test/random_test.cc Sun Jun 15 22:05:23 2008 +0200
19.3 @@ -19,11 +19,6 @@
19.4 #include <lemon/random.h>
19.5 #include "test_tools.h"
19.6
19.7 -///\file \brief Test cases for random.h
19.8 -///
19.9 -///\todo To be extended
19.10 -///
19.11 -
19.12 int seed_array[] = {1, 2};
19.13
19.14 int main()
20.1 --- a/test/test_tools.h Sun Jun 15 22:03:33 2008 +0200
20.2 +++ b/test/test_tools.h Sun Jun 15 22:05:23 2008 +0200
20.3 @@ -19,163 +19,29 @@
20.4 #ifndef LEMON_TEST_TEST_TOOLS_H
20.5 #define LEMON_TEST_TEST_TOOLS_H
20.6
20.7 +///\ingroup misc
20.8 +///\file
20.9 +///\brief Some utilities to write test programs.
20.10 +
20.11 #include <iostream>
20.12 -#include <vector>
20.13
20.14 -#include <cstdlib>
20.15 -#include <ctime>
20.16 +///If \c rc is fail, writes an error message and exits.
20.17
20.18 -#include <lemon/concept_check.h>
20.19 -#include <lemon/concepts/digraph.h>
20.20 -
20.21 -#include <lemon/random.h>
20.22 -
20.23 -using namespace lemon;
20.24 -
20.25 -//! \ingroup misc
20.26 -//! \file
20.27 -//! \brief Some utilities to write test programs.
20.28 -
20.29 -
20.30 -///If \c rc is fail, writes an error message end exit.
20.31 -
20.32 -///If \c rc is fail, writes an error message end exit.
20.33 +///If \c rc is fail, writes an error message and exits.
20.34 ///The error message contains the file name and the line number of the
20.35 ///source code in a standard from, which makes it possible to go there
20.36 ///using good source browsers like e.g. \c emacs.
20.37 ///
20.38 ///For example
20.39 ///\code check(0==1,"This is obviously false.");\endcode will
20.40 -///print this (and then exits).
20.41 -///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
20.42 +///print something like this (and then exits).
20.43 +///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
20.44 ///
20.45 -///\todo It should be in \c error.h
20.46 +///\todo It should be in \c assert.h
20.47 #define check(rc, msg) \
20.48 if(!(rc)) { \
20.49 std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
20.50 abort(); \
20.51 } else { } \
20.52
20.53 -///Structure returned by \ref addPetersen().
20.54 -
20.55 -///Structure returned by \ref addPetersen().
20.56 -///
20.57 -template<class Digraph> struct PetStruct
20.58 -{
20.59 - ///Vector containing the outer nodes.
20.60 - std::vector<typename Digraph::Node> outer;
20.61 - ///Vector containing the inner nodes.
20.62 - std::vector<typename Digraph::Node> inner;
20.63 - ///Vector containing the arcs of the inner circle.
20.64 - std::vector<typename Digraph::Arc> incir;
20.65 - ///Vector containing the arcs of the outer circle.
20.66 - std::vector<typename Digraph::Arc> outcir;
20.67 - ///Vector containing the chord arcs.
20.68 - std::vector<typename Digraph::Arc> chords;
20.69 -};
20.70 -
20.71 -
20.72 -
20.73 -///Adds a Petersen digraph to \c G.
20.74 -
20.75 -///Adds a Petersen digraph to \c G.
20.76 -///\return The nodes and arcs of the generated digraph.
20.77 -
20.78 -template<typename Digraph>
20.79 -PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
20.80 -{
20.81 - PetStruct<Digraph> n;
20.82 -
20.83 - for(int i=0;i<num;i++) {
20.84 - n.outer.push_back(G.addNode());
20.85 - n.inner.push_back(G.addNode());
20.86 - }
20.87 -
20.88 - for(int i=0;i<num;i++) {
20.89 - n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
20.90 - n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
20.91 - n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
20.92 - }
20.93 - return n;
20.94 -}
20.95 -
20.96 -/// \brief Adds to the digraph the reverse pair of all arcs.
20.97 -///
20.98 -/// Adds to the digraph the reverse pair of all arcs.
20.99 -///
20.100 -template<class Digraph> void bidirDigraph(Digraph &G)
20.101 -{
20.102 - typedef typename Digraph::Arc Arc;
20.103 - typedef typename Digraph::ArcIt ArcIt;
20.104 -
20.105 - std::vector<Arc> ee;
20.106 -
20.107 - for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
20.108 -
20.109 - for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
20.110 - G.addArc(G.target(*p),G.source(*p));
20.111 -}
20.112 -
20.113 -
20.114 -/// \brief Checks the bidirectioned Petersen digraph.
20.115 -///
20.116 -/// Checks the bidirectioned Petersen digraph.
20.117 -///
20.118 -template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
20.119 -{
20.120 - typedef typename Digraph::Node Node;
20.121 -
20.122 - typedef typename Digraph::ArcIt ArcIt;
20.123 - typedef typename Digraph::NodeIt NodeIt;
20.124 -
20.125 - checkDigraphNodeList(G, 2 * num);
20.126 - checkDigraphArcList(G, 6 * num);
20.127 -
20.128 - for(NodeIt n(G);n!=INVALID;++n) {
20.129 - checkDigraphInArcList(G, n, 3);
20.130 - checkDigraphOutArcList(G, n, 3);
20.131 - }
20.132 -}
20.133 -
20.134 -///Structure returned by \ref addUPetersen().
20.135 -
20.136 -///Structure returned by \ref addUPetersen().
20.137 -///
20.138 -template<class Digraph> struct UPetStruct
20.139 -{
20.140 - ///Vector containing the outer nodes.
20.141 - std::vector<typename Digraph::Node> outer;
20.142 - ///Vector containing the inner nodes.
20.143 - std::vector<typename Digraph::Node> inner;
20.144 - ///Vector containing the arcs of the inner circle.
20.145 - std::vector<typename Digraph::Edge> incir;
20.146 - ///Vector containing the arcs of the outer circle.
20.147 - std::vector<typename Digraph::Edge> outcir;
20.148 - ///Vector containing the chord arcs.
20.149 - std::vector<typename Digraph::Edge> chords;
20.150 -};
20.151 -
20.152 -///Adds a Petersen digraph to the undirected \c G.
20.153 -
20.154 -///Adds a Petersen digraph to the undirected \c G.
20.155 -///\return The nodes and arcs of the generated digraph.
20.156 -
20.157 -template<typename Digraph>
20.158 -UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
20.159 -{
20.160 - UPetStruct<Digraph> n;
20.161 -
20.162 - for(int i=0;i<num;i++) {
20.163 - n.outer.push_back(G.addNode());
20.164 - n.inner.push_back(G.addNode());
20.165 - }
20.166 -
20.167 - for(int i=0;i<num;i++) {
20.168 - n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
20.169 - n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));
20.170 - n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
20.171 - }
20.172 - return n;
20.173 -}
20.174 -
20.175 #endif
21.1 --- a/test/time_measure_test.cc Sun Jun 15 22:03:33 2008 +0200
21.2 +++ b/test/time_measure_test.cc Sun Jun 15 22:05:23 2008 +0200
21.3 @@ -18,11 +18,6 @@
21.4
21.5 #include <lemon/time_measure.h>
21.6
21.7 -///\file \brief Test cases for time_measure.h
21.8 -///
21.9 -///\todo To be extended
21.10 -
21.11 -
21.12 using namespace lemon;
21.13
21.14 void f()
22.1 --- a/test/unionfind_test.cc Sun Jun 15 22:03:33 2008 +0200
22.2 +++ b/test/unionfind_test.cc Sun Jun 15 22:05:23 2008 +0200
22.3 @@ -16,8 +16,6 @@
22.4 *
22.5 */
22.6
22.7 -#include <iostream>
22.8 -
22.9 #include <lemon/list_graph.h>
22.10 #include <lemon/maps.h>
22.11 #include <lemon/unionfind.h>
22.12 @@ -39,7 +37,7 @@
22.13 U.insert(n[1]);
22.14 U.insert(n[2]);
22.15
22.16 - check(U.join(n[1],n[2]) != -1,"Test failed.");
22.17 + check(U.join(n[1],n[2]) != -1, "Something is wrong with UnionFindEnum");
22.18
22.19 U.insert(n[3]);
22.20 U.insert(n[4]);
22.21 @@ -48,54 +46,54 @@
22.22 U.insert(n[7]);
22.23
22.24
22.25 - check(U.join(n[1],n[4]) != -1,"Test failed.");
22.26 - check(U.join(n[2],n[4]) == -1,"Test failed.");
22.27 - check(U.join(n[3],n[5]) != -1,"Test failed.");
22.28 + check(U.join(n[1],n[4]) != -1, "Something is wrong with UnionFindEnum");
22.29 + check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
22.30 + check(U.join(n[3],n[5]) != -1, "Something is wrong with UnionFindEnum");
22.31
22.32
22.33 U.insert(n[8],U.find(n[5]));
22.34
22.35
22.36 - check(U.size(U.find(n[4])) == 3,"Test failed.");
22.37 - check(U.size(U.find(n[5])) == 3,"Test failed.");
22.38 - check(U.size(U.find(n[6])) == 1,"Test failed.");
22.39 - check(U.size(U.find(n[2])) == 3,"Test failed.");
22.40 + check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
22.41 + check(U.size(U.find(n[5])) == 3, "Something is wrong with UnionFindEnum");
22.42 + check(U.size(U.find(n[6])) == 1, "Something is wrong with UnionFindEnum");
22.43 + check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
22.44
22.45
22.46 U.insert(n[9]);
22.47 U.insert(n[10],U.find(n[9]));
22.48
22.49
22.50 - check(U.join(n[8],n[10]) != -1,"Test failed.");
22.51 + check(U.join(n[8],n[10]) != -1, "Something is wrong with UnionFindEnum");
22.52
22.53
22.54 - check(U.size(U.find(n[4])) == 3,"Test failed.");
22.55 - check(U.size(U.find(n[9])) == 5,"Test failed.");
22.56 + check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
22.57 + check(U.size(U.find(n[9])) == 5, "Something is wrong with UnionFindEnum");
22.58
22.59 - check(U.size(U.find(n[8])) == 5,"Test failed.");
22.60 + check(U.size(U.find(n[8])) == 5, "Something is wrong with UnionFindEnum");
22.61
22.62 U.erase(n[9]);
22.63 U.erase(n[1]);
22.64
22.65 - check(U.size(U.find(n[10])) == 4,"Test failed.");
22.66 - check(U.size(U.find(n[2])) == 2,"Test failed.");
22.67 + check(U.size(U.find(n[10])) == 4, "Something is wrong with UnionFindEnum");
22.68 + check(U.size(U.find(n[2])) == 2, "Something is wrong with UnionFindEnum");
22.69
22.70 U.erase(n[6]);
22.71 U.split(U.find(n[8]));
22.72
22.73
22.74 - check(U.size(U.find(n[4])) == 2,"Test failed.");
22.75 - check(U.size(U.find(n[3])) == 1,"Test failed.");
22.76 - check(U.size(U.find(n[2])) == 2,"Test failed.");
22.77 + check(U.size(U.find(n[4])) == 2, "Something is wrong with UnionFindEnum");
22.78 + check(U.size(U.find(n[3])) == 1, "Something is wrong with UnionFindEnum");
22.79 + check(U.size(U.find(n[2])) == 2, "Something is wrong with UnionFindEnum");
22.80
22.81
22.82 - check(U.join(n[3],n[4]) != -1,"Test failed.");
22.83 - check(U.join(n[2],n[4]) == -1,"Test failed.");
22.84 + check(U.join(n[3],n[4]) != -1, "Something is wrong with UnionFindEnum");
22.85 + check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
22.86
22.87
22.88 - check(U.size(U.find(n[4])) == 3,"Test failed.");
22.89 - check(U.size(U.find(n[3])) == 3,"Test failed.");
22.90 - check(U.size(U.find(n[2])) == 3,"Test failed.");
22.91 + check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
22.92 + check(U.size(U.find(n[3])) == 3, "Something is wrong with UnionFindEnum");
22.93 + check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
22.94
22.95 U.eraseClass(U.find(n[4]));
22.96 U.eraseClass(U.find(n[7]));