← Back to branch summary

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

« back to all changes in this revision

Viewing changes to app_intsinpolytope.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:
app_intsinpolytope.cpp
 
1
#include "vektor.h"
 
2
#include "printer.h"
 
3
#include "parser.h"
 
4
#include "gfanapplication.h"
 
5
#include "intsinpolytope.h"
 
6
#include "lattice.h"
 
7
#include "determinant.h"
 
8
 
 
9
class IntsInPolytopeApplication : public GFanApplication
 
10
{
 
11
public:
 
12
  bool includeInDefaultInstallation()
 
13
  {
 
14
    return false;
 
15
  }
 
16
  IntsInPolytopeApplication()
 
17
  {
 
18
    registerOptions();
 
19
  }
 
20
  const char *name()
 
21
  {
 
22
    return "_intsinpolytope";
 
23
  }
 
24
 
 
25
  // a is a squarematrix whose rows span a simplicial cone
 
26
  bool isInSimplicialCone(IntegerMatrix const &a, IntegerVector const &v)
 
27
  {
 
28
 
 
29
    for(int i=0;i<a.getHeight();i++)
 
30
      {
 
31
        IntegerMatrix b=a;
 
32
        b[i]=v;
 
33
        IntegerVectorList A=a.getRows();
 
34
        IntegerVectorList B=b.getRows();
 
35
        if((determinantSign(A)*determinantSign(B))<0)return false;
 
36
      }
 
37
    return true;
 
38
  }
 
39
 
 
40
 
 
41
  set<set<int> > partsOfZBases(set<set<int> > const &s, IntegerMatrix const &M)
 
42
  {
 
43
    set<set<int> > setsToCheck;
 
44
 
 
45
    for(set<set<int> >::const_iterator i=s.begin();i!=s.end();i++)
 
46
      {
 
47
        for(int j=0;j<M.getHeight();j++)
 
48
          {
 
49
            set<int> temp=*i;
 
50
            temp.insert(j);
 
51
            if(temp.size()!=i->size())
 
52
              {
 
53
                bool isOK=true;
 
54
                /*              if(temp.size()==5)
 
55
                  {
 
56
                    IntegerMatrix MM(5,5);
 
57
                    int I=0;
 
58
                    for(set<int>::const_iterator k=temp.begin();k!=temp.end();k++,I++)
 
59
                      {
 
60
                        MM[I]=M[*k];
 
61
                      }
 
62
                    IntegerVector v(5);
 
63
                    v[0]=2;//?????????????????????????????????????????????????
 
64
                    v[1]=2;
 
65
                    v[2]=2;
 
66
                    v[3]=17;
 
67
                    v[4]=8;
 
68
                    if(!isInSimplicialCone(MM,v))
 
69
                      isOK=false;
 
70
                      }*/
 
71
 
 
72
                if(isOK)
 
73
                  for(set<int>::const_iterator k=temp.begin();k!=temp.end();k++)
 
74
                    {
 
75
                      set<int> temp2=temp;
 
76
                      temp2.erase(*k);
 
77
                      if(s.count(temp2)==0)
 
78
                        {
 
79
                          isOK=false;
 
80
                          break;
 
81
                        }
 
82
                    }
 
83
                if(isOK)
 
84
                  {
 
85
                    static int c;
 
86
                    c++;
 
87
                    if(!(c&4095))fprintf(stderr,"tocheck:%i\n",c);
 
88
 
 
89
                    /*              if(temp.size()==5)
 
90
                      {
 
91
                        IntegerMatrix MM(5,5);
 
92
                        int I=0;
 
93
                        for(set<int>::const_iterator k=temp.begin();k!=temp.end();k++,I++)
 
94
                          {
 
95
                            MM[I]=M[*k];
 
96
                          }
 
97
 
 
98
                        fprintf(stderr,"Candidate:\n");
 
99
                        AsciiPrinter(Stderr).printVectorList(MM.getRows());
 
100
                        }*/
 
101
                    setsToCheck.insert(temp);
 
102
                  }
 
103
              }
 
104
          }
 
105
      }
 
106
 
 
107
    fprintf(stderr,"Sets to test: %i\n",setsToCheck.size());
 
108
 
 
109
    set<set<int> > ret;
 
110
    for(set<set<int> >::const_iterator i=setsToCheck.begin();i!=setsToCheck.end();i++)
 
111
      {
 
112
        static int c;
 
113
        c++;
 
114
        if(!(c&4095))fprintf(stderr,"%i\n",c);
 
115
        IntegerVectorList l;
 
116
        for(set<int>::const_iterator j=i->begin();j!=i->end();j++)
 
117
          l.push_back(M[*j]);
 
118
        if(isPartOfAZBasis(l))ret.insert(*i);
 
119
      }
 
120
 
 
121
    fprintf(stderr,"Produced sets: %i\n",ret.size());
 
122
 
 
123
    return ret;
 
124
  }
 
125
 
 
126
  int main()
 
127
  {
 
128
    FileParser p(Stdin);
 
129
 
 
130
    IntegerVectorList ivl=p.parseIntegerVectorList();
 
131
    IntegerMatrix A=rowsToIntegerMatrix(ivl);//.transposed();
 
132
 
 
133
    IntegerVector rightHandSide=p.parseIntegerVector();
 
134
        IntegerVector v=p.parseIntegerVector();
 
135
 
 
136
    AsciiPrinter P(stdout);
 
137
 
 
138
    fprintf(Stdout,"Lattice Kernel:\n");
 
139
    IntegerVectorList l=intsInPolytopeGivenIneqAndPt(A,rightHandSide,v);
 
140
    P.printVectorList(l);
 
141
 
 
142
    //    return 0;//!!!!!!!!!!!!!!!!!!!!!!!!
 
143
 
 
144
    //    P.printVectorList(intsInPolytopeGivenIneq(A,rightHandSide));
 
145
 
 
146
 
 
147
 
 
148
 
 
149
 
 
150
 
 
151
    {
 
152
 
 
153
      IntegerVectorList l2;
 
154
      for(IntegerVectorList::const_iterator i=l.begin();i!=l.end();i++)
 
155
        {
 
156
          IntegerVector temp(i->size()+1);
 
157
          temp[0]=1;
 
158
          for(int j=0;j<i->size();j++)temp[j+1]=(*i)[j];
 
159
          l2.push_back(temp);
 
160
          /*      IntegerVectorList k;
 
161
          k.push_back(*i);
 
162
          if(isPartOfAZBasis(k))
 
163
            P.printVector(*i);
 
164
          */
 
165
        }
 
166
 
 
167
      IntegerVectorList l3;
 
168
      for(IntegerVectorList::const_iterator i=l2.begin();i!=l2.end();i++)
 
169
        //if(((*i)[1]<=2)&&((*i)[2]<=2)&&((*i)[3]<=17)&&((*i)[4]<=8))
 
170
          l3.push_back(*i);
 
171
      //        if(((*i)[0]<=2)&&((*i)[1]<=2)&&((*i)[2]<=17)&&((*i)[3]<=8))l3.push_back(*i);
 
172
 
 
173
      IntegerMatrix M=rowsToIntegerMatrix(l3);
 
174
 
 
175
      P.printVectorList(M.getRows());
 
176
      fprintf(stdout,"size:%i\n",M.getHeight());
 
177
 
 
178
      set<set<int> > s;
 
179
      s.insert(set<int>());
 
180
      for(int i=0;i<5;i++)
 
181
        {
 
182
          s=partsOfZBases(s,M);
 
183
 
 
184
 
 
185
      for(set<set<int> >::const_iterator i=s.begin();i!=s.end();i++)
 
186
        {
 
187
          for(set<int>::const_iterator j=i->begin();j!=i->end();j++)
 
188
            {
 
189
              //              fprintf(stderr,"%i ",*j);
 
190
            }
 
191
          //      fprintf(stderr,"\n");
 
192
        }
 
193
 
 
194
      //          fprintf(stderr,"\n\n\n\n");
 
195
 
 
196
        }
 
197
    }
 
198
 
 
199
 
 
200
 
 
201
    return 0;
 
202
  }
 
203
  const char *helpText()
 
204
  {
 
205
    return "This program computes the integer points in a polytope.\n";
 
206
  }
 
207
};
 
208
 
 
209
static IntsInPolytopeApplication theApplication;