1 #ifndef BLISS_ORBIT_HH 2 #define BLISS_ORBIT_HH 3 4 /* 5 Copyright (c) 2003-2021 Tommi Junttila 6 Released under the GNU Lesser General Public License version 3. 7 8 This file is part of bliss. 9 10 bliss is free software: you can redistribute it and/or modify 11 it under the terms of the GNU Lesser General Public License as published by 12 the Free Software Foundation, version 3 of the License. 13 14 bliss is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU Lesser General Public License for more details. 18 19 You should have received a copy of the GNU Lesser General Public License 20 along with bliss. If not, see <http://www.gnu.org/licenses/>. 21 */ 22 23 namespace bliss { 24 25 /** 26 * \brief A class for representing orbit information. 27 * 28 * Given a set {0,...,N-1} of N elements, represent equivalence 29 * classes (that is, unordered partitions) of the elements. 30 * Supports only equivalence class merging, not splitting. 31 * Merging two classes requires time O(k), where k is the number of 32 * the elements in the smaller of the merged classes. 33 * Getting the smallest representative in a class 34 * (and thus testing whether two elements belong to the same class) 35 * is a constant time operation. 36 */ 37 class Orbit 38 { 39 class OrbitEntry 40 { 41 public: 42 unsigned int element; 43 OrbitEntry *next; 44 unsigned int size; 45 }; 46 47 OrbitEntry *orbits; 48 OrbitEntry **in_orbit; 49 unsigned int nof_elements; 50 unsigned int _nof_orbits; 51 void merge_orbits(OrbitEntry *o1, OrbitEntry *o2); 52 53 public: 54 /** 55 * Create a new orbit information object. 56 * The init() function must be called next to actually initialize 57 * the object. 58 */ 59 Orbit(); 60 ~Orbit(); 61 62 /** 63 * Initialize the orbit information to consider sets of \a N elements. 64 * It is required that \a N > 0. 65 * The orbit information is reset so that each element forms 66 * an orbit of its own. 67 * Time complexity is O(N). 68 * \sa reset() 69 */ 70 void init(const unsigned int N); 71 72 /** 73 * Reset the orbits so that each element forms an orbit of its own. 74 * Time complexity is O(N). 75 */ 76 void reset(); 77 78 /** 79 * Merge the orbits of the elements \a e1 and \a e2. 80 * Time complexity is O(k), where k is the number of elements in 81 * the smaller of the merged orbits. 82 */ 83 void merge_orbits(unsigned int e1, unsigned int e2); 84 85 /** 86 * Is the element \a e the smallest element in its orbit? 87 * Time complexity is O(1). 88 */ 89 bool is_minimal_representative(unsigned int e) const; 90 91 /** 92 * Get the smallest element in the orbit of the element \a e. 93 * Time complexity is O(1). 94 */ 95 unsigned int get_minimal_representative(unsigned int e) const; 96 97 /** 98 * Get the number of elements in the orbit of the element \a e. 99 * Time complexity is O(1). 100 */ 101 unsigned int orbit_size(unsigned int e) const; 102 103 /** 104 * Get the number of orbits. 105 * Time complexity is O(1). 106 */ nof_orbits() const107 unsigned int nof_orbits() const {return _nof_orbits; } 108 }; 109 110 } // namespace bliss 111 112 #endif // BLISS_ORBIT_HH 113