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