← Back to branch summary

~ubuntu-branches/ubuntu/saucy/gfan/saucy-proposed

« back to all changes in this revision

Viewing changes to symmetry.h

  • Committer: Package Import Robot
  • Author(s): Cédric Boutillier
  • Date: 2013-07-09 10:44:01 UTC
  • mfrom: (2.1.2 experimental)
  • Revision ID: package-import@ubuntu.com-20130709104401-5q66ozz5j5af0dak
Tags: 0.5+dfsg-3
* Upload to unstable.
* modify remove_failing_tests_on_32bits.patch to replace command of
  0009RenderStairCase test with an empty one instead of deleting it.
* remove lintian override about spelling error

Show diffs side-by-side

added added

removed removed

Lines of Context:
symmetry.h
8
8
#include "termorder.h"
9
9
 
10
10
class SymmetryGroup{
 
11
  unsigned char *byteTable;
 
12
  int byteTableHeight;
 
13
  class Trie *trie;
11
14
 public:
12
15
  typedef set<IntegerVector,LexicographicTermOrder> ElementContainer;
13
16
  ElementContainer elements;
14
 
  int sizeOfBaseSet();
 
17
  int sizeOfBaseSet()const;
 
18
  /**
 
19
     Applies the permutation v to each vector in the list l.
 
20
   */
15
21
  static IntegerVectorList permuteIntegerVectorList(IntegerVectorList const &l, IntegerVector const &v);
16
22
  static Polynomial permutePolynomial(const Polynomial &p, IntegerVector const &v);
17
23
  static PolynomialSet permutePolynomialSet(PolynomialSet const &s, IntegerVector const &v);
18
24
  Polynomial computeUniqueRepresentative(Polynomial p);
19
 
  static IntegerVector compose(IntegerVector const &a, IntegerVector const &b);
 
25
  static IntegerVector compose(IntegerVector const &perm, IntegerVector const &b);
20
26
  static IntegerVector composeInverse(IntegerVector const &a, IntegerVector const &b);
21
27
  static IntegerVector identity(int numberOfElements);
22
28
  static IntegerVector inverse(IntegerVector const &a);
 
29
  static bool isPermutation(IntegerVector const &a);
 
30
/**
 
31
 * Takes a permutation of variables and sign changes of variables and combines them in to a single permutation of the variables and their inverses. That is, the permutation is a permutation on 2n elements.
 
32
 */
 
33
  static IntegerVector combinePermutationAndSignChanges(IntegerVector const &permutation, IntegerVector const &signChanges);
 
34
/**
 
35
 * Does the opposite transformation as combinePermutationAndSignChanges.
 
36
 */
 
37
  static void extractPermuationAndSignChanges(IntegerVector const &v, IntegerVector &permutation, IntegerVector &signChanges);
 
38
  /**
 
39
     The set of vectors which are not improved lexicographically when
 
40
     perm is applied to them is convex. Its closure is a
 
41
     halfspace. This routine returns the inner normal of this
 
42
     halfspace. The only exception is if perm is the identity then the
 
43
     zero vector is returned.
 
44
   */
 
45
  static IntegerVector fundamentalDomainInequality(IntegerVector const &perm);
 
46
  /**
 
47
     The set of vectors which cannot be improved lexicographically by
 
48
     applying an element from the group is a convex set. Its closure
 
49
     is a polyhedral cone. This routine returns a set of inequalities
 
50
     The returned list does not contain the zero vector.
 
51
   */
 
52
  IntegerVectorList fundamentalDomainInequalities()const;
23
53
  SymmetryGroup(int n);
24
54
  void computeClosure(IntegerVector const &v);
25
55
  void computeClosure(IntegerVectorList const &l);
 
56
  IntegerVectorList getUniqueGenerators()const;
 
57
  int orbitSize(IntegerVector const &stable)const;
 
58
  bool isTrivial()const;
26
59
  void print(FILE *f);
 
60
  /**
 
61
     The symmetry group acts on vectors by permuting the entries. The
 
62
     following routine returns a unique representative for the orbit
 
63
     containing v. This makes it easy to check if two elements are in
 
64
     the same orbit. The permutation used to get this representative
 
65
     is stored in *usedPermutation (if pointer not 0).
 
66
   */
 
67
  IntegerVector orbitRepresentative(IntegerVector const &v, IntegerVector *usedPermutation=0)const;
 
68
  /**
 
69
     This routine works as orbitRepresentative() except that the
 
70
     symmetry group considered is only the subgroup keeping the vector
 
71
     fixed fixed.
 
72
   */
 
73
  IntegerVector orbitRepresentativeFixing(IntegerVector const &v, IntegerVector const &fixed)const;
 
74
 
 
75
  // Methods for highly optimized symmetry group computations:
 
76
  void createByteTable();//Can only be called once. SymmetryGroup is not allowed to be changed afterwards or to be copied. Leaks memory at destruction.
 
77
  void createTrie();
 
78
  unsigned char *getByteTable()const;
 
79
  int getByteTableHeight()const;
27
80
};
28
81
 
 
82
/**
 
83
 * Sorts v and returns the number of swaps performed.
 
84
 */
 
85
int mergeSort(IntegerVector &v);
 
86
 
29
87
#endif