Loading...
Searching...
No Matches
bliss::Orbit Class Reference

A class for representing orbit information. More...

`#include <orbit.hh>`

## Public Member Functions

| Orbit ()
void | init (const unsigned int N)
void | reset ()
void | merge_orbits (unsigned int e1, unsigned int e2)
bool | is_minimal_representative (unsigned int e) const
unsigned int | get_minimal_representative (unsigned int e) const
unsigned int | orbit_size (unsigned int e) const
unsigned int | nof_orbits () const

## Detailed Description

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.

## Constructor & Destructor Documentation

## Orbit()

bliss::Orbit::Orbit | ( |  | ) |

Create a new orbit information object. The init() function must be called next to actually initialize the object.

## Member Function Documentation

## get_minimal_representative()

unsigned int bliss::Orbit::get_minimal_representative | ( | unsigned int | e | ) | const

Get the smallest element in the orbit of the element e. Time complexity is O(1).

## init()

void bliss::Orbit::init | ( | const unsigned int | N | ) |

Initialize the orbit information to consider sets of N elements. It is required that N > 0. The orbit information is reset so that each element forms an orbit of its own. Time complexity is O(N).

See also
  reset()

## is_minimal_representative()

bool bliss::Orbit::is_minimal_representative | ( | unsigned int | e | ) | const

Is the element e the smallest element in its orbit? Time complexity is O(1).

## merge_orbits()

void bliss::Orbit::merge_orbits | ( | unsigned int | e1,
|  | unsigned int | e2 )

Merge the orbits of the elements e1 and e2. Time complexity is O(k), where k is the number of elements in the smaller of the merged orbits.

## nof_orbits()

unsigned int bliss::Orbit::nof_orbits | ( |  | ) | const

inline

Get the number of orbits. Time complexity is O(1).

## orbit_size()

unsigned int bliss::Orbit::orbit_size | ( | unsigned int | e | ) | const

Get the number of elements in the orbit of the element e. Time complexity is O(1).

## reset()

void bliss::Orbit::reset | ( |  | ) |

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

The documentation for this class was generated from the following files:

- src/orbit.hh
- src/orbit.cc