← Back to branch summary

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

« back to all changes in this revision

Viewing changes to symmetry.cpp

  • 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.cpp
1
1
#include "symmetry.h"
2
2
 
3
3
#include "printer.h"
 
4
#include "log.h"
 
5
#include <iostream>
 
6
 
 
7
#include <map>
 
8
using namespace std;
 
9
 
 
10
class Trie
 
11
{
 
12
        class TrieNode
 
13
        {
 
14
                typedef map<int,class TrieNode> Map;
 
15
                Map m;
 
16
        public:
 
17
                TrieNode()
 
18
                {
 
19
 
 
20
                }
 
21
                TrieNode(IntegerVector const &v, int i)
 
22
                {
 
23
                        if(i<v.size())
 
24
                        m[v[i]]=TrieNode(v,i+1);
 
25
                }
 
26
                int stabilizerSize(IntegerVector const &v, int i)const
 
27
                {
 
28
                  int ret=0;
 
29
                  if(i==v.size())return 1;
 
30
                  for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
31
                    {
 
32
                      if(v[i]==v[j->first])
 
33
                        ret+=j->second.stabilizerSize(v,i+1);
 
34
                    }
 
35
                  return ret;
 
36
                }
 
37
                void search(IntegerVector const &v, IntegerVector  &building, IntegerVector &tempPerm, IntegerVector &ret, IntegerVector &optimal, int i, bool &isImproving)const
 
38
                {
 
39
                        if(i==v.size()){ret=tempPerm;optimal=building;isImproving=false;return;}
 
40
                        if(isImproving)
 
41
                                building[i]=-0x7fffffff;
 
42
                        else
 
43
                                building[i]=optimal[i];
 
44
                        for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
45
                                if(v[j->first]>building[i])
 
46
                                {
 
47
                                        isImproving=true;
 
48
                                        building[i]=v[j->first];
 
49
                                }
 
50
                                for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
51
                                if(v[j->first]==building[i])
 
52
                                {
 
53
                                        tempPerm[i]=j->first;
 
54
                                        j->second.search(v,building,tempPerm,ret,optimal,i+1,isImproving);
 
55
                                }
 
56
                }
 
57
                void searchStabalizer(IntegerVector const &v, IntegerVector  &building, IntegerVector &tempPerm, IntegerVector &ret, IntegerVector &optimal, int i, bool &isImproving, IntegerVector const &toBeFixed)const
 
58
                {
 
59
                        if(i==v.size())
 
60
                                if(!(SymmetryGroup::compose(tempPerm,v)<optimal))
 
61
                                        {
 
62
                                        ret=tempPerm;
 
63
                                        optimal=SymmetryGroup::compose(tempPerm,v);
 
64
                                        return;
 
65
                                        }
 
66
                                for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
67
                                        if(toBeFixed[i]==toBeFixed[j->first])
 
68
                                {
 
69
                                        tempPerm[i]=j->first;
 
70
                                        j->second.searchStabalizer(v,building,tempPerm,ret,optimal,i+1,isImproving,toBeFixed);
 
71
                                }
 
72
                }
 
73
/* this code contains mistakes          void searchStabalizer(IntegerVector const &v, IntegerVector  &building, IntegerVector &tempPerm, IntegerVector &ret, IntegerVector &optimal, int i, bool &isImproving, IntegerVector const &toBeFixed)const
 
74
                {
 
75
                        if(i==v.size()){ret=tempPerm;optimal=building;isImproving=false;debug<<"DEEP";return;}
 
76
                        if(isImproving)
 
77
                                building[i]=-0x7fffffff;
 
78
                        else
 
79
                                building[i]=optimal[i];
 
80
                        for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
81
                                if(toBeFixed[i]==toBeFixed[j->first])
 
82
                                if(v[j->first]>building[i])
 
83
                                {
 
84
                                        isImproving=true;
 
85
                                        building[i]=v[j->first];
 
86
                                }
 
87
                                for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
88
                                        if(toBeFixed[i]==toBeFixed[j->first])
 
89
                                if(v[j->first]==building[i])
 
90
                                {
 
91
                                        debug.printInteger(i);debug<<":";
 
92
                                        debug.printInteger(j->first);debug<<" ";
 
93
                                        tempPerm[i]=j->first;
 
94
                                        j->second.searchStabalizer(v,building,tempPerm,ret,optimal,i+1,isImproving,toBeFixed);
 
95
                                }
 
96
                }*/
 
97
        //      void doubleSearch();
 
98
                void insert(IntegerVector const &v, int i)
 
99
                {
 
100
                        if(i==v.size())return;
 
101
                        if(m.count(v[i]))
 
102
                                m[v[i]].insert(v,i+1);
 
103
                        else
 
104
                                m[v[i]]=                TrieNode(v,i+1);
 
105
                }
 
106
                void print(int i, int n)const
 
107
                {
 
108
                        if(i==n)return;
 
109
                        for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
110
                        {
 
111
                                {for(int j=0;j<2*i;j++)debug<<" ";}
 
112
                                debug.printInteger(j->first);
 
113
                                debug<<"\n";
 
114
                                j->second.print(i+1,n);
 
115
                        }
 
116
                        }
 
117
                int size(int i,int n)const
 
118
                {
 
119
                        if(i==n)return 1;
 
120
                        int ret=0;
 
121
                        for(Map::const_iterator j=m.begin();j!=m.end();j++)
 
122
                                ret+=j->second.size(i+1,n);
 
123
                        return ret;
 
124
                }
 
125
        };
 
126
public:
 
127
        TrieNode theTree;
 
128
        int n;
 
129
        Trie(int n_):
 
130
                n(n_),
 
131
                theTree(SymmetryGroup::identity(n_),0)
 
132
        {
 
133
        }
 
134
        int size()const
 
135
        {
 
136
                return theTree.size(0,n);
 
137
        }
 
138
        void insert(IntegerVector const &v)
 
139
        {
 
140
                theTree.insert(v,0);
 
141
//              debug<<v;
 
142
//              theTree.print(0,v.size());
 
143
 
 
144
//              debug<<"---------------------------------------------\n";
 
145
        }
 
146
        /**
 
147
         * returns the sigma from the set with sigma(v) maximal in the lexicographic ordering.
 
148
         */
 
149
        IntegerVector search(IntegerVector const &v)
 
150
        {
 
151
                IntegerVector tempPerm(v.size());
 
152
                IntegerVector ret(v.size());
 
153
                IntegerVector building(v.size());
 
154
                IntegerVector optimal=v;//the identity is always in the trie
 
155
                bool isImproving=true;
 
156
                theTree.search(v,building,tempPerm,ret,optimal,0,isImproving);
 
157
                return ret;
 
158
        }
 
159
        IntegerVector searchStabalizer(IntegerVector const &v, IntegerVector const &toBeFixed)
 
160
        {
 
161
                IntegerVector tempPerm=SymmetryGroup::identity(v.size());
 
162
                IntegerVector ret(v.size());
 
163
                IntegerVector building(v.size());
 
164
                IntegerVector optimal=v;//the identity is always in the trie
 
165
                bool isImproving=true;
 
166
                theTree.searchStabalizer(v,building,tempPerm,ret,optimal,0,isImproving,toBeFixed);
 
167
                return ret;
 
168
        }
 
169
        int stabilizerSize(IntegerVector const &v)const
 
170
        {
 
171
          return theTree.stabilizerSize(v,0);
 
172
        }
 
173
};
 
