File: orbit.hh

package info (click to toggle)
bliss 0.73-4
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, sid
  • size: 712 kB
  • sloc: cpp: 6,538; makefile: 144; sh: 6
file content (111 lines) | stat: -rw-r--r-- 3,085 bytes parent folder | download | duplicates (6)
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
#ifndef BLISS_ORBIT_HH
#define BLISS_ORBIT_HH

/*
  Copyright (c) 2003-2015 Tommi Junttila
  Released under the GNU Lesser General Public License version 3.
  
  This file is part of bliss.
  
  bliss is free software: you can redistribute it and/or modify
  it under the terms of the GNU Lesser General Public License as published by
  the Free Software Foundation, version 3 of the License.

  bliss is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with bliss.  If not, see <http://www.gnu.org/licenses/>.
*/

namespace bliss {

/** \internal
 * \brief A class for representing orbit information.
 *
 * Given a set {0,...,N-1} of N elements, represent equivalence
 * classes (that is, unordered partitions) of the elements.
 * Supports only equivalence class merging, not splitting.
 * Merging two classes requires time O(k), where k is the number of
 * the elements in the smaller of the merged classes.
 * Getting the smallest representative in a class (and thus testing
 * whether two elements belong to the same class) is a constant time operation.
 */
class Orbit
{
  class OrbitEntry
  {
  public:
    unsigned int element;
    OrbitEntry *next;
    unsigned int size;
  };

  OrbitEntry *orbits;
  OrbitEntry **in_orbit;
  unsigned int nof_elements;
  unsigned int _nof_orbits;
  void merge_orbits(OrbitEntry *o1, OrbitEntry *o2);

public:
  /**
   * Create a new orbit information object.
   * The init() function must be called next to actually initialize
   * the object.
   */
  Orbit();
  ~Orbit();

  /**
   * Initialize the orbit information to consider sets of \a N elements.
   * It is required that \a N > 0.
   * The orbit information is reset so that each element forms
   * an orbit of its own.
   * Time complexity is O(N).
   * \sa reset()
   */
  void init(const unsigned int N);

  /**
   * Reset the orbits so that each element forms an orbit of its own.
   * Time complexity is O(N).
   */
  void reset();

  /**
   * Merge the orbits of the elements \a e1 and \a e2.
   * Time complexity is O(k), where k is the number of elements in
   * the smaller of the merged orbits.
   */
  void merge_orbits(unsigned int e1, unsigned int e2);

  /**
   * Is the element \a e the smallest element in its orbit?
   * Time complexity is O(1).
   */
  bool is_minimal_representative(unsigned int e) const;

  /**
   * Get the smallest element in the orbit of the element \a e.
   * Time complexity is O(1).
   */
  unsigned int get_minimal_representative(unsigned int e) const;

  /**
   * Get the number of elements in the orbit of the element \a e.
   * Time complexity is O(1).
   */
  unsigned int orbit_size(unsigned int e) const;

  /**
   * Get the number of orbits.
   * Time complexity is O(1).
   */
  unsigned int nof_orbits() const {return _nof_orbits; }
};

} // namespace bliss

#endif