Changeset 105:e4948ef6a4ca in lemon
- Timestamp:
- 03/20/08 23:59:58 (17 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/unionfind_test.cc
r103 r105 19 19 #include <iostream> 20 20 21 #include <lemon/list_graph.h> 21 22 #include <lemon/maps.h> 22 23 #include <lemon/unionfind.h> … … 26 27 using namespace std; 27 28 28 typedef UnionFindEnum< StdMap<int,int> > UFE;29 typedef UnionFindEnum<ListGraph::NodeMap<int> > UFE; 29 30 30 void print(UFE const &ufe) { 31 cout << "Print the classes of the structure:" << endl; 32 int i = 1; 33 for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) { 34 cout << " " << i << " (" << cit << "):" << flush; 35 for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) { 36 cout << " " << iit << flush; 37 } 38 cout << endl; 39 i++; 40 } 41 cout << "done" << endl; 42 } 31 int main() { 32 ListGraph g; 33 ListGraph::NodeMap<int> base(g); 34 UFE U(base); 35 vector<ListGraph::Node> n; 36 37 for(int i=0;i<20;i++) n.push_back(g.addNode()); 38 39 U.insert(n[1]); 40 U.insert(n[2]); 41 42 check(U.join(n[1],n[2]) != -1,"Test failed."); 43 44 U.insert(n[3]); 45 U.insert(n[4]); 46 U.insert(n[5]); 47 U.insert(n[6]); 48 U.insert(n[7]); 43 49 44 50 45 int main() { 46 StdMap<int, int> base; 47 UFE U(base); 48 49 U.insert(1); 50 U.insert(2); 51 52 check(U.join(1,2) != -1,"Test failed."); 53 54 U.insert(3); 55 U.insert(4); 56 U.insert(5); 57 U.insert(6); 58 U.insert(7); 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."); 59 54 60 55 61 check(U.join(1,4) != -1,"Test failed."); 62 check(U.join(2,4) == -1,"Test failed."); 63 check(U.join(3,5) != -1,"Test failed."); 56 U.insert(n[8],U.find(n[5])); 64 57 65 58 66 U.insert(8,U.find(5)); 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."); 67 63 68 64 69 check(U.size(U.find(4)) == 3,"Test failed."); 70 check(U.size(U.find(5)) == 3,"Test failed."); 71 check(U.size(U.find(6)) == 1,"Test failed."); 72 check(U.size(U.find(2)) == 3,"Test failed."); 65 U.insert(n[9]); 66 U.insert(n[10],U.find(n[9])); 73 67 74 68 75 U.insert(9); 76 U.insert(10,U.find(9)); 69 check(U.join(n[8],n[10]) != -1,"Test failed."); 77 70 78 71 79 check(U.join(8,10) != -1,"Test failed."); 72 check(U.size(U.find(n[4])) == 3,"Test failed."); 73 check(U.size(U.find(n[9])) == 5,"Test failed."); 74 75 check(U.size(U.find(n[8])) == 5,"Test failed."); 76 77 U.erase(n[9]); 78 U.erase(n[1]); 79 80 check(U.size(U.find(n[10])) == 4,"Test failed."); 81 check(U.size(U.find(n[2])) == 2,"Test failed."); 82 83 U.erase(n[6]); 84 U.split(U.find(n[8])); 80 85 81 86 82 check(U.size(U.find(4)) == 3,"Test failed."); 83 check(U.size(U.find(9)) == 5,"Test failed."); 84 85 check(U.size(U.find(8)) == 5,"Test failed."); 86 87 U.erase(9); 88 U.erase(1); 89 90 check(U.size(U.find(10)) == 4,"Test failed."); 91 check(U.size(U.find(2)) == 2,"Test failed."); 92 93 U.erase(6); 94 U.split(U.find(8)); 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."); 95 90 96 91 97 check(U.size(U.find(4)) == 2,"Test failed."); 98 check(U.size(U.find(3)) == 1,"Test failed."); 99 check(U.size(U.find(2)) == 2,"Test failed."); 92 check(U.join(n[3],n[4]) != -1,"Test failed."); 93 check(U.join(n[2],n[4]) == -1,"Test failed."); 100 94 101 95 102 check(U.join(3,4) != -1,"Test failed."); 103 check(U.join(2,4) == -1,"Test failed."); 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."); 104 99 105 106 check(U.size(U.find(4)) == 3,"Test failed."); 107 check(U.size(U.find(3)) == 3,"Test failed."); 108 check(U.size(U.find(2)) == 3,"Test failed."); 109 110 U.eraseClass(U.find(4)); 111 U.eraseClass(U.find(7)); 100 U.eraseClass(U.find(n[4])); 101 U.eraseClass(U.find(n[7])); 112 102 113 103 return 0;
Note: See TracChangeset
for help on using the changeset viewer.