174
 
 
175
 
 
176
 
 
177
 
 
178
 
 
179
 
4
180
 
5
181
IntegerVector SymmetryGroup::identity(int n)
6
182
{
17
193
}
18
194
 
19
195
 
20
 
SymmetryGroup::SymmetryGroup(int n)
 
196
SymmetryGroup::SymmetryGroup(int n):
 
197
  byteTable(0),
 
198
  trie(0)
21
199
{
22
200
  elements.insert(identity(n));
23
201
}
24
202
 
25
203
 
26
 
int SymmetryGroup::sizeOfBaseSet()
 
204
int SymmetryGroup::sizeOfBaseSet()const
27
205
{
28
206
  assert(!elements.empty());
29
207
  return elements.begin()->size();
30
208
}
31
209
 
32
210
void SymmetryGroup::computeClosure(IntegerVector const &v) //does this work??
33
 
{  
 
211
{
34
212
  ElementContainer newOnes;
35
213
 
36
214
  newOnes.insert(v);
90
268
    }
91
269
}
92
270
 
 
271
IntegerVectorList SymmetryGroup::getUniqueGenerators()const
 
272
{
 
273
  int n=sizeOfBaseSet();
 
274
  IntegerVectorList ret;
 
275
 
 
276
restart:
 
277
  SymmetryGroup temp(n);
 
278
  temp.computeClosure(ret);
 
279
  ElementContainer::const_iterator j=temp.elements.begin();
 
280
  for(ElementContainer::const_iterator i=elements.begin();i!=elements.end();i++,j++)
 
281
    {
 
282
      if(*j!=*i)
 
283
        {
 
284
          ret.push_back(*i);
 
285
          goto restart;
 
286
        }
 
287
    }
 
288
  return ret;
 
289
}
93
290
 
