partition_def.h

Go to the documentation of this file.

/*
  This is partition_def.h.

  Copyright (C) 2004,2005 Fokko du Cloux
  part of the Atlas of Lie Groups and Representations

  For license information see the LICENSE file
*/

#include <queue>

#include "bitmap.h"
#include "sl_list.h"

/*****************************************************************************

  This file contains the definition of the template declared in partition.h:

    - Partition orbits(F a, unsigned long n, unsigned long limit) : constructs
      the orbit partition defined by the "action function" a;

******************************************************************************/

namespace atlas {

namespace partition {

/* Although the function |orbits| currently needs only one instantiation (from
   cartanclass.cpp), it has to be defined as a template, and has to be
   dynamically instantiated: explicit instantiation here is impossible because
   the template argument |F| needs to be specialised to a class local to the
   instantiating code (in the anonymous namespace of the file cartanclass.cpp)
*/

template<typename F> // class F serving as function object (ul,ul)->ul
  Partition orbits(const F& a, size_t c, unsigned long n)
{
  Partition result(n);

  bitmap::BitMap b(n); // as yet unclassified elements
  b.fill();            // initially that means everyone

  for (bitmap::BitMap::iterator it=b.begin(); it(); ++it) // |b| will shrink
  {
    unsigned long root = *it; // starting element for a fresh orbit
    unsigned long thisClass = result.new_class(root);
    std::queue<unsigned long,containers::sl_list<unsigned long> > q;
    q.push(root);
    b.remove(root); // avoid looping back to |root| later

    do
    {
      unsigned long x = q.front(); q.pop();

      for (unsigned long i=0; i<c; ++i)
      {
    unsigned long y = a(i,x);
    if (b.isMember(y)) // new element was found
    {
      b.remove(y);
      result.addToClass(thisClass,y);
      q.push(y);
    }
      }
    }
    while (not q.empty());
  }
  return result;
}

} // |namespace partition|

} // |namespace atlas|