DisjointSet

Source: tests/multifrontal/symbolic/DisjointSet.cpp

// ========================================================================= //
// This file is part of MyraMath, copyright (c) 2014-2019 by Ryan A Chilton  //
// and distributed by MyraCore, LLC. See LICENSE.txt for license terms.      //
// ========================================================================= //

// Containers.
#include <myramath/multifrontal/symbolic/detail/DisjointSet.h>

// Reporting.
#include <tests/myratest.h>
#include <myramath/utility/stlprint.h>
#include <map>
#include <set>

using namespace myra;

// Makes a DisjointSet of 100 int's, then merges them according to a mod (%) operation.
ADD_TEST("DisjointSet","[symbolic]")
  {
  int N = 100;
  int K = 13;
  DisjointSet set(N);
  for (int n = 0; n < N; ++n)
    set.merge(n, n%K);
  // Should be K roots at the end.
  REQUIRE(set.roots() == K);
  // Examine resulting sets.
  using myra_stlprint::operator<<;
  std::map<int,std::set<int> > output;
  for (int n = 0; n < N; ++n)
    output[set.root(n)].insert(n);
  for (auto i = output.begin(); i != output.end(); ++i)
    myra::out() << "output[" << i->first << "] = " << i->second << std::endl;
  // Check equivalence between all (i,j) pairs in [0,N)
  bool equivalence = true;
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j)  
      if ( (i%K) == (j%K) )
        if ( set.root(i) != set.root(j) )
          equivalence = false;
  REQUIRE(equivalence);
  }

Results: [PASS]

output[87] = [ 9 22 35 48 61 74 87 ]
output[88] = [ 10 23 36 49 62 75 88 ]
output[89] = [ 11 24 37 50 63 76 89 ]
output[90] = [ 12 25 38 51 64 77 90 ]
output[91] = [ 0 13 26 39 52 65 78 91 ]
output[92] = [ 1 14 27 40 53 66 79 92 ]
output[93] = [ 2 15 28 41 54 67 80 93 ]
output[94] = [ 3 16 29 42 55 68 81 94 ]
output[95] = [ 4 17 30 43 56 69 82 95 ]
output[96] = [ 5 18 31 44 57 70 83 96 ]
output[97] = [ 6 19 32 45 58 71 84 97 ]
output[98] = [ 7 20 33 46 59 72 85 98 ]
output[99] = [ 8 21 34 47 60 73 86 99 ]

Go back to Summary of /test programs.