94
291
void SymmetryGroup::print(FILE *f)
95
292
{
108
305
}
109
306
 
110
307
 
111
 
IntegerVector SymmetryGroup::compose(IntegerVector const &a, IntegerVector const &b)
 
308
IntegerVector SymmetryGroup::compose(IntegerVector const &perm, IntegerVector const &b)
112
309
{
113
 
  IntegerVector v(a);
114
 
  assert(a.size()==b.size());
115
 
  for(int i=0;i<a.size();i++)v[i]=b[a[i]];
 
310
  IntegerVector v(perm);
 
311
  assert(perm.size()==b.size());
 
312
  for(int i=0;i<perm.size();i++)v[i]=b[perm[i]];
116
313
  return v;
117
314
}
118
315
 
175
372
    }
176
373
  return best;
177
374
}
 
375
 
 
376
 
 
377
IntegerVector SymmetryGroup::orbitRepresentative(IntegerVector const &v, IntegerVector *usedPermutation)const
 
378
{
 
379
        if(trie){
 
380
                  if(usedPermutation)
 
381
                          {
 
382
                          *usedPermutation=trie->search(v);
 
383
                                return compose(*usedPermutation,v);
 
384
                          }
 
385
                return compose(trie->search(v),v);
 
386
        }
 
387
  IntegerVector ret=v;
 
388
  ElementContainer::const_iterator usedPerm;
 
389
  for(ElementContainer::const_iterator i=elements.begin();i!=elements.end();i++)
 
390
    {
 
391
      IntegerVector q=compose(*i,v);
 
392
      if(! (q<ret))//negation to make sure that usedPerm is set
 
393
        {
 
394
          usedPerm=i;
 
395
          ret=q;
 
396
        }
 
397
    }
 
398
 
 
399
  if(usedPermutation)*usedPermutation=*usedPerm;
 
400
 
 
401
  if(trie)
 
402
  {
 
403
//        debug<<"Input"<<v<<"\n";
 
404
//        debug<<"Bruteforce"<<ret<<"\n";
 
405
          IntegerVector triePerm=trie->search(v);
 
406
//        debug<<"Trie"<<compose(triePerm,v)<<"\n";
 
407
          assert((compose(triePerm,v)-ret).isZero());
 
408
  }
 
409
 
 
410
  return ret;
 
411
}
 
412
 
 
413
IntegerVector SymmetryGroup::orbitRepresentativeFixing(IntegerVector const &v, IntegerVector const &fixed)const
 
414
{
 
415
        if(trie){
 
416
                return compose(trie->searchStabalizer(v,fixed),v);
 
417
        }
 
418
  IntegerVector ret=v;
 
419
 
 
420
  for(ElementContainer::const_iterator i=elements.begin();i!=elements.end();i++)
 
421
    if(compose(*i,fixed)==fixed)
 
422
      {
 
423
        IntegerVector q=compose(*i,v);
 
424
        if(ret<q)ret=q;
 
425
      }
 
426
        if(trie){
 
427
                IntegerVector temp=compose(trie->searchStabalizer(v,fixed),v);
 
428
//              debug<<"Input"<<v;
 
429
//              debug<<"Brute"<<ret;
 
430
//              debug<<"Quick"<<temp;
 
431
                assert((temp-ret).isZero());
 
432
//              return compose(trie->searchStabalizer(v,fixed),v);
 
433
        }
 
434
  return ret;
 
435
}
 
