source: git/IntegerProgramming/IP_algorithms.cc @ 543931

spielwiese
Last change on this file since 543931 was 543931, checked in by Hans Schönemann <hannes@…>, 18 years ago
*hannes: sparc-cc git-svn-id: file:///usr/local/Singular/svn/trunk@9229 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 104.1 KB
Line 
1// IP_algorithms.cc
2
3#ifndef IP_ALGORITMS_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 short& version,
64                   const short& 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  short constraints;       // number of equality constraints
74  short 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 positve"<<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 positve"<<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  short 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 short& version,
352                            const short& 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  short constraints;       // number of equality constraints
362  short 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 positve"<<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 positve"<<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  short 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 short& version,
649                        const short& 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  short constraints;       // number of equality constraints
659  short 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 positve"<<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 positve"<<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  short 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 short& version,
938            const short& 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  short constraints;       // number of equality constraints
948  short 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 positve"<<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 positve"<<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  short 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 short& version,
1226                     const short& 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  short constraints;       // number of equality constraints
1236  short 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 positve"<<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 positve"<<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(short 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  short *sat_var;
1509  short 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(short 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  short 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 short& version,
1637                    const short& 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  short constraints;       // number of equality constraints
1647  short 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 positve"<<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 positve"<<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  short* F;
1825  short 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(short 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(short 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  short 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 short& version,
2003                             const short& 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  short constraints;       // number of equality constraints
2013  short 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 positve"<<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 positve"<<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(short _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  short 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  short problem_variables;
2413  short elimination_variables;
2414  short 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  short 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    short 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  short 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=new Integer[weighted_variables+elimination_variables];
3084
3085    for(short 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          delete[] right_hand;
3105          return 0;
3106        }
3107      }
3108
3109      // determine the exponent of the inversion variable, i.e.
3110      // - min{negative components of right_hand}.
3111      Integer min=0;
3112      for(i=weighted_variables;
3113          i<weighted_variables+elimination_variables-1;i++)
3114        if(right_hand[i]<min)
3115          min=right_hand[i];
3116
3117      // transform right_hand so that all components are nonnegative
3118      if(min<0)
3119        for(i=weighted_variables;
3120            i<weighted_variables+elimination_variables-1;i++)
3121          right_hand[i]-=min;
3122
3123      // set exponent of the inversion variable
3124      right_hand[weighted_variables+elimination_variables-1]=-min;
3125
3126      // construct binomial to reduce
3127      binomial to_reduce(weighted_variables+elimination_variables,right_hand);
3128
3129      // prepare time measurement
3130      clock_t start, end;
3131
3132      // reduce binomial
3133      start=clock();
3134      I.reduce(to_reduce,TRUE);
3135      end=clock();
3136
3137      // time measurement
3138      float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3139
3140      // output
3141
3142      output<<"right hand vector:"<<endl;
3143      for(i=weighted_variables;
3144          i<weighted_variables+elimination_variables-1;i++)
3145        output<<setw(6)<<right_hand[i]+min;
3146        // original vector
3147      output<<endl;
3148
3149      output<<"solvable:"<<endl;
3150
3151      BOOLEAN solvable=TRUE;
3152      for(i=weighted_variables;
3153          i<=weighted_variables+elimination_variables-1;i++)
3154        if(to_reduce[i]!=0)
3155        {
3156          solvable=FALSE;
3157          break;
3158        }
3159
3160      if(solvable==TRUE)
3161      {
3162        output<<"YES"<<endl;
3163        output<<"optimal solution:"<<endl;
3164        for(i=0;i<weighted_variables;i++)
3165          output<<setw(6)<<to_reduce[i];
3166        output<<endl;
3167      }
3168      else
3169        output<<"NO"<<endl;
3170
3171      output<<"computation time"<<endl;
3172      output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3173      delete[] right_hand;
3174    }
3175  }
3176
3177  else
3178    // Positive Conti-Traverso: vectors are read as right hand vectors
3179    // vector dimension = number of elimination variables
3180    if(!strcmp(algorithm,"pct"))
3181    {
3182      if(problem_variables!=elimination_variables)
3183      {
3184        cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3185          "vector dimension in first input file and number of variables in\n"
3186          "second input file do not match with respect to the\n"
3187          "Positive Conti-Traverso algorithm"<<endl;
3188        return 0;
3189      }
3190
3191      Integer *right_hand=new Integer[weighted_variables+elimination_variables];
3192      BOOLEAN error=FALSE;    // to test legality of right hand vectors
3193
3194      for(short k=0;k<instances;k++)
3195      {
3196        // at the beginning, the variables of interest are zero
3197        for(i=0;i<weighted_variables;i++)
3198          right_hand[i]=0;
3199
3200        // right hand vector is read from the input stream into the
3201        // elimination variables
3202        for(i=weighted_variables;
3203            i<weighted_variables+elimination_variables;i++)
3204        {
3205          problem>>right_hand[i];
3206
3207          if(!problem)
3208          {
3209            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3210              "input failure when reading right hand vector "<<k+1<<" from "
3211              "first input \nfile, this and all following right hand vectors "
3212              "will be ignored"<<endl;
3213            delete[] right_hand;
3214            return 0;
3215          }
3216
3217          if(right_hand[i]<0)
3218          {
3219            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3220              "right hand vectors with negative components cannot be handled\n"
3221              "by the Positive Conti-Traverso algorithm,\n"
3222              "right hand vector "<<k+1<<" will be ignored"<<endl;
3223            error=TRUE;
3224          }
3225        }
3226
3227        if(error==TRUE)
3228        {
3229          error=FALSE;
3230          continue;
3231          // for-loop
3232        }
3233
3234        // construct binomial to reduce
3235        binomial to_reduce(weighted_variables+elimination_variables,
3236                           right_hand);
3237
3238        // prepare time measurement
3239        clock_t start, end;
3240
3241        // reduce binomial
3242        start=clock();
3243        I.reduce(to_reduce,TRUE);
3244        end=clock();
3245
3246        // time measurement
3247        float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3248
3249        // output
3250
3251        output<<"right hand vector:"<<endl;
3252        for(i=weighted_variables;
3253            i<weighted_variables+elimination_variables;i++)
3254          output<<setw(6)<<right_hand[i];
3255        // original vector
3256        output<<endl;
3257
3258        output<<"solvable:"<<endl;
3259
3260        BOOLEAN solvable=TRUE;
3261        for(i=weighted_variables;
3262            i<weighted_variables+elimination_variables;i++)
3263          if(to_reduce[i]!=0)
3264          {
3265            solvable=FALSE;
3266            break;
3267          }
3268
3269        if(solvable==TRUE)
3270        {
3271          output<<"YES"<<endl;
3272          output<<"optimal solution:"<<endl;
3273          for(i=0;i<weighted_variables;i++)
3274            output<<setw(6)<<to_reduce[i];
3275          output<<endl;
3276        }
3277        else
3278          output<<"NO"<<endl;
3279
3280        output<<"computation time"<<endl;
3281        output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3282        delete[] right_hand;
3283      }
3284    }
3285
3286    else
3287      // other algorithms: vectors are read as initial solutions
3288      // vector dimension = number of weighted variables
3289    {
3290      if(problem_variables!=weighted_variables)
3291      {
3292        cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3293          "vector dimension in first input file and number of variables in\n"
3294          "second input file do not match with respect to the\n"
3295          "chosen algorithm"<<endl;
3296        return 0;
3297      }
3298
3299      Integer *initial_solution=new Integer[weighted_variables];
3300
3301      for(short k=0;k<instances;k++)
3302      {
3303        // initial solution vector is read from the input stream into the
3304        // elimination variables
3305        for(i=0;i<weighted_variables;i++)
3306        {
3307          problem>>initial_solution[i];
3308
3309          if(!problem)
3310          {
3311            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3312              "input failure when reading right hand vector "<<k+1<<" from "
3313              "first input \nfile, this and all following right hand vectors "
3314              "will be ignored"<<endl;
3315            delete[] initial_solution;
3316            return 0;
3317          }
3318
3319          if(initial_solution[i]<0)
3320            cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
3321              "initial solution vectors should be nonnegative"<<endl;
3322        }
3323
3324        // construct binomial to reduce
3325        binomial to_reduce(weighted_variables,initial_solution);
3326
3327        // prepare time measurement
3328        clock_t start, end;
3329
3330        // reduce binomial
3331        start=clock();
3332        I.reduce(to_reduce,TRUE);
3333        end=clock();
3334
3335        // time measurement
3336        float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3337
3338        // output
3339
3340        output<<"initial solution vector:"<<endl;
3341        for(i=0;i<weighted_variables;i++)
3342          output<<setw(6)<<initial_solution[i];
3343        // original vector
3344        output<<endl;
3345
3346        output<<"optimal solution:"<<endl;
3347        for(i=0;i<weighted_variables;i++)
3348          output<<setw(6)<<to_reduce[i];
3349        output<<endl;
3350
3351        output<<"computation time"<<endl;
3352        output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3353      }
3354      delete[] initial_solution;
3355    }
3356
3357  return 1;
3358
3359}
3360
3361
3362
3363////////////////////////////////////////////////////////////////////////////
3364////////////////////////////////////////////////////////////////////////////
3365////////////////////////////////////////////////////////////////////////////
3366
3367
3368
3369
3370int change_cost(INPUT_FILE GROEBNER, INPUT_FILE NEW_COST,
3371                const short& version,
3372                const short& S_pair_criteria,
3373                const float& interred_percentage,
3374                const BOOLEAN& verbose)
3375{
3376
3377  char format_string[128];
3378  short elimination_variables;
3379  short weighted_variables;
3380  char elimination_refinement[128];
3381  char weighted_refinement[128];
3382  short new_variables;
3383  char algorithm[128];
3384  long old_size;
3385
3386  ifstream old(GROEBNER);
3387  ifstream _new(NEW_COST);
3388
3389  // verifie existence of files
3390
3391  if(!old)
3392  {
3393    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3394      "cannot read from first input file, possibly not found"<<endl;
3395    return 0;
3396  }
3397
3398  if(!_new)
3399  {
3400    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3401      "cannot read from second input file, possibly not found"<<endl;
3402    return 0;
3403  }
3404
3405
3406// read first part of GROEBNER file (until term ordering reached)
3407
3408  // read format specification
3409
3410  old>>format_string;
3411
3412  if(!old)
3413  {
3414    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3415      "input failure when reading format specification of first input file,\n"
3416      "input format not accepted"<<endl;
3417    return 0;
3418  }
3419
3420  if(strcmp(format_string,"GROEBNER"))
3421  {
3422    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3423      "first input file has suspicious format"<<endl;
3424  }
3425
3426  // read algorithm
3427
3428  old>>format_string;
3429
3430  if(!old)
3431  {
3432    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3433      "input failure before reading algorithm from first input file,\n"
3434      "input format not accepted"<<endl;
3435    return 0;
3436  }
3437
3438  if(strcmp(format_string,"computed"))
3439  {
3440    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3441      "first input file has suspicious format"<<endl;
3442  }
3443
3444  old>>format_string;
3445
3446  if(!old)
3447  {
3448    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3449      "input failure before reading algorithm from first input file,\n"
3450      "input format not accepted"<<endl;
3451    return 0;
3452  }
3453
3454  if(strcmp(format_string,"with"))
3455  {
3456    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3457      "first input file has suspicious format"<<endl;
3458  }
3459
3460  old>>format_string;
3461
3462  if(!old)
3463  {
3464    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3465      "input failure before reading algorithm from first input file,\n"
3466      "input format not accepted"<<endl;
3467    return 0;
3468  }
3469
3470  if(strcmp(format_string,"algorithm:"))
3471  {
3472    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3473      "first input file has suspicious format"<<endl;
3474  }
3475
3476  old>>algorithm;
3477
3478  if(!old)
3479  {
3480    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3481      "input failure when reading algorithm from first input file,\n"
3482      "input format not accepted"<<endl;
3483    return 0;
3484  }
3485
3486  if(strcmp(algorithm,"ct") && strcmp(algorithm,"pct") &&
3487     strcmp(algorithm,"ect") && strcmp(algorithm,"pt") &&
3488     strcmp(algorithm,"hs") && strcmp(algorithm,"du")
3489     && strcmp(algorithm,"blr"))
3490  {
3491    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3492      "first input file computed with unknown algorithm"<<endl;
3493  }
3494
3495  // override optional lines
3496
3497  do
3498  {
3499    old>>format_string;
3500
3501    if(!old)
3502    {
3503      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3504        "input failure before reading term ordering from first \n"
3505        "input file, input format not accepted"<<endl;
3506      return 0;
3507    }
3508  }
3509  while(strcmp(format_string,"term"));
3510
3511  // read term ordering
3512
3513  old>>format_string;
3514
3515  if(!old)
3516  {
3517    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3518      "input failure before reading term ordering \n"
3519      "from first input file, input format not accepted"<<endl;
3520    return 0;
3521  }
3522
3523  if(strcmp(format_string,"ordering:"))
3524  {
3525    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3526      "first input file has suspicious format"<<endl;
3527  }
3528
3529  old>>format_string;
3530
3531  if(!old)
3532  {
3533    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3534      "input failure when reading term ordering \n"
3535      "from first input file, input format not accepted"<<endl;
3536    return 0;
3537  }
3538
3539  if(strcmp(format_string,"elimination"))
3540  {
3541    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3542      "first input file has suspicious format"<<endl;
3543  }
3544
3545  old>>format_string;
3546
3547  if(!old)
3548  {
3549    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3550      "input failure when reading term ordering \n"
3551      "from first input file, input format not accepted"<<endl;
3552    return 0;
3553  }
3554
3555  if(strcmp(format_string,"block"))
3556  {
3557    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3558      "first input file has suspicious format"<<endl;
3559  }
3560
3561  old>>elimination_variables;
3562
3563  if(!old)
3564  {
3565    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3566      "input failure when reading term ordering \n"
3567      "from first input file, input format not accepted"<<endl;
3568    return 0;
3569  }
3570
3571  if(elimination_variables<0)
3572  {
3573    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3574      "number of elimination variables in first input file must be "
3575      "nonnegative"<<endl;
3576    return 0;
3577  }
3578
3579  if(elimination_variables>0)
3580  {
3581    old>>elimination_refinement;
3582
3583    if(!old)
3584    {
3585      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3586        "input failure when reading term ordering \n"
3587        "from first input file, input format not accepted"<<endl;
3588      return 0;
3589    }
3590
3591    if(strcmp(elimination_refinement,"LEX") &&
3592       strcmp(elimination_refinement,"DEG_LEX") &&
3593       strcmp(elimination_refinement,"DEG_REV_LEX"))
3594    {
3595      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3596        "unknown elimination ordering in first input file"<<endl;
3597      return 0;
3598    }
3599  }
3600
3601  old>>format_string;
3602
3603  if(!old)
3604  {
3605    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3606      "input failure when reading term ordering \n"
3607      "from first input file, input format not accepted"<<endl;
3608    return 0;
3609  }
3610
3611  if(strcmp(format_string,"weighted"))
3612  {
3613    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3614      "first input file has suspicious format"<<endl;
3615  }
3616
3617  old>>format_string;
3618
3619  if(!old)
3620  {
3621    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3622      "input failure when reading term ordering \n"
3623      "from first input file, input format not accepted"<<endl;
3624    return 0;
3625  }
3626
3627  if(strcmp(format_string,"block"))
3628  {
3629    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3630      "first input file has suspicious format"<<endl;
3631  }
3632
3633  old>>weighted_variables;
3634
3635  if(!old)
3636  {
3637    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3638      "input failure when reading term ordering \n"
3639      "from first input file, input format not accepted"<<endl;
3640    return 0;
3641  }
3642
3643  if(weighted_variables<=0)
3644  {
3645    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3646      "number of weighted variables in first input file must be "
3647      "positive"<<endl;
3648    return 0;
3649  }
3650
3651  old>>weighted_refinement;
3652
3653  if(!old)
3654  {
3655    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3656      "input failure when reading term ordering \n"
3657      "from first input file, input format not accepted"<<endl;
3658    return 0;
3659  }
3660
3661  if(strcmp(weighted_refinement,"W_LEX") &&
3662     strcmp(weighted_refinement,"W_REV_LEX") &&
3663     strcmp(weighted_refinement,"W_DEG_LEX") &&
3664     strcmp(weighted_refinement,"W_DEG_REV_LEX"))
3665  {
3666    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3667      "unknown weighted ordering in first input file"<<endl;
3668    return 0;
3669  }
3670
3671// read NEW_COST file
3672
3673  // read format specification
3674
3675  _new>>format_string;
3676
3677  if(!_new)
3678  {
3679    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3680      "input failure when reading format specification\n"
3681      "from second input file, input format not accepted"<<endl;
3682    return 0;
3683  }
3684
3685  if(strcmp(format_string,"MATRIX") && strcmp(format_string,"NEW_COST"))
3686  {
3687    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3688      "second input file has suspicious format"<<endl;
3689  }
3690
3691  // read number of variables
3692
3693  _new>>format_string;
3694
3695  if(!_new)
3696  {
3697    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3698      "input failure before reading number of variables \n"
3699      "from second input file, input format not accepted"<<endl;
3700    return 0;
3701  }
3702
3703  if(strcmp(format_string,"columns:") && strcmp(format_string,"variables:"))
3704    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3705      "second input file has suspicious format"<<endl;
3706
3707  _new>>new_variables;
3708
3709  if(!_new)
3710  {
3711    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3712      "input failure when reading number of variables \n"
3713      "from second input file, input format not accepted"<<endl;
3714    return 0;
3715  }
3716
3717  if(new_variables<=0)
3718  {
3719    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3720      "number of variables in second input file must be positve"<<endl;
3721    return 0;
3722  }
3723
3724  // Now we can verifie consistency of both files with respect to the number
3725  // of weighted variables:
3726
3727  if(weighted_variables!=new_variables)
3728  {
3729    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3730      "number of variables in first and second input file do not match"<<endl;
3731    return 0;
3732  }
3733
3734  // read term ordering
3735
3736  _new>>format_string;
3737
3738  if(!_new)
3739  {
3740    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3741      "input failure before reading new cost vector from second input file,\n"
3742      "input format not accepted"<<endl;
3743    return 0;
3744  }
3745
3746  if(strcmp(format_string,"cost"))
3747    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3748      "second input file has suspicious format"<<endl;
3749
3750  _new>>format_string;
3751
3752  if(!_new)
3753  {
3754    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3755      "input failure before reading new cost vector from second input file,\n"
3756      "input format not accepted"<<endl;
3757    return 0;
3758  }
3759
3760  if(strcmp(format_string,"vector:"))
3761    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3762      "second input file has suspicious format"<<endl;
3763
3764  // the term ordering to refine the weight is taken to be the same as that
3765  // for the old Groebner basis
3766  short weighted_ref;
3767  if(!strcmp(weighted_refinement,"W_LEX"))
3768    weighted_ref=W_LEX;
3769  if(!strcmp(weighted_refinement,"W_REV_LEX"))
3770    weighted_ref=W_REV_LEX;
3771  if(!strcmp(weighted_refinement,"W_DEG_LEX"))
3772    weighted_ref=W_DEG_LEX;
3773  if(!strcmp(weighted_refinement,"W_DEG_REV_LEX"))
3774    weighted_ref=W_DEG_REV_LEX;
3775
3776  term_ordering w(weighted_variables,_new,weighted_ref);
3777
3778  if(w.error_status()<0)
3779  {
3780    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3781      "input failure when reading new cost vector from second input file,\n"
3782      "input format not accepted"<<endl;
3783    return 0;
3784  }
3785
3786  if(w.is_nonnegative()==FALSE)
3787  {
3788    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3789      "cost vectors with negative components are not supported"<<endl;
3790    return 0;
3791  }
3792
3793  if(elimination_variables>0)
3794  {
3795    short elimination_ref;
3796    if(!strcmp(elimination_refinement,"LEX"))
3797      elimination_ref=LEX;
3798    if(!strcmp(elimination_refinement,"DEG_LEX"))
3799      elimination_ref=DEG_LEX;
3800    if(!strcmp(elimination_refinement,"DEG_REV_LEX"))
3801      elimination_ref=DEG_REV_LEX;
3802    w.convert_to_elimination_ordering(elimination_variables,elimination_ref);
3803
3804    if(w.error_status()<0)
3805    {
3806      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3807        "input failure when reading new cost vector from second input file,\n"
3808        "input format not accepted"<<endl;
3809      return 0;
3810    }
3811  }
3812
3813// read second part of the GROEBNER file
3814
3815  // override old weight vector
3816
3817  do
3818  {
3819    old>>format_string;
3820
3821    if(!old)
3822    {
3823      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3824        "input failure before reading number of ideal generators \n"
3825        "from first input file, input format not accepted"<<endl;
3826      return 0;
3827    }
3828  }
3829  while(strcmp(format_string,"size:"));
3830
3831  // read old Groebner basis
3832
3833  old>>old_size;
3834
3835  if(!old)
3836  {
3837    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3838      "input failure when reading number of ideal generators \n"
3839      "from first input file, input format not accepted"<<endl;
3840    return 0;
3841  }
3842
3843  if(old_size<=0)
3844  {
3845    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3846      "ideal in first input file is corrupt"<<endl;
3847    return 0;
3848  }
3849
3850  old>>format_string;
3851
3852  if(!old)
3853  {
3854    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3855      "input failure before reading ideal generators \n"
3856      "from first input file, input format not accepted"<<endl;
3857    return 0;
3858  }
3859
3860  if(strcmp(format_string,"Groebner"))
3861  {
3862    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3863      "first input file has suspicious format"<<endl;
3864  }
3865
3866  old>>format_string;
3867
3868  if(!old)
3869  {
3870    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3871      "input failure before reading ideal generators \n"
3872      "from first input file, input format not accepted"<<endl;
3873    return 0;
3874  }
3875
3876  if(strcmp(format_string,"basis:"))
3877  {
3878    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3879      "first input file has suspicious format"<<endl;
3880  }
3881
3882  // read ideal generators from first input file, already with respect to
3883  // the new term ordering
3884  ideal I(old,w,old_size);
3885
3886  if(!old)
3887  {
3888    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3889      "input failure when reading ideal generators from first input file,\n"
3890      "input format not accepted."<<endl;
3891    return 0;
3892  }
3893
3894  if(I.error_status()<0)
3895  {
3896    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3897      "cannot compute with corrupt ideal\n"<<endl;
3898    return 0;
3899  }
3900
3901
3902///////////////////////// computation ////////////////////////////////////////
3903
3904  // prepare time measurement
3905  clock_t start, end;
3906
3907  // compute new Groebner basis
3908  start=clock();
3909  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
3910  end=clock();
3911
3912  // time measurement
3913  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3914
3915
3916///////////////////////// output ////////////////////////////////////////////
3917
3918  // create output file
3919
3920  char NEW_GROEBNER[128];
3921
3922  short i=0;
3923  while(NEW_COST[i]!='\0' && NEW_COST[i]!='.')
3924  {
3925    NEW_GROEBNER[i]=NEW_COST[i];
3926    i++;
3927  }
3928  NEW_GROEBNER[i]='\0';
3929  strcat(NEW_GROEBNER,".GB.");
3930  strcat(NEW_GROEBNER,algorithm);
3931
3932  ofstream output(NEW_GROEBNER);
3933
3934  // format output file
3935
3936  output.flags(output.flags()|ios::fixed);
3937  // output of fixed point numbers
3938
3939  output<<"GROEBNER"<<endl<<endl;
3940
3941  output<<"computed with algorithm:"<<endl;
3942  output<<algorithm<<endl;
3943  output<<"from file(s):"<<endl;
3944  output<<GROEBNER<<", "<<NEW_COST<<endl;
3945  output<<"computation time"<<endl;
3946  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3947
3948  output<<"term ordering:"<<endl;
3949  output<<"elimination block"<<endl;
3950  // elimination variables
3951  output<<elimination_variables<<endl;
3952  if(elimination_variables>0)
3953    output<<elimination_refinement<<endl;
3954  output<<"weighted block"<<endl;
3955  // weighted variables (>0)
3956  output<<weighted_variables<<endl;
3957  output<<weighted_refinement<<endl;
3958  w.format_print_weight_vector(output);
3959
3960  output<<"size:"<<endl;
3961  output<<I.number_of_generators()<<endl<<endl;
3962
3963  output<<"Groebner basis:"<<endl;
3964  I.format_print(output);
3965  output<<endl;
3966
3967  if(verbose==TRUE)
3968  {
3969    output<<"settings for the Buchberger algorithm:"<<endl;
3970
3971    output<<"version:"<<endl;
3972    if(version==0)
3973      output<<"1a"<<endl;
3974    else
3975      output<<version<<endl;
3976
3977    output<<"S-pair criteria:"<<endl;
3978    if(S_pair_criteria & REL_PRIMENESS)
3979      output<<"relatively prime leading terms"<<endl;
3980    if(S_pair_criteria & M_CRITERION)
3981      output<<"criterion M"<<endl;
3982    if(S_pair_criteria & F_CRITERION)
3983      output<<"criterion F"<<endl;
3984    if(S_pair_criteria & B_CRITERION)
3985      output<<"criterion B"<<endl;
3986    if(S_pair_criteria & SECOND_CRITERION)
3987      output<<"second criterion"<<endl;
3988    output<<endl;
3989
3990    print_flags(output);
3991    output<<endl;
3992  }
3993
3994  return 1;
3995}
3996
3997#endif // IP_ALGORITHMS_CC
Note: See TracBrowser for help on using the repository browser.