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