436
 
 
437
bool SymmetryGroup::isPermutation(IntegerVector const &a)
 
438
{
 
439
  int n=a.size();
 
440
  IntegerVector temp(n);
 
441
  for(int i=0;i<n;i++)temp[i]=-1;
 
442
  for(int i=0;i<n;i++)
 
443
    {
 
444
      if(a[i]<0 || a[i]>=n)return false;
 
445
      temp[i]=i;
 
446
    }
 
447
  for(int i=0;i<n;i++)if(temp[i]<0)return false;
 
448
  return true;
 
449
}
 
450
 
 
451
 
 
452
IntegerVector SymmetryGroup::combinePermutationAndSignChanges(IntegerVector const &permutation, IntegerVector const &signChanges)
 
453
{
 
454
        assert(isPermutation(permutation));
 
455
        int n=permutation.size();
 
456
        assert(n==signChanges.size());
 
457
        IntegerVector ret(2*n);
 
458
        for(int i=0;i<n;i++)
 
459
                if(signChanges[i]==1)
 
460
                {
 
461
                        ret[i]=permutation[i];
 
462
                        ret[i+n]=n+permutation[i];
 
463
                }
 
464
                else
 
465
                {
 
466
                        ret[i]=n+permutation[i];
 
467
                        ret[i+n]=permutation[i];
 
468
                }
 
469
        return ret;
 
470
}
 
471
 
 
472
void SymmetryGroup::extractPermuationAndSignChanges(IntegerVector const &v, IntegerVector &permutation, IntegerVector &signChanges)
 
473
{
 
474
        int n=v.size()/2;
 
475
        permutation=IntegerVector(n);
 
476
        signChanges=IntegerVector(n);
 
477
 
 
478
        for(int i=0;i<n;i++)
 
479
        {
 
480
                permutation[i]=v[i]%n;
 
481
                if(v[i]<n)
 
482
                        signChanges[i]=1;
 
483
                else
 
484
                        signChanges[i]=-1;
 
485
        }
 
486
}
 
487
 
 
488
 
 
489
int SymmetryGroup::orbitSize(IntegerVector const &stable)const
 
490
{
 
491
  int groupSize=elements.size();
 
492
 
 
493
  int n=stable.size();
 
494
  int numFixed=0;
 
495
 
 
496
  if(trie)
 
497
    {
 
498
      numFixed=trie->stabilizerSize(stable);
 
499
    }
 
500
  else
 
501
    {
 
502
      for(SymmetryGroup::ElementContainer::const_iterator j=elements.begin();j!=elements.end();j++)
 
503
        {
 
504
          bool doesFix=true;
 
505
 
 
506
          for(int i=0;i<n;i++)
 
507
            if(stable[i]!=stable[(*j)[i]])
 
508
              {
 
509
                doesFix=false;
 
510
                break;
 
511
              }
 
512
          if(doesFix)numFixed++;
 
513
        }
 
514
    }
 
515
  return groupSize/numFixed;
 
516
}
 
517
 
 
518
 
 
519
IntegerVector SymmetryGroup::fundamentalDomainInequality(IntegerVector const &perm)
 
520
{
 
521
  for(int i=0;i<perm.size();i++)
 
522
    if(perm[i]!=i)
 
523
      return IntegerVector::standardVector(perm.size(),i)-IntegerVector::standardVector(perm.size(),perm[i]);
 
524
      //      return -IntegerVector::standardVector(perm.size(),i)-IntegerVector::standardVector(perm.size(),perm[i]);//USE this for 4x4 of 5x5
 
525
  return IntegerVector(perm.size());
 
526
}
 
