Files @ r104:b68a7e348e00

Location: LEMON/LEMON-main/test/unionfind_test.cc

Load file history 
r104:b68a7e348e00
2.5 KiB
text/x-c++src
Show annotation Show as raw Download as raw
gravatar
alpar (Alpar Juttner)
Port kruskal() and UnionFind from svn -r3468 The class type interface of Kruskal has not been ported yet
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */



#include <iostream>



#include <lemon/maps.h>

#include <lemon/unionfind.h>

#include "test_tools.h"



using namespace lemon;

using namespace std;



typedef UnionFindEnum<StdMap<int, int> > UFE;



void print(UFE const &ufe) {

  cout << "Print the classes of the structure:" << endl;

  int i = 1;

  for (UFE::ClassIt cit(ufe); cit != INVALID; ++cit) {

    cout << "  " << i << " (" << cit << "):" << flush;

    for (UFE::ItemIt iit(ufe, cit); iit != INVALID; ++iit) {

      cout << " " << iit << flush;

    }

    cout << endl;

    i++;

  }

  cout << "done" << endl;

}





int main() {

  StdMap<int, int> base;

  UFE U(base);



  U.insert(1);

  U.insert(2);



  check(U.join(1,2) != -1,"Test failed.");



  U.insert(3);

  U.insert(4);

  U.insert(5);

  U.insert(6);

  U.insert(7);





  check(U.join(1,4) != -1,"Test failed.");

  check(U.join(2,4) == -1,"Test failed.");

  check(U.join(3,5) != -1,"Test failed.");





  U.insert(8,U.find(5));





  check(U.size(U.find(4)) == 3,"Test failed.");

  check(U.size(U.find(5)) == 3,"Test failed.");

  check(U.size(U.find(6)) == 1,"Test failed.");

  check(U.size(U.find(2)) == 3,"Test failed.");





  U.insert(9);

  U.insert(10,U.find(9));





  check(U.join(8,10) != -1,"Test failed.");





  check(U.size(U.find(4)) == 3,"Test failed.");

  check(U.size(U.find(9)) == 5,"Test failed.");



  check(U.size(U.find(8)) == 5,"Test failed.");



  U.erase(9);

  U.erase(1);



  check(U.size(U.find(10)) == 4,"Test failed.");

  check(U.size(U.find(2)) == 2,"Test failed.");



  U.erase(6);

  U.split(U.find(8));





  check(U.size(U.find(4)) == 2,"Test failed.");

  check(U.size(U.find(3)) == 1,"Test failed.");

  check(U.size(U.find(2)) == 2,"Test failed.");





  check(U.join(3,4) != -1,"Test failed.");

  check(U.join(2,4) == -1,"Test failed.");





  check(U.size(U.find(4)) == 3,"Test failed.");

  check(U.size(U.find(3)) == 3,"Test failed.");

  check(U.size(U.find(2)) == 3,"Test failed.");



  U.eraseClass(U.find(4));

  U.eraseClass(U.find(7));



  return 0;

}