Changeset 171:02f4d5d9bfd7 in lemon for test
- Timestamp:
- 06/15/08 22:05:23 (16 years ago)
- Branch:
- default
- Children:
- 172:c94a80f38d7f, 173:b026e9779b28, 175:4eb8900a865c
- Phase:
- public
- Location:
- test
- Files:
-
- 2 added
- 3 deleted
- 17 edited
Legend:
- Unmodified
- Added
- Removed
-
test/CMakeLists.txt
r170 r171 12 12 error_test 13 13 graph_test 14 graph_utils_test 14 15 kruskal_test 15 16 maps_test 17 path_test 16 18 random_test 17 path_test18 19 time_measure_test 19 20 unionfind_test) -
test/Makefile.am
r170 r171 3 3 4 4 noinst_HEADERS += \ 5 test/digraph_test.h \ 6 test/graph_utils_test.h \ 5 test/graph_test.h \ 7 6 test/heap_test.h \ 8 test/ map_test.h \7 test/graph_maps_test.h \ 9 8 test/test_tools.h 10 9 -
test/bfs_test.cc
r100 r171 17 17 */ 18 18 19 #include "test_tools.h"20 //#include <lemon/smart_graph.h>19 #include <lemon/concepts/digraph.h> 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 22 #include <lemon/bfs.h> 23 23 #include <lemon/path.h> 24 #include<lemon/concepts/digraph.h> 24 25 #include "graph_test.h" 26 #include "test_tools.h" 25 27 26 28 using namespace lemon; 27 29 28 const int PET_SIZE =5; 29 30 31 void check_Bfs_Compile() 30 void checkBfsCompile() 32 31 { 33 32 typedef concepts::Digraph Digraph; 34 35 typedef Digraph::Arc Arc;36 typedef Digraph::Node Node;37 typedef Digraph::ArcIt ArcIt;38 typedef Digraph::NodeIt NodeIt;39 40 33 typedef Bfs<Digraph> BType; 41 34 42 35 Digraph G; 43 Node n;44 Arc e;36 Digraph::Node n; 37 Digraph::Arc e; 45 38 int l; 46 39 bool b; … … 64 57 } 65 58 66 void check _Bfs_Function_Compile()59 void checkBfsFunctionCompile() 67 60 { 68 61 typedef int VType; 69 62 typedef concepts::Digraph Digraph; 70 71 63 typedef Digraph::Arc Arc; 72 64 typedef Digraph::Node Node; 73 typedef Digraph::ArcIt ArcIt;74 typedef Digraph::NodeIt NodeIt;75 typedef concepts::ReadMap<Arc,VType> LengthMap;76 65 77 66 Digraph g; … … 84 73 .processedMap(concepts::WriteMap<Node,bool>()) 85 74 .run(Node()); 86 87 75 } 88 76 89 int main() 90 { 91 92 // typedef SmartDigraph Digraph; 93 typedef ListDigraph Digraph; 94 95 typedef Digraph::Arc Arc; 96 typedef Digraph::Node Node; 97 typedef Digraph::ArcIt ArcIt; 98 typedef Digraph::NodeIt NodeIt; 99 typedef Digraph::ArcMap<int> LengthMap; 77 template <class Digraph> 78 void checkBfs() { 79 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 100 80 101 81 Digraph G; 102 82 Node s, t; 103 PetStruct<Digraph> ps = addPetersen(G, PET_SIZE);83 PetStruct<Digraph> ps = addPetersen(G, 5); 104 84 105 85 s=ps.outer[2]; … … 109 89 bfs_test.run(s); 110 90 111 check(bfs_test.dist(t)==3,"Bfs found a wrong path. 91 check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t)); 112 92 113 93 Path<Digraph> p = bfs_test.path(t); 114 check(p.length()==3," getPath() found a wrong path.");94 check(p.length()==3,"path() found a wrong path."); 115 95 check(checkPath(G, p),"path() found a wrong path."); 116 96 check(pathSource(G, p) == s,"path() found a wrong path."); … … 140 120 } 141 121 122 int main() 123 { 124 checkBfs<ListDigraph>(); 125 checkBfs<SmartDigraph>(); 126 return 0; 127 } -
test/counter_test.cc
r119 r171 18 18 19 19 #include <lemon/counter.h> 20 #include <vector> 20 21 21 ///\file \brief Test cases for time_measure.h 22 /// 23 ///\todo To be extended 22 using namespace lemon; 24 23 24 template <typename T> 25 void bubbleSort(std::vector<T>& v) { 26 Counter op("Bubble Sort - Operations: "); 27 Counter::NoSubCounter as(op, "Assignments: "); 28 Counter::NoSubCounter co(op, "Comparisons: "); 29 for (int i = v.size()-1; i > 0; --i) { 30 for (int j = 0; j < i; ++j) { 31 if (v[j] > v[j+1]) { 32 T tmp = v[j]; 33 v[j] = v[j+1]; 34 v[j+1] = tmp; 35 as += 3; 36 } 37 ++co; 38 } 39 } 40 } 25 41 26 int fibonacci(int f) 27 { 28 static lemon::Counter count("Fibonacci steps: "); 29 count++; 30 if(f<1) return 0; 31 else if(f==1) return 1; 32 else return fibonacci(f-1)+fibonacci(f-2); 42 template <typename T> 43 void insertionSort(std::vector<T>& v) { 44 Counter op("Insertion Sort - Operations: "); 45 Counter::NoSubCounter as(op, "Assignments: "); 46 Counter::NoSubCounter co(op, "Comparisons: "); 47 for (int i = 1; i < int(v.size()); ++i) { 48 T value = v[i]; 49 ++as; 50 int j = i; 51 while (j > 0 && v[j-1] > value) { 52 v[j] = v[j-1]; 53 --j; 54 ++co; ++as; 55 } 56 v[j] = value; 57 ++as; 58 } 59 } 60 61 template <typename MyCounter> 62 void counterTest() { 63 MyCounter c("Main Counter: "); 64 c++; 65 typename MyCounter::SubCounter d(c, "SubCounter: "); 66 d++; 67 typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: "); 68 e++; 69 d+=3; 70 c-=4; 71 e-=2; 72 c.reset(2); 73 c.reset(); 74 } 75 76 void init(std::vector<int>& v) { 77 v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100; 78 v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70; 33 79 } 34 80 35 81 int main() 36 82 { 37 fibonacci(10); 83 counterTest<Counter>(); 84 counterTest<NoCounter>(); 38 85 39 { 40 typedef lemon::Counter MyCounter; 41 MyCounter c("Main counter: "); 42 c++; 43 c++; 44 MyCounter::SubCounter d(c,"Subcounter: "); 45 d++; 46 d++; 47 MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: "); 48 e++; 49 e++; 50 } 51 52 { 53 typedef lemon::NoCounter MyCounter; 54 MyCounter c("Main counter: "); 55 c++; 56 c++; 57 MyCounter::SubCounter d(c,"Subcounter: "); 58 d++; 59 d++; 60 MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: "); 61 e++; 62 e++; 63 } 86 std::vector<int> x(10); 87 init(x); bubbleSort(x); 88 init(x); insertionSort(x); 64 89 65 90 return 0; -
test/dfs_test.cc
r100 r171 17 17 */ 18 18 19 #include "test_tools.h"20 //#include <lemon/smart_graph.h>19 #include <lemon/concepts/digraph.h> 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 22 #include <lemon/dfs.h> 23 23 #include <lemon/path.h> 24 #include <lemon/concepts/digraph.h> 24 25 #include "graph_test.h" 26 #include "test_tools.h" 25 27 26 28 using namespace lemon; 27 29 28 const int PET_SIZE =5; 29 30 31 void check_Dfs_SmartDigraph_Compile() 30 void checkDfsCompile() 32 31 { 33 32 typedef concepts::Digraph Digraph; 34 35 typedef Digraph::Arc Arc;36 typedef Digraph::Node Node;37 typedef Digraph::ArcIt ArcIt;38 typedef Digraph::NodeIt NodeIt;39 40 33 typedef Dfs<Digraph> DType; 41 34 42 35 Digraph G; 43 Node n;44 Arc e;36 Digraph::Node n; 37 Digraph::Arc e; 45 38 int l; 46 39 bool b; … … 64 57 } 65 58 66 67 void check_Dfs_Function_Compile() 59 void checkDfsFunctionCompile() 68 60 { 69 61 typedef int VType; 70 62 typedef concepts::Digraph Digraph; 71 72 63 typedef Digraph::Arc Arc; 73 64 typedef Digraph::Node Node; 74 typedef Digraph::ArcIt ArcIt;75 typedef Digraph::NodeIt NodeIt;76 typedef concepts::ReadMap<Arc,VType> LengthMap;77 65 78 66 Digraph g; … … 84 72 .reachedMap(concepts::ReadWriteMap<Node,bool>()) 85 73 .processedMap(concepts::WriteMap<Node,bool>()) 86 .run(Node()); 87 74 .run(Node()); 88 75 } 89 76 90 int main() 91 { 92 93 // typedef SmartDigraph Digraph; 94 typedef ListDigraph Digraph; 95 96 typedef Digraph::Arc Arc; 97 typedef Digraph::Node Node; 98 typedef Digraph::ArcIt ArcIt; 99 typedef Digraph::NodeIt NodeIt; 100 typedef Digraph::ArcMap<int> LengthMap; 77 template <class Digraph> 78 void checkDfs() { 79 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 101 80 102 81 Digraph G; 103 82 Node s, t; 104 PetStruct<Digraph> ps = addPetersen(G, PET_SIZE);83 PetStruct<Digraph> ps = addPetersen(G, 5); 105 84 106 85 s=ps.outer[2]; … … 111 90 112 91 Path<Digraph> p = dfs_test.path(t); 113 check(p.length() ==dfs_test.dist(t),"path() found a wrong path.");92 check(p.length() == dfs_test.dist(t),"path() found a wrong path."); 114 93 check(checkPath(G, p),"path() found a wrong path."); 115 94 check(pathSource(G, p) == s,"path() found a wrong path."); … … 129 108 } 130 109 110 int main() 111 { 112 checkDfs<ListDigraph>(); 113 checkDfs<SmartDigraph>(); 114 return 0; 115 } -
test/digraph_test.cc
r107 r171 17 17 */ 18 18 19 #include <iostream>20 #include <vector>21 22 19 #include <lemon/concepts/digraph.h> 23 20 #include <lemon/list_graph.h> 24 //#include <lemon/smart_graph.h>21 #include <lemon/smart_graph.h> 25 22 //#include <lemon/full_graph.h> 26 23 //#include <lemon/hypercube_graph.h> 27 24 28 25 #include "test_tools.h" 29 #include "digraph_test.h" 30 #include "map_test.h" 31 26 #include "graph_test.h" 27 #include "graph_maps_test.h" 32 28 33 29 using namespace lemon; 34 30 using namespace lemon::concepts; 35 31 36 37 int main() { 38 { // checking digraph components 32 void check_concepts() { 33 { // Checking digraph components 39 34 checkConcept<BaseDigraphComponent, BaseDigraphComponent >(); 40 35 … … 47 42 checkConcept<MappableDigraphComponent<>, 48 43 MappableDigraphComponent<> >(); 49 50 44 } 51 { // checking skeleton digraphs45 { // Checking skeleton digraph 52 46 checkConcept<Digraph, Digraph>(); 53 47 } 54 { // checking list digraph55 checkConcept<Digraph, ListDigraph 48 { // Checking ListDigraph 49 checkConcept<Digraph, ListDigraph>(); 56 50 checkConcept<AlterableDigraphComponent<>, ListDigraph>(); 57 51 checkConcept<ExtendableDigraphComponent<>, ListDigraph>(); 58 52 checkConcept<ClearableDigraphComponent<>, ListDigraph>(); 59 53 checkConcept<ErasableDigraphComponent<>, ListDigraph>(); 54 checkDigraphIterators<ListDigraph>(); 55 } 56 { // Checking SmartDigraph 57 checkConcept<Digraph, SmartDigraph>(); 58 checkConcept<AlterableDigraphComponent<>, SmartDigraph>(); 59 checkConcept<ExtendableDigraphComponent<>, SmartDigraph>(); 60 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 61 checkDigraphIterators<SmartDigraph>(); 62 } 63 // { // Checking FullDigraph 64 // checkConcept<Digraph, FullDigraph>(); 65 // checkDigraphIterators<FullDigraph>(); 66 // } 67 // { // Checking HyperCubeDigraph 68 // checkConcept<Digraph, HyperCubeDigraph>(); 69 // checkDigraphIterators<HyperCubeDigraph>(); 70 // } 71 } 60 72 73 template <typename Digraph> 74 void check_graph_validity() { 75 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 76 Digraph g; 77 78 Node 79 n1 = g.addNode(), 80 n2 = g.addNode(), 81 n3 = g.addNode(); 82 83 Arc 84 e1 = g.addArc(n1, n2), 85 e2 = g.addArc(n2, n3); 86 87 check(g.valid(n1), "Wrong validity check"); 88 check(g.valid(e1), "Wrong validity check"); 89 90 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); 91 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 92 } 93 94 template <typename Digraph> 95 void check_graph_validity_erase() { 96 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 97 Digraph g; 98 99 Node 100 n1 = g.addNode(), 101 n2 = g.addNode(), 102 n3 = g.addNode(); 103 104 Arc 105 e1 = g.addArc(n1, n2), 106 e2 = g.addArc(n2, n3); 107 108 check(g.valid(n1), "Wrong validity check"); 109 check(g.valid(e1), "Wrong validity check"); 110 111 g.erase(n1); 112 113 check(!g.valid(n1), "Wrong validity check"); 114 check(g.valid(n2), "Wrong validity check"); 115 check(g.valid(n3), "Wrong validity check"); 116 check(!g.valid(e1), "Wrong validity check"); 117 check(g.valid(e2), "Wrong validity check"); 118 119 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); 120 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 121 } 122 123 void check_digraphs() { 124 { // Checking ListDigraph 61 125 checkDigraph<ListDigraph>(); 62 126 checkGraphNodeMap<ListDigraph>(); 63 127 checkGraphArcMap<ListDigraph>(); 128 129 check_graph_validity_erase<ListDigraph>(); 64 130 } 65 // { // checking smart digraph 66 // checkConcept<Digraph, SmartDigraph >(); 131 { // Checking SmartDigraph 132 checkDigraph<SmartDigraph>(); 133 checkGraphNodeMap<SmartDigraph>(); 134 checkGraphArcMap<SmartDigraph>(); 67 135 68 // checkDigraph<SmartDigraph>(); 69 // checkDigraphNodeMap<SmartDigraph>(); 70 // checkDigraphArcMap<SmartDigraph>(); 71 // } 72 // { // checking full digraph 73 // checkConcept<Digraph, FullDigraph >(); 74 // } 75 // { // checking full digraph 76 // checkConcept<Digraph, HyperCubeDigraph >(); 77 // } 136 check_graph_validity<SmartDigraph>(); 137 } 138 } 78 139 79 std::cout << __FILE__ ": All tests passed.\n"; 80 140 int main() { 141 check_concepts(); 142 check_digraphs(); 81 143 return 0; 82 144 } -
test/dijkstra_test.cc
r170 r171 17 17 */ 18 18 19 ///\file20 ///\brief Test cases for Dijkstra algorithm.21 22 19 #include <lemon/concepts/digraph.h> 23 20 #include <lemon/smart_graph.h> … … 27 24 #include <lemon/path.h> 28 25 26 #include "graph_test.h" 29 27 #include "test_tools.h" 30 28 -
test/dim_test.cc
r39 r171 26 26 int main() 27 27 { 28 cout << "Testing classes 'dim2::Point' and 'dim2::BoundingBox'." << endl;29 30 28 typedef dim2::Point<int> Point; 31 29 32 30 Point p; 33 check(p.size()==2, "Wrong vectorinitialization.");31 check(p.size()==2, "Wrong dim2::Point initialization."); 34 32 35 33 Point a(1,2); 36 34 Point b(3,4); 37 check(a[0]==1 && a[1]==2, "Wrong vectorinitialization.");35 check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization."); 38 36 39 37 p = a+b; 40 check(p.x==4 && p.y==6, "Wrong vectoraddition.");38 check(p.x==4 && p.y==6, "Wrong dim2::Point addition."); 41 39 42 40 p = a-b; 43 check(p.x==-2 && p.y==-2, "Wrong vectorsubtraction.");41 check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction."); 44 42 45 check(a.normSquare()==5,"Wrong vectornorm calculation.");46 check(a*b==11, "Wrong vectorscalar product.");43 check(a.normSquare()==5,"Wrong dim2::Point norm calculation."); 44 check(a*b==11, "Wrong dim2::Point scalar product."); 47 45 48 46 int l=2; 49 47 p = a*l; 50 check(p.x==2 && p.y==4, "Wrong vectormultiplication by a scalar.");48 check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar."); 51 49 52 50 p = b/l; 53 check(p.x==1 && p.y==2, "Wrong vectordivision by a scalar.");51 check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar."); 54 52 55 53 typedef dim2::BoundingBox<int> BB; 56 54 BB box1; 57 check(box1.empty(), " It should be empty.");55 check(box1.empty(), "Wrong empty() in dim2::BoundingBox."); 58 56 59 57 box1.add(a); 60 check(!box1.empty(), " It should not be empty.");58 check(!box1.empty(), "Wrong empty() in dim2::BoundingBox."); 61 59 box1.add(b); 62 60 … … 65 63 box1.topRight().x==3 && 66 64 box1.topRight().y==4, 67 "Wrong addition of points to box.");65 "Wrong addition of points to dim2::BoundingBox."); 68 66 69 67 p.x=2; p.y=3; 70 check(box1.inside(p), " It should be inside.");68 check(box1.inside(p), "Wrong inside() in dim2::BoundingBox."); 71 69 72 70 p.x=1; p.y=3; 73 check(box1.inside(p), " It should be inside.");71 check(box1.inside(p), "Wrong inside() in dim2::BoundingBox."); 74 72 75 73 p.x=0; p.y=3; 76 check(!box1.inside(p), " It should not be inside.");74 check(!box1.inside(p), "Wrong inside() in dim2::BoundingBox."); 77 75 78 76 BB box2(p); 79 check(!box2.empty(), 80 "It should not be empty. Constructed from 1 point."); 77 check(!box2.empty(), "Wrong empty() in dim2::BoundingBox."); 81 78 82 79 box2.add(box1); 83 check(box2.inside(p), 84 "It should be inside. Incremented a box with another one."); 80 check(box2.inside(p), "Wrong inside() in dim2::BoundingBox."); 85 81 86 82 return 0; -
test/error_test.cc
r118 r171 55 55 #undef LEMON_DISABLE_ASSERTS 56 56 57 //checking custom assert handler 57 58 #define LEMON_ASSERT_CUSTOM 58 59 -
test/graph_test.cc
r149 r171 23 23 // #include <lemon/grid_graph.h> 24 24 25 #include <lemon/graph_utils.h>26 27 25 #include "test_tools.h" 28 26 #include "graph_test.h" 27 #include "graph_maps_test.h" 29 28 30 29 using namespace lemon; … … 32 31 33 32 void check_concepts() { 34 35 { // checking digraph components 33 { // Checking graph components 36 34 checkConcept<BaseGraphComponent, BaseGraphComponent >(); 37 35 … … 44 42 checkConcept<MappableGraphComponent<>, 45 43 MappableGraphComponent<> >(); 46 47 } 48 { 49 checkConcept<Graph, ListGraph>(); 50 checkConcept<Graph, SmartGraph>(); 51 // checkConcept<Graph, FullGraph>(); 52 // checkConcept<Graph, Graph>(); 53 // checkConcept<Graph, GridGraph>(); 54 } 44 } 45 { // Checking skeleton graph 46 checkConcept<Graph, Graph>(); 47 } 48 { // Checking ListGraph 49 checkConcept<Graph, ListGraph>(); 50 checkConcept<AlterableGraphComponent<>, ListGraph>(); 51 checkConcept<ExtendableGraphComponent<>, ListGraph>(); 52 checkConcept<ClearableGraphComponent<>, ListGraph>(); 53 checkConcept<ErasableGraphComponent<>, ListGraph>(); 54 checkGraphIterators<ListGraph>(); 55 } 56 { // Checking SmartGraph 57 checkConcept<Graph, SmartGraph>(); 58 checkConcept<AlterableGraphComponent<>, SmartGraph>(); 59 checkConcept<ExtendableGraphComponent<>, SmartGraph>(); 60 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 61 checkGraphIterators<SmartGraph>(); 62 } 63 // { // Checking FullGraph 64 // checkConcept<Graph, FullGraph>(); 65 // checkGraphIterators<FullGraph>(); 66 // } 67 // { // Checking GridGraph 68 // checkConcept<Graph, GridGraph>(); 69 // checkGraphIterators<GridGraph>(); 70 // } 55 71 } 56 72 57 73 template <typename Graph> 58 void check_item_counts(Graph &g, int n, int e) { 59 int nn = 0; 60 for (typename Graph::NodeIt it(g); it != INVALID; ++it) { 61 ++nn; 62 } 63 64 check(nn == n, "Wrong node number."); 65 // check(countNodes(g) == n, "Wrong node number."); 66 67 int ee = 0; 68 for (typename Graph::ArcIt it(g); it != INVALID; ++it) { 69 ++ee; 70 } 71 72 check(ee == 2*e, "Wrong arc number."); 73 // check(countArcs(g) == 2*e, "Wrong arc number."); 74 75 int uee = 0; 76 for (typename Graph::EdgeIt it(g); it != INVALID; ++it) { 77 ++uee; 78 } 79 80 check(uee == e, "Wrong edge number."); 81 // check(countEdges(g) == e, "Wrong edge number."); 82 } 83 84 template <typename Graph> 85 void check_graph_counts() { 86 74 void check_graph_validity() { 87 75 TEMPLATE_GRAPH_TYPEDEFS(Graph); 88 76 Graph g; 89 90 check_item_counts(g,0,0);91 77 92 78 Node … … 99 85 e2 = g.addEdge(n2, n3); 100 86 101 check_item_counts(g,3,2); 87 check(g.valid(n1), "Wrong validity check"); 88 check(g.valid(e1), "Wrong validity check"); 89 check(g.valid(g.direct(e1, true)), "Wrong validity check"); 90 91 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); 92 check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); 93 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 102 94 } 103 95 104 96 template <typename Graph> 105 void check_graph_validity() { 106 97 void check_graph_validity_erase() { 107 98 TEMPLATE_GRAPH_TYPEDEFS(Graph); 108 99 Graph g; 109 110 check_item_counts(g,0,0);111 100 112 101 Node … … 119 108 e2 = g.addEdge(n2, n3); 120 109 121 check(g.valid(n1), "Validity check"); 122 check(g.valid(e1), "Validity check"); 123 check(g.valid(g.direct(e1, true)), "Validity check"); 124 125 check(!g.valid(g.nodeFromId(-1)), "Validity check"); 126 check(!g.valid(g.edgeFromId(-1)), "Validity check"); 127 check(!g.valid(g.arcFromId(-1)), "Validity check"); 128 129 } 130 131 template <typename Graph> 132 void check_graph_validity_erase() { 133 134 TEMPLATE_GRAPH_TYPEDEFS(Graph); 135 Graph g; 136 137 check_item_counts(g,0,0); 138 139 Node 140 n1 = g.addNode(), 141 n2 = g.addNode(), 142 n3 = g.addNode(); 143 144 Edge 145 e1 = g.addEdge(n1, n2), 146 e2 = g.addEdge(n2, n3); 147 148 check(g.valid(n1), "Validity check"); 149 check(g.valid(e1), "Validity check"); 150 check(g.valid(g.direct(e1, true)), "Validity check"); 110 check(g.valid(n1), "Wrong validity check"); 111 check(g.valid(e1), "Wrong validity check"); 112 check(g.valid(g.direct(e1, true)), "Wrong validity check"); 151 113 152 114 g.erase(n1); 153 115 154 check(!g.valid(n1), "Validity check"); 155 check(g.valid(n2), "Validity check"); 156 check(g.valid(n3), "Validity check"); 157 check(!g.valid(e1), "Validity check"); 158 check(g.valid(e2), "Validity check"); 159 160 check(!g.valid(g.nodeFromId(-1)), "Validity check"); 161 check(!g.valid(g.edgeFromId(-1)), "Validity check"); 162 check(!g.valid(g.arcFromId(-1)), "Validity check"); 163 164 } 165 166 116 check(!g.valid(n1), "Wrong validity check"); 117 check(g.valid(n2), "Wrong validity check"); 118 check(g.valid(n3), "Wrong validity check"); 119 check(!g.valid(e1), "Wrong validity check"); 120 check(g.valid(e2), "Wrong validity check"); 121 122 check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); 123 check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); 124 check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); 125 } 167 126 168 127 // void checkGridGraph(const GridGraph& g, int w, int h) { … … 210 169 // } 211 170 171 void check_graphs() { 172 { // Checking ListGraph 173 checkGraph<ListGraph>(); 174 checkGraphNodeMap<ListGraph>(); 175 checkGraphEdgeMap<ListGraph>(); 176 177 check_graph_validity_erase<ListGraph>(); 178 } 179 { // Checking SmartGraph 180 checkGraph<SmartGraph>(); 181 checkGraphNodeMap<SmartGraph>(); 182 checkGraphEdgeMap<SmartGraph>(); 183 184 check_graph_validity<SmartGraph>(); 185 } 186 // { // Checking FullGraph 187 // FullGraph g(5); 188 // checkGraphNodeList(g, 5); 189 // checkGraphEdgeList(g, 10); 190 // } 191 // { // Checking GridGraph 192 // GridGraph g(5, 6); 193 // checkGraphNodeList(g, 30); 194 // checkGraphEdgeList(g, 49); 195 // checkGridGraph(g, 5, 6); 196 // } 197 } 198 212 199 int main() { 213 200 check_concepts(); 214 215 check_graph_counts<ListGraph>(); 216 check_graph_counts<SmartGraph>(); 217 218 check_graph_validity_erase<ListGraph>(); 219 check_graph_validity<SmartGraph>(); 220 221 // { 222 // FullGraph g(5); 223 // check_item_counts(g, 5, 10); 224 // } 225 226 // { 227 // GridGraph g(5, 6); 228 // check_item_counts(g, 30, 49); 229 // checkGridGraph(g, 5, 6); 230 // } 231 232 std::cout << __FILE__ ": All tests passed.\n"; 233 201 check_graphs(); 234 202 return 0; 235 203 } -
test/graph_utils_test.cc
r139 r171 17 17 */ 18 18 19 #include <iostream> 20 #include <vector> 21 19 #include <cstdlib> 20 #include <ctime> 21 22 #include <lemon/random.h> 22 23 #include <lemon/graph_utils.h> 23 24 24 #include <lemon/list_graph.h> 25 25 #include <lemon/smart_graph.h> 26 26 27 #include "graph_test.h" 27 28 #include "test_tools.h" 28 #include "graph_utils_test.h"29 30 29 31 30 using namespace lemon; 32 31 33 template <class Graph> 34 void checkSnapDeg() 32 template <typename Digraph> 33 void checkFindArcs() { 34 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 35 36 { 37 Digraph digraph; 38 for (int i = 0; i < 10; ++i) { 39 digraph.addNode(); 40 } 41 DescriptorMap<Digraph, Node> nodes(digraph); 42 typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes); 43 for (int i = 0; i < 100; ++i) { 44 int src = rnd[invNodes.size()]; 45 int trg = rnd[invNodes.size()]; 46 digraph.addArc(invNodes[src], invNodes[trg]); 47 } 48 typename Digraph::template ArcMap<bool> found(digraph, false); 49 DescriptorMap<Digraph, Arc> arcs(digraph); 50 for (NodeIt src(digraph); src != INVALID; ++src) { 51 for (NodeIt trg(digraph); trg != INVALID; ++trg) { 52 for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) { 53 check(digraph.source(con) == src, "Wrong source."); 54 check(digraph.target(con) == trg, "Wrong target."); 55 check(found[con] == false, "The arc found already."); 56 found[con] = true; 57 } 58 } 59 } 60 for (ArcIt it(digraph); it != INVALID; ++it) { 61 check(found[it] == true, "The arc is not found."); 62 } 63 } 64 65 { 66 int num = 5; 67 Digraph fg; 68 std::vector<Node> nodes; 69 for (int i = 0; i < num; ++i) { 70 nodes.push_back(fg.addNode()); 71 } 72 for (int i = 0; i < num * num; ++i) { 73 fg.addArc(nodes[i / num], nodes[i % num]); 74 } 75 check(countNodes(fg) == num, "Wrong node number."); 76 check(countArcs(fg) == num*num, "Wrong arc number."); 77 for (NodeIt src(fg); src != INVALID; ++src) { 78 for (NodeIt trg(fg); trg != INVALID; ++trg) { 79 ConArcIt<Digraph> con(fg, src, trg); 80 check(con != INVALID, "There is no connecting arc."); 81 check(fg.source(con) == src, "Wrong source."); 82 check(fg.target(con) == trg, "Wrong target."); 83 check(++con == INVALID, "There is more connecting arc."); 84 } 85 } 86 ArcLookUp<Digraph> al1(fg); 87 DynArcLookUp<Digraph> al2(fg); 88 AllArcLookUp<Digraph> al3(fg); 89 for (NodeIt src(fg); src != INVALID; ++src) { 90 for (NodeIt trg(fg); trg != INVALID; ++trg) { 91 Arc con1 = al1(src, trg); 92 Arc con2 = al2(src, trg); 93 Arc con3 = al3(src, trg); 94 Arc con4 = findArc(fg, src, trg); 95 check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.") 96 check(con1 != INVALID, "There is no connecting arc."); 97 check(fg.source(con1) == src, "Wrong source."); 98 check(fg.target(con1) == trg, "Wrong target."); 99 check(al3(src, trg, con3) == INVALID, "There is more connecting arc."); 100 check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc."); 101 } 102 } 103 } 104 } 105 106 template <typename Graph> 107 void checkFindEdges() { 108 TEMPLATE_GRAPH_TYPEDEFS(Graph); 109 Graph graph; 110 for (int i = 0; i < 10; ++i) { 111 graph.addNode(); 112 } 113 DescriptorMap<Graph, Node> nodes(graph); 114 typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes); 115 for (int i = 0; i < 100; ++i) { 116 int src = rnd[invNodes.size()]; 117 int trg = rnd[invNodes.size()]; 118 graph.addEdge(invNodes[src], invNodes[trg]); 119 } 120 typename Graph::template EdgeMap<int> found(graph, 0); 121 DescriptorMap<Graph, Edge> edges(graph); 122 for (NodeIt src(graph); src != INVALID; ++src) { 123 for (NodeIt trg(graph); trg != INVALID; ++trg) { 124 for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) { 125 check( (graph.u(con) == src && graph.v(con) == trg) || 126 (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes."); 127 ++found[con]; 128 check(found[con] <= 2, "The edge found more than twice."); 129 } 130 } 131 } 132 for (EdgeIt it(graph); it != INVALID; ++it) { 133 check( (graph.u(it) != graph.v(it) && found[it] == 2) || 134 (graph.u(it) == graph.v(it) && found[it] == 1), 135 "The edge is not found correctly."); 136 } 137 } 138 139 template <class Digraph> 140 void checkDeg() 35 141 { 36 Graph g; 37 typename Graph::Node n1=g.addNode(); 38 typename Graph::Node n2=g.addNode(); 39 40 InDegMap<Graph> ind(g); 41 142 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 143 144 const int nodeNum = 10; 145 const int arcNum = 100; 146 Digraph digraph; 147 InDegMap<Digraph> inDeg(digraph); 148 OutDegMap<Digraph> outDeg(digraph); 149 std::vector<Node> nodes(nodeNum); 150 for (int i = 0; i < nodeNum; ++i) { 151 nodes[i] = digraph.addNode(); 152 } 153 std::vector<Arc> arcs(arcNum); 154 for (int i = 0; i < arcNum; ++i) { 155 arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]); 156 } 157 for (int i = 0; i < nodeNum; ++i) { 158 check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 159 "Wrong in degree map"); 160 } 161 for (int i = 0; i < nodeNum; ++i) { 162 check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 163 "Wrong out degree map"); 164 } 165 } 166 167 template <class Digraph> 168 void checkSnapDeg() 169 { 170 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 171 172 Digraph g; 173 Node n1=g.addNode(); 174 Node n2=g.addNode(); 175 176 InDegMap<Digraph> ind(g); 177 42 178 g.addArc(n1,n2); 43 179 44 typename Graph::Snapshot snap(g);45 46 OutDegMap< Graph> outd(g);180 typename Digraph::Snapshot snap(g); 181 182 OutDegMap<Digraph> outd(g); 47 183 48 184 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); … … 51 187 g.addArc(n1,n2); 52 188 g.addArc(n2,n1); 53 189 54 190 check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value."); 55 191 check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value."); … … 59 195 check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value."); 60 196 check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value."); 61 62 197 } 63 198 64 199 int main() { 65 ///\file 66 { // checking list graph 67 checkDigraphCounters<ListDigraph>(); 68 checkFindArc<ListDigraph>(); 69 } 70 { // checking smart graph 71 checkDigraphCounters<SmartDigraph>(); 72 checkFindArc<SmartDigraph>(); 73 } 74 { 75 int num = 5; 76 SmartDigraph fg; 77 std::vector<SmartDigraph::Node> nodes; 78 for (int i = 0; i < num; ++i) { 79 nodes.push_back(fg.addNode()); 80 } 81 for (int i = 0; i < num * num; ++i) { 82 fg.addArc(nodes[i / num], nodes[i % num]); 83 } 84 check(countNodes(fg) == num, "FullGraph: wrong node number."); 85 check(countArcs(fg) == num*num, "FullGraph: wrong arc number."); 86 for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) { 87 for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) { 88 ConArcIt<SmartDigraph> con(fg, src, trg); 89 check(con != INVALID, "There is no connecting arc."); 90 check(fg.source(con) == src, "Wrong source."); 91 check(fg.target(con) == trg, "Wrong target."); 92 check(++con == INVALID, "There is more connecting arc."); 93 } 94 } 95 AllArcLookUp<SmartDigraph> el(fg); 96 for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) { 97 for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) { 98 SmartDigraph::Arc con = el(src, trg); 99 check(con != INVALID, "There is no connecting arc."); 100 check(fg.source(con) == src, "Wrong source."); 101 check(fg.target(con) == trg, "Wrong target."); 102 check(el(src,trg,con) == INVALID, "There is more connecting arc."); 103 } 104 } 105 } 106 107 //check In/OutDegMap (and Snapshot feature) 108 200 // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp 201 checkFindArcs<ListDigraph>(); 202 checkFindArcs<SmartDigraph>(); 203 checkFindEdges<ListGraph>(); 204 checkFindEdges<SmartGraph>(); 205 206 // Checking In/OutDegMap (and Snapshot feature) 207 checkDeg<ListDigraph>(); 208 checkDeg<SmartDigraph>(); 109 209 checkSnapDeg<ListDigraph>(); 110 210 checkSnapDeg<SmartDigraph>(); 111 112 {113 const int nodeNum = 10;114 const int arcNum = 100;115 ListDigraph digraph;116 InDegMap<ListDigraph> inDeg(digraph);117 OutDegMap<ListDigraph> outDeg(digraph);118 std::vector<ListDigraph::Node> nodes(nodeNum);119 for (int i = 0; i < nodeNum; ++i) {120 nodes[i] = digraph.addNode();121 }122 std::vector<ListDigraph::Arc> arcs(arcNum);123 for (int i = 0; i < arcNum; ++i) {124 arcs[i] =125 digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);126 }127 for (int i = 0; i < nodeNum; ++i) {128 check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]),129 "Wrong in degree map");130 }131 for (int i = 0; i < nodeNum; ++i) {132 check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]),133 "Wrong in degree map");134 }135 }136 137 ///Everything is OK138 std::cout << __FILE__ ": All tests passed.\n";139 211 140 212 return 0; -
test/heap_test.cc
r100 r171 43 43 using namespace lemon::concepts; 44 44 45 46 45 int main() { 47 46 … … 78 77 79 78 { 80 std::c err<< "Checking Bin Heap" << std::endl;79 std::cout << "Checking Bin Heap" << std::endl; 81 80 82 81 typedef BinHeap<Prio, ItemIntMap> IntHeap; … … 92 91 } 93 92 { 94 std::c err<< "Checking Fib Heap" << std::endl;93 std::cout << "Checking Fib Heap" << std::endl; 95 94 96 95 typedef FibHeap<Prio, ItemIntMap> IntHeap; … … 106 105 } 107 106 { 108 std::c err<< "Checking Radix Heap" << std::endl;107 std::cout << "Checking Radix Heap" << std::endl; 109 108 110 109 typedef RadixHeap<ItemIntMap> IntHeap; … … 121 120 122 121 { 123 std::c err<< "Checking Bucket Heap" << std::endl;122 std::cout << "Checking Bucket Heap" << std::endl; 124 123 125 124 typedef BucketHeap<ItemIntMap> IntHeap; … … 135 134 } 136 135 137 std::cout << __FILE__ ": All tests passed.\n";138 139 136 return 0; 140 137 } -
test/kruskal_test.cc
r103 r171 29 29 #include <lemon/concepts/graph.h> 30 30 31 32 31 using namespace std; 33 32 using namespace lemon; … … 58 57 kruskal(g, r, ws.begin()); 59 58 kruskal(ug, ur, uws.begin()); 60 61 59 } 62 60 … … 98 96 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10, 99 97 "Total cost should be 10"); 100 //Test with a edge map (filled with uniform costs).98 //Test with an edge map (filled with uniform costs). 101 99 check(kruskal(G, edge_cost_map, tree_map)==10, 102 100 "Total cost should be 10"); -
test/random_test.cc
r102 r171 20 20 #include "test_tools.h" 21 21 22 ///\file \brief Test cases for random.h23 ///24 ///\todo To be extended25 ///26 27 22 int seed_array[] = {1, 2}; 28 23 -
test/test_tools.h
r100 r171 20 20 #define LEMON_TEST_TEST_TOOLS_H 21 21 22 ///\ingroup misc 23 ///\file 24 ///\brief Some utilities to write test programs. 25 22 26 #include <iostream> 23 #include <vector>24 27 25 #include <cstdlib> 26 #include <ctime> 28 ///If \c rc is fail, writes an error message and exits. 27 29 28 #include <lemon/concept_check.h> 29 #include <lemon/concepts/digraph.h> 30 31 #include <lemon/random.h> 32 33 using namespace lemon; 34 35 //! \ingroup misc 36 //! \file 37 //! \brief Some utilities to write test programs. 38 39 40 ///If \c rc is fail, writes an error message end exit. 41 42 ///If \c rc is fail, writes an error message end exit. 30 ///If \c rc is fail, writes an error message and exits. 43 31 ///The error message contains the file name and the line number of the 44 32 ///source code in a standard from, which makes it possible to go there … … 47 35 ///For example 48 36 ///\code check(0==1,"This is obviously false.");\endcode will 49 ///print this (and then exits).50 ///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim37 ///print something like this (and then exits). 38 ///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim 51 39 /// 52 ///\todo It should be in \c error.h40 ///\todo It should be in \c assert.h 53 41 #define check(rc, msg) \ 54 42 if(!(rc)) { \ … … 57 45 } else { } \ 58 46 59 ///Structure returned by \ref addPetersen().60 61 ///Structure returned by \ref addPetersen().62 ///63 template<class Digraph> struct PetStruct64 {65 ///Vector containing the outer nodes.66 std::vector<typename Digraph::Node> outer;67 ///Vector containing the inner nodes.68 std::vector<typename Digraph::Node> inner;69 ///Vector containing the arcs of the inner circle.70 std::vector<typename Digraph::Arc> incir;71 ///Vector containing the arcs of the outer circle.72 std::vector<typename Digraph::Arc> outcir;73 ///Vector containing the chord arcs.74 std::vector<typename Digraph::Arc> chords;75 };76 77 78 79 ///Adds a Petersen digraph to \c G.80 81 ///Adds a Petersen digraph to \c G.82 ///\return The nodes and arcs of the generated digraph.83 84 template<typename Digraph>85 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)86 {87 PetStruct<Digraph> n;88 89 for(int i=0;i<num;i++) {90 n.outer.push_back(G.addNode());91 n.inner.push_back(G.addNode());92 }93 94 for(int i=0;i<num;i++) {95 n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));96 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));97 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));98 }99 return n;100 }101 102 /// \brief Adds to the digraph the reverse pair of all arcs.103 ///104 /// Adds to the digraph the reverse pair of all arcs.105 ///106 template<class Digraph> void bidirDigraph(Digraph &G)107 {108 typedef typename Digraph::Arc Arc;109 typedef typename Digraph::ArcIt ArcIt;110 111 std::vector<Arc> ee;112 113 for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);114 115 for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)116 G.addArc(G.target(*p),G.source(*p));117 }118 119 120 /// \brief Checks the bidirectioned Petersen digraph.121 ///122 /// Checks the bidirectioned Petersen digraph.123 ///124 template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)125 {126 typedef typename Digraph::Node Node;127 128 typedef typename Digraph::ArcIt ArcIt;129 typedef typename Digraph::NodeIt NodeIt;130 131 checkDigraphNodeList(G, 2 * num);132 checkDigraphArcList(G, 6 * num);133 134 for(NodeIt n(G);n!=INVALID;++n) {135 checkDigraphInArcList(G, n, 3);136 checkDigraphOutArcList(G, n, 3);137 }138 }139 140 ///Structure returned by \ref addUPetersen().141 142 ///Structure returned by \ref addUPetersen().143 ///144 template<class Digraph> struct UPetStruct145 {146 ///Vector containing the outer nodes.147 std::vector<typename Digraph::Node> outer;148 ///Vector containing the inner nodes.149 std::vector<typename Digraph::Node> inner;150 ///Vector containing the arcs of the inner circle.151 std::vector<typename Digraph::Edge> incir;152 ///Vector containing the arcs of the outer circle.153 std::vector<typename Digraph::Edge> outcir;154 ///Vector containing the chord arcs.155 std::vector<typename Digraph::Edge> chords;156 };157 158 ///Adds a Petersen digraph to the undirected \c G.159 160 ///Adds a Petersen digraph to the undirected \c G.161 ///\return The nodes and arcs of the generated digraph.162 163 template<typename Digraph>164 UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)165 {166 UPetStruct<Digraph> n;167 168 for(int i=0;i<num;i++) {169 n.outer.push_back(G.addNode());170 n.inner.push_back(G.addNode());171 }172 173 for(int i=0;i<num;i++) {174 n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));175 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));176 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));177 }178 return n;179 }180 181 47 #endif -
test/time_measure_test.cc
r119 r171 18 18 19 19 #include <lemon/time_measure.h> 20 21 ///\file \brief Test cases for time_measure.h22 ///23 ///\todo To be extended24 25 20 26 21 using namespace lemon; -
test/unionfind_test.cc
r105 r171 16 16 * 17 17 */ 18 19 #include <iostream>20 18 21 19 #include <lemon/list_graph.h> … … 40 38 U.insert(n[2]); 41 39 42 check(U.join(n[1],n[2]) != -1, "Test failed.");40 check(U.join(n[1],n[2]) != -1, "Something is wrong with UnionFindEnum"); 43 41 44 42 U.insert(n[3]); … … 49 47 50 48 51 check(U.join(n[1],n[4]) != -1, "Test failed.");52 check(U.join(n[2],n[4]) == -1, "Test failed.");53 check(U.join(n[3],n[5]) != -1, "Test failed.");49 check(U.join(n[1],n[4]) != -1, "Something is wrong with UnionFindEnum"); 50 check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum"); 51 check(U.join(n[3],n[5]) != -1, "Something is wrong with UnionFindEnum"); 54 52 55 53 … … 57 55 58 56 59 check(U.size(U.find(n[4])) == 3, "Test failed.");60 check(U.size(U.find(n[5])) == 3, "Test failed.");61 check(U.size(U.find(n[6])) == 1, "Test failed.");62 check(U.size(U.find(n[2])) == 3, "Test failed.");57 check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum"); 58 check(U.size(U.find(n[5])) == 3, "Something is wrong with UnionFindEnum"); 59 check(U.size(U.find(n[6])) == 1, "Something is wrong with UnionFindEnum"); 60 check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum"); 63 61 64 62 … … 67 65 68 66 69 check(U.join(n[8],n[10]) != -1,"Test failed.");67 check(U.join(n[8],n[10]) != -1, "Something is wrong with UnionFindEnum"); 70 68 71 69 72 check(U.size(U.find(n[4])) == 3, "Test failed.");73 check(U.size(U.find(n[9])) == 5, "Test failed.");70 check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum"); 71 check(U.size(U.find(n[9])) == 5, "Something is wrong with UnionFindEnum"); 74 72 75 check(U.size(U.find(n[8])) == 5, "Test failed.");73 check(U.size(U.find(n[8])) == 5, "Something is wrong with UnionFindEnum"); 76 74 77 75 U.erase(n[9]); 78 76 U.erase(n[1]); 79 77 80 check(U.size(U.find(n[10])) == 4, "Test failed.");81 check(U.size(U.find(n[2])) == 2,"Test failed.");78 check(U.size(U.find(n[10])) == 4, "Something is wrong with UnionFindEnum"); 79 check(U.size(U.find(n[2])) == 2, "Something is wrong with UnionFindEnum"); 82 80 83 81 U.erase(n[6]); … … 85 83 86 84 87 check(U.size(U.find(n[4])) == 2, "Test failed.");88 check(U.size(U.find(n[3])) == 1, "Test failed.");89 check(U.size(U.find(n[2])) == 2, "Test failed.");85 check(U.size(U.find(n[4])) == 2, "Something is wrong with UnionFindEnum"); 86 check(U.size(U.find(n[3])) == 1, "Something is wrong with UnionFindEnum"); 87 check(U.size(U.find(n[2])) == 2, "Something is wrong with UnionFindEnum"); 90 88 91 89 92 check(U.join(n[3],n[4]) != -1, "Test failed.");93 check(U.join(n[2],n[4]) == -1, "Test failed.");90 check(U.join(n[3],n[4]) != -1, "Something is wrong with UnionFindEnum"); 91 check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum"); 94 92 95 93 96 check(U.size(U.find(n[4])) == 3, "Test failed.");97 check(U.size(U.find(n[3])) == 3, "Test failed.");98 check(U.size(U.find(n[2])) == 3, "Test failed.");94 check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum"); 95 check(U.size(U.find(n[3])) == 3, "Something is wrong with UnionFindEnum"); 96 check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum"); 99 97 100 98 U.eraseClass(U.find(n[4]));
Note: See TracChangeset
for help on using the changeset viewer.