source: git/IntegerProgramming/IP_algorithms.cc @ 1095e9

spielwiese
Last change on this file since 1095e9 was e8c9869, checked in by jgmbenoit <quatermaster@…>, 8 years ago
correct spelling error as detected by Lintian
  • Property mode set to 100644
File size: 103.8 KB
Line 
1// IP_algorithms.cc
2
3#ifndef IP_ALGORITHMS_CC
4#define IP_ALGORITHMS_CC
5
6#include "IP_algorithms.h"
7#include <time.h>
8#include <unistd.h>
9
10/////////////// method for printing compilation settings ////////////////////
11
12void print_flags(ofstream& output)
13{
14  output<<"compiler settings:"<<endl;
15
16#ifdef NO_SUPPORT_DRIVEN_METHODS
17  output<<"NO_SUPPORT_DRIVEN_METHODS"<<endl;
18#endif
19
20#ifdef SUPPORT_DRIVEN_METHODS
21
22#ifdef NO_SUPPORT_DRIVEN_METHODS_EXTENDED
23  output<<"SUPPORT_DRIVEN_METHODS"<<endl;
24#endif
25
26#ifdef SUPPORT_DRIVEN_METHODS_EXTENDED
27  output<<"SUPPORT_DRIVEN_METHODS_EXTENDED"<<endl;
28  output<<"List Support Variables:  "<<endl;
29  output<<List_Support_Variables<<endl;
30#endif
31
32#ifdef SUPPORT_VARIABLES_FIRST
33  output<<"SUPPORT_VARIABLES_FIRST"<<endl;
34#endif
35
36#ifdef SUPPORT_VARIABLES_LAST
37  output<<"SUPPORT_VARIABLES_LAST"<<endl;
38#endif
39
40#endif  // SUPPORT_DRIVEN_METHODS
41
42#ifdef DL_LIST
43  output<<"doubly linked lists"<<endl<<endl;
44#endif
45
46#ifdef SL_LIST
47  output<<"simply linked lists"<<endl<<endl;
48#endif
49
50}
51
52
53
54
55////////////////////////////////////////////////////////////////////////////
56///////////////////// IP algorithms ////////////////////////////////////////
57////////////////////////////////////////////////////////////////////////////
58
59
60
61
62int Conti_Traverso(INPUT_FILE MATRIX,
63                   const int& version,
64                   const int& S_pair_criteria,
65                   const float& interred_percentage,
66                   const BOOLEAN& verbose)
67{
68
69
70/////////////////////////// input /////////////////////////////////////////
71
72  char format_string[128]; // to verifie file format
73  int constraints;       // number of equality constraints
74  int variables;         // number of variables (without auxiliary variables)
75
76  ifstream input(MATRIX);
77
78  // verfifie existence of file
79
80  if(!input)
81  {
82    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
83      "cannot read from input file, possibly not found"<<endl;
84    return 0;
85  }
86
87  // read format specification
88
89  input>>format_string;
90
91  if(!input)
92  {
93    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
94      "input failure when reading format specification,\n"
95      "input format not accepted"<<endl;
96    return 0;
97  }
98
99  if(strcmp(format_string,"MATRIX"))
100    cerr<<"Warning: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
101      "input file has suspicious format"<<endl;
102
103  // read number of variables
104
105  input>>format_string;
106
107  if(!input)
108  {
109    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
110      "input failure before reading number of variables / matrix columns,\n"
111      "input format not accepted"<<endl;
112    return 0;
113  }
114
115  if(strcmp(format_string,"columns:"))
116    cerr<<"WARNING: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
117      "input file has suspicious format"<<endl;
118
119  input>>variables;
120
121  if(!input)
122  {
123    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
124      "input failure when reading number of variables / matrix columns,\n"
125      "input format not accepted"<<endl;
126    return 0;
127  }
128
129  if(variables<=0)
130  {
131    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
132      "number of variables / matrix columns must be positive"<<endl;
133    return 0;
134  }
135
136  // read term ordering
137
138  input>>format_string;
139
140  if(!input)
141  {
142    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
143      "input failure before reading cost vector,\n"
144      "input format not accepted"<<endl;
145    return 0;
146  }
147
148  if(strcmp(format_string,"cost"))
149    cerr<<"WARNING: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
150      "input file has suspicious format"<<endl;
151
152  input>>format_string;
153
154  if(!input)
155  {
156    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
157      "input failure before reading cost vector,\n"
158      "input format not accepted"<<endl;
159    return 0;
160  }
161
162  if(strcmp(format_string,"vector:"))
163    cerr<<"WARNING: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
164      "input file has suspicious format"<<endl;
165
166  term_ordering w(variables,input,W_LEX);
167
168  if(w.error_status()<0)
169  {
170    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
171      "input failure when reading cost vector, input format not accepted"
172        <<endl;
173    return 0;
174  }
175
176  if(w.is_nonnegative()==FALSE)
177  {
178    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
179      "cost vectors with negative components are not supported"<<endl;
180    return 0;
181  }
182
183  // read number of constraints
184
185  input>>format_string;
186
187  if(!input)
188  {
189    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
190      "input failure before reading number of constraints / matrix rows,\n"
191      "input format not accepted"<<endl;
192    return 0;
193  }
194
195  if(strcmp(format_string,"rows:"))
196    cerr<<"WARNING: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
197      "input file has suspicious format"<<endl;
198
199  input>>constraints;
200
201  if(!input)
202  {
203    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
204      "input failure when reading number of constraints / matrix rows,\n"
205      "input format not accepted"
206        <<endl;
207    return 0;
208  }
209
210  if(constraints<=0)
211  {
212    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
213      "number of constraints / matrix rows must be positive"<<endl;
214    // Solving problems without constraints is possible, but not very
215    // interesting (because trivial). To avoid the problems and the overhead
216    // incurred by an "empty" matrix, such problems are refused.
217    return 0;
218  }
219
220  // read matrix
221
222  input>>format_string;
223
224  if(!input)
225  {
226    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
227      "input failure before reading matrix,\n"
228      "input format not accepted"<<endl;
229    return 0;
230  }
231
232  if(strcmp(format_string,"matrix:"))
233    cerr<<"WARNING: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
234      "input file has suspicious format"<<endl;
235
236  matrix A(constraints,variables,input);
237  if(A.error_status()<0)
238  {
239    cerr<<"ERROR: int Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
240      "input failure when reading matrix, input format not accepted"<<endl;
241    return 0;
242  }
243
244
245///////////////////////// computation ////////////////////////////////////////
246
247  // prepare time measurement
248  clock_t start, end;
249
250  // create toric ideal
251  ideal I(A,w,CONTI_TRAVERSO);
252
253  // compute the standard basis
254  start=clock();
255  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
256  end=clock();
257
258  // time measurement
259  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
260
261
262///////////////////////// output ////////////////////////////////////////////
263
264  // create output file
265
266  char GROEBNER[128];
267  int i=0;
268  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
269  {
270    GROEBNER[i]=MATRIX[i];
271    i++;
272  }
273  GROEBNER[i]='\0';
274  strcat(GROEBNER,".GB.ct");
275
276  ofstream output(GROEBNER);
277
278  // format output file
279
280  output.flags(output.flags()|ios::fixed);
281  // output of fixed point numbers
282
283  output<<"GROEBNER"<<endl<<endl;
284
285  output<<"computed with algorithm:"<<endl;
286  output<<"ct"<<endl;
287  output<<"from file(s):"<<endl;
288  output<<MATRIX<<endl;
289  output<<"computation time"<<endl;
290  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
291
292  output<<"term ordering:"<<endl;
293  output<<"elimination block"<<endl;
294  // elimination variables (>0)
295  output<<constraints+1<<endl;
296  output<<"LEX"<<endl;
297  output<<"weighted block"<<endl;
298  // weighted variables (>0)
299  output<<variables<<endl;
300  output<<"W_LEX"<<endl;
301  w.format_print_weight_vector(output);
302
303  output<<"size:"<<endl;
304  output<<I.number_of_generators()<<endl<<endl;
305
306  output<<"Groebner basis:"<<endl;
307  I.format_print(output);
308  output<<endl;
309
310  if(verbose==TRUE)
311  {
312    output<<"settings for the Buchberger algorithm:"<<endl;
313
314    output<<"version:"<<endl;
315    if(version==0)
316      output<<"1a"<<endl;
317    else
318      output<<version<<endl;
319
320    output<<"S-pair criteria:"<<endl;
321    if(S_pair_criteria & REL_PRIMENESS)
322      output<<"relatively prime leading terms"<<endl;
323    if(S_pair_criteria & M_CRITERION)
324      output<<"criterion M"<<endl;
325    if(S_pair_criteria & F_CRITERION)
326      output<<"criterion F"<<endl;
327    if(S_pair_criteria & B_CRITERION)
328      output<<"criterion B"<<endl;
329    if(S_pair_criteria & SECOND_CRITERION)
330      output<<"second criterion"<<endl;
331    output<<endl;
332
333    print_flags(output);
334    output<<endl;
335  }
336
337  return 1;
338}
339
340
341
342
343////////////////////////////////////////////////////////////////////////////
344////////////////////////////////////////////////////////////////////////////
345////////////////////////////////////////////////////////////////////////////
346
347
348
349
350int Positive_Conti_Traverso(INPUT_FILE MATRIX,
351                            const int& version,
352                            const int& S_pair_criteria,
353                            const float& interred_percentage,
354                            const BOOLEAN& verbose)
355{
356
357
358/////////////////////////// input /////////////////////////////////////////
359
360  char format_string[128]; // to verifie file format
361  int constraints;       // number of equality constraints
362  int variables;         // number of variables (without auxiliary variables)
363
364  ifstream input(MATRIX);
365
366  // verfifie existence of file
367
368  if(!input)
369  {
370    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
371      "cannot read from input file, possibly not found"<<endl;
372    return 0;
373  }
374
375  // read format specification
376
377  input>>format_string;
378
379  if(!input)
380  {
381    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
382      "input failure when reading format specification,\n"
383      "input format not accepted"<<endl;
384    return 0;
385  }
386
387  if(strcmp(format_string,"MATRIX"))
388    cerr<<"Warning: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
389      "input file has suspicious format"<<endl;
390
391  // read number of variables
392
393  input>>format_string;
394
395  if(!input)
396  {
397    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
398      "input failure before reading number of variables / matrix columns,\n"
399      "input format not accepted"<<endl;
400    return 0;
401  }
402
403  if(strcmp(format_string,"columns:"))
404    cerr<<"WARNING: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
405      "input file has suspicious format"<<endl;
406
407  input>>variables;
408
409  if(!input)
410  {
411    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
412      "input failure when reading number of variables / matrix columns,\n"
413      "input format not accepted"<<endl;
414    return 0;
415  }
416
417  if(variables<=0)
418  {
419    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
420      "number of variables / matrix columns must be positive"<<endl;
421    return 0;
422  }
423
424  // read term ordering
425
426  input>>format_string;
427
428  if(!input)
429  {
430    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
431      "input failure before reading cost vector,\n"
432      " input format not accepted"<<endl;
433    return 0;
434  }
435
436  if(strcmp(format_string,"cost"))
437    cerr<<"WARNING: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
438      "input file has suspicious format"<<endl;
439
440  input>>format_string;
441
442  if(!input)
443  {
444    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
445      "input failure before reading cost vector,\n"
446      "input format not accepted"<<endl;
447    return 0;
448  }
449
450  if(strcmp(format_string,"vector:"))
451    cerr<<"WARNING: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
452      "input file has suspicious format"<<endl;
453
454  term_ordering w(variables,input,W_LEX);
455
456  if(w.error_status()<0)
457  {
458    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
459      "input failure when reading cost vector, input format not accepted"
460        <<endl;
461    return 0;
462  }
463
464  if(w.is_nonnegative()==FALSE)
465  {
466    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
467      "cost vectors with negative components are not supported"<<endl;
468    return 0;
469  }
470
471  // read number of constraints
472
473  input>>format_string;
474
475  if(!input)
476  {
477    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
478      "input failure before reading number of constraints / matrix rows,\n"
479      "input format not accepted"<<endl;
480    return 0;
481  }
482
483  if(strcmp(format_string,"rows:"))
484    cerr<<"WARNING: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
485      "input file has suspicious format"<<endl;
486
487  input>>constraints;
488
489  if(!input)
490  {
491    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
492      "input failure when reading number of constraints / matrix rows,\n"
493      "input format not accepted"
494        <<endl;
495    return 0;
496  }
497
498  if(constraints<=0)
499  {
500    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
501      "number of constraints / matrix rows must be positive"<<endl;
502    // Solving problems without constraints is possible, but not very
503    // interesting (because trivial). To avoid the problems and the overhead
504    // incurred by an "empty" matrix, such problems are refused.
505    return 0;
506  }
507
508  // read matrix
509
510  input>>format_string;
511
512  if(!input)
513  {
514    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
515      "input failure before reading matrix,\n"
516      "input format not accepted"<<endl;
517    return 0;
518  }
519
520  if(strcmp(format_string,"matrix:"))
521    cerr<<"WARNING: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
522      "input file has suspicious format"<<endl;
523
524  matrix A(constraints,variables,input);
525  if(A.error_status()<0)
526  {
527    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
528      "input failure when reading matrix, input format not accepted"<<endl;
529    return 0;
530  }
531
532  if(A.is_nonnegative()==FALSE)
533  {
534    cerr<<"ERROR: int Positive_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
535      "input matrix has negative coefficients,\n"
536      "please use the general Conti-Traverso algorithm"<<endl;
537    return 0;
538  }
539
540
541///////////////////////// computation ////////////////////////////////////////
542
543  // prepare time measurement
544  clock_t start, end;
545
546  // create toric ideal
547  ideal I(A,w,POSITIVE_CONTI_TRAVERSO);
548
549  // compute the standard basis
550  start=clock();
551  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
552  end=clock();
553
554  // time measurement
555  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
556
557
558///////////////////////// output ////////////////////////////////////////////
559
560  // create output file
561
562  char GROEBNER[128];
563  int i=0;
564  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
565  {
566    GROEBNER[i]=MATRIX[i];
567    i++;
568  }
569  GROEBNER[i]='\0';
570  strcat(GROEBNER,".GB.pct");
571
572  ofstream output(GROEBNER);
573
574  // format output file
575
576  output.flags(output.flags()|ios::fixed);
577  // output of fixed point numbers
578
579  output<<"GROEBNER"<<endl<<endl;
580
581  output<<"computed with algorithm:"<<endl;
582  output<<"pct"<<endl;
583  output<<"from file(s):"<<endl;
584  output<<MATRIX<<endl;
585  output<<"computation time"<<endl;
586  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
587
588  output<<"term ordering:"<<endl;
589  output<<"elimination block"<<endl;
590  // elimination variables (>0)
591  output<<constraints<<endl;
592  output<<"LEX"<<endl;
593  output<<"weighted block"<<endl;
594  // weighted variables (>0)
595  output<<variables<<endl;
596  output<<"W_LEX"<<endl;
597  w.format_print_weight_vector(output);
598  output<<endl;
599
600  output<<"size:"<<endl;
601  output<<I.number_of_generators()<<endl<<endl;
602
603  output<<"Groebner basis:"<<endl;
604  I.format_print(output);
605  output<<endl;
606
607  if(verbose==TRUE)
608  {
609    output<<"settings for the Buchberger algorithm:"<<endl;
610
611    output<<"version:"<<endl;
612    if(version==0)
613      output<<"1a"<<endl;
614    else
615      output<<version<<endl;
616
617    output<<"S-pair criteria:"<<endl;
618    if(S_pair_criteria & REL_PRIMENESS)
619      output<<"relatively prime leading terms"<<endl;
620    if(S_pair_criteria & M_CRITERION)
621      output<<"criterion M"<<endl;
622    if(S_pair_criteria & F_CRITERION)
623      output<<"criterion F"<<endl;
624    if(S_pair_criteria & B_CRITERION)
625      output<<"criterion B"<<endl;
626    if(S_pair_criteria & SECOND_CRITERION)
627      output<<"second criterion"<<endl;
628    output<<endl;
629
630    print_flags(output);
631    output<<endl;
632  }
633
634  return 1;
635}
636
637
638
639
640////////////////////////////////////////////////////////////////////////////
641////////////////////////////////////////////////////////////////////////////
642////////////////////////////////////////////////////////////////////////////
643
644
645
646
647int Elim_Conti_Traverso(INPUT_FILE MATRIX,
648                        const int& version,
649                        const int& S_pair_criteria,
650                        const float& interred_percentage,
651                        const BOOLEAN& verbose)
652{
653
654
655/////////////////////////// input /////////////////////////////////////////
656
657  char format_string[128]; // to verifie file format
658  int constraints;       // number of equality constraints
659  int variables;         // number of variables (without auxiliary variables)
660
661  ifstream input(MATRIX);
662
663  // verfifie existence of file
664
665  if(!input)
666  {
667    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
668      "cannot read from input file, possibly not found"<<endl;
669    return 0;
670  }
671
672  // read format specification
673
674  input>>format_string;
675
676  if(!input)
677  {
678    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
679      "input failure when reading format specification,\n"
680      "input format not accepted"<<endl;
681    return 0;
682  }
683
684  if(strcmp(format_string,"MATRIX"))
685    cerr<<"Warning: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
686      "input file has suspicious format"<<endl;
687
688  // read number of variables
689
690  input>>format_string;
691
692  if(!input)
693  {
694    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
695      "input failure before reading number of variables / matrix columns,\n"
696      "input format not accepted"<<endl;
697    return 0;
698  }
699
700  if(strcmp(format_string,"columns:"))
701    cerr<<"WARNING: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
702      "input file has suspicious format"<<endl;
703
704  input>>variables;
705
706  if(!input)
707  {
708    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
709      "input failure when reading number of variables / matrix columns,\n"
710      "input format not accepted"<<endl;
711    return 0;
712  }
713
714  if(variables<=0)
715  {
716    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
717      "number of variables / matrix columns must be positive"<<endl;
718    return 0;
719  }
720
721  // read term ordering
722
723  input>>format_string;
724
725  if(!input)
726  {
727    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
728      "input failure before reading cost vector,\n"
729      "input format not accepted"<<endl;
730    return 0;
731  }
732
733  if(strcmp(format_string,"cost"))
734    cerr<<"WARNING: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
735      "input file has suspicious format"<<endl;
736
737  input>>format_string;
738
739  if(!input)
740  {
741    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
742      "input failure before reading cost vector,\n"
743      "input format not accepted"<<endl;
744    return 0;
745  }
746
747  if(strcmp(format_string,"vector:"))
748    cerr<<"WARNING: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
749      "input file has suspicious format"<<endl;
750
751  term_ordering w(variables,input,W_LEX);
752
753  if(w.error_status()<0)
754  {
755    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
756      "input failure when reading cost vector, input format not accepted"
757        <<endl;
758    return 0;
759  }
760
761  if(w.is_nonnegative()==FALSE)
762  {
763    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
764      "cost vectors with negative components are not supported"<<endl;
765    return 0;
766  }
767
768  // read number of constraints
769
770  input>>format_string;
771
772  if(!input)
773  {
774    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
775      "input failure before reading number of constraints / matrix rows,\n"
776      "input format not accepted"<<endl;
777    return 0;
778  }
779
780  if(strcmp(format_string,"rows:"))
781    cerr<<"WARNING: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
782      "input file has suspicious format"<<endl;
783
784  input>>constraints;
785
786  if(!input)
787  {
788    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
789      "input failure when reading number of constraints / matrix rows,\n"
790      "input format not accepted"
791        <<endl;
792    return 0;
793  }
794
795  if(constraints<=0)
796  {
797    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
798      "number of constraints / matrix rows must be positive"<<endl;
799    // Solving problems without constraints is possible, but not very
800    // interesting (because trivial). To avoid the problems and the overhead
801    // incurred by an "empty" matrix, such problems are refused.
802    return 0;
803  }
804
805  // read matrix
806
807  input>>format_string;
808
809  if(!input)
810  {
811    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
812      "input failure before reading matrix,\n"
813      "input format not accepted"<<endl;
814    return 0;
815  }
816
817  if(strcmp(format_string,"matrix:"))
818    cerr<<"WARNING: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
819      "input file has suspicious format"<<endl;
820
821  matrix A(constraints,variables,input);
822  if(A.error_status()<0)
823  {
824    cerr<<"ERROR: int Elim_Conti_Traverso(INPUT_FILE, const BOOLEAN&):\n"
825      "input failure when reading matrix, input format not accepted"<<endl;
826    return 0;
827  }
828
829
830///////////////////////// computation ////////////////////////////////////////
831
832  // prepare time measurement
833  clock_t start, end;
834
835  // create toric ideal: this is done with the CONTI_TRAVERSO constructor;
836  // some elimination has to be done later
837  ideal I(A,w,CONTI_TRAVERSO);
838
839  // compute the standard basis and eliminate auxiliary variables
840  start=clock();
841  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
842  I.eliminate();
843  end=clock();
844
845  // time measurement
846  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
847
848
849///////////////////////// output ////////////////////////////////////////////
850
851  // create output file
852
853  char GROEBNER[128];
854  int i=0;
855  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
856  {
857    GROEBNER[i]=MATRIX[i];
858    i++;
859  }
860  GROEBNER[i]='\0';
861  strcat(GROEBNER,".GB.ect");
862
863  ofstream output(GROEBNER);
864
865  // format output file
866
867  output.flags(output.flags()|ios::fixed);
868  // output of fixed point numbers
869
870  output<<"GROEBNER"<<endl<<endl;
871
872  output<<"computed with algorithm:"<<endl;
873  output<<"ect"<<endl;
874  output<<"from file(s):"<<endl;
875  output<<MATRIX<<endl;
876  output<<"computation time"<<endl;
877  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
878
879  output<<"term ordering:"<<endl;
880  output<<"elimination block"<<endl;
881  // elimination variables (=0)
882  output<<0<<endl;
883  output<<"weighted block"<<endl;
884  // weighted variables (>0)
885  output<<variables<<endl;
886  output<<"W_LEX"<<endl;
887  w.format_print_weight_vector(output);
888
889  output<<"size:"<<endl;
890  output<<I.number_of_generators()<<endl<<endl;
891
892  output<<"Groebner basis:"<<endl;
893  I.format_print(output);
894  output<<endl;
895
896  if(verbose==TRUE)
897  {
898    output<<"settings for the Buchberger algorithm:"<<endl;
899
900    output<<"version:"<<endl;
901    if(version==0)
902      output<<"1a"<<endl;
903    else
904      output<<version<<endl;
905
906    output<<"S-pair criteria:"<<endl;
907    if(S_pair_criteria & REL_PRIMENESS)
908      output<<"relatively prime leading terms"<<endl;
909    if(S_pair_criteria & M_CRITERION)
910      output<<"criterion M"<<endl;
911    if(S_pair_criteria & F_CRITERION)
912      output<<"criterion F"<<endl;
913    if(S_pair_criteria & B_CRITERION)
914      output<<"criterion B"<<endl;
915    if(S_pair_criteria & SECOND_CRITERION)
916      output<<"second criterion"<<endl;
917    output<<endl;
918
919    print_flags(output);
920    output<<endl;
921  }
922
923  return 1;
924}
925
926
927
928
929////////////////////////////////////////////////////////////////////////////
930////////////////////////////////////////////////////////////////////////////
931////////////////////////////////////////////////////////////////////////////
932
933
934
935
936int Pottier(INPUT_FILE MATRIX,
937            const int& version,
938            const int& S_pair_criteria,
939            const float& interred_percentage,
940            const BOOLEAN& verbose)
941{
942
943
944/////////////////////////// input /////////////////////////////////////////
945
946  char format_string[128]; // to verifie file format
947  int constraints;       // number of equality constraints
948  int variables;         // number of variables (without auxiliary variables)
949
950  ifstream input(MATRIX);
951
952  // verfifie existence of file
953
954  if(!input)
955  {
956    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
957      "cannot read from input file, possibly not found"<<endl;
958    return 0;
959  }
960
961  // read format specification
962
963  input>>format_string;
964
965  if(!input)
966  {
967    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
968      "input failure when reading format specification,\n"
969      "input format not accepted"<<endl;
970    return 0;
971  }
972
973  if(strcmp(format_string,"MATRIX"))
974    cerr<<"Warning: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
975      "input file has suspicious format"<<endl;
976
977  // read number of variables
978
979  input>>format_string;
980
981  if(!input)
982  {
983    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
984      "input failure before reading number of variables / matrix columns,\n"
985      "input format not accepted"<<endl;
986    return 0;
987  }
988
989  if(strcmp(format_string,"columns:"))
990    cerr<<"WARNING: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
991      "input file has suspicious format"<<endl;
992
993  input>>variables;
994
995  if(!input)
996  {
997    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
998      "input failure when reading number of variables / matrix columns,\n"
999      "input format not accepted"<<endl;
1000    return 0;
1001  }
1002
1003  if(variables<=0)
1004  {
1005    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1006      "number of variables / matrix columns must be positive"<<endl;
1007    return 0;
1008  }
1009
1010  // read term ordering
1011
1012  input>>format_string;
1013
1014  if(!input)
1015  {
1016    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1017      "input failure before reading cost vector,\n"
1018      "input format not accepted"<<endl;
1019    return 0;
1020  }
1021
1022  if(strcmp(format_string,"cost"))
1023    cerr<<"WARNING: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1024      "input file has suspicious format"<<endl;
1025
1026  input>>format_string;
1027
1028  if(!input)
1029  {
1030    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1031      "input failure before reading cost vector,\n"
1032      "input format not accepted"<<endl;
1033    return 0;
1034  }
1035
1036  if(strcmp(format_string,"vector:"))
1037    cerr<<"WARNING: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1038      "input file has suspicious format"<<endl;
1039
1040  term_ordering w(variables,input,W_LEX);
1041
1042  if(w.error_status()<0)
1043  {
1044    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1045      "input failure when reading cost vector, input format not accepted"
1046        <<endl;
1047    return 0;
1048  }
1049
1050  if(w.is_nonnegative()==FALSE)
1051  {
1052    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1053      "cost vectors with negative components are not supported"<<endl;
1054    return 0;
1055  }
1056
1057  // read number of constraints
1058
1059  input>>format_string;
1060
1061  if(!input)
1062  {
1063    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1064      "input failure before reading number of constraints / matrix rows,\n"
1065      " input format not accepted"<<endl;
1066    return 0;
1067  }
1068
1069  if(strcmp(format_string,"rows:"))
1070    cerr<<"WARNING: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1071      "input file has suspicious format"<<endl;
1072
1073  input>>constraints;
1074
1075  if(!input)
1076  {
1077    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1078      "input failure when reading number of constraints / matrix rows,\n "
1079      "input format not accepted"
1080        <<endl;
1081    return 0;
1082  }
1083
1084  if(constraints<=0)
1085  {
1086    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1087      "number of constraints / matrix rows must be positive"<<endl;
1088    // Solving problems without constraints is possible, but not very
1089    // interesting (because trivial). To avoid the problems and the overhead
1090    // incurred by an "empty" matrix, such problems are refused.
1091    return 0;
1092  }
1093
1094  // read matrix
1095
1096  input>>format_string;
1097
1098  if(!input)
1099  {
1100    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1101      "input failure before reading matrix,\n"
1102      "input format not accepted"<<endl;
1103    return 0;
1104  }
1105
1106  if(strcmp(format_string,"matrix:"))
1107    cerr<<"WARNING: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1108      "input file has suspicious format"<<endl;
1109
1110  matrix A(constraints,variables,input);
1111  if(A.error_status()<0)
1112  {
1113    cerr<<"ERROR: int Pottier(INPUT_FILE, const BOOLEAN&):\n"
1114      "input failure when reading matrix, input format not accepted"<<endl;
1115    return 0;
1116  }
1117
1118
1119///////////////////////// computation ////////////////////////////////////////
1120
1121  // prepare time measurement
1122  clock_t start, end;
1123
1124  // create toric ideal
1125  ideal I(A,w,POTTIER);
1126
1127  // compute the standard basis and eliminate auxiliary variable
1128  start=clock();
1129  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
1130  I.eliminate();
1131  end=clock();
1132
1133  // time measurement
1134  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
1135
1136
1137///////////////////////// output ////////////////////////////////////////////
1138
1139  // create output file
1140
1141  char GROEBNER[128];
1142  int i=0;
1143  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
1144  {
1145    GROEBNER[i]=MATRIX[i];
1146    i++;
1147  }
1148  GROEBNER[i]='\0';
1149  strcat(GROEBNER,".GB.pt");
1150
1151  ofstream output(GROEBNER);
1152
1153  // format output file
1154
1155  output.flags(output.flags()|ios::fixed);
1156  // output of fixed point numbers
1157
1158  output<<"GROEBNER"<<endl<<endl;
1159
1160  output<<"computed with algorithm:"<<endl;
1161  output<<"pt"<<endl;
1162  output<<"from file(s):"<<endl;
1163  output<<MATRIX<<endl;
1164  output<<"computation time"<<endl;
1165  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
1166
1167  output<<"term ordering:"<<endl;
1168  output<<"elimination block"<<endl;
1169  // elimination variables (=0)
1170  output<<0<<endl;
1171  output<<"weighted block"<<endl;
1172  // weighted variables (>0)
1173  output<<variables<<endl;
1174  output<<"W_LEX"<<endl;
1175  w.format_print_weight_vector(output);
1176
1177  output<<"size:"<<endl;
1178  output<<I.number_of_generators()<<endl<<endl;
1179
1180  output<<"Groebner basis:"<<endl;
1181  I.format_print(output);
1182  output<<endl;
1183
1184  if(verbose==TRUE)
1185  {
1186    output<<"settings for the Buchberger algorithm:"<<endl;
1187
1188    output<<"version:"<<endl;
1189    if(version==0)
1190      output<<"1a"<<endl;
1191    else
1192      output<<version<<endl;
1193
1194    output<<"S-pair criteria:"<<endl;
1195    if(S_pair_criteria & REL_PRIMENESS)
1196      output<<"relatively prime leading terms"<<endl;
1197    if(S_pair_criteria & M_CRITERION)
1198      output<<"criterion M"<<endl;
1199    if(S_pair_criteria & F_CRITERION)
1200      output<<"criterion F"<<endl;
1201    if(S_pair_criteria & B_CRITERION)
1202      output<<"criterion B"<<endl;
1203    if(S_pair_criteria & SECOND_CRITERION)
1204      output<<"second criterion"<<endl;
1205    output<<endl;
1206
1207    print_flags(output);
1208    output<<endl;
1209  }
1210
1211  return 1;
1212}
1213
1214
1215
1216
1217////////////////////////////////////////////////////////////////////////////
1218////////////////////////////////////////////////////////////////////////////
1219////////////////////////////////////////////////////////////////////////////
1220
1221
1222
1223
1224int Hosten_Sturmfels(INPUT_FILE MATRIX,
1225                     const int& version,
1226                     const int& S_pair_criteria,
1227                     const float& interred_percentage,
1228                     const BOOLEAN& verbose)
1229{
1230
1231
1232/////////////////////////// input /////////////////////////////////////////
1233
1234  char format_string[128]; // to verifie file format
1235  int constraints;       // number of equality constraints
1236  int variables;         // number of variables
1237
1238  ifstream input(MATRIX);
1239
1240  // verfifie existence of file
1241
1242  if(!input)
1243  {
1244    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1245      "cannot read from input file, possibly not found"<<endl;
1246    return 0;
1247  }
1248
1249  // read format specification
1250
1251  input>>format_string;
1252
1253  if(!input)
1254  {
1255    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1256      "input failure when reading format specification,\n"
1257      "input format not accepted"<<endl;
1258    return 0;
1259  }
1260
1261  if(strcmp(format_string,"MATRIX"))
1262    cerr<<"Warning: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1263      "input file has suspicious format"<<endl;
1264
1265  // read number of variables
1266
1267  input>>format_string;
1268
1269  if(!input)
1270  {
1271    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1272      "input failure before reading number of variables / matrix columns,\n"
1273      "input format not accepted"<<endl;
1274    return 0;
1275  }
1276
1277  if(strcmp(format_string,"columns:"))
1278    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1279      "input file has suspicious format"<<endl;
1280
1281  input>>variables;
1282
1283  if(!input)
1284  {
1285    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1286      "input failure when reading number of variables / matrix columns,\n"
1287      "input format not accepted"<<endl;
1288    return 0;
1289  }
1290
1291  if(variables<=0)
1292  {
1293    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1294      "number of variables / matrix columns must be positive"<<endl;
1295    return 0;
1296  }
1297
1298  // read term ordering
1299
1300  input>>format_string;
1301
1302  if(!input)
1303  {
1304    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1305      "input failure before reading cost vector,\n"
1306      "input format not accepted"<<endl;
1307    return 0;
1308  }
1309
1310  if(strcmp(format_string,"cost"))
1311    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1312      "input file has suspicious format"<<endl;
1313
1314  input>>format_string;
1315
1316  if(!input)
1317  {
1318    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1319      "input failure before reading cost vector,\n"
1320      "input format not accepted"<<endl;
1321    return 0;
1322  }
1323
1324  if(strcmp(format_string,"vector:"))
1325    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1326      "input file has suspicious format"<<endl;
1327
1328  term_ordering c(variables,input,W_LEX);
1329
1330  if(c.error_status()<0)
1331  {
1332    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1333      "input failure when reading cost vector, input format not accepted"
1334        <<endl;
1335    return 0;
1336  }
1337
1338  if(c.is_nonnegative()==FALSE)
1339  {
1340    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1341      "cost vectors with negative components are not supported"<<endl;
1342    return 0;
1343  }
1344
1345  // read number of constraints
1346
1347  input>>format_string;
1348
1349  if(!input)
1350  {
1351    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1352      "input failure before reading number of constraints / matrix rows,\n"
1353      "input format not accepted"<<endl;
1354    return 0;
1355  }
1356
1357  if(strcmp(format_string,"rows:"))
1358    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1359      "input file has suspicious format"<<endl;
1360
1361  input>>constraints;
1362
1363  if(!input)
1364  {
1365    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1366      "input failure when reading number of constraints / matrix rows,\n"
1367      "input format not accepted"
1368        <<endl;
1369    return 0;
1370  }
1371
1372  if(constraints<=0)
1373  {
1374    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1375      "number of constraints / matrix rows must be positive"<<endl;
1376    // Solving problems without constraints is possible, but not very
1377    // interesting (because trivial). To avoid the problems and the overhead
1378    // incurred by an "empty" matrix, such problems are refused.
1379    return 0;
1380  }
1381
1382  // read matrix
1383
1384  input>>format_string;
1385
1386  if(!input)
1387  {
1388    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1389      "input failure before reading matrix,\n"
1390      "input format not accepted"<<endl;
1391    return 0;
1392  }
1393
1394  if(strcmp(format_string,"matrix:"))
1395    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1396      "input file has suspicious format"<<endl;
1397
1398  matrix A(constraints,variables,input);
1399  if(A.error_status()<0)
1400  {
1401    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1402      "input failure when reading matrix, input format not accepted"<<endl;
1403    return 0;
1404  }
1405
1406  // read positive vector in the row space of the matrix
1407  // such a vector induces a homogenous grading on the ideal
1408
1409  input>>format_string;
1410
1411  if(!input)
1412  {
1413    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1414      "input failure before reading positive row space vector,\n"
1415      "input format not accepted"<<endl;
1416    return 0;
1417  }
1418
1419  if(strcmp(format_string,"positive"))
1420    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1421      "input file has suspicious format"<<endl;
1422
1423  input>>format_string;
1424
1425  if(!input)
1426  {
1427    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1428      "input failure before reading positive row space vector,\n"
1429      "input format not accepted"<<endl;
1430    return 0;
1431  }
1432
1433  if(strcmp(format_string,"row"))
1434    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1435      "input file has suspicious format"<<endl;
1436
1437  input>>format_string;
1438
1439  if(!input)
1440  {
1441    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1442      "input failure before reading positive row space vector,\n"
1443      " input format not accepted"<<endl;
1444    return 0;
1445  }
1446
1447  if(strcmp(format_string,"space"))
1448    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1449      "input file has suspicious format"<<endl;
1450
1451  input>>format_string;
1452
1453  if(!input)
1454  {
1455    cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1456      "input failure before reading positive row space vector,\n"
1457      "input format not accepted"<<endl;
1458    return 0;
1459  }
1460
1461  if(strcmp(format_string,"vector:"))
1462    cerr<<"WARNING: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1463      "input file has suspicious format"<<endl;
1464
1465  float *hom_grad=new float[variables];
1466
1467  for(int i=0;i<variables;i++)
1468  {
1469    input>>hom_grad[i];
1470
1471    if(!input)
1472    {
1473      cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1474        "input failure when reading positive grading / row space vector,\n"
1475        "input format not accepted"<<endl;
1476      delete[] hom_grad;
1477      return 0;
1478    }
1479
1480    if(hom_grad[i]<=0)
1481    {
1482      cerr<<"ERROR: int Hosten_Sturmfels(INPUT_FILE, const BOOLEAN&):\n"
1483        "row space vector / grading must be positive"<<endl;
1484      delete[] hom_grad;
1485      return 0;
1486    }
1487  }
1488
1489
1490///////////////////////// computation ////////////////////////////////////////
1491
1492  // prepare time measurement
1493  clock_t start, end;
1494
1495  // construct homogenous term ordering
1496  term_ordering w(variables, hom_grad, W_REV_LEX, HOMOGENEOUS);
1497
1498  delete[] hom_grad;
1499
1500  // create toric ideal
1501  ideal I(A,w,HOSTEN_STURMFELS);
1502
1503  // compute the standard basis of the saturation:
1504
1505  start=clock();
1506
1507  // determine saturation variables
1508  int *sat_var;
1509  int number_of_sat_var=A.hosten_shapiro(sat_var);
1510  // memory for sat_var is allocated in the hosten_shapiro procedure
1511
1512  // saturate the ideal
1513  for(int i=0;i<number_of_sat_var;i++)
1514  {
1515    I.swap_variables(sat_var[i],variables-1);
1516    // This operation simply makes the i-th saturation variable the cheapest.
1517    // This involves swapping the weights in the ideal's term ordering,
1518    // the variables in the generating binomials and rebuilding the
1519    // list structure if SUPPORT_DRIVEN_METHODS_EXTENDED are used.
1520
1521    I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
1522    // This calculation saturates the ideal with respect to the i-th
1523    // variable.
1524
1525    I.swap_variables_unsafe(sat_var[i],variables-1);
1526    // This operation does the same as ideal::swap_variables(...) except
1527    // from rebuilding the list structure. It may cause an inconsistent
1528    // structure, but is more efficient then the safe method. Before
1529    // performing a Groebner basis computation, however, the ideal structure
1530    // has to be rebuild. Procedures like ideal::swap_variables(...) and
1531    // ideal::change_term_ordering_to(...) do this. But these are exactly
1532    // the operations that follow.
1533  }
1534
1535  delete[] sat_var;
1536
1537  // Now the ideal is saturated. The last Groebner basis computation is done
1538  // with respect to the term ordering induced by the objective function.
1539  I.change_term_ordering_to(c);
1540  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
1541
1542  end=clock();
1543
1544  // time measurement
1545  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
1546
1547
1548///////////////////////// output ////////////////////////////////////////////
1549
1550  // create output file
1551
1552  char GROEBNER[128];
1553  int i=0;
1554  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
1555  {
1556    GROEBNER[i]=MATRIX[i];
1557    i++;
1558  }
1559  GROEBNER[i]='\0';
1560  strcat(GROEBNER,".GB.hs");
1561
1562  ofstream output(GROEBNER);
1563
1564  // format output file
1565
1566  output.flags(output.flags()|ios::fixed);
1567  // output of fixed point numbers
1568
1569  output<<"GROEBNER"<<endl<<endl;
1570
1571  output<<"computed with algorithm:"<<endl;
1572  output<<"hs"<<endl;
1573  output<<"from file(s):"<<endl;
1574  output<<MATRIX<<endl;
1575  output<<"computation time"<<endl;
1576  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
1577
1578  output<<"term ordering:"<<endl;
1579  output<<"elimination block"<<endl;
1580  // elimination variables (=0)
1581  output<<0<<endl;
1582  output<<"weighted block"<<endl;
1583  // weighted variables (>0)
1584  output<<variables<<endl;
1585  output<<"W_LEX"<<endl;
1586  c.format_print_weight_vector(output);
1587
1588  output<<"size:"<<endl;
1589  output<<I.number_of_generators()<<endl<<endl;
1590
1591  output<<"Groebner basis:"<<endl;
1592  I.format_print(output);
1593  output<<endl;
1594
1595  if(verbose==TRUE)
1596  {
1597    output<<"settings for the Buchberger algorithm:"<<endl;
1598
1599    output<<"version:"<<endl;
1600    if(version==0)
1601      output<<"1a"<<endl;
1602    else
1603      output<<version<<endl;
1604
1605    output<<"S-pair criteria:"<<endl;
1606    if(S_pair_criteria & REL_PRIMENESS)
1607      output<<"relatively prime leading terms"<<endl;
1608    if(S_pair_criteria & M_CRITERION)
1609      output<<"criterion M"<<endl;
1610    if(S_pair_criteria & F_CRITERION)
1611      output<<"criterion F"<<endl;
1612    if(S_pair_criteria & B_CRITERION)
1613      output<<"criterion B"<<endl;
1614    if(S_pair_criteria & SECOND_CRITERION)
1615      output<<"second criterion"<<endl;
1616    output<<endl;
1617
1618    print_flags(output);
1619    output<<endl;
1620  }
1621
1622  return 1;
1623}
1624
1625
1626
1627
1628////////////////////////////////////////////////////////////////////////////
1629////////////////////////////////////////////////////////////////////////////
1630////////////////////////////////////////////////////////////////////////////
1631
1632
1633
1634
1635int DiBiase_Urbanke(INPUT_FILE MATRIX,
1636                    const int& version,
1637                    const int& S_pair_criteria,
1638                    const float& interred_percentage,
1639                    const BOOLEAN& verbose)
1640{
1641
1642
1643/////////////////////////// input /////////////////////////////////////////
1644
1645  char format_string[128]; // to verify file format
1646  int constraints;       // number of equality constraints
1647  int variables;         // number of variables
1648
1649  ifstream input(MATRIX);
1650
1651  // verfifie existence of file
1652
1653  if(!input)
1654  {
1655    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1656      "cannot read from input file, possibly not found"<<endl;
1657    return 0;
1658  }
1659
1660  // read format specification
1661
1662  input>>format_string;
1663
1664  if(!input)
1665  {
1666    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1667      "input failure when reading format specification,\n"
1668      "input format not accepted"<<endl;
1669    return 0;
1670  }
1671
1672  if(strcmp(format_string,"MATRIX"))
1673    cerr<<"Warning: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1674      "input file has suspicious format"<<endl;
1675
1676  // read number of variables
1677
1678  input>>format_string;
1679
1680  if(!input)
1681  {
1682    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1683      "input failure before reading number of variables / matrix columns,\n"
1684      "input format not accepted"<<endl;
1685    return 0;
1686  }
1687
1688  if(strcmp(format_string,"columns:"))
1689    cerr<<"WARNING: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1690      "input file has suspicious format"<<endl;
1691
1692  input>>variables;
1693
1694  if(!input)
1695  {
1696    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1697      "input failure when reading number of variables / matrix columns,\n"
1698      "input format not accepted"<<endl;
1699    return 0;
1700  }
1701
1702  if(variables<=0)
1703  {
1704    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1705      "number of variables / matrix columns must be positive"<<endl;
1706    return 0;
1707  }
1708
1709  // read term ordering
1710
1711  input>>format_string;
1712
1713  if(!input)
1714  {
1715    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1716      "input failure before reading cost vector,\n"
1717      "input format not accepted"<<endl;
1718    return 0;
1719  }
1720
1721  if(strcmp(format_string,"cost"))
1722    cerr<<"WARNING: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1723      "input file has suspicious format"<<endl;
1724
1725  input>>format_string;
1726
1727  if(!input)
1728  {
1729    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1730      "input failure before reading cost vector,\n"
1731      " input format not accepted"<<endl;
1732    return 0;
1733  }
1734
1735  if(strcmp(format_string,"vector:"))
1736    cerr<<"WARNING: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1737      "input file has suspicious format"<<endl;
1738
1739  term_ordering c(variables,input,W_LEX);
1740
1741  if(c.error_status()<0)
1742  {
1743    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1744      "input failure when reading cost vector, input format not accepted"
1745        <<endl;
1746    return 0;
1747  }
1748
1749  if(c.is_nonnegative()==FALSE)
1750  {
1751    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1752      "cost vectors with negative components are not supported"<<endl;
1753    return 0;
1754  }
1755
1756  // read number of constraints
1757
1758  input>>format_string;
1759
1760  if(!input)
1761  {
1762    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1763      "input failure before reading number of constraints / matrix rows,\n"
1764      " input format not accepted"<<endl;
1765    return 0;
1766  }
1767
1768  if(strcmp(format_string,"rows:"))
1769    cerr<<"WARNING: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1770      "input file has suspicious format"<<endl;
1771
1772  input>>constraints;
1773
1774  if(!input)
1775  {
1776    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1777      "input failure when reading number of constraints / matrix rows,\n"
1778      "input format not accepted"
1779        <<endl;
1780    return 0;
1781  }
1782
1783  if(constraints<=0)
1784  {
1785    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1786      "number of constraints / matrix rows must be positive"<<endl;
1787    // Solving problems without constraints is possible, but not very
1788    // interesting (because trivial). To avoid the problems and the overhead
1789    // incurred by an "empty" matrix, such problems are refused.
1790    return 0;
1791  }
1792
1793  // read matrix
1794
1795  input>>format_string;
1796
1797  if(!input)
1798  {
1799    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1800      "input failure before reading matrix,\n"
1801      "input format not accepted"<<endl;
1802    return 0;
1803  }
1804
1805  if(strcmp(format_string,"matrix:"))
1806    cerr<<"WARNING: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1807      "input file has suspicious format"<<endl;
1808
1809  matrix A(constraints,variables,input);
1810  if(A.error_status()<0)
1811  {
1812    cerr<<"ERROR: int DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1813      "input failure when reading matrix, input format not accepted"<<endl;
1814    return 0;
1815  }
1816
1817
1818///////////////////////// computation ////////////////////////////////////////
1819
1820  // prepare time measurement
1821  clock_t start, end;
1822
1823  // compute flip variables (also to check the suitability of the algorithm)
1824  int* F;
1825  int r=A.compute_flip_variables(F);
1826
1827  if(r<0)
1828    // algorithm not suitable
1829  {
1830    cout<<"ERROR: DiBiase_Urbanke(INPUT_FILE, const BOOLEAN&):\n"
1831      "Kernel of the input matrix contains no vector with nonzero "
1832      "components,\ninstance cannot be solved with this algorithm.\n"
1833      "No output file created. Please use another algorithm."<<endl;
1834    return 0;
1835  }
1836
1837  ideal *I;
1838  // We use a pointer here because we need to distinguish two cases
1839  // for the ideal construction.
1840
1841  start=clock();
1842
1843  if(r==0)
1844    // no variable flip needed
1845    // create toric ideal from the lattice basis already with respect to the
1846    // objective function
1847  {
1848    I=new ideal(A,c,DIBIASE_URBANKE);
1849    I->reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
1850  }
1851
1852  else
1853  {
1854    // construct term ordering to start with
1855    // Here we have much freedom: The term ordering must only be an
1856    // elimination ordering for the actual flip variable.
1857    // To avoid supplementary functions to manipulate term orderings, we
1858    // simply realize this as follows: The weight of the actual
1859    // flip variable is set to 1, all other weights are set to zero. This
1860    // still allows the use of different term orderings (by setting the
1861    // refining ordering).
1862
1863    float* weights=new float[variables];
1864    for(int j=0;j<variables;j++)
1865      weights[j]=0;
1866    weights[F[0]]=1;
1867
1868    term_ordering w(variables, weights, W_LEX);
1869    // Which term ordering is the best here?
1870
1871    delete[] weights;
1872
1873    // create toric ideal
1874    I=new ideal(A,w,DIBIASE_URBANKE);
1875
1876    I->reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
1877    I->flip_variable_unsafe(F[0]);
1878    // "unsafe" means that head and tail can be exchanged (cf. the routine
1879    // ideal::swap_variables_unsafe(...) )
1880    // But the following change of the term ordering will correct this.
1881
1882    for(int l=1;l<r;l++)
1883    {
1884      w.swap_weights(F[l-1],F[l]);
1885      // This means concretely:
1886      // The weight of x_F[l-1] is set to zero, that of x_F[l] to one.
1887      // Now, x_F[l] is the elimination variable.
1888
1889      I->change_term_ordering_to(w);
1890      I->reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
1891      I->flip_variable_unsafe(F[l]);
1892    }
1893
1894    // Now we have a generating system of the saturated ideal.
1895    // Compute Groebner basis with respect to the objective function.
1896    I->change_term_ordering_to(c);
1897    I->reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
1898
1899  }
1900
1901  end=clock();
1902
1903  // time measurement
1904  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
1905
1906
1907///////////////////////// output ////////////////////////////////////////////
1908
1909  // create output file
1910
1911  char GROEBNER[128];
1912  int i=0;
1913  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
1914  {
1915    GROEBNER[i]=MATRIX[i];
1916    i++;
1917  }
1918  GROEBNER[i]='\0';
1919  strcat(GROEBNER,".GB.du");
1920
1921  ofstream output(GROEBNER);
1922
1923  // format output file
1924
1925  output.flags(output.flags()|ios::fixed);
1926  // output of fixed point numbers
1927
1928  output<<"GROEBNER"<<endl<<endl;
1929
1930  output<<"computed with algorithm:"<<endl;
1931  output<<"du"<<endl;
1932  output<<"from file(s):"<<endl;
1933  output<<MATRIX<<endl;
1934  output<<"computation time"<<endl;
1935  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
1936
1937  output<<"term ordering:"<<endl;
1938  output<<"elimination block"<<endl;
1939  // elimination variables (=0)
1940  output<<0<<endl;
1941  output<<"weighted block"<<endl;
1942  // weighted variables (>0)
1943  output<<variables<<endl;
1944  output<<"W_LEX"<<endl;
1945  c.format_print_weight_vector(output);
1946
1947  output<<"size:"<<endl;
1948  output<<I->number_of_generators()<<endl<<endl;
1949
1950  output<<"Groebner basis:"<<endl;
1951  I->format_print(output);
1952  output<<endl;
1953
1954  if(verbose==TRUE)
1955  {
1956    output<<"settings for the Buchberger algorithm:"<<endl;
1957
1958    output<<"version:"<<endl;
1959    if(version==0)
1960      output<<"1a"<<endl;
1961    else
1962      output<<version<<endl;
1963
1964    output<<"S-pair criteria:"<<endl;
1965    if(S_pair_criteria & REL_PRIMENESS)
1966      output<<"relatively prime leading terms"<<endl;
1967    if(S_pair_criteria & M_CRITERION)
1968      output<<"criterion M"<<endl;
1969    if(S_pair_criteria & F_CRITERION)
1970      output<<"criterion F"<<endl;
1971    if(S_pair_criteria & B_CRITERION)
1972      output<<"criterion B"<<endl;
1973    if(S_pair_criteria & SECOND_CRITERION)
1974      output<<"second criterion"<<endl;
1975    output<<endl;
1976
1977    print_flags(output);
1978    output<<endl;
1979  }
1980
1981
1982////////////////////////////// memory cleanup ////////////////////////////////
1983
1984  if(r>0)
1985    delete[] F;
1986  delete I;
1987
1988  return 1;
1989}
1990
1991
1992
1993
1994////////////////////////////////////////////////////////////////////////////
1995////////////////////////////////////////////////////////////////////////////
1996////////////////////////////////////////////////////////////////////////////
1997
1998
1999
2000
2001int Bigatti_LaScala_Robbiano(INPUT_FILE MATRIX,
2002                             const int& version,
2003                             const int& S_pair_criteria,
2004                             const float& interred_percentage,
2005                             const BOOLEAN& verbose)
2006{
2007
2008
2009/////////////////////////// input /////////////////////////////////////////
2010
2011  char format_string[128];     // to verifie file format
2012  int constraints;       // number of equality constraints
2013  int variables;         // number of variables
2014
2015  ifstream input(MATRIX);
2016
2017  // verfifie existence of file
2018
2019  if(!input)
2020  {
2021    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2022      "cannot read from input file, possibly not found"<<endl;
2023    return 0;
2024  }
2025
2026  // read format specification
2027
2028  input>>format_string;
2029
2030  if(!input)
2031  {
2032    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2033      "input failure when reading format specification,\n"
2034      "input format not accepted"<<endl;
2035    return 0;
2036  }
2037
2038  if(strcmp(format_string,"MATRIX"))
2039    cerr<<"Warning: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2040      "\n"
2041      "input file has suspicious format"<<endl;
2042
2043  // read number of variables
2044
2045  input>>format_string;
2046
2047  if(!input)
2048  {
2049    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2050      "input failure before reading number of variables / matrix columns,\n"
2051      "input format not accepted"<<endl;
2052    return 0;
2053  }
2054
2055  if(strcmp(format_string,"columns:"))
2056    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2057      "\n"
2058      "input file has suspicious format"<<endl;
2059
2060  input>>variables;
2061
2062  if(!input)
2063  {
2064    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2065      "input failure when reading number of variables / matrix columns,\n"
2066      "input format not accepted"<<endl;
2067    return 0;
2068  }
2069
2070  if(variables<=0)
2071  {
2072    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2073      "number of variables / matrix columns must be positive"<<endl;
2074    return 0;
2075  }
2076
2077  // read term ordering
2078
2079  input>>format_string;
2080
2081  if(!input)
2082  {
2083    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2084      "input failure before reading cost vector,\n"
2085      "input format not accepted"<<endl;
2086    return 0;
2087  }
2088
2089  if(strcmp(format_string,"cost"))
2090    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2091      "\n"
2092      "input file has suspicious format"<<endl;
2093
2094  input>>format_string;
2095
2096  if(!input)
2097  {
2098    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2099      "input failure before reading cost vector,\n"
2100      "input format not accepted"<<endl;
2101    return 0;
2102  }
2103
2104  if(strcmp(format_string,"vector:"))
2105    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2106      "\n"
2107      "input file has suspicious format"<<endl;
2108
2109  term_ordering c(variables,input,W_LEX);
2110
2111  if(c.error_status()<0)
2112  {
2113    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2114      "input failure when reading cost vector, input format not accepted"
2115        <<endl;
2116    return 0;
2117  }
2118
2119  if(c.is_nonnegative()==FALSE)
2120  {
2121    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2122      "cost vectors with negative components are not supported"<<endl;
2123    return 0;
2124  }
2125
2126  // read number of constraints
2127
2128  input>>format_string;
2129
2130  if(!input)
2131  {
2132    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2133      "input failure before reading number of constraints / matrix rows,\n"
2134      "input format not accepted"<<endl;
2135    return 0;
2136  }
2137
2138  if(strcmp(format_string,"rows:"))
2139    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2140      "\n"
2141      "input file has suspicious format"<<endl;
2142
2143  input>>constraints;
2144
2145  if(!input)
2146  {
2147    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2148      "input failure when reading number of constraints / matrix rows,\n"
2149      "input format not accepted"
2150        <<endl;
2151    return 0;
2152  }
2153
2154  if(constraints<=0)
2155  {
2156    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2157      "number of constraints / matrix rows must be positive"<<endl;
2158    // Solving problems without constraints is possible, but not very
2159    // interesting (because trivial). To avoid the problems and the overhead
2160    // incurred by an "empty" matrix, such problems are refused.
2161    return 0;
2162  }
2163
2164  // read matrix
2165
2166  input>>format_string;
2167
2168  if(!input)
2169  {
2170    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2171      "input failure before reading matrix,\n"
2172      "input format not accepted"<<endl;
2173    return 0;
2174  }
2175
2176  if(strcmp(format_string,"matrix:"))
2177    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2178      "\n"
2179      "input file has suspicious format"<<endl;
2180
2181  matrix A(constraints,variables,input);
2182  if(A.error_status()<0)
2183  {
2184    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2185      "input failure when reading matrix, input format not accepted"<<endl;
2186    return 0;
2187  }
2188
2189  // read positive vector in the row space of the matrix
2190  // such a vector induces a grading with respect to which the ideal is
2191  // homogenous
2192
2193  input>>format_string;
2194
2195  if(!input)
2196  {
2197    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2198      "input failure before reading positive row space vector,\n"
2199      "input format not accepted"<<endl;
2200    return 0;
2201  }
2202
2203  if(strcmp(format_string,"positive"))
2204    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2205      "\n"
2206      "input file has suspicious format"<<endl;
2207
2208  input>>format_string;
2209
2210  if(!input)
2211  {
2212    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2213      "input failure before reading positive row space vector,\n"
2214      "input format not accepted"<<endl;
2215    return 0;
2216  }
2217
2218  if(strcmp(format_string,"row"))
2219    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2220      "\n"
2221      "input file has suspicious format"<<endl;
2222
2223  input>>format_string;
2224
2225  if(!input)
2226  {
2227    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2228      "input failure before reading positive row space vector,\n"
2229      " input format not accepted"<<endl;
2230    return 0;
2231  }
2232
2233  if(strcmp(format_string,"space"))
2234    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2235      "\n"
2236      "input file has suspicious format"<<endl;
2237
2238  input>>format_string;
2239
2240  if(!input)
2241  {
2242    cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):\n"
2243      "input failure before reading positive row space vector,\n"
2244      "input format not accepted"<<endl;
2245    return 0;
2246  }
2247
2248  if(strcmp(format_string,"vector:"))
2249    cerr<<"WARNING: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2250      "\n"
2251      "input file has suspicious format"<<endl;
2252
2253  float *hom_grad=new float[variables];
2254
2255  for(int _i=0;_i<variables;_i++)
2256  {
2257    input>>hom_grad[_i];
2258
2259    if(!input)
2260    {
2261      cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2262        "\n"
2263        "input failure when reading positive grading / row space vector,\n"
2264        "input format not accepted"<<endl;
2265      delete[] hom_grad;
2266      return 0;
2267    }
2268
2269    if(hom_grad[_i]<=0)
2270    {
2271      cerr<<"ERROR: int Bigatti_LaScala_Robbiano(INPUT_FILE, const BOOLEAN&):"
2272        "\n"
2273        "row space vector / grading must be positive"<<endl;
2274      delete[] hom_grad;
2275      return 0;
2276    }
2277  }
2278
2279
2280
2281///////////////////////// computation ////////////////////////////////////////
2282
2283  // prepare time measurement
2284  clock_t start, end;
2285
2286  // construct homogenous term ordering
2287  term_ordering w(variables, hom_grad, W_REV_LEX, HOMOGENEOUS);
2288
2289  delete[] hom_grad;
2290
2291  // create toric ideal
2292  ideal I(A,w,BIGATTI_LASCALA_ROBBIANO);
2293
2294  // compute the standard basis
2295  start=clock();
2296  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
2297
2298  // now we have a generating system
2299  // to perform the substitution of the auxiliary variable U by the saturation
2300  // variables:
2301  // make U the revlex most expensive variable by swapping with the first,
2302  // recompute the Groebner basis, undo the swap
2303  I.swap_variables(0,variables);
2304  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
2305  I.swap_variables(0,variables);
2306
2307  I.pseudo_eliminate();
2308  // eliminate the auxiliary variable
2309
2310  // Now the ideal is saturated. Compute the Groebner basis
2311  // with respect to the term ordering induced by the objective function.
2312  I.change_term_ordering_to(c);
2313  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
2314
2315  end=clock();
2316
2317  // time measurement
2318  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
2319
2320
2321///////////////////////// output ////////////////////////////////////////////
2322
2323  // create output file
2324
2325  char GROEBNER[128];
2326  int i=0;
2327  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
2328  {
2329    GROEBNER[i]=MATRIX[i];
2330    i++;
2331  }
2332  GROEBNER[i]='\0';
2333  strcat(GROEBNER,".GB.blr");
2334
2335  ofstream output(GROEBNER);
2336
2337  // format output file
2338
2339  output.flags(output.flags()|ios::fixed);
2340  // output of fixed point numbers
2341
2342  output<<"GROEBNER"<<endl<<endl;
2343
2344  output<<"computed with algorithm:"<<endl;
2345  output<<"blr"<<endl;
2346  output<<"from file(s):"<<endl;
2347  output<<MATRIX<<endl;
2348  output<<"computation time"<<endl;
2349  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
2350
2351  output<<"term ordering:"<<endl;
2352  output<<"elimination block"<<endl;
2353  // elimination variables (00)
2354  output<<0<<endl;
2355  output<<"weighted block"<<endl;
2356  // weighted variables (>0)
2357  output<<variables<<endl;
2358  output<<"W_LEX"<<endl;
2359  c.format_print_weight_vector(output);
2360
2361  output<<"size:"<<endl;
2362  output<<I.number_of_generators()<<endl<<endl;
2363
2364  output<<"Groebner basis:"<<endl;
2365  I.format_print(output);
2366  output<<endl;
2367
2368  if(verbose==TRUE)
2369  {
2370    output<<"settings for the Buchberger algorithm:"<<endl;
2371
2372    output<<"version:"<<endl;
2373    if(version==0)
2374      output<<"1a"<<endl;
2375    else
2376      output<<version<<endl;
2377
2378    output<<"S-pair criteria:"<<endl;
2379    if(S_pair_criteria & REL_PRIMENESS)
2380      output<<"relatively prime leading terms"<<endl;
2381    if(S_pair_criteria & M_CRITERION)
2382      output<<"criterion M"<<endl;
2383    if(S_pair_criteria & F_CRITERION)
2384      output<<"criterion F"<<endl;
2385    if(S_pair_criteria & B_CRITERION)
2386      output<<"criterion B"<<endl;
2387    if(S_pair_criteria & SECOND_CRITERION)
2388      output<<"second criterion"<<endl;
2389    output<<endl;
2390
2391    print_flags(output);
2392    output<<endl;
2393  }
2394
2395  return 1;
2396}
2397
2398
2399
2400
2401////////////////////////////////////////////////////////////////////////////
2402////////////////////////////////////////////////////////////////////////////
2403////////////////////////////////////////////////////////////////////////////
2404
2405
2406
2407
2408int solve(INPUT_FILE PROBLEM, INPUT_FILE GROEBNER)
2409{
2410
2411  char format_string[128];
2412  int problem_variables;
2413  int elimination_variables;
2414  int weighted_variables;
2415  char elimination_refinement[128];
2416  char weighted_refinement[128];
2417  char algorithm[128];
2418  long size;
2419  long instances;
2420
2421  ifstream problem(PROBLEM);
2422  ifstream groebner(GROEBNER);
2423
2424  // verfifie existence of files
2425
2426  if(!problem)
2427  {
2428    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2429      "cannot read from first input file "<< PROBLEM <<", possibly not found"<<endl;
2430    return 0;
2431  }
2432
2433  if(!groebner)
2434  {
2435    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2436      "cannot read from second input file "<< GROEBNER <<", possibly not found"<<endl;
2437    return 0;
2438  }
2439
2440// read GROEBNER file
2441
2442  // read format specification
2443
2444  groebner>>format_string;
2445
2446  if(!groebner)
2447  {
2448    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2449      "input failure when reading format specification of second input file,\n"
2450      "input format not accepted"<<endl;
2451    return 0;
2452  }
2453
2454  if(strcmp(format_string,"GROEBNER"))
2455    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2456      "second input file has suspicious format"<<endl;
2457
2458  // read algorithm
2459
2460  groebner>>format_string;
2461
2462  if(!groebner)
2463  {
2464    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2465      "input failure before reading algorithm from second input file,\n"
2466      "input format not accepted"<<endl;
2467    return 0;
2468  }
2469
2470  if(strcmp(format_string,"computed"))
2471    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2472      "second input file has suspicious format"<<endl;
2473
2474  groebner>>format_string;
2475
2476  if(!groebner)
2477  {
2478    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2479      "input failure before reading algorithm from second input file,\n"
2480      "input format not accepted"<<endl;
2481    return 0;
2482  }
2483
2484  if(strcmp(format_string,"with"))
2485    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2486      "second input file has suspicious format"<<endl;
2487
2488  groebner>>format_string;
2489
2490  if(!groebner)
2491  {
2492    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2493      "input failure before reading algorithm from second input file,\n"
2494      "input format not accepted"<<endl;
2495    return 0;
2496  }
2497
2498  if(strcmp(format_string,"algorithm:"))
2499    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2500      "second input file has suspicious format"<<endl;
2501
2502  groebner>>algorithm;
2503
2504  if(!groebner)
2505  {
2506    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2507      "input failure when reading algorithm from second input file,\n"
2508      "input format not accepted"<<endl;
2509    return 0;
2510  }
2511
2512  if(strcmp(algorithm,"ct") && strcmp(algorithm,"pct") &&
2513     strcmp(algorithm,"ect") && strcmp(algorithm,"pt") &&
2514     strcmp(algorithm,"hs") && strcmp(algorithm,"du")
2515     && strcmp(algorithm,"blr"))
2516    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2517      "second input file computed with unknown algorithm"<<endl;
2518
2519  // override optional lines
2520
2521  do
2522  {
2523    groebner>>format_string;
2524
2525    if(!groebner)
2526    {
2527      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2528        "input failure before reading term ordering from second \n"
2529        "input file, input format not accepted"<<endl;
2530      return 0;
2531    }
2532  }
2533  while(strcmp(format_string,"term"));
2534
2535  // read term ordering
2536
2537  groebner>>format_string;
2538
2539  if(!groebner)
2540  {
2541    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2542      "input failure before reading term ordering \n"
2543      "from second input file, input format not accepted"<<endl;
2544    return 0;
2545  }
2546
2547  if(strcmp(format_string,"ordering:"))
2548    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2549      "second input file has suspicious format"<<endl;
2550
2551  groebner>>format_string;
2552
2553  if(!groebner)
2554  {
2555    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2556      "input failure when reading term ordering \n"
2557      "from second input file, input format not accepted"<<endl;
2558    return 0;
2559  }
2560
2561  if(strcmp(format_string,"elimination"))
2562    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2563      "second input file has suspicious format"<<endl;
2564
2565  groebner>>format_string;
2566
2567  if(!groebner)
2568  {
2569    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2570      "input failure when reading term ordering \n"
2571      "from second input file, input format not accepted"<<endl;
2572    return 0;
2573  }
2574
2575  if(strcmp(format_string,"block"))
2576    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2577      "second input file has suspicious format"<<endl;
2578
2579  groebner>>elimination_variables;
2580
2581  if(!groebner)
2582  {
2583    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2584      "input failure when reading term ordering \n"
2585      "from second input file, input format not accepted"<<endl;
2586    return 0;
2587  }
2588
2589  if(elimination_variables<0)
2590  {
2591    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2592      "number of elimination variables in second input file must be "
2593      "nonnegative"<<endl;
2594    return 0;
2595  }
2596
2597  if(elimination_variables>0)
2598  {
2599    groebner>>elimination_refinement;
2600
2601    if(!groebner)
2602    {
2603      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2604        "input failure when reading term ordering \n"
2605        "from second input file, input format not accepted"<<endl;
2606      return 0;
2607    }
2608
2609    if(strcmp(elimination_refinement,"LEX") &&
2610       strcmp(elimination_refinement,"DEG_LEX") &&
2611       strcmp(elimination_refinement,"DEG_REV_LEX"))
2612    {
2613      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2614        "unknown elimination ordering in second input file"<<endl;
2615      return 0;
2616    }
2617  }
2618
2619  groebner>>format_string;
2620
2621  if(!groebner)
2622  {
2623    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2624      "input failure when reading term ordering \n"
2625      "from second input file, input format not accepted"<<endl;
2626    return 0;
2627  }
2628
2629  if(strcmp(format_string,"weighted"))
2630    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2631      "second input file has suspicious format"<<endl;
2632
2633  groebner>>format_string;
2634
2635  if(!groebner)
2636  {
2637    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2638      "input failure when reading term ordering \n"
2639      "from second input file, input format not accepted"<<endl;
2640    return 0;
2641  }
2642
2643  if(strcmp(format_string,"block"))
2644    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2645      "second input file has suspicious format"<<endl;
2646
2647  groebner>>weighted_variables;
2648
2649  if(!groebner)
2650  {
2651    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2652      "input failure when reading term ordering \n"
2653      "from second input file, input format not accepted"<<endl;
2654    return 0;
2655  }
2656
2657  if(weighted_variables<=0)
2658  {
2659    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2660      "number of weighted variables in second input file must be "
2661      "positive"<<endl;
2662    return 0;
2663  }
2664
2665  groebner>>weighted_refinement;
2666
2667  if(!groebner)
2668  {
2669    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2670      "input failure when reading term ordering \n"
2671      "from second input file, input format not accepted"<<endl;
2672    return 0;
2673  }
2674
2675  if(strcmp(weighted_refinement,"W_LEX") &&
2676     strcmp(weighted_refinement,"W_REV_LEX") &&
2677     strcmp(weighted_refinement,"W_DEG_LEX") &&
2678     strcmp(weighted_refinement,"W_DEG_REV_LEX"))
2679  {
2680    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2681      "unknown weighted ordering in second input file"<<endl;
2682    return 0;
2683  }
2684
2685  int weighted_ref;
2686  if(!strcmp(weighted_refinement,"W_LEX"))
2687    weighted_ref=W_LEX;
2688  if(!strcmp(weighted_refinement,"W_REV_LEX"))
2689    weighted_ref=W_REV_LEX;
2690  if(!strcmp(weighted_refinement,"W_DEG_LEX"))
2691    weighted_ref=W_DEG_LEX;
2692  if(!strcmp(weighted_refinement,"W_DEG_REV_LEX"))
2693    weighted_ref=W_DEG_REV_LEX;
2694
2695  term_ordering w(weighted_variables,groebner,weighted_ref);
2696
2697  if(w.error_status()<0)
2698  {
2699    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2700      "input failure when reading new cost vector from second input file,\n"
2701      "input format not accepted"<<endl;
2702    return 0;
2703  }
2704
2705  if(w.is_nonnegative()==FALSE)
2706  {
2707    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2708      "cost vectors with negative components are not supported"<<endl;
2709    return 0;
2710  }
2711
2712  if(elimination_variables>0)
2713  {
2714    int elimination_ref;
2715    if(!strcmp(elimination_refinement,"LEX"))
2716      elimination_ref=LEX;
2717    if(!strcmp(elimination_refinement,"DEG_LEX"))
2718      elimination_ref=DEG_LEX;
2719    if(!strcmp(elimination_refinement,"DEG_REV_LEX"))
2720      elimination_ref=DEG_REV_LEX;
2721
2722    w.convert_to_elimination_ordering(elimination_variables,elimination_ref);
2723
2724    if(w.error_status()<0)
2725    {
2726      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2727        "input failure when reading new cost vector from second input file,\n"
2728        "input format not accepted"<<endl;
2729      return 0;
2730    }
2731  }
2732
2733  // read ideal
2734
2735  groebner>>format_string;
2736
2737  if(!groebner)
2738  {
2739    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2740      "input failure before reading number of ideal generators \n"
2741      "from second input file, input format not accepted"<<endl;
2742    return 0;
2743  }
2744
2745  if(strcmp(format_string,"size:"))
2746    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2747      "second input file has suspicious format"<<endl;
2748
2749  groebner>>size;
2750
2751  if(!groebner)
2752  {
2753    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2754      "input failure when reading number of ideal generators \n"
2755      "from second input file, input format not accepted"<<endl;
2756    return 0;
2757  }
2758
2759  if(size<0)
2760  {
2761    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2762      "ideal in second input file is corrupt"<<endl;
2763    return 0;
2764  }
2765
2766  groebner>>format_string;
2767
2768  if(!groebner)
2769  {
2770    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2771      "input failure before reading ideal generators \n"
2772      "from second input file, input format not accepted"<<endl;
2773    return 0;
2774  }
2775
2776  if(strcmp(format_string,"Groebner"))
2777    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2778      "second input file has suspicious format"<<endl;
2779
2780  groebner>>format_string;
2781
2782  if(!groebner)
2783  {
2784    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2785      "input failure before reading ideal generators \n"
2786      "from second input file, input format not accepted"<<endl;
2787    return 0;
2788  }
2789
2790  if(strcmp(format_string,"basis:"))
2791    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2792      "second input file has suspicious format"<<endl;
2793
2794  ideal I(groebner,w,size);
2795
2796  if(!groebner)
2797  {
2798    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2799      "input failure when reading ideal generators from second input file,\n"
2800      "input format not accepted."<<endl;
2801    return 0;
2802  }
2803
2804  if(I.error_status()<0)
2805  {
2806    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2807      "cannot compute with corrupt ideal\n"<<endl;
2808    return 0;
2809  }
2810
2811// read PROBLEM file
2812
2813  // read format specification
2814
2815  problem>>format_string;
2816
2817  if(!problem)
2818  {
2819    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2820      "input failure when reading format specification of first input file,\n"
2821      "input format not accepted"<<endl;
2822    return 0;
2823  }
2824
2825  if(strcmp(format_string,"PROBLEM"))
2826    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2827      "first input file has suspicious format"<<endl;
2828
2829  // read vector dimension
2830
2831  problem>>format_string;
2832
2833  if(!problem)
2834  {
2835    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2836      "input failure before reading vector dimension from first input file,\n"
2837      "input format not accepted"<<endl;
2838    return 0;
2839  }
2840
2841  if(strcmp(format_string,"vector"))
2842    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2843      "first input file has suspicious format"<<endl;
2844
2845  problem>>format_string;
2846
2847  if(!problem)
2848  {
2849    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2850      "input failure before reading vector dimension from first input file,\n"
2851      "input format not accepted"<<endl;
2852    return 0;
2853  }
2854
2855  if(strcmp(format_string,"size:"))
2856    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2857      "first input file has suspicious format"<<endl;
2858
2859  problem>>problem_variables;
2860
2861  if(!problem)
2862  {
2863    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2864      "input failure when reading vector dimension from first input file,\n"
2865      "input format not accepted"<<endl;
2866    return 0;
2867  }
2868
2869  if(problem_variables<=0)
2870  {
2871    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2872      "vector dimension in first input file must be positive"<<endl;
2873    return 0;
2874  }
2875
2876  // consistency with respect to the number of variables is checked later
2877
2878  // read number of instances
2879
2880  problem>>format_string;
2881
2882  if(!problem)
2883  {
2884    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2885      "input failure before reading number of instances from first input file,"
2886      "\n"
2887      "input format not accepted"<<endl;
2888    return 0;
2889  }
2890
2891  if(strcmp(format_string,"number"))
2892    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2893      "first input file has suspicious format"<<endl;
2894
2895  problem>>format_string;
2896
2897  if(!problem)
2898  {
2899    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2900      "input failure before reading number of instances from first input file,"
2901      "\n"
2902      "input format not accepted"<<endl;
2903    return 0;
2904  }
2905
2906  if(strcmp(format_string,"of"))
2907    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2908      "first input file has suspicious format"<<endl;
2909
2910  problem>>format_string;
2911
2912  if(!problem)
2913  {
2914    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2915      "input failure before reading number of instances from first input file,"
2916      "\n"
2917      "input format not accepted"<<endl;
2918    return 0;
2919  }
2920
2921  if(strcmp(format_string,"instances:"))
2922    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2923      "first input file has suspicious format"<<endl;
2924
2925  problem>>instances;
2926
2927  if(!problem)
2928  {
2929    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2930      "input failure when reading number of instances from first input file,\n"
2931      "input format not accepted"<<endl;
2932    return 0;
2933  }
2934
2935  if(instances<=0)
2936  {
2937    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2938      "number of instances is <1, no output file created"<<endl;
2939    return 1;
2940    // no error
2941  }
2942
2943  // read problem vectors (first part)
2944
2945  problem>>format_string;
2946
2947  if(!problem)
2948  {
2949    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2950      "input failure before reading right hand / initial solution vectors \n"
2951      "from first input file, input format not accepted"<<endl;
2952    return 0;
2953  }
2954
2955  if(strcmp(format_string,"right"))
2956    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2957      "first input file has suspicious format"<<endl;
2958
2959  problem>>format_string;
2960
2961  if(!problem)
2962  {
2963    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2964      "input failure before reading right hand / initial solution vectors \n"
2965      "from first input file, input format not accepted"<<endl;
2966    return 0;
2967  }
2968
2969  if(strcmp(format_string,"hand"))
2970    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2971      "first input file has suspicious format"<<endl;
2972
2973  problem>>format_string;
2974
2975  if(!problem)
2976  {
2977    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2978      "input failure before reading right hand / initial solution vectors \n"
2979      "from first input file, input format not accepted"<<endl;
2980    return 0;
2981  }
2982
2983  if(strcmp(format_string,"or"))
2984    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2985      "first input file has suspicious format"<<endl;
2986
2987  problem>>format_string;
2988
2989  if(!problem)
2990  {
2991    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2992      "input failure before reading right hand / initial solution vectors \n"
2993      "from first input file, input format not accepted"<<endl;
2994    return 0;
2995  }
2996
2997  if(strcmp(format_string,"initial"))
2998    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2999      "first input file has suspicious format"<<endl;
3000
3001  problem>>format_string;
3002
3003  if(!problem)
3004  {
3005    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3006      "input failure before reading right hand / initial solution vectors \n"
3007      "from first input file, input format not accepted"<<endl;
3008    return 0;
3009  }
3010
3011  if(strcmp(format_string,"solution"))
3012    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
3013      "first input file has suspicious format"<<endl;
3014
3015  problem>>format_string;
3016
3017  if(!problem)
3018  {
3019    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3020      "input failure before reading right hand / initial solution vectors \n"
3021      "from first input file, input format not accepted"<<endl;
3022    return 0;
3023  }
3024
3025  if(strcmp(format_string,"vectors:"))
3026    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
3027      "first input file has suspicious format"<<endl;
3028
3029  // the vectors are read in the section "computation" because we need to
3030  // distinguish between the different algorithms
3031
3032
3033//////////////////// output (first part) ///////////////////////////////////
3034
3035  // open output file (append mode)
3036
3037  char SOLUTION[128];
3038
3039  int i=0;
3040  while(GROEBNER[i]!='\0' && GROEBNER[i]!='.')
3041  {
3042    SOLUTION[i]=GROEBNER[i];
3043    i++;
3044  }
3045  SOLUTION[i]='\0';
3046  strcat(SOLUTION,".sol.");
3047  strcat(SOLUTION,algorithm);
3048
3049  ofstream output(SOLUTION,ios::app);
3050
3051  // format output file
3052
3053  output.flags(output.flags()|ios::fixed);
3054  // output of fixed point numbers
3055
3056  output<<"SOLUTION"<<endl<<endl;
3057
3058  output<<"computed with algorithm:"<<endl;
3059  output<<algorithm<<endl;
3060  output<<"from file:"<<endl;
3061  output<<GROEBNER<<endl;
3062
3063
3064/////////// computation and output (second part) //////////////////////////
3065
3066  // distinguish 3 cases to verifie the consistency of the vector dimension
3067  // and the number of variables
3068
3069  // Conti-Traverso: vectors are read as right hand vectors
3070  // vector dimension = number of elimination variables without inversion
3071  // variable
3072  if(!strcmp(algorithm,"ct"))
3073  {
3074    if(problem_variables!=elimination_variables-1)
3075    {
3076      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3077        "vector dimension in first input file and number of variables in\n"
3078        "second input file do not match with respect to the\n"
3079        "Conti-Traverso-algorithm"<<endl;
3080      return 0;
3081    }
3082
3083    Integer right_hand[weighted_variables+elimination_variables];
3084
3085    for(int k=0;k<instances;k++)
3086    {
3087      // at the beginning, the variables of interest are zero
3088      for(i=0;i<weighted_variables;i++)
3089        right_hand[i]=0;
3090
3091      // right hand vector is read from the input stream into the
3092      // elimination variables
3093      for(i=weighted_variables;
3094          i<weighted_variables+elimination_variables-1;i++)
3095      {
3096        problem>>right_hand[i];
3097
3098        if(!problem)
3099        {
3100          cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3101            "input failure when reading right hand vector "<<k+1<<" from "
3102            "first input \nfile, "
3103            "this and all following right hand vectors will be ignored"<<endl;
3104          return 0;
3105        }
3106      }
3107
3108      // determine the exponent of the inversion variable, i.e.
3109      // - min{negative components of right_hand}.
3110      Integer min=0;
3111      for(i=weighted_variables;
3112          i<weighted_variables+elimination_variables-1;i++)
3113        if(right_hand[i]<min)
3114          min=right_hand[i];
3115
3116      // transform right_hand so that all components are nonnegative
3117      if(min<0)
3118        for(i=weighted_variables;
3119            i<weighted_variables+elimination_variables-1;i++)
3120          right_hand[i]-=min;
3121
3122      // set exponent of the inversion variable
3123      right_hand[weighted_variables+elimination_variables-1]=-min;
3124
3125      // construct binomial to reduce
3126      binomial to_reduce(weighted_variables+elimination_variables,right_hand);
3127
3128      // prepare time measurement
3129      clock_t start, end;
3130
3131      // reduce binomial
3132      start=clock();
3133      I.reduce(to_reduce,TRUE);
3134      end=clock();
3135
3136      // time measurement
3137      float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3138
3139      // output
3140
3141      output<<"right hand vector:"<<endl;
3142      for(i=weighted_variables;
3143          i<weighted_variables+elimination_variables-1;i++)
3144        output<<setw(6)<<right_hand[i]+min;
3145        // original vector
3146      output<<endl;
3147
3148      output<<"solvable:"<<endl;
3149
3150      BOOLEAN solvable=TRUE;
3151      for(i=weighted_variables;
3152          i<=weighted_variables+elimination_variables-1;i++)
3153        if(to_reduce[i]!=0)
3154        {
3155          solvable=FALSE;
3156          break;
3157        }
3158
3159      if(solvable==TRUE)
3160      {
3161        output<<"YES"<<endl;
3162        output<<"optimal solution:"<<endl;
3163        for(i=0;i<weighted_variables;i++)
3164          output<<setw(6)<<to_reduce[i];
3165        output<<endl;
3166      }
3167      else
3168        output<<"NO"<<endl;
3169
3170      output<<"computation time"<<endl;
3171      output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3172    }
3173  }
3174
3175  else
3176    // Positive Conti-Traverso: vectors are read as right hand vectors
3177    // vector dimension = number of elimination variables
3178    if(!strcmp(algorithm,"pct"))
3179    {
3180      if(problem_variables!=elimination_variables)
3181      {
3182        cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3183          "vector dimension in first input file and number of variables in\n"
3184          "second input file do not match with respect to the\n"
3185          "Positive Conti-Traverso algorithm"<<endl;
3186        return 0;
3187      }
3188
3189      Integer right_hand[weighted_variables+elimination_variables];
3190      BOOLEAN error=FALSE;    // to test legality of right hand vectors
3191
3192      for(int k=0;k<instances;k++)
3193      {
3194        // at the beginning, the variables of interest are zero
3195        for(i=0;i<weighted_variables;i++)
3196          right_hand[i]=0;
3197
3198        // right hand vector is read from the input stream into the
3199        // elimination variables
3200        for(i=weighted_variables;
3201            i<weighted_variables+elimination_variables;i++)
3202        {
3203          problem>>right_hand[i];
3204
3205          if(!problem)
3206          {
3207            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3208              "input failure when reading right hand vector "<<k+1<<" from "
3209              "first input \nfile, this and all following right hand vectors "
3210              "will be ignored"<<endl;
3211            return 0;
3212          }
3213
3214          if(right_hand[i]<0)
3215          {
3216            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3217              "right hand vectors with negative components cannot be handled\n"
3218              "by the Positive Conti-Traverso algorithm,\n"
3219              "right hand vector "<<k+1<<" will be ignored"<<endl;
3220            error=TRUE;
3221          }
3222        }
3223
3224        if(error==TRUE)
3225        {
3226          error=FALSE;
3227          continue;
3228          // for-loop
3229        }
3230
3231        // construct binomial to reduce
3232        binomial to_reduce(weighted_variables+elimination_variables,
3233                           right_hand);
3234
3235        // prepare time measurement
3236        clock_t start, end;
3237
3238        // reduce binomial
3239        start=clock();
3240        I.reduce(to_reduce,TRUE);
3241        end=clock();
3242
3243        // time measurement
3244        float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3245
3246        // output
3247
3248        output<<"right hand vector:"<<endl;
3249        for(i=weighted_variables;
3250            i<weighted_variables+elimination_variables;i++)
3251          output<<setw(6)<<right_hand[i];
3252        // original vector
3253        output<<endl;
3254
3255        output<<"solvable:"<<endl;
3256
3257        BOOLEAN solvable=TRUE;
3258        for(i=weighted_variables;
3259            i<weighted_variables+elimination_variables;i++)
3260          if(to_reduce[i]!=0)
3261          {
3262            solvable=FALSE;
3263            break;
3264          }
3265
3266        if(solvable==TRUE)
3267        {
3268          output<<"YES"<<endl;
3269          output<<"optimal solution:"<<endl;
3270          for(i=0;i<weighted_variables;i++)
3271            output<<setw(6)<<to_reduce[i];
3272          output<<endl;
3273        }
3274        else
3275          output<<"NO"<<endl;
3276
3277        output<<"computation time"<<endl;
3278        output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3279      }
3280    }
3281
3282    else
3283      // other algorithms: vectors are read as initial solutions
3284      // vector dimension = number of weighted variables
3285    {
3286      if(problem_variables!=weighted_variables)
3287      {
3288        cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3289          "vector dimension in first input file and number of variables in\n"
3290          "second input file do not match with respect to the\n"
3291          "chosen algorithm"<<endl;
3292        return 0;
3293      }
3294
3295      Integer initial_solution[weighted_variables];
3296
3297      for(int k=0;k<instances;k++)
3298      {
3299        // initial solution vector is read from the input stream into the
3300        // elimination variables
3301        for(i=0;i<weighted_variables;i++)
3302        {
3303          problem>>initial_solution[i];
3304
3305          if(!problem)
3306          {
3307            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3308              "input failure when reading right hand vector "<<k+1<<" from "
3309              "first input \nfile, this and all following right hand vectors "
3310              "will be ignored"<<endl;
3311            return 0;
3312          }
3313
3314          if(initial_solution[i]<0)
3315            cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
3316              "initial solution vectors should be nonnegative"<<endl;
3317        }
3318
3319        // construct binomial to reduce
3320        binomial to_reduce(weighted_variables,initial_solution);
3321
3322        // prepare time measurement
3323        clock_t start, end;
3324
3325        // reduce binomial
3326        start=clock();
3327        I.reduce(to_reduce,TRUE);
3328        end=clock();
3329
3330        // time measurement
3331        float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3332
3333        // output
3334
3335        output<<"initial solution vector:"<<endl;
3336        for(i=0;i<weighted_variables;i++)
3337          output<<setw(6)<<initial_solution[i];
3338        // original vector
3339        output<<endl;
3340
3341        output<<"optimal solution:"<<endl;
3342        for(i=0;i<weighted_variables;i++)
3343          output<<setw(6)<<to_reduce[i];
3344        output<<endl;
3345
3346        output<<"computation time"<<endl;
3347        output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3348      }
3349    }
3350
3351  return 1;
3352
3353}
3354
3355
3356
3357////////////////////////////////////////////////////////////////////////////
3358////////////////////////////////////////////////////////////////////////////
3359////////////////////////////////////////////////////////////////////////////
3360
3361
3362
3363
3364int change_cost(INPUT_FILE GROEBNER, INPUT_FILE NEW_COST,
3365                const int& version,
3366                const int& S_pair_criteria,
3367                const float& interred_percentage,
3368                const BOOLEAN& verbose)
3369{
3370
3371  char format_string[128];
3372  int elimination_variables;
3373  int weighted_variables;
3374  char elimination_refinement[128];
3375  char weighted_refinement[128];
3376  int new_variables;
3377  char algorithm[128];
3378  long old_size;
3379
3380  ifstream old(GROEBNER);
3381  ifstream _new(NEW_COST);
3382
3383  // verifie existence of files
3384
3385  if(!old)
3386  {
3387    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3388      "cannot read from first input file, possibly not found"<<endl;
3389    return 0;
3390  }
3391
3392  if(!_new)
3393  {
3394    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3395      "cannot read from second input file, possibly not found"<<endl;
3396    return 0;
3397  }
3398
3399
3400// read first part of GROEBNER file (until term ordering reached)
3401
3402  // read format specification
3403
3404  old>>format_string;
3405
3406  if(!old)
3407  {
3408    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3409      "input failure when reading format specification of first input file,\n"
3410      "input format not accepted"<<endl;
3411    return 0;
3412  }
3413
3414  if(strcmp(format_string,"GROEBNER"))
3415  {
3416    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3417      "first input file has suspicious format"<<endl;
3418  }
3419
3420  // read algorithm
3421
3422  old>>format_string;
3423
3424  if(!old)
3425  {
3426    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3427      "input failure before reading algorithm from first input file,\n"
3428      "input format not accepted"<<endl;
3429    return 0;
3430  }
3431
3432  if(strcmp(format_string,"computed"))
3433  {
3434    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3435      "first input file has suspicious format"<<endl;
3436  }
3437
3438  old>>format_string;
3439
3440  if(!old)
3441  {
3442    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3443      "input failure before reading algorithm from first input file,\n"
3444      "input format not accepted"<<endl;
3445    return 0;
3446  }
3447
3448  if(strcmp(format_string,"with"))
3449  {
3450    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3451      "first input file has suspicious format"<<endl;
3452  }
3453
3454  old>>format_string;
3455
3456  if(!old)
3457  {
3458    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3459      "input failure before reading algorithm from first input file,\n"
3460      "input format not accepted"<<endl;
3461    return 0;
3462  }
3463
3464  if(strcmp(format_string,"algorithm:"))
3465  {
3466    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3467      "first input file has suspicious format"<<endl;
3468  }
3469
3470  old>>algorithm;
3471
3472  if(!old)
3473  {
3474    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3475      "input failure when reading algorithm from first input file,\n"
3476      "input format not accepted"<<endl;
3477    return 0;
3478  }
3479
3480  if(strcmp(algorithm,"ct") && strcmp(algorithm,"pct") &&
3481     strcmp(algorithm,"ect") && strcmp(algorithm,"pt") &&
3482     strcmp(algorithm,"hs") && strcmp(algorithm,"du")
3483     && strcmp(algorithm,"blr"))
3484  {
3485    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3486      "first input file computed with unknown algorithm"<<endl;
3487  }
3488
3489  // override optional lines
3490
3491  do
3492  {
3493    old>>format_string;
3494
3495    if(!old)
3496    {
3497      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3498        "input failure before reading term ordering from first \n"
3499        "input file, input format not accepted"<<endl;
3500      return 0;
3501    }
3502  }
3503  while(strcmp(format_string,"term"));
3504
3505  // read term ordering
3506
3507  old>>format_string;
3508
3509  if(!old)
3510  {
3511    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3512      "input failure before reading term ordering \n"
3513      "from first input file, input format not accepted"<<endl;
3514    return 0;
3515  }
3516
3517  if(strcmp(format_string,"ordering:"))
3518  {
3519    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3520      "first input file has suspicious format"<<endl;
3521  }
3522
3523  old>>format_string;
3524
3525  if(!old)
3526  {
3527    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3528      "input failure when reading term ordering \n"
3529      "from first input file, input format not accepted"<<endl;
3530    return 0;
3531  }
3532
3533  if(strcmp(format_string,"elimination"))
3534  {
3535    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3536      "first input file has suspicious format"<<endl;
3537  }
3538
3539  old>>format_string;
3540
3541  if(!old)
3542  {
3543    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3544      "input failure when reading term ordering \n"
3545      "from first input file, input format not accepted"<<endl;
3546    return 0;
3547  }
3548
3549  if(strcmp(format_string,"block"))
3550  {
3551    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3552      "first input file has suspicious format"<<endl;
3553  }
3554
3555  old>>elimination_variables;
3556
3557  if(!old)
3558  {
3559    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3560      "input failure when reading term ordering \n"
3561      "from first input file, input format not accepted"<<endl;
3562    return 0;
3563  }
3564
3565  if(elimination_variables<0)
3566  {
3567    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3568      "number of elimination variables in first input file must be "
3569      "nonnegative"<<endl;
3570    return 0;
3571  }
3572
3573  if(elimination_variables>0)
3574  {
3575    old>>elimination_refinement;
3576
3577    if(!old)
3578    {
3579      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3580        "input failure when reading term ordering \n"
3581        "from first input file, input format not accepted"<<endl;
3582      return 0;
3583    }
3584
3585    if(strcmp(elimination_refinement,"LEX") &&
3586       strcmp(elimination_refinement,"DEG_LEX") &&
3587       strcmp(elimination_refinement,"DEG_REV_LEX"))
3588    {
3589      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3590        "unknown elimination ordering in first input file"<<endl;
3591      return 0;
3592    }
3593  }
3594
3595  old>>format_string;
3596
3597  if(!old)
3598  {
3599    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3600      "input failure when reading term ordering \n"
3601      "from first input file, input format not accepted"<<endl;
3602    return 0;
3603  }
3604
3605  if(strcmp(format_string,"weighted"))
3606  {
3607    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3608      "first input file has suspicious format"<<endl;
3609  }
3610
3611  old>>format_string;
3612
3613  if(!old)
3614  {
3615    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3616      "input failure when reading term ordering \n"
3617      "from first input file, input format not accepted"<<endl;
3618    return 0;
3619  }
3620
3621  if(strcmp(format_string,"block"))
3622  {
3623    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3624      "first input file has suspicious format"<<endl;
3625  }
3626
3627  old>>weighted_variables;
3628
3629  if(!old)
3630  {
3631    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3632      "input failure when reading term ordering \n"
3633      "from first input file, input format not accepted"<<endl;
3634    return 0;
3635  }
3636
3637  if(weighted_variables<=0)
3638  {
3639    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3640      "number of weighted variables in first input file must be "
3641      "positive"<<endl;
3642    return 0;
3643  }
3644
3645  old>>weighted_refinement;
3646
3647  if(!old)
3648  {
3649    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3650      "input failure when reading term ordering \n"
3651      "from first input file, input format not accepted"<<endl;
3652    return 0;
3653  }
3654
3655  if(strcmp(weighted_refinement,"W_LEX") &&
3656     strcmp(weighted_refinement,"W_REV_LEX") &&
3657     strcmp(weighted_refinement,"W_DEG_LEX") &&
3658     strcmp(weighted_refinement,"W_DEG_REV_LEX"))
3659  {
3660    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3661      "unknown weighted ordering in first input file"<<endl;
3662    return 0;
3663  }
3664
3665// read NEW_COST file
3666
3667  // read format specification
3668
3669  _new>>format_string;
3670
3671  if(!_new)
3672  {
3673    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3674      "input failure when reading format specification\n"
3675      "from second input file, input format not accepted"<<endl;
3676    return 0;
3677  }
3678
3679  if(strcmp(format_string,"MATRIX") && strcmp(format_string,"NEW_COST"))
3680  {
3681    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3682      "second input file has suspicious format"<<endl;
3683  }
3684
3685  // read number of variables
3686
3687  _new>>format_string;
3688
3689  if(!_new)
3690  {
3691    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3692      "input failure before reading number of variables \n"
3693      "from second input file, input format not accepted"<<endl;
3694    return 0;
3695  }
3696
3697  if(strcmp(format_string,"columns:") && strcmp(format_string,"variables:"))
3698    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3699      "second input file has suspicious format"<<endl;
3700
3701  _new>>new_variables;
3702
3703  if(!_new)
3704  {
3705    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3706      "input failure when reading number of variables \n"
3707      "from second input file, input format not accepted"<<endl;
3708    return 0;
3709  }
3710
3711  if(new_variables<=0)
3712  {
3713    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3714      "number of variables in second input file must be positive"<<endl;
3715    return 0;
3716  }
3717
3718  // Now we can verifie consistency of both files with respect to the number
3719  // of weighted variables:
3720
3721  if(weighted_variables!=new_variables)
3722  {
3723    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3724      "number of variables in first and second input file do not match"<<endl;
3725    return 0;
3726  }
3727
3728  // read term ordering
3729
3730  _new>>format_string;
3731
3732  if(!_new)
3733  {
3734    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3735      "input failure before reading new cost vector from second input file,\n"
3736      "input format not accepted"<<endl;
3737    return 0;
3738  }
3739
3740  if(strcmp(format_string,"cost"))
3741    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3742      "second input file has suspicious format"<<endl;
3743
3744  _new>>format_string;
3745
3746  if(!_new)
3747  {
3748    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3749      "input failure before reading new cost vector from second input file,\n"
3750      "input format not accepted"<<endl;
3751    return 0;
3752  }
3753
3754  if(strcmp(format_string,"vector:"))
3755    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3756      "second input file has suspicious format"<<endl;
3757
3758  // the term ordering to refine the weight is taken to be the same as that
3759  // for the old Groebner basis
3760  int weighted_ref;
3761  if(!strcmp(weighted_refinement,"W_LEX"))
3762    weighted_ref=W_LEX;
3763  if(!strcmp(weighted_refinement,"W_REV_LEX"))
3764    weighted_ref=W_REV_LEX;
3765  if(!strcmp(weighted_refinement,"W_DEG_LEX"))
3766    weighted_ref=W_DEG_LEX;
3767  if(!strcmp(weighted_refinement,"W_DEG_REV_LEX"))
3768    weighted_ref=W_DEG_REV_LEX;
3769
3770  term_ordering w(weighted_variables,_new,weighted_ref);
3771
3772  if(w.error_status()<0)
3773  {
3774    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3775      "input failure when reading new cost vector from second input file,\n"
3776      "input format not accepted"<<endl;
3777    return 0;
3778  }
3779
3780  if(w.is_nonnegative()==FALSE)
3781  {
3782    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3783      "cost vectors with negative components are not supported"<<endl;
3784    return 0;
3785  }
3786
3787  if(elimination_variables>0)
3788  {
3789    int elimination_ref;
3790    if(!strcmp(elimination_refinement,"LEX"))
3791      elimination_ref=LEX;
3792    if(!strcmp(elimination_refinement,"DEG_LEX"))
3793      elimination_ref=DEG_LEX;
3794    if(!strcmp(elimination_refinement,"DEG_REV_LEX"))
3795      elimination_ref=DEG_REV_LEX;
3796    w.convert_to_elimination_ordering(elimination_variables,elimination_ref);
3797
3798    if(w.error_status()<0)
3799    {
3800      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3801        "input failure when reading new cost vector from second input file,\n"
3802        "input format not accepted"<<endl;
3803      return 0;
3804    }
3805  }
3806
3807// read second part of the GROEBNER file
3808
3809  // override old weight vector
3810
3811  do
3812  {
3813    old>>format_string;
3814
3815    if(!old)
3816    {
3817      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3818        "input failure before reading number of ideal generators \n"
3819        "from first input file, input format not accepted"<<endl;
3820      return 0;
3821    }
3822  }
3823  while(strcmp(format_string,"size:"));
3824
3825  // read old Groebner basis
3826
3827  old>>old_size;
3828
3829  if(!old)
3830  {
3831    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3832      "input failure when reading number of ideal generators \n"
3833      "from first input file, input format not accepted"<<endl;
3834    return 0;
3835  }
3836
3837  if(old_size<=0)
3838  {
3839    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3840      "ideal in first input file is corrupt"<<endl;
3841    return 0;
3842  }
3843
3844  old>>format_string;
3845
3846  if(!old)
3847  {
3848    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3849      "input failure before reading ideal generators \n"
3850      "from first input file, input format not accepted"<<endl;
3851    return 0;
3852  }
3853
3854  if(strcmp(format_string,"Groebner"))
3855  {
3856    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3857      "first input file has suspicious format"<<endl;
3858  }
3859
3860  old>>format_string;
3861
3862  if(!old)
3863  {
3864    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3865      "input failure before reading ideal generators \n"
3866      "from first input file, input format not accepted"<<endl;
3867    return 0;
3868  }
3869
3870  if(strcmp(format_string,"basis:"))
3871  {
3872    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3873      "first input file has suspicious format"<<endl;
3874  }
3875
3876  // read ideal generators from first input file, already with respect to
3877  // the new term ordering
3878  ideal I(old,w,old_size);
3879
3880  if(!old)
3881  {
3882    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3883      "input failure when reading ideal generators from first input file,\n"
3884      "input format not accepted."<<endl;
3885    return 0;
3886  }
3887
3888  if(I.error_status()<0)
3889  {
3890    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3891      "cannot compute with corrupt ideal\n"<<endl;
3892    return 0;
3893  }
3894
3895
3896///////////////////////// computation ////////////////////////////////////////
3897
3898  // prepare time measurement
3899  clock_t start, end;
3900
3901  // compute new Groebner basis
3902  start=clock();
3903  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
3904  end=clock();
3905
3906  // time measurement
3907  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3908
3909
3910///////////////////////// output ////////////////////////////////////////////
3911
3912  // create output file
3913
3914  char NEW_GROEBNER[128];
3915
3916  int i=0;
3917  while(NEW_COST[i]!='\0' && NEW_COST[i]!='.')
3918  {
3919    NEW_GROEBNER[i]=NEW_COST[i];
3920    i++;
3921  }
3922  NEW_GROEBNER[i]='\0';
3923  strcat(NEW_GROEBNER,".GB.");
3924  strcat(NEW_GROEBNER,algorithm);
3925
3926  ofstream output(NEW_GROEBNER);
3927
3928  // format output file
3929
3930  output.flags(output.flags()|ios::fixed);
3931  // output of fixed point numbers
3932
3933  output<<"GROEBNER"<<endl<<endl;
3934
3935  output<<"computed with algorithm:"<<endl;
3936  output<<algorithm<<endl;
3937  output<<"from file(s):"<<endl;
3938  output<<GROEBNER<<", "<<NEW_COST<<endl;
3939  output<<"computation time"<<endl;
3940  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3941
3942  output<<"term ordering:"<<endl;
3943  output<<"elimination block"<<endl;
3944  // elimination variables
3945  output<<elimination_variables<<endl;
3946  if(elimination_variables>0)
3947    output<<elimination_refinement<<endl;
3948  output<<"weighted block"<<endl;
3949  // weighted variables (>0)
3950  output<<weighted_variables<<endl;
3951  output<<weighted_refinement<<endl;
3952  w.format_print_weight_vector(output);
3953
3954  output<<"size:"<<endl;
3955  output<<I.number_of_generators()<<endl<<endl;
3956
3957  output<<"Groebner basis:"<<endl;
3958  I.format_print(output);
3959  output<<endl;
3960
3961  if(verbose==TRUE)
3962  {
3963    output<<"settings for the Buchberger algorithm:"<<endl;
3964
3965    output<<"version:"<<endl;
3966    if(version==0)
3967      output<<"1a"<<endl;
3968    else
3969      output<<version<<endl;
3970
3971    output<<"S-pair criteria:"<<endl;
3972    if(S_pair_criteria & REL_PRIMENESS)
3973      output<<"relatively prime leading terms"<<endl;
3974    if(S_pair_criteria & M_CRITERION)
3975      output<<"criterion M"<<endl;
3976    if(S_pair_criteria & F_CRITERION)
3977      output<<"criterion F"<<endl;
3978    if(S_pair_criteria & B_CRITERION)
3979      output<<"criterion B"<<endl;
3980    if(S_pair_criteria & SECOND_CRITERION)
3981      output<<"second criterion"<<endl;
3982    output<<endl;
3983
3984    print_flags(output);
3985    output<<endl;
3986  }
3987
3988  return 1;
3989}
3990
3991#endif // IP_ALGORITHMS_CC
Note: See TracBrowser for help on using the repository browser.