atlas::partition Namespace Reference

Functions for working with a partition of a finite set into classes. More...

Classes
struct	atlas::partition::End
class	atlas::partition::Partition
	Partition of some set [0,n[ into classes. More...
class	atlas::partition::PartitionIterator
Functions
template<typename F>
void	makeOrbits (Partition &, const F &, unsigned long, unsigned long)

---

Detailed Description

Functions for working with a partition of a finite set into classes.

Typically classes are orbits of a finite group (like a Weyl group) on a vector space over Z/2Z (like elements of order 2 in a torus).

---

Function Documentation

template<typename F> void atlas::partition::makeOrbits (  Partition &  pi, const F &  a, unsigned long  c, unsigned long  n )

Constructs the orbit partition defined by the "action function" a. The type F is that of some function object that can be given a pair of unsigned long argument to produce an unsigned long result. The parameter a is such a function object; its first argument is the index i of a generator in the range [0,c[, its second argument is the value acted upon, which is an integer in the range [0,n[; the result is again a vlaue in the range [0,n[. It is assumed that for any fixed i, the function a(i,.) is a permutation of [0,n[; thus the action parameter a defines c generators of a permutation subgroup of Sym([0,n[). The orbits for this action are returned as a Partition object in pi. The algorithm is straightforward orbit generation, using a set B of elements that have not yet joined any orbit, and a collection S of elements that are in the current orbit but whose acted-upon images have yet to be generated. The set B is represented as a bitmap on [0,n[, initially full, while S is realized as a stack (but it could equally well have been a queue), initially empty. While B is not empty : move an element (the first one left) from B to (the currently empty) S; start a new orbit with this element while S is not empty : x = S.top(); S.pop(); for j in [0,c[ if x'=a(j,x) is in B: remove x' from B, push x' onto S, and add it to the current orbit Definition at line 48 of file partition_def.h. References atlas::partition::Partition::addToClass(), atlas::partition::Partition::clear(), atlas::partition::Partition::newClass(), and atlas::partition::Partition::resize(). Referenced by atlas::cartanclass::Fiber::makeStrongReal(), and atlas::cartanclass::Fiber::makeWeakReal().

---