527
 
 
528
 
 
529
IntegerVectorList SymmetryGroup::fundamentalDomainInequalities()const
 
530
{
 
531
  set<IntegerVector> ret2;
 
532
  for(ElementContainer::const_iterator i=elements.begin();i!=elements.end();i++)
 
533
    ret2.insert(fundamentalDomainInequality(*i));
 
534
 
 
535
  IntegerVectorList ret;
 
536
  for(set<IntegerVector>::const_iterator i=ret2.begin();i!=ret2.end();i++)
 
537
    if(!i->isZero())ret.push_back(*i);
 
538
 
 
539
  return ret;
 
540
}
 
541
 
 
542
 
 
543
void SymmetryGroup::createByteTable()
 
544
{
 
545
  assert(!byteTable);
 
546
  int n=sizeOfBaseSet();
 
547
  byteTableHeight=elements.size();
 
548
  byteTable=(unsigned char*)malloc(n*byteTableHeight*sizeof(unsigned char));
 
549
  assert(byteTable);
 
550
  int j=0;
 
551
  for(ElementContainer::const_iterator i=elements.begin();i!=elements.end();i++,j++)
 
552
    {
 
553
      for(int k=0;k<n;k++)
 
554
        byteTable[j*n+k]=(*i)[k];
 
555
    }
 
556
}
 
557
 
 
558
void SymmetryGroup::createTrie()
 
559
{
 
560
        log1 debug<<"Creating symmetry trie.\n";
 
561
        trie=new Trie(sizeOfBaseSet());
 
562
        for(ElementContainer::const_iterator i=elements.begin();i!=elements.end();i++)
 
563
                trie->insert(*i);
 
564
        log2 debug<<"Number of elements";log2 debug.printInteger(trie->size());log2 debug<<"\n";
 
565
        log1 debug<<"Done creating symmetry trie.\n";
 
566
}
 
567
 
 
568
 
 
569
unsigned char * SymmetryGroup::getByteTable()const
 
570
{
 
571
  return byteTable;
 
572
}
 
573
 
 
574
 
 
575
int  SymmetryGroup::getByteTableHeight()const
 
576
{
 
577
  return byteTableHeight;
 
578
}
 
579
 
 
580
 
 
581
bool SymmetryGroup::isTrivial()const
 
582
{
 
583
        ElementContainer::const_iterator i=elements.begin();
 
584
        assert(i!=elements.end());
 
585
        i++;
 
586
        return i==elements.end();
 
587
}
 
588
 
 
589
static int mergeSortRek(IntegerVector &v, int begin, int end, IntegerVector &temp)
 
590
{
 
591
  if(end-begin<2)return 0;
 
592
  int med=(begin+end)>>1;
 
593
  int nswaps=mergeSortRek(v,begin,med,temp);
 
594
  nswaps+=mergeSortRek(v,med,end,temp);
 
595
 
 
596
  {
 
597
    int Astart=begin;
 
598
    int Alength=med-begin;
 
599
    int Bstart=med;
 
600
    int Blength=end-med;
 
601
    int nextFree=begin;
 
602
    while(nextFree!=end)
 
603
      {
 
604
//        debug<<"Astart:"<<Astart<<"Alength:"<<Alength<<"Bstart:"<<Bstart<<"Blength:"<<Blength<<"nextFree:"<<nextFree<<"\n";
 
605
        if(Blength==0 || (Alength!=0 && v[Astart]<v[Bstart]))
 
606
          {
 
607
            temp[nextFree++]=v[Astart++];
 
608
            Alength--;
 
609
          }
 
610
        else
 
611
          {
 
612
            temp[nextFree++]=v[Bstart++];
 
613
            nswaps+=Alength;
 
614
            Blength--;
 
615
          }
 
616
      }
 
617
    for(int i=begin;i!=end;i++)v[i]=temp[i];
 
618
  }
 
619
//debug<<"return\n";
 
620
  return nswaps;
 
621
}
 
622
 
 
623
int mergeSort(IntegerVector &v)
 
624
{
 
625
  IntegerVector temp(v.size());
 
626
  return mergeSortRek(v,0,v.size(),temp);
 
627
}
 
628