source: git/IntegerProgramming/IP_algorithms.cc @ 27e935

spielwiese
Last change on this file since 27e935 was 6ba162, checked in by Hans Schönemann <hannes@…>, 24 years ago
This commit was generated by cvs2svn to compensate for changes in r4282, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@4283 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 104.0 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=1,
64                   const short& S_pair_criteria=11,
65                   const float& interred_percentage=12.0,
66                   const BOOLEAN& verbose=FALSE)
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=1,
352                            const short& S_pair_criteria=11,
353                            const float& interred_percentage=12.0,
354                            const BOOLEAN& verbose=FALSE)
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=1,
649                        const short& S_pair_criteria=11,
650                        const float& interred_percentage=12.0,
651                        const BOOLEAN& verbose=FALSE)
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=1,
938            const short& S_pair_criteria=11,
939            const float& interred_percentage=12.0,
940            const BOOLEAN& verbose=FALSE)
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=1,
1226                     const short& S_pair_criteria=11,
1227                     const float& interred_percentage=12.0,
1228                     const BOOLEAN& verbose=FALSE)
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=1,
1637                    const short& S_pair_criteria=11,
1638                    const float& interred_percentage=12.0,
1639                    const BOOLEAN& verbose=FALSE)
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=1,
2003                             const short& S_pair_criteria=11,
2004                             const float& interred_percentage=12.0,
2005                             const BOOLEAN& verbose=FALSE)
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///////////////////////// computation ////////////////////////////////////////
2281
2282  // prepare time measurement
2283  clock_t start, end;
2284
2285  // construct homogenous term ordering
2286  term_ordering w(variables, hom_grad, W_REV_LEX, HOMOGENEOUS);
2287
2288  delete[] hom_grad;
2289
2290  // create toric ideal
2291  ideal I(A,w,BIGATTI_LASCALA_ROBBIANO);
2292
2293  // compute the standard basis
2294  start=clock();
2295  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
2296
2297  // now we have a generating system
2298  // to perform the substitution of the auxiliary variable U by the saturation
2299  // variables:
2300  // make U the revlex most expensive variable by swapping with the first,
2301  // recompute the Groebner basis, undo the swap
2302  I.swap_variables(0,variables);
2303  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
2304  I.swap_variables(0,variables);
2305
2306  I.pseudo_eliminate();
2307  // eliminate the auxiliary variable
2308
2309  // Now the ideal is saturated. Compute the Groebner basis
2310  // with respect to the term ordering induced by the objective function.
2311  I.change_term_ordering_to(c);
2312  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
2313
2314  end=clock();
2315
2316  // time measurement
2317  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
2318
2319
2320///////////////////////// output ////////////////////////////////////////////
2321
2322  // create output file
2323
2324  char GROEBNER[128];
2325  short i=0;
2326  while(MATRIX[i]!='\0' && MATRIX[i]!='.')
2327  {
2328    GROEBNER[i]=MATRIX[i];
2329    i++;
2330  }
2331  GROEBNER[i]='\0';
2332  strcat(GROEBNER,".GB.blr");
2333
2334  ofstream output(GROEBNER);
2335
2336  // format output file
2337
2338  output.flags(output.flags()|ios::fixed);
2339  // output of fixed point numbers
2340
2341  output<<"GROEBNER"<<endl<<endl;
2342
2343  output<<"computed with algorithm:"<<endl;
2344  output<<"blr"<<endl;
2345  output<<"from file(s):"<<endl;
2346  output<<MATRIX<<endl;
2347  output<<"computation time"<<endl;
2348  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
2349
2350  output<<"term ordering:"<<endl;
2351  output<<"elimination block"<<endl;
2352  // elimination variables (00)
2353  output<<0<<endl;
2354  output<<"weighted block"<<endl;
2355  // weighted variables (>0)
2356  output<<variables<<endl;
2357  output<<"W_LEX"<<endl;
2358  c.format_print_weight_vector(output);
2359
2360  output<<"size:"<<endl;
2361  output<<I.number_of_generators()<<endl<<endl;
2362
2363  output<<"Groebner basis:"<<endl;
2364  I.format_print(output);
2365  output<<endl;
2366
2367  if(verbose==TRUE)
2368  {
2369    output<<"settings for the Buchberger algorithm:"<<endl;
2370
2371    output<<"version:"<<endl;
2372    if(version==0)
2373      output<<"1a"<<endl;
2374    else
2375      output<<version<<endl;
2376
2377    output<<"S-pair criteria:"<<endl;
2378    if(S_pair_criteria & REL_PRIMENESS)
2379      output<<"relatively prime leading terms"<<endl;
2380    if(S_pair_criteria & M_CRITERION)
2381      output<<"criterion M"<<endl;
2382    if(S_pair_criteria & F_CRITERION)
2383      output<<"criterion F"<<endl;
2384    if(S_pair_criteria & B_CRITERION)
2385      output<<"criterion B"<<endl;
2386    if(S_pair_criteria & SECOND_CRITERION)
2387      output<<"second criterion"<<endl;
2388    output<<endl;
2389
2390    print_flags(output);
2391    output<<endl;
2392  }
2393
2394  return 1;
2395}
2396
2397
2398
2399
2400////////////////////////////////////////////////////////////////////////////
2401////////////////////////////////////////////////////////////////////////////
2402////////////////////////////////////////////////////////////////////////////
2403
2404
2405
2406
2407int solve(INPUT_FILE PROBLEM, INPUT_FILE GROEBNER)
2408{
2409
2410  char format_string[128];
2411  short problem_variables;
2412  short elimination_variables;
2413  short weighted_variables;
2414  char elimination_refinement[128];
2415  char weighted_refinement[128];
2416  char algorithm[128];
2417  long size;
2418  long instances;
2419
2420  ifstream problem(PROBLEM);
2421  ifstream groebner(GROEBNER);
2422
2423  // verfifie existence of files
2424
2425  if(!problem)
2426  {
2427    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2428      "cannot read from first input file, possibly not found"<<endl;
2429    return 0;
2430  }
2431
2432  if(!groebner)
2433  {
2434    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2435      "cannot read from second input file, possibly not found"<<endl;
2436    return 0;
2437  }
2438
2439// read GROEBNER file
2440
2441  // read format specification
2442
2443  groebner>>format_string;
2444
2445  if(!groebner)
2446  {
2447    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2448      "input failure when reading format specification of second input file,\n"
2449      "input format not accepted"<<endl;
2450    return 0;
2451  }
2452
2453  if(strcmp(format_string,"GROEBNER"))
2454    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2455      "second input file has suspicious format"<<endl;
2456
2457  // read algorithm
2458
2459  groebner>>format_string;
2460
2461  if(!groebner)
2462  {
2463    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2464      "input failure before reading algorithm from second input file,\n"
2465      "input format not accepted"<<endl;
2466    return 0;
2467  }
2468
2469  if(strcmp(format_string,"computed"))
2470    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2471      "second input file has suspicious format"<<endl;
2472
2473  groebner>>format_string;
2474
2475  if(!groebner)
2476  {
2477    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2478      "input failure before reading algorithm from second input file,\n"
2479      "input format not accepted"<<endl;
2480    return 0;
2481  }
2482
2483  if(strcmp(format_string,"with"))
2484    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2485      "second input file has suspicious format"<<endl;
2486
2487  groebner>>format_string;
2488
2489  if(!groebner)
2490  {
2491    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2492      "input failure before reading algorithm from second input file,\n"
2493      "input format not accepted"<<endl;
2494    return 0;
2495  }
2496
2497  if(strcmp(format_string,"algorithm:"))
2498    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2499      "second input file has suspicious format"<<endl;
2500
2501  groebner>>algorithm;
2502
2503  if(!groebner)
2504  {
2505    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2506      "input failure when reading algorithm from second input file,\n"
2507      "input format not accepted"<<endl;
2508    return 0;
2509  }
2510
2511  if(strcmp(algorithm,"ct") && strcmp(algorithm,"pct") &&
2512     strcmp(algorithm,"ect") && strcmp(algorithm,"pt") &&
2513     strcmp(algorithm,"hs") && strcmp(algorithm,"du")
2514     && strcmp(algorithm,"blr"))
2515    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2516      "second input file computed with unknown algorithm"<<endl;
2517
2518  // override optional lines
2519
2520  do
2521  {
2522    groebner>>format_string;
2523
2524    if(!groebner)
2525    {
2526      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2527        "input failure before reading term ordering from second \n"
2528        "input file, input format not accepted"<<endl;
2529      return 0;
2530    }
2531  }
2532  while(strcmp(format_string,"term"));
2533
2534  // read term ordering
2535
2536  groebner>>format_string;
2537
2538  if(!groebner)
2539  {
2540    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2541      "input failure before reading term ordering \n"
2542      "from second input file, input format not accepted"<<endl;
2543    return 0;
2544  }
2545
2546  if(strcmp(format_string,"ordering:"))
2547    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2548      "second input file has suspicious format"<<endl;
2549
2550  groebner>>format_string;
2551
2552  if(!groebner)
2553  {
2554    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2555      "input failure when reading term ordering \n"
2556      "from second input file, input format not accepted"<<endl;
2557    return 0;
2558  }
2559
2560  if(strcmp(format_string,"elimination"))
2561    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2562      "second input file has suspicious format"<<endl;
2563
2564  groebner>>format_string;
2565
2566  if(!groebner)
2567  {
2568    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2569      "input failure when reading term ordering \n"
2570      "from second input file, input format not accepted"<<endl;
2571    return 0;
2572  }
2573
2574  if(strcmp(format_string,"block"))
2575    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2576      "second input file has suspicious format"<<endl;
2577
2578  groebner>>elimination_variables;
2579
2580  if(!groebner)
2581  {
2582    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2583      "input failure when reading term ordering \n"
2584      "from second input file, input format not accepted"<<endl;
2585    return 0;
2586  }
2587
2588  if(elimination_variables<0)
2589  {
2590    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2591      "number of elimination variables in second input file must be "
2592      "nonnegative"<<endl;
2593    return 0;
2594  }
2595
2596  if(elimination_variables>0)
2597  {
2598    groebner>>elimination_refinement;
2599
2600    if(!groebner)
2601    {
2602      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2603        "input failure when reading term ordering \n"
2604        "from second input file, input format not accepted"<<endl;
2605      return 0;
2606    }
2607
2608    if(strcmp(elimination_refinement,"LEX") &&
2609       strcmp(elimination_refinement,"DEG_LEX") &&
2610       strcmp(elimination_refinement,"DEG_REV_LEX"))
2611    {
2612      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2613        "unknown elimination ordering in second input file"<<endl;
2614      return 0;
2615    }
2616  }
2617
2618  groebner>>format_string;
2619
2620  if(!groebner)
2621  {
2622    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2623      "input failure when reading term ordering \n"
2624      "from second input file, input format not accepted"<<endl;
2625    return 0;
2626  }
2627
2628  if(strcmp(format_string,"weighted"))
2629    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2630      "second input file has suspicious format"<<endl;
2631
2632  groebner>>format_string;
2633
2634  if(!groebner)
2635  {
2636    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2637      "input failure when reading term ordering \n"
2638      "from second input file, input format not accepted"<<endl;
2639    return 0;
2640  }
2641
2642  if(strcmp(format_string,"block"))
2643    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2644      "second input file has suspicious format"<<endl;
2645
2646  groebner>>weighted_variables;
2647
2648  if(!groebner)
2649  {
2650    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2651      "input failure when reading term ordering \n"
2652      "from second input file, input format not accepted"<<endl;
2653    return 0;
2654  }
2655
2656  if(weighted_variables<=0)
2657  {
2658    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2659      "number of weighted variables in second input file must be "
2660      "positive"<<endl;
2661    return 0;
2662  }
2663
2664  groebner>>weighted_refinement;
2665
2666  if(!groebner)
2667  {
2668    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2669      "input failure when reading term ordering \n"
2670      "from second input file, input format not accepted"<<endl;
2671    return 0;
2672  }
2673
2674  if(strcmp(weighted_refinement,"W_LEX") &&
2675     strcmp(weighted_refinement,"W_REV_LEX") &&
2676     strcmp(weighted_refinement,"W_DEG_LEX") &&
2677     strcmp(weighted_refinement,"W_DEG_REV_LEX"))
2678  {
2679    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2680      "unknown weighted ordering in second input file"<<endl;
2681    return 0;
2682  }
2683
2684  short weighted_ref;
2685  if(!strcmp(weighted_refinement,"W_LEX"))
2686    weighted_ref=W_LEX;
2687  if(!strcmp(weighted_refinement,"W_REV_LEX"))
2688    weighted_ref=W_REV_LEX;
2689  if(!strcmp(weighted_refinement,"W_DEG_LEX"))
2690    weighted_ref=W_DEG_LEX;
2691  if(!strcmp(weighted_refinement,"W_DEG_REV_LEX"))
2692    weighted_ref=W_DEG_REV_LEX;
2693
2694  term_ordering w(weighted_variables,groebner,weighted_ref);
2695
2696  if(w.error_status()<0)
2697  {
2698    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2699      "input failure when reading new cost vector from second input file,\n"
2700      "input format not accepted"<<endl;
2701    return 0;
2702  }
2703
2704  if(w.is_nonnegative()==FALSE)
2705  {
2706    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2707      "cost vectors with negative components are not supported"<<endl;
2708    return 0;
2709  }
2710
2711  if(elimination_variables>0)
2712  {
2713    short elimination_ref;
2714    if(!strcmp(elimination_refinement,"LEX"))
2715      elimination_ref=LEX;
2716    if(!strcmp(elimination_refinement,"DEG_LEX"))
2717      elimination_ref=DEG_LEX;
2718    if(!strcmp(elimination_refinement,"DEG_REV_LEX"))
2719      elimination_ref=DEG_REV_LEX;
2720
2721    w.convert_to_elimination_ordering(elimination_variables,elimination_ref);
2722
2723    if(w.error_status()<0)
2724    {
2725      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2726        "input failure when reading new cost vector from second input file,\n"
2727        "input format not accepted"<<endl;
2728      return 0;
2729    }
2730  }
2731
2732  // read ideal
2733
2734  groebner>>format_string;
2735
2736  if(!groebner)
2737  {
2738    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2739      "input failure before reading number of ideal generators \n"
2740      "from second input file, input format not accepted"<<endl;
2741    return 0;
2742  }
2743
2744  if(strcmp(format_string,"size:"))
2745    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2746      "second input file has suspicious format"<<endl;
2747
2748  groebner>>size;
2749
2750  if(!groebner)
2751  {
2752    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2753      "input failure when reading number of ideal generators \n"
2754      "from second input file, input format not accepted"<<endl;
2755    return 0;
2756  }
2757
2758  if(size<0)
2759  {
2760    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2761      "ideal in second input file is corrupt"<<endl;
2762    return 0;
2763  }
2764
2765  groebner>>format_string;
2766
2767  if(!groebner)
2768  {
2769    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2770      "input failure before reading ideal generators \n"
2771      "from second input file, input format not accepted"<<endl;
2772    return 0;
2773  }
2774
2775  if(strcmp(format_string,"Groebner"))
2776    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2777      "second input file has suspicious format"<<endl;
2778
2779  groebner>>format_string;
2780
2781  if(!groebner)
2782  {
2783    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2784      "input failure before reading ideal generators \n"
2785      "from second input file, input format not accepted"<<endl;
2786    return 0;
2787  }
2788
2789  if(strcmp(format_string,"basis:"))
2790    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2791      "second input file has suspicious format"<<endl;
2792
2793  ideal I(groebner,w,size);
2794
2795  if(!groebner)
2796  {
2797    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2798      "input failure when reading ideal generators from second input file,\n"
2799      "input format not accepted."<<endl;
2800    return 0;
2801  }
2802
2803  if(I.error_status()<0)
2804  {
2805    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2806      "cannot compute with corrupt ideal\n"<<endl;
2807    return 0;
2808  }
2809
2810// read PROBLEM file
2811
2812  // read format specification
2813
2814  problem>>format_string;
2815
2816  if(!problem)
2817  {
2818    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2819      "input failure when reading format specification of first input file,\n"
2820      "input format not accepted"<<endl;
2821    return 0;
2822  }
2823
2824  if(strcmp(format_string,"PROBLEM"))
2825    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2826      "first input file has suspicious format"<<endl;
2827
2828  // read vector dimension
2829
2830  problem>>format_string;
2831
2832  if(!problem)
2833  {
2834    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2835      "input failure before reading vector dimension from first input file,\n"
2836      "input format not accepted"<<endl;
2837    return 0;
2838  }
2839
2840  if(strcmp(format_string,"vector"))
2841    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2842      "first input file has suspicious format"<<endl;
2843
2844  problem>>format_string;
2845
2846  if(!problem)
2847  {
2848    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2849      "input failure before reading vector dimension from first input file,\n"
2850      "input format not accepted"<<endl;
2851    return 0;
2852  }
2853
2854  if(strcmp(format_string,"size:"))
2855    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2856      "first input file has suspicious format"<<endl;
2857
2858  problem>>problem_variables;
2859
2860  if(!problem)
2861  {
2862    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2863      "input failure when reading vector dimension from first input file,\n"
2864      "input format not accepted"<<endl;
2865    return 0;
2866  }
2867
2868  if(problem_variables<=0)
2869  {
2870    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2871      "vector dimension in first input file must be positive"<<endl;
2872    return 0;
2873  }
2874
2875  // consistency with respect to the number of variables is checked later
2876
2877  // read number of instances
2878
2879  problem>>format_string;
2880
2881  if(!problem)
2882  {
2883    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2884      "input failure before reading number of instances from first input file,"
2885      "\n"
2886      "input format not accepted"<<endl;
2887    return 0;
2888  }
2889
2890  if(strcmp(format_string,"number"))
2891    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2892      "first input file has suspicious format"<<endl;
2893
2894  problem>>format_string;
2895
2896  if(!problem)
2897  {
2898    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2899      "input failure before reading number of instances from first input file,"
2900      "\n"
2901      "input format not accepted"<<endl;
2902    return 0;
2903  }
2904
2905  if(strcmp(format_string,"of"))
2906    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2907      "first input file has suspicious format"<<endl;
2908
2909  problem>>format_string;
2910
2911  if(!problem)
2912  {
2913    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2914      "input failure before reading number of instances from first input file,"
2915      "\n"
2916      "input format not accepted"<<endl;
2917    return 0;
2918  }
2919
2920  if(strcmp(format_string,"instances:"))
2921    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2922      "first input file has suspicious format"<<endl;
2923
2924  problem>>instances;
2925
2926  if(!problem)
2927  {
2928    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2929      "input failure when reading number of instances from first input file,\n"
2930      "input format not accepted"<<endl;
2931    return 0;
2932  }
2933
2934  if(instances<=0)
2935  {
2936    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2937      "number of instances is <1, no output file created"<<endl;
2938    return 1;
2939    // no error
2940  }
2941
2942  // read problem vectors (first part)
2943
2944  problem>>format_string;
2945
2946  if(!problem)
2947  {
2948    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2949      "input failure before reading right hand / initial solution vectors \n"
2950      "from first input file, input format not accepted"<<endl;
2951    return 0;
2952  }
2953
2954  if(strcmp(format_string,"right"))
2955    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2956      "first input file has suspicious format"<<endl;
2957
2958  problem>>format_string;
2959
2960  if(!problem)
2961  {
2962    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2963      "input failure before reading right hand / initial solution vectors \n"
2964      "from first input file, input format not accepted"<<endl;
2965    return 0;
2966  }
2967
2968  if(strcmp(format_string,"hand"))
2969    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2970      "first input file has suspicious format"<<endl;
2971
2972  problem>>format_string;
2973
2974  if(!problem)
2975  {
2976    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2977      "input failure before reading right hand / initial solution vectors \n"
2978      "from first input file, input format not accepted"<<endl;
2979    return 0;
2980  }
2981
2982  if(strcmp(format_string,"or"))
2983    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2984      "first input file has suspicious format"<<endl;
2985
2986  problem>>format_string;
2987
2988  if(!problem)
2989  {
2990    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
2991      "input failure before reading right hand / initial solution vectors \n"
2992      "from first input file, input format not accepted"<<endl;
2993    return 0;
2994  }
2995
2996  if(strcmp(format_string,"initial"))
2997    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
2998      "first input file has suspicious format"<<endl;
2999
3000  problem>>format_string;
3001
3002  if(!problem)
3003  {
3004    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3005      "input failure before reading right hand / initial solution vectors \n"
3006      "from first input file, input format not accepted"<<endl;
3007    return 0;
3008  }
3009
3010  if(strcmp(format_string,"solution"))
3011    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
3012      "first input file has suspicious format"<<endl;
3013
3014  problem>>format_string;
3015
3016  if(!problem)
3017  {
3018    cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3019      "input failure before reading right hand / initial solution vectors \n"
3020      "from first input file, input format not accepted"<<endl;
3021    return 0;
3022  }
3023
3024  if(strcmp(format_string,"vectors:"))
3025    cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
3026      "first input file has suspicious format"<<endl;
3027
3028  // the vectors are read in the section "computation" because we need to
3029  // distinguish between the different algorithms
3030
3031
3032//////////////////// output (first part) ///////////////////////////////////
3033
3034  // open output file (append mode)
3035
3036  char SOLUTION[128];
3037
3038  short i=0;
3039  while(GROEBNER[i]!='\0' && GROEBNER[i]!='.')
3040  {
3041    SOLUTION[i]=GROEBNER[i];
3042    i++;
3043  }
3044  SOLUTION[i]='\0';
3045  strcat(SOLUTION,".sol.");
3046  strcat(SOLUTION,algorithm);
3047
3048  ofstream output(SOLUTION,ios::app);
3049
3050  // format output file
3051
3052  output.flags(output.flags()|ios::fixed);
3053  // output of fixed point numbers
3054
3055  output<<"SOLUTION"<<endl<<endl;
3056
3057  output<<"computed with algorithm:"<<endl;
3058  output<<algorithm<<endl;
3059  output<<"from file:"<<endl;
3060  output<<GROEBNER<<endl;
3061
3062
3063/////////// computation and output (second part) //////////////////////////
3064
3065  // distinguish 3 cases to verifie the consistency of the vector dimension
3066  // and the number of variables
3067
3068  // Conti-Traverso: vectors are read as right hand vectors
3069  // vector dimension = number of elimination variables without inversion
3070  // variable
3071  if(!strcmp(algorithm,"ct"))
3072  {
3073    if(problem_variables!=elimination_variables-1)
3074    {
3075      cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3076        "vector dimension in first input file and number of variables in\n"
3077        "second input file do not match with respect to the\n"
3078        "Conti-Traverso-algorithm"<<endl;
3079      return 0;
3080    }
3081
3082    Integer right_hand[weighted_variables+elimination_variables];
3083
3084    for(short k=0;k<instances;k++)
3085    {
3086      // at the beginning, the variables of interest are zero
3087      for(short i=0;i<weighted_variables;i++)
3088        right_hand[i]=0;
3089
3090      // right hand vector is read from the input stream into the
3091      // elimination variables
3092      for(short i=weighted_variables;
3093          i<weighted_variables+elimination_variables-1;i++)
3094      {
3095        problem>>right_hand[i];
3096
3097        if(!problem)
3098        {
3099          cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3100            "input failure when reading right hand vector "<<k+1<<" from "
3101            "first input \nfile, "
3102            "this and all following right hand vectors will be ignored"<<endl;
3103          return 0;
3104        }
3105      }
3106
3107      // determine the exponent of the inversion variable, i.e.
3108      // - min{negative components of right_hand}.
3109      Integer min=0;
3110      for(short i=weighted_variables;
3111          i<weighted_variables+elimination_variables-1;i++)
3112        if(right_hand[i]<min)
3113          min=right_hand[i];
3114
3115      // transform right_hand so that all components are nonnegative
3116      if(min<0)
3117        for(short i=weighted_variables;
3118            i<weighted_variables+elimination_variables-1;i++)
3119          right_hand[i]-=min;
3120
3121      // set exponent of the inversion variable
3122      right_hand[weighted_variables+elimination_variables-1]=-min;
3123
3124      // construct binomial to reduce
3125      binomial to_reduce(weighted_variables+elimination_variables,right_hand);
3126
3127      // prepare time measurement
3128      clock_t start, end;
3129
3130      // reduce binomial
3131      start=clock();
3132      I.reduce(to_reduce,TRUE);
3133      end=clock();
3134
3135      // time measurement
3136      float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3137
3138      // output
3139
3140      output<<"right hand vector:"<<endl;
3141      for(short i=weighted_variables;
3142          i<weighted_variables+elimination_variables-1;i++)
3143        output<<setw(6)<<right_hand[i]+min;
3144        // original vector
3145      output<<endl;
3146
3147      output<<"solvable:"<<endl;
3148
3149      BOOLEAN solvable=TRUE;
3150      for(short i=weighted_variables;
3151          i<=weighted_variables+elimination_variables-1;i++)
3152        if(to_reduce[i]!=0)
3153        {
3154          solvable=FALSE;
3155          break;
3156        }
3157
3158      if(solvable==TRUE)
3159      {
3160        output<<"YES"<<endl;
3161        output<<"optimal solution:"<<endl;
3162        for(short i=0;i<weighted_variables;i++)
3163          output<<setw(6)<<to_reduce[i];
3164        output<<endl;
3165      }
3166      else
3167        output<<"NO"<<endl;
3168
3169      output<<"computation time"<<endl;
3170      output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3171    }
3172  }
3173
3174  else
3175    // Positive Conti-Traverso: vectors are read as right hand vectors
3176    // vector dimension = number of elimination variables
3177    if(!strcmp(algorithm,"pct"))
3178    {
3179      if(problem_variables!=elimination_variables)
3180      {
3181        cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3182          "vector dimension in first input file and number of variables in\n"
3183          "second input file do not match with respect to the\n"
3184          "Positive Conti-Traverso algorithm"<<endl;
3185        return 0;
3186      }
3187
3188      Integer right_hand[weighted_variables+elimination_variables];
3189      BOOLEAN error=FALSE;    // to test legality of right hand vectors
3190
3191      for(short k=0;k<instances;k++)
3192      {
3193        // at the beginning, the variables of interest are zero
3194        for(short i=0;i<weighted_variables;i++)
3195          right_hand[i]=0;
3196
3197        // right hand vector is read from the input stream into the
3198        // elimination variables
3199        for(short i=weighted_variables;
3200            i<weighted_variables+elimination_variables;i++)
3201        {
3202          problem>>right_hand[i];
3203
3204          if(!problem)
3205          {
3206            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3207              "input failure when reading right hand vector "<<k+1<<" from "
3208              "first input \nfile, this and all following right hand vectors "
3209              "will be ignored"<<endl;
3210            return 0;
3211          }
3212
3213          if(right_hand[i]<0)
3214          {
3215            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3216              "right hand vectors with negative components cannot be handled\n"
3217              "by the Positive Conti-Traverso algorithm,\n"
3218              "right hand vector "<<k+1<<" will be ignored"<<endl;
3219            error=TRUE;
3220          }
3221        }
3222
3223        if(error==TRUE)
3224        {
3225          error=FALSE;
3226          continue;
3227          // for-loop
3228        }
3229
3230        // construct binomial to reduce
3231        binomial to_reduce(weighted_variables+elimination_variables,
3232                           right_hand);
3233
3234        // prepare time measurement
3235        clock_t start, end;
3236
3237        // reduce binomial
3238        start=clock();
3239        I.reduce(to_reduce,TRUE);
3240        end=clock();
3241
3242        // time measurement
3243        float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3244
3245        // output
3246
3247        output<<"right hand vector:"<<endl;
3248        for(short i=weighted_variables;
3249            i<weighted_variables+elimination_variables;i++)
3250          output<<setw(6)<<right_hand[i];
3251        // original vector
3252        output<<endl;
3253
3254        output<<"solvable:"<<endl;
3255
3256        BOOLEAN solvable=TRUE;
3257        for(short i=weighted_variables;
3258            i<weighted_variables+elimination_variables;i++)
3259          if(to_reduce[i]!=0)
3260          {
3261            solvable=FALSE;
3262            break;
3263          }
3264
3265        if(solvable==TRUE)
3266        {
3267          output<<"YES"<<endl;
3268          output<<"optimal solution:"<<endl;
3269          for(short i=0;i<weighted_variables;i++)
3270            output<<setw(6)<<to_reduce[i];
3271          output<<endl;
3272        }
3273        else
3274          output<<"NO"<<endl;
3275
3276        output<<"computation time"<<endl;
3277        output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3278      }
3279    }
3280
3281    else
3282      // other algorithms: vectors are read as initial solutions
3283      // vector dimension = number of weighted variables
3284    {
3285      if(problem_variables!=weighted_variables)
3286      {
3287        cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3288          "vector dimension in first input file and number of variables in\n"
3289          "second input file do not match with respect to the\n"
3290          "chosen algorithm"<<endl;
3291        return 0;
3292      }
3293
3294      Integer initial_solution[weighted_variables];
3295
3296      for(short k=0;k<instances;k++)
3297      {
3298        // initial solution vector is read from the input stream into the
3299        // elimination variables
3300        for(short i=0;i<weighted_variables;i++)
3301        {
3302          problem>>initial_solution[i];
3303
3304          if(!problem)
3305          {
3306            cerr<<"ERROR: int solve(INPUT_FILE, INPUT_FILE):\n"
3307              "input failure when reading right hand vector "<<k+1<<" from "
3308              "first input \nfile, this and all following right hand vectors "
3309              "will be ignored"<<endl;
3310            return 0;
3311          }
3312
3313          if(initial_solution[i]<0)
3314            cerr<<"WARNING: int solve(INPUT_FILE, INPUT_FILE):\n"
3315              "initial solution vectors should be nonnegative"<<endl;
3316        }
3317
3318        // construct binomial to reduce
3319        binomial to_reduce(weighted_variables,initial_solution);
3320
3321        // prepare time measurement
3322        clock_t start, end;
3323
3324        // reduce binomial
3325        start=clock();
3326        I.reduce(to_reduce,TRUE);
3327        end=clock();
3328
3329        // time measurement
3330        float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3331
3332        // output
3333
3334        output<<"initial solution vector:"<<endl;
3335        for(short i=0;i<weighted_variables;i++)
3336          output<<setw(6)<<initial_solution[i];
3337        // original vector
3338        output<<endl;
3339
3340        output<<"optimal solution:"<<endl;
3341        for(short i=0;i<weighted_variables;i++)
3342          output<<setw(6)<<to_reduce[i];
3343        output<<endl;
3344
3345        output<<"computation time"<<endl;
3346        output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3347      }
3348    }
3349
3350  return 1;
3351
3352}
3353
3354
3355
3356////////////////////////////////////////////////////////////////////////////
3357////////////////////////////////////////////////////////////////////////////
3358////////////////////////////////////////////////////////////////////////////
3359
3360
3361
3362
3363int change_cost(INPUT_FILE GROEBNER, INPUT_FILE NEW_COST,
3364                const short& version=1,
3365                const short& S_pair_criteria=11,
3366                const float& interred_percentage=12.0,
3367                const BOOLEAN& verbose=FALSE)
3368{
3369
3370  char format_string[128];
3371  short elimination_variables;
3372  short weighted_variables;
3373  char elimination_refinement[128];
3374  char weighted_refinement[128];
3375  short new_variables;
3376  char algorithm[128];
3377  long old_size;
3378
3379  ifstream old(GROEBNER);
3380  ifstream _new(NEW_COST);
3381
3382  // verifie existence of files
3383
3384  if(!old)
3385  {
3386    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3387      "cannot read from first input file, possibly not found"<<endl;
3388    return 0;
3389  }
3390
3391  if(!_new)
3392  {
3393    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3394      "cannot read from second input file, possibly not found"<<endl;
3395    return 0;
3396  }
3397
3398
3399// read first part of GROEBNER file (until term ordering reached)
3400
3401  // read format specification
3402
3403  old>>format_string;
3404
3405  if(!old)
3406  {
3407    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3408      "input failure when reading format specification of first input file,\n"
3409      "input format not accepted"<<endl;
3410    return 0;
3411  }
3412
3413  if(strcmp(format_string,"GROEBNER"))
3414  {
3415    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3416      "first input file has suspicious format"<<endl;
3417  }
3418
3419  // read algorithm
3420
3421  old>>format_string;
3422
3423  if(!old)
3424  {
3425    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3426      "input failure before reading algorithm from first input file,\n"
3427      "input format not accepted"<<endl;
3428    return 0;
3429  }
3430
3431  if(strcmp(format_string,"computed"))
3432  {
3433    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3434      "first input file has suspicious format"<<endl;
3435  }
3436
3437  old>>format_string;
3438
3439  if(!old)
3440  {
3441    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3442      "input failure before reading algorithm from first input file,\n"
3443      "input format not accepted"<<endl;
3444    return 0;
3445  }
3446
3447  if(strcmp(format_string,"with"))
3448  {
3449    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3450      "first input file has suspicious format"<<endl;
3451  }
3452
3453  old>>format_string;
3454
3455  if(!old)
3456  {
3457    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3458      "input failure before reading algorithm from first input file,\n"
3459      "input format not accepted"<<endl;
3460    return 0;
3461  }
3462
3463  if(strcmp(format_string,"algorithm:"))
3464  {
3465    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3466      "first input file has suspicious format"<<endl;
3467  }
3468
3469  old>>algorithm;
3470
3471  if(!old)
3472  {
3473    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3474      "input failure when reading algorithm from first input file,\n"
3475      "input format not accepted"<<endl;
3476    return 0;
3477  }
3478
3479  if(strcmp(algorithm,"ct") && strcmp(algorithm,"pct") &&
3480     strcmp(algorithm,"ect") && strcmp(algorithm,"pt") &&
3481     strcmp(algorithm,"hs") && strcmp(algorithm,"du")
3482     && strcmp(algorithm,"blr"))
3483  {
3484    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3485      "first input file computed with unknown algorithm"<<endl;
3486  }
3487
3488  // override optional lines
3489
3490  do
3491  {
3492    old>>format_string;
3493
3494    if(!old)
3495    {
3496      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3497        "input failure before reading term ordering from first \n"
3498        "input file, input format not accepted"<<endl;
3499      return 0;
3500    }
3501  }
3502  while(strcmp(format_string,"term"));
3503
3504  // read term ordering
3505
3506  old>>format_string;
3507
3508  if(!old)
3509  {
3510    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3511      "input failure before reading term ordering \n"
3512      "from first input file, input format not accepted"<<endl;
3513    return 0;
3514  }
3515
3516  if(strcmp(format_string,"ordering:"))
3517  {
3518    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3519      "first input file has suspicious format"<<endl;
3520  }
3521
3522  old>>format_string;
3523
3524  if(!old)
3525  {
3526    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3527      "input failure when reading term ordering \n"
3528      "from first input file, input format not accepted"<<endl;
3529    return 0;
3530  }
3531
3532  if(strcmp(format_string,"elimination"))
3533  {
3534    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3535      "first input file has suspicious format"<<endl;
3536  }
3537
3538  old>>format_string;
3539
3540  if(!old)
3541  {
3542    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3543      "input failure when reading term ordering \n"
3544      "from first input file, input format not accepted"<<endl;
3545    return 0;
3546  }
3547
3548  if(strcmp(format_string,"block"))
3549  {
3550    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3551      "first input file has suspicious format"<<endl;
3552  }
3553
3554  old>>elimination_variables;
3555
3556  if(!old)
3557  {
3558    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3559      "input failure when reading term ordering \n"
3560      "from first input file, input format not accepted"<<endl;
3561    return 0;
3562  }
3563
3564  if(elimination_variables<0)
3565  {
3566    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3567      "number of elimination variables in first input file must be "
3568      "nonnegative"<<endl;
3569    return 0;
3570  }
3571
3572  if(elimination_variables>0)
3573  {
3574    old>>elimination_refinement;
3575
3576    if(!old)
3577    {
3578      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3579        "input failure when reading term ordering \n"
3580        "from first input file, input format not accepted"<<endl;
3581      return 0;
3582    }
3583
3584    if(strcmp(elimination_refinement,"LEX") &&
3585       strcmp(elimination_refinement,"DEG_LEX") &&
3586       strcmp(elimination_refinement,"DEG_REV_LEX"))
3587    {
3588      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3589        "unknown elimination ordering in first input file"<<endl;
3590      return 0;
3591    }
3592  }
3593
3594  old>>format_string;
3595
3596  if(!old)
3597  {
3598    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3599      "input failure when reading term ordering \n"
3600      "from first input file, input format not accepted"<<endl;
3601    return 0;
3602  }
3603
3604  if(strcmp(format_string,"weighted"))
3605  {
3606    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3607      "first input file has suspicious format"<<endl;
3608  }
3609
3610  old>>format_string;
3611
3612  if(!old)
3613  {
3614    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3615      "input failure when reading term ordering \n"
3616      "from first input file, input format not accepted"<<endl;
3617    return 0;
3618  }
3619
3620  if(strcmp(format_string,"block"))
3621  {
3622    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3623      "first input file has suspicious format"<<endl;
3624  }
3625
3626  old>>weighted_variables;
3627
3628  if(!old)
3629  {
3630    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3631      "input failure when reading term ordering \n"
3632      "from first input file, input format not accepted"<<endl;
3633    return 0;
3634  }
3635
3636  if(weighted_variables<=0)
3637  {
3638    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3639      "number of weighted variables in first input file must be "
3640      "positive"<<endl;
3641    return 0;
3642  }
3643
3644  old>>weighted_refinement;
3645
3646  if(!old)
3647  {
3648    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3649      "input failure when reading term ordering \n"
3650      "from first input file, input format not accepted"<<endl;
3651    return 0;
3652  }
3653
3654  if(strcmp(weighted_refinement,"W_LEX") &&
3655     strcmp(weighted_refinement,"W_REV_LEX") &&
3656     strcmp(weighted_refinement,"W_DEG_LEX") &&
3657     strcmp(weighted_refinement,"W_DEG_REV_LEX"))
3658  {
3659    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3660      "unknown weighted ordering in first input file"<<endl;
3661    return 0;
3662  }
3663
3664// read NEW_COST file
3665
3666  // read format specification
3667
3668  _new>>format_string;
3669
3670  if(!_new)
3671  {
3672    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3673      "input failure when reading format specification\n"
3674      "from second input file, input format not accepted"<<endl;
3675    return 0;
3676  }
3677
3678  if(strcmp(format_string,"MATRIX") && strcmp(format_string,"NEW_COST"))
3679  {
3680    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3681      "second input file has suspicious format"<<endl;
3682  }
3683
3684  // read number of variables
3685
3686  _new>>format_string;
3687
3688  if(!_new)
3689  {
3690    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3691      "input failure before reading number of variables \n"
3692      "from second input file, input format not accepted"<<endl;
3693    return 0;
3694  }
3695
3696  if(strcmp(format_string,"columns:") && strcmp(format_string,"variables:"))
3697    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3698      "second input file has suspicious format"<<endl;
3699
3700  _new>>new_variables;
3701
3702  if(!_new)
3703  {
3704    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3705      "input failure when reading number of variables \n"
3706      "from second input file, input format not accepted"<<endl;
3707    return 0;
3708  }
3709
3710  if(new_variables<=0)
3711  {
3712    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3713      "number of variables in second input file must be positve"<<endl;
3714    return 0;
3715  }
3716
3717  // Now we can verifie consistency of both files with respect to the number
3718  // of weighted variables:
3719
3720  if(weighted_variables!=new_variables)
3721  {
3722    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3723      "number of variables in first and second input file do not match"<<endl;
3724    return 0;
3725  }
3726
3727  // read term ordering
3728
3729  _new>>format_string;
3730
3731  if(!_new)
3732  {
3733    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3734      "input failure before reading new cost vector from second input file,\n"
3735      "input format not accepted"<<endl;
3736    return 0;
3737  }
3738
3739  if(strcmp(format_string,"cost"))
3740    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3741      "second input file has suspicious format"<<endl;
3742
3743  _new>>format_string;
3744
3745  if(!_new)
3746  {
3747    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3748      "input failure before reading new cost vector from second input file,\n"
3749      "input format not accepted"<<endl;
3750    return 0;
3751  }
3752
3753  if(strcmp(format_string,"vector:"))
3754    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3755      "second input file has suspicious format"<<endl;
3756
3757  // the term ordering to refine the weight is taken to be the same as that
3758  // for the old Groebner basis
3759  short weighted_ref;
3760  if(!strcmp(weighted_refinement,"W_LEX"))
3761    weighted_ref=W_LEX;
3762  if(!strcmp(weighted_refinement,"W_REV_LEX"))
3763    weighted_ref=W_REV_LEX;
3764  if(!strcmp(weighted_refinement,"W_DEG_LEX"))
3765    weighted_ref=W_DEG_LEX;
3766  if(!strcmp(weighted_refinement,"W_DEG_REV_LEX"))
3767    weighted_ref=W_DEG_REV_LEX;
3768
3769  term_ordering w(weighted_variables,_new,weighted_ref);
3770
3771  if(w.error_status()<0)
3772  {
3773    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3774      "input failure when reading new cost vector from second input file,\n"
3775      "input format not accepted"<<endl;
3776    return 0;
3777  }
3778
3779  if(w.is_nonnegative()==FALSE)
3780  {
3781    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3782      "cost vectors with negative components are not supported"<<endl;
3783    return 0;
3784  }
3785
3786  if(elimination_variables>0)
3787  {
3788    short elimination_ref;
3789    if(!strcmp(elimination_refinement,"LEX"))
3790      elimination_ref=LEX;
3791    if(!strcmp(elimination_refinement,"DEG_LEX"))
3792      elimination_ref=DEG_LEX;
3793    if(!strcmp(elimination_refinement,"DEG_REV_LEX"))
3794      elimination_ref=DEG_REV_LEX;
3795    w.convert_to_elimination_ordering(elimination_variables,elimination_ref);
3796
3797    if(w.error_status()<0)
3798    {
3799      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3800        "input failure when reading new cost vector from second input file,\n"
3801        "input format not accepted"<<endl;
3802      return 0;
3803    }
3804  }
3805
3806// read second part of the GROEBNER file
3807
3808  // override old weight vector
3809
3810  do
3811  {
3812    old>>format_string;
3813
3814    if(!old)
3815    {
3816      cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3817        "input failure before reading number of ideal generators \n"
3818        "from first input file, input format not accepted"<<endl;
3819      return 0;
3820    }
3821  }
3822  while(strcmp(format_string,"size:"));
3823
3824  // read old Groebner basis
3825
3826  old>>old_size;
3827
3828  if(!old)
3829  {
3830    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3831      "input failure when reading number of ideal generators \n"
3832      "from first input file, input format not accepted"<<endl;
3833    return 0;
3834  }
3835
3836  if(old_size<=0)
3837  {
3838    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3839      "ideal in first input file is corrupt"<<endl;
3840    return 0;
3841  }
3842
3843  old>>format_string;
3844
3845  if(!old)
3846  {
3847    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3848      "input failure before reading ideal generators \n"
3849      "from first input file, input format not accepted"<<endl;
3850    return 0;
3851  }
3852
3853  if(strcmp(format_string,"Groebner"))
3854  {
3855    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3856      "first input file has suspicious format"<<endl;
3857  }
3858
3859  old>>format_string;
3860
3861  if(!old)
3862  {
3863    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3864      "input failure before reading ideal generators \n"
3865      "from first input file, input format not accepted"<<endl;
3866    return 0;
3867  }
3868
3869  if(strcmp(format_string,"basis:"))
3870  {
3871    cerr<<"WARNING: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3872      "first input file has suspicious format"<<endl;
3873  }
3874
3875  // read ideal generators from first input file, already with respect to
3876  // the new term ordering
3877  ideal I(old,w,old_size);
3878
3879  if(!old)
3880  {
3881    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3882      "input failure when reading ideal generators from first input file,\n"
3883      "input format not accepted."<<endl;
3884    return 0;
3885  }
3886
3887  if(I.error_status()<0)
3888  {
3889    cerr<<"ERROR: int change_cost(INPUT_FILE, INPUT_FILE):\n"
3890      "cannot compute with corrupt ideal\n"<<endl;
3891    return 0;
3892  }
3893
3894
3895///////////////////////// computation ////////////////////////////////////////
3896
3897  // prepare time measurement
3898  clock_t start, end;
3899
3900  // compute new Groebner basis
3901  start=clock();
3902  I.reduced_Groebner_basis(version,S_pair_criteria,interred_percentage);
3903  end=clock();
3904
3905  // time measurement
3906  float elapsed=((float) (end-start))/CLOCKS_PER_SEC;
3907
3908
3909///////////////////////// output ////////////////////////////////////////////
3910
3911  // create output file
3912
3913  char NEW_GROEBNER[128];
3914
3915  short i=0;
3916  while(NEW_COST[i]!='\0' && NEW_COST[i]!='.')
3917  {
3918    NEW_GROEBNER[i]=NEW_COST[i];
3919    i++;
3920  }
3921  NEW_GROEBNER[i]='\0';
3922  strcat(NEW_GROEBNER,".GB.");
3923  strcat(NEW_GROEBNER,algorithm);
3924
3925  ofstream output(NEW_GROEBNER);
3926
3927  // format output file
3928
3929  output.flags(output.flags()|ios::fixed);
3930  // output of fixed point numbers
3931
3932  output<<"GROEBNER"<<endl<<endl;
3933
3934  output<<"computed with algorithm:"<<endl;
3935  output<<algorithm<<endl;
3936  output<<"from file(s):"<<endl;
3937  output<<GROEBNER<<", "<<NEW_COST<<endl;
3938  output<<"computation time"<<endl;
3939  output<<setw(6)<<setprecision(2)<<elapsed<<" sec"<<endl<<endl;
3940
3941  output<<"term ordering:"<<endl;
3942  output<<"elimination block"<<endl;
3943  // elimination variables
3944  output<<elimination_variables<<endl;
3945  if(elimination_variables>0)
3946    output<<elimination_refinement<<endl;
3947  output<<"weighted block"<<endl;
3948  // weighted variables (>0)
3949  output<<weighted_variables<<endl;
3950  output<<weighted_refinement<<endl;
3951  w.format_print_weight_vector(output);
3952
3953  output<<"size:"<<endl;
3954  output<<I.number_of_generators()<<endl<<endl;
3955
3956  output<<"Groebner basis:"<<endl;
3957  I.format_print(output);
3958  output<<endl;
3959
3960  if(verbose==TRUE)
3961  {
3962    output<<"settings for the Buchberger algorithm:"<<endl;
3963
3964    output<<"version:"<<endl;
3965    if(version==0)
3966      output<<"1a"<<endl;
3967    else
3968      output<<version<<endl;
3969
3970    output<<"S-pair criteria:"<<endl;
3971    if(S_pair_criteria & REL_PRIMENESS)
3972      output<<"relatively prime leading terms"<<endl;
3973    if(S_pair_criteria & M_CRITERION)
3974      output<<"criterion M"<<endl;
3975    if(S_pair_criteria & F_CRITERION)
3976      output<<"criterion F"<<endl;
3977    if(S_pair_criteria & B_CRITERION)
3978      output<<"criterion B"<<endl;
3979    if(S_pair_criteria & SECOND_CRITERION)
3980      output<<"second criterion"<<endl;
3981    output<<endl;
3982
3983    print_flags(output);
3984    output<<endl;
3985  }
3986
3987  return 1;
3988}
3989
3990#endif // IP_ALGORITHMS_CC
Note: See TracBrowser for help on using the repository browser.