Scippy

SCIP

Solving Constraint Integer Programs

grphload.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file grphload.c
17  * @brief Methods for loading Steiner problems in .stp format
18  * @author Thorsten Koch
19  * @author Daniel Rehfeldt
20  *
21  * This file includes methods for reading a Steiner problem in .stp format.
22  *
23  * A list of all interface methods can be found in grph.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 /*lint -esym(750,GRPHLOAD_C) -esym(766,errno.h) */
29 
30 #define GRPHLOAD_C
31 
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <ctype.h>
36 #include <errno.h> /* errno */
37 #include <assert.h>
38 #include <stdarg.h> /* message: va_list etc */
39 
40 #if defined(_MSC_VER)
41 #include <io.h>
42 #endif
43 
44 #if defined(_WIN32) || defined(_WIN64) || defined(_MSC_VER)
45 #ifndef R_OK
46 #define R_OK 1
47 #endif
48 #else
49 #include <unistd.h> /* R_OK */
50 #endif
51 
52 #include "portab.h"
53 #include "grph.h"
54 
55 #define MSG_FATAL 0
56 #define MSG_ERROR 1
57 #define MSG_WARN 2
58 #define MSG_INFO 3
59 #define MSG_DEBUG 4
60 
61 #define VERBOSE MSG_INFO
62 
63 /* Try to get the maximum length of a path.
64  *
65  * WARNING: if a path found or build during the scanning process is
66  * longer than defined below, the program will probably
67  * crash, because scanf() will overwrite some memory.
68  */
69 #if defined(PATH_MAX) /* Found this on SCO UNIX */
70 #define MAX_PATH_LEN PATH_MAX
71 #elif defined(_MAX_PATH) /* Watcom C on MSDOS */
72 #define MAX_PATH_LEN _MAX_PATH
73 #elif defined(_POSIX_PATH_MAX) /* Maybe POSIX */
74 #define MAX_PATH_LEN _POSIX_PATH_MAX
75 #else
76 #define MAX_PATH_LEN 1024
77 #endif
78 
79 /* Extension separators
80  */
81 #define EXTSEP '.'
82 
83 #define MAX_LINE_LEN 1024
84 #define MAX_KEYWORD_LEN 64
85 #define MAX_STRING_LEN 256
86 #define MAX_ARGUMENTS 8
87 
88 struct key
89 {
90  const char* keyword;
91  int sw_code;
92  const char* format;
93 };
94 
95 #define KEY_SECTION 0001
96 #define KEY_EOF 9999
97 #define KEY_END 9998
98 
99 #define KEY_COMMENT_NAME 1001
100 #define KEY_COMMENT_DATE 1002
101 #define KEY_COMMENT_CREATOR 1003
102 #define KEY_COMMENT_PROBLEM 1004
103 #define KEY_COMMENT_REMARK 1005
104 
105 #define KEY_GRAPH_NODES 2001
106 #define KEY_GRAPH_EDGES 2002
107 #define KEY_GRAPH_E 2003
108 #define KEY_GRAPH_A 2004
109 #define KEY_GRAPH_AA 2005
110 #define KEY_GRAPH_OBSTACLES 2006
111 #define KEY_GRAPH_HOPLIMIT 2007
112 
113 #define KEY_TERMINALS_END 3001
114 #define KEY_TERMINALS_TERMINALS 3002
115 #define KEY_TERMINALS_T 3003
116 #define KEY_TERMINALS_TP 3004
117 #define KEY_TERMINALS_ROOT 3005
118 #define KEY_TERMINALS_ROOTP 3006
119 #define KEY_TERMINALS_TG 3007
120 #define KEY_TERMINALS_GROUPS 3008
121 #define KEY_TERMINALS_TR 3009
122 
123 #define KEY_COORDINATES_DD 4001
124 #define KEY_COORDINATES_DDD 4002
125 #define KEY_COORDINATES_DDDD 4003
126 #define KEY_COORDINATES_DDDDD 4004
127 #define KEY_COORDINATES_DDDDDD 4005
128 #define KEY_COORDINATES_DDDDDDD 4006
129 #define KEY_COORDINATES_DDDDDDDD 4007
130 
131 #define KEY_COORDINATES_END 4011
132 #define KEY_COORDINATES_GRID 4012
133 
134 #define KEY_SOLUTION_VALUE 4021
135 #define KEY_SOLUTION_DATE 4022
136 #define KEY_SOLUTION_TIME 4023
137 #define KEY_SOLUTION_STEINER 4024
138 #define KEY_SOLUTION_S 4025
139 
140 #define KEY_PRESOLVE_DATE 5001
141 #define KEY_PRESOLVE_FIXED 5002
142 #define KEY_PRESOLVE_LOWER 5003
143 #define KEY_PRESOLVE_UPPER 5004
144 #define KEY_PRESOLVE_TIME 5005
145 #define KEY_PRESOLVE_EA 5006
146 #define KEY_PRESOLVE_EC 5007
147 #define KEY_PRESOLVE_ED 5008
148 #define KEY_PRESOLVE_ES 5009
149 
150 
151 #define KEY_NODEWEIGHTS_NW 6000
152 #define KEY_NODEWEIGHTS_END 6001
153 
154 #define KEY_MAXDEGS_MD 8000
155 
156 #define KEY_OBSTACLES_RR 9000
157 #define KEY_OBSTACLES_END 9001
158 
159 #define KEY_HOPCONS_LIM 10000
160 #define KEY_HOPCONS_FACTOR 10001
161 
162 #define KEY_TREE_S 11000
163 
164 static const struct key keyword_table[] =
165  {
166  /*
167  * *** The keywords MUST be sorted alphabetically ! ***
168  */
169  { ".eof", KEY_EOF, NULL },
170  { ".section", KEY_SECTION, NULL },
171 
172  { "comment.creator", KEY_COMMENT_CREATOR, "s" },
173  { "comment.date", KEY_COMMENT_DATE, "s" },
174  { "comment.end", KEY_END, NULL },
175  { "comment.name", KEY_COMMENT_NAME, "s" },
176  { "comment.problem", KEY_COMMENT_PROBLEM, "s" },
177  { "comment.remark", KEY_COMMENT_REMARK, "s" },
178 
179  { "coordinates.dd", KEY_COORDINATES_DD, "nnn" },
180  { "coordinates.ddd", KEY_COORDINATES_DDD, "nnnn" },
181  { "coordinates.dddd", KEY_COORDINATES_DDDD, "nnnnn" },
182  { "coordinates.ddddd", KEY_COORDINATES_DDDDD, "nnnnnn" },
183  { "coordinates.dddddd", KEY_COORDINATES_DDDDDD, "nnnnnnn" },
184  { "coordinates.ddddddd", KEY_COORDINATES_DDDDDDD, "nnnnnnnn" },
185  { "coordinates.dddddddd", KEY_COORDINATES_DDDDDDDD, "nnnnnnnnn" },
186  { "coordinates.end", KEY_COORDINATES_END, NULL },
187  { "coordinates.grid", KEY_COORDINATES_GRID, NULL },
188 
189  { "graph.a", KEY_GRAPH_A, "nnn" },
190  { "graph.aa", KEY_GRAPH_AA, "nnnn" },
191  { "graph.e", KEY_GRAPH_E, "nnn" },
192  { "graph.edges", KEY_GRAPH_EDGES, "n" },
193  { "graph.end", KEY_END, NULL },
194  { "graph.hoplimit", KEY_GRAPH_HOPLIMIT, "n" },
195  { "graph.nodes", KEY_GRAPH_NODES, "n" },
196  { "graph.obstacles", KEY_GRAPH_OBSTACLES, "n" },
197 
198  { "hopconstraint.limit", KEY_HOPCONS_LIM, "n" },
199  { "hopconstraint.factor", KEY_HOPCONS_FACTOR, "nn" },
200 
201  { "maximumdegrees.end", KEY_END, NULL },
202  { "maximumdegrees.md", KEY_MAXDEGS_MD, "n" },
203 
204  { "nodeweights.end", KEY_NODEWEIGHTS_END, NULL },
205  { "nodeweights.nw", KEY_NODEWEIGHTS_NW, "n" },
206 
207  { "obstacles.end", KEY_OBSTACLES_END, NULL },
208  { "obstacles.rr", KEY_OBSTACLES_RR, "nnnn" },
209 
210  { "presolve.date", KEY_PRESOLVE_DATE, "s" },
211  { "presolve.ea", KEY_PRESOLVE_ED, "nnnn" },
212  { "presolve.ec", KEY_PRESOLVE_EC, "nnn" },
213  { "presolve.ed", KEY_PRESOLVE_ED, "nnn" },
214  { "presolve.end", KEY_END, NULL },
215  { "presolve.es", KEY_PRESOLVE_ES, "nn" },
216  { "presolve.fixed", KEY_PRESOLVE_FIXED, "n" },
217  { "presolve.lower", KEY_PRESOLVE_LOWER, "n" },
218  { "presolve.orgnodes", KEY_EOF, "n" },
219  { "presolve.time", KEY_PRESOLVE_TIME, "n" },
220  { "presolve.upper", KEY_PRESOLVE_UPPER, "n" },
221 
222  { "solution.date", KEY_SOLUTION_DATE, "s" },
223  { "solution.end", KEY_END, NULL },
224  { "solution.s", KEY_SOLUTION_S, "n" },
225  { "solution.steiner", KEY_SOLUTION_STEINER, "n" },
226  { "solution.time", KEY_SOLUTION_TIME, "n" },
227  { "solution.value", KEY_SOLUTION_VALUE, "n" },
228 
229  { "terminals.end", KEY_TERMINALS_END, NULL },
230  { "terminals.groups", KEY_TERMINALS_GROUPS, "n" },
231  { "terminals.root", KEY_TERMINALS_ROOT, "n" },
232  { "terminals.rootp", KEY_TERMINALS_ROOTP, "n" },
233  { "terminals.t", KEY_TERMINALS_T, "n" },
234  { "terminals.terminals", KEY_TERMINALS_TERMINALS, "n" },
235  { "terminals.tg", KEY_TERMINALS_TG, "nn" },
236  { "terminals.tp", KEY_TERMINALS_TP, "nn" },
237  { "terminals.tr", KEY_TERMINALS_TR, "nn" },
238 
239  { "tree.s", KEY_TREE_S, NULL },
240  };
241 
242 struct section
243 {
244  const char* name;
245  const char* extension;
246  const int flag;
247  int mark;
248 };
249 
250 #define FLAG_OPTIONAL 1
251 #define FLAG_REQUIRED 2
252 
253 #define SECTION_MISSING 0
254 #define SECTION_EXISTEND 1
255 
256 /* Extension NULL = no separate file possible !
257  */
258 static struct section section_table[] =
259  {
260  { "", "stp", FLAG_REQUIRED, SECTION_EXISTEND },
261 
262  /*
263  * *** The section names MUST be sorted alphabetically ! ***
264  */
265  { "comment", NULL, FLAG_OPTIONAL, SECTION_MISSING },
266  { "coordinates", "crd", FLAG_OPTIONAL, SECTION_MISSING },
267  { "graph", "grp", FLAG_REQUIRED, SECTION_MISSING },
268  { "maximumdegrees", "mdg", FLAG_OPTIONAL, SECTION_MISSING },
269  { "nodeweights", "nwg", FLAG_OPTIONAL, SECTION_MISSING },
270  { "obstacles", "obs", FLAG_OPTIONAL, SECTION_MISSING },
271  { "presolve", "prs", FLAG_OPTIONAL, SECTION_MISSING },
272  { "solution", "slt", FLAG_OPTIONAL, SECTION_MISSING },
273  { "terminals", "trm", FLAG_OPTIONAL, SECTION_MISSING },
274  { "tree", "tre", FLAG_OPTIONAL, SECTION_MISSING },
275  };
276 
277 typedef struct current_file
278 {
279  char filename[MAX_PATH_LEN];
280  int line;
281  FILE* fp;
282  struct section* section;
283 } CURF;
284 
285 typedef union parameter
286 {
287  double n; /* Could be long long */
288  char s[MAX_STRING_LEN];
289 } PARA;
290 
291 /*---------------------------------------------------------------------------*/
292 /*--- Name : String to Lower ---*/
293 /*--- Function : Converts a string to lower case. ---*/
294 /*--- Arguments: Pointer to string. ---*/
295 /*--- Returns : The argument, but now pointing to a lower case string. ---*/
296 /*---------------------------------------------------------------------------*/
297 static
298 char* strlower(
299  char* s
300  )
301 {
302  char* t;
303 
304  for( t = s; *s != '\0'; s++ )
305  *s = (char)tolower(*s);
306 
307  return t;
308 }
309 
310 /*---------------------------------------------------------------------------*/
311 /*--- Name : Print Message ---*/
312 /*--- Function : Prints a message on stderr. ---*/
313 /*--- Arguments: Type of message, Info about filename and line number, ---*/
314 /*--- printf format string and parameters to be printed. ---*/
315 /*--- Returns : Nothing ---*/
316 /*---------------------------------------------------------------------------*/
317 static void message(
318  unsigned int type,
319  const CURF* curf,
320  const char* msg,
321  ...)
322 {
323  va_list params;
324 
325  const char* intro[] = { "Fatal Error", "Error ", "Warning ",
326  "Info ", "Debug "
327  };
328  const char* header = "*** %s File \"%s\" line %05d: ";
329 
330  assert(type < sizeof(intro) / sizeof(char*));
331  assert(curf != NULL);
332  assert(curf->filename != NULL);
333  assert(curf->line >= 0);
334  assert(msg != NULL);
335 
336  va_start(params, msg);
337 
338  if (type <= VERBOSE)
339  {
340  (void)fprintf(stderr, header, intro[type], curf->filename, curf->line);
341  (void)vfprintf(stderr, msg, params);
342  (void)fputc('\n', stderr);
343  }
344  va_end(params);
345 }
346 
347 /*---------------------------------------------------------------------------*/
348 /*--- Name : Key Compare ---*/
349 /*--- Function : Compares the key with an element of the list. ---*/
350 /*--- Parameter: Pointer to key, pointer to element ---*/
351 /*--- Returns : <0 : key<elem, =0 : key=elem, >0 : key>elem ---*/
352 /*---------------------------------------------------------------------------*/
353 static int key_cmp(
354  const void* key,
355  const void* elem)
356 {
357  assert(key != NULL);
358  assert(elem != NULL);
359  assert(((const struct key*)elem)->keyword != NULL);
360 
361  return(strcmp((const char*)key, ((const struct key*)elem)->keyword));
362 }
363 
364 /*---------------------------------------------------------------------------*/
365 /*--- Name : Section Compare ---*/
366 /*--- Function : Compares the key with an section name. ---*/
367 /*--- Parameter: Pointer to key, pointer to section ---*/
368 /*--- Returns : <0 : key<sec, =0 : key=sec, >0 : key>sec ---*/
369 /*---------------------------------------------------------------------------*/
370 static int sec_cmp(
371  const void* key,
372  const void* section)
373 {
374  assert(key != NULL);
375  assert(section != NULL);
376  assert(((const struct section*)section)->name != NULL);
377 
378  return(strcmp((const char*)key, ((const struct section*)section)->name));
379 }
380 
381 /*---------------------------------------------------------------------------*/
382 /*--- Name : Get Arguments ---*/
383 /*--- Function : Extract the arguments following a keyword. ---*/
384 /*--- Parameter: Current file info, argument format string, input line, ---*/
385 /*--- pointer to array of MAX_ARGUMENTS PARA's. ---*/
386 /*--- Returns : 0 for success and < 0 for failure. ---*/
387 /*---------------------------------------------------------------------------*/
388 static int get_arguments(
389  const CURF* curf,
390  const char* format,
391  const char* s,
392  PARA* para)
393 {
394  const char* err_missmatch_v = "Wrong Syntax";
395  const char* msg_hello_ss = "get_arguments(\"%s\", \"%s\")";
396 
397  int missmatch = FALSE;
398  int i;
399  int decimal_spaces;
400  SCIP_Bool is_negative;
401  assert(format != NULL);
402  assert(s != NULL);
403  assert(para != NULL);
404 
405  message(MSG_DEBUG, curf, msg_hello_ss, format, s);
406 
407  /* We try until we run out of input or have enough arguments.
408  */
409  while((*s != '\0') && (*format != '\0') && !missmatch)
410  {
411  missmatch = TRUE;
412 
413  switch(*format)
414  {
415  case 'n' : /* Numeric */
416  /* Go to next digit.
417  */
418  while((*s != '\0') && !isdigit(*s) && (*s != '.') && (*s != '-') )
419  {
420  s++;
421  }
422  /* Something left ?
423  */
424  if (*s != '\0')
425  {
426  assert(isdigit(*s) || (*s == '.') || (*s == '-'));
427 
428  /* Get it.
429  */
430  para->n = 0;
431  decimal_spaces = -1;
432  is_negative = FALSE;
433  while(isdigit(*s) || (*s == '.') || (*s == '-'))
434  {
435  if( *s == '.' )
436  decimal_spaces = 0;
437  else if( *s == '-' )
438  is_negative = TRUE;
439  else if( decimal_spaces != -1 )
440  para->n = para->n + pow(10.0, (double) -(++decimal_spaces)) * (*s - '0');
441  else
442  para->n = para->n * 10 + (*s - '0');
443  s++;
444  }
445  if( is_negative )
446  para->n = (-1) * para->n;
447  missmatch = FALSE;
448  }
449  break;
450  case 's' : /* String */
451  /* Go to the beginning of the string.
452  */
453  while((*s != '\0') && (*s != '\"'))
454  s++;
455 
456  /* Someting left ?
457  */
458  if (*s != '\0')
459  {
460  assert(*s == '\"');
461 
462  /* Get the String.
463  */
464  i = 0;
465  s++;
466 
467  while((*s != '\0') && (*s != '\"') && (i < MAX_STRING_LEN - 1))
468  para->s[i++] = *s++;
469 
470  para->s[i] = '\0';
471  missmatch = FALSE;
472  }
473  break;
474  case 'b' : /* Bool */
475  case 'd' : /* Date */
476  default :
477  /* CONSTCOND */
478  assert(FALSE);
479  break;
480  }
481  if (missmatch)
482  message(MSG_ERROR, curf, err_missmatch_v);
483  else
484  {
485  para++;
486  format++;
487 
488  }
489  }
490  return((*format == '\0') ? SUCCESS : FAILURE);
491 }
492 
493 /*---------------------------------------------------------------------------*/
494 /*--- Name : Open File ---*/
495 /*--- Function : Opens a file, processes the file header and secures it's ---*/
496 /*--- the right file. ---*/
497 /*--- Arguments: Info about filename and wanted section (file type). ---*/
498 /*--- Returns : 0 for success with curf->fp and curf->line filled or ---*/
499 /*--- or < 0 for failure. ---*/
500 /*---------------------------------------------------------------------------*/
501 static int open_file(
502  CURF* curf,
503  unsigned char main_file
504 )
505 {
506  const char* err_cantopen_s = "%s.";
507  const char* err_noheader_v = "Wrong file header.";
508  const char* err_nomagic_d = "Wrong Magic-Number %d.";
509  const char* err_wrongtype_ss = "Wrong file type. Found %s, expected %s.";
510  const char* msg_version_dd = "Format Version %d.%d.";
511 
512  char type[4];
513  unsigned int magic;
514  int version_major;
515  int version_minor;
516  int result = FAILURE;
517 
518  assert(curf != NULL);
519  assert(curf->filename != NULL);
520  assert(curf->section != NULL);
521 
522  /* Prepare the result.
523  */
524  curf->line = 1;
525  curf->fp = NULL;
526 
527  /* reading in the main file? */
528  if( main_file )
529  {
530  char fillname_gr[MAX_PATH_LEN + 3];
531 
532  (void)sprintf(fillname_gr, "%s.%s",
533  curf->filename, "gr");
534 
535  /* try to open .gr */
536  if ((curf->fp = fopen(fillname_gr, "r")) != NULL)
537  {
538  (void)sprintf(curf->filename, "%s", fillname_gr);
539  return(SUCCESS);
540  }
541  else
542  {
543  /* try to open .stp */
544  char fillname_stp[MAX_PATH_LEN + 4];
545  (void) sprintf(fillname_stp, "%s.%s", curf->filename, "stp");
546 
547  if ((curf->fp = fopen(fillname_stp, "r")) == NULL)
548  {
549  message(MSG_FATAL, curf, err_cantopen_s, strerror(errno));
550  return result;
551  }
552  (void)sprintf(curf->filename, "%s", fillname_stp);
553  }
554  }
555 
556 
557  /* Try to open the file...
558  */
559  if (!main_file && (curf->fp = fopen(curf->filename, "r")) == NULL)
560  message(MSG_FATAL, curf, err_cantopen_s, strerror(errno));
561 
562  /* Read Header...
563  */
564  else if (fscanf(curf->fp, "%8x %3s File, STP Format Version %2d.%2d \n",
565  &magic, type, &version_major, &version_minor) != 4)
566  message(MSG_FATAL, curf, err_noheader_v);
567 
568  /* Test Magic...
569  */
570  else if (magic != STP_MAGIC)
571  message(MSG_FATAL, curf, err_nomagic_d, magic);
572 
573  /* Did we get the right type of file ?
574  */
575  else if (strcmp(strlower(type), curf->section->extension))
576  message(MSG_FATAL, curf, err_wrongtype_ss, type, curf->section->extension);
577  else
578  {
579  /* Succeeded. Just give a warning if the file has a different
580  * version number than the reader and hope it will be ok.
581  */
582  if ((version_major != VERSION_MAJOR) || (version_minor != VERSION_MINOR))
583  message(MSG_WARN, curf, msg_version_dd, version_minor, version_major);
584 
585  result = SUCCESS;
586  }
587  return(result);
588 }
589 
590 /*---------------------------------------------------------------------------*/
591 /*--- Name : Start a new Section ---*/
592 /*--- Function : Starts a new section, maybe in another file. ---*/
593 /*--- Parameter: Path for files, Basename, pointer to actual file info, ---*/
594 /*--- Pointer to where to save actual file info, inputline. ---*/
595 /*--- Returns : 0 for success and < 0 for failure. ---*/
596 /*---------------------------------------------------------------------------*/
597 static int start_section(
598  const char* pathname,
599  const char* basename,
600  CURF* curf,
601  CURF* save,
602  const char* s)
603 {
604  const char* err_missing_v = "Section name missing";
605  const char* err_badsect_s = "Unknown section name [%s]";
606  const char* err_required_s = "Can't access required file [%s]";
607 
608  CURF temp;
609  char inclname[MAX_PATH_LEN];
610  char sectname[MAX_KEYWORD_LEN];
611  char dummy [MAX_KEYWORD_LEN];
612  int tokens;
613  int ret = FAILURE;
614 
615  assert(pathname != NULL);
616  assert(basename != NULL);
617  assert(curf != NULL);
618  assert(save != NULL);
619  assert(s != NULL);
620 
621  sectname[0] = '\0';
622  inclname[0] = '\0';
623 
624  /* Extract names
625  */
626  if( (tokens = sscanf(s, "%63s %63s %s", sectname, dummy, inclname)) < 1 )
627  message(MSG_FATAL, curf, err_missing_v);
628  else
629  {
630  /* Known section ?
631  */
632  if( strcmp(strlower(sectname),"comments") == 0 )
633  sectname[7] = '\0';
634 
635  temp.section = (struct section*)bsearch(strlower(sectname),
636  &section_table[1],
637  (sizeof(section_table) / sizeof(struct section)) - 1,
638  sizeof(struct section), sec_cmp);
639 
640  if( temp.section == NULL )
641  message(MSG_FATAL, curf, err_badsect_s, sectname);
642  else
643  {
644  /* Is this section in a separate file ?
645  */
646  if( tokens == 1 || (tokens == 2 && strcmp(strlower(sectname),"tree") == 0) )
647  {
648  curf->section = temp.section;
649  curf->section->mark |= SECTION_EXISTEND;
650  ret = SUCCESS;
651  }
652  else
653  {
654  (void)sprintf(temp.filename, "%s%s%c%s",
655  pathname,
656  (*inclname == '\0') ? basename : inclname,
657  EXTSEP,
658  temp.section->extension);
659 #if defined(_MSC_VER)
660  if (_access(temp.filename, R_OK))
661 #else
662  if (access(temp.filename, R_OK))
663 #endif
664  {
665  /* We can't access the include file.
666  * If the section is optional, we just ignore
667  * the whole thing, otherwise we have a problem.
668  */
669  if (temp.section->flag & FLAG_REQUIRED)
670  message(MSG_FATAL, curf, err_required_s, temp.filename);
671  else
672  {
673  temp.section = &section_table[0];
674  ret = SUCCESS;
675  }
676  }
677  else
678  {
679  if (!open_file(&temp, FALSE) )
680  {
681  *save = *curf;
682  *curf = temp;
683  curf->section->mark |= SECTION_EXISTEND;
684 
685  ret = SUCCESS;
686  }
687  }
688  }
689  }
690  }
691  return(ret);
692 }
693 
694 static
696  SCIP* scip,
697  GRAPH* g,
698  PARA* para,
699  double*** coordinates,
700  int* grid_dim,
701  int* termcount,
702  int dim,
703  int nodes
704  )
705 {
706  int i;
707 
708  if( *coordinates == NULL )
709  {
710  assert(g == NULL);
711  assert(termcount != NULL);
712  assert(grid_dim != NULL);
713  assert(*termcount == 0);
714  assert(nodes > 0);
715 
716  *grid_dim = dim;
717 
718  /* allocate memory for the coordinate arrays */
719  SCIP_CALL( SCIPallocMemoryArray(scip, coordinates, dim) );
720 
721  for( i = 0; i < dim; i++ )
722  SCIP_CALL( SCIPallocMemoryArray(scip, &((*coordinates)[i]), nodes) ); /*lint !e866*/
723  }
724 
725  for( i = 0; i < dim; i++ )
726  (*coordinates)[i][*termcount] = (double)para[i + 1].n;
727 
728  (*termcount)++;
729  return SCIP_OKAY;
730 }
731 
732 static
735  )
736 {
737  int ints;
738  int order;
739  int trail_zeroes;
740  int i;
741  int length;
742  char s;
743  char str_number[SCIP_MAXSTRLEN];
744  (void)SCIPsnprintf(str_number, SCIP_MAXSTRLEN, "%f", number);
745  length = (int) strlen(str_number);
746  if( SCIP_MAXSTRLEN < length )
747  length = (int) SCIP_MAXSTRLEN;
748 
749  for( i = 0; i < length; i++ )
750  {
751  if( str_number[length - i - 1] != '0' )
752  break;
753  }
754  trail_zeroes = i;
755 
756  for( i = 0; i < length; i++ )
757  {
758  s = str_number[i];
759  if( s == '.' )
760  break;
761  }
762  ints = i;
763  order = length - ints - trail_zeroes - 1;
764 
765  return order;
766 }
767 
768 
769 /* scales coordinates in such a way, that they become integer */
770 static
772  double** coordinates,
773  int*** scaled_coords,
774  int* scale_order,
775  int nnodes,
776  int grid_dim
777  )
778 {
779  int i;
780  int j;
781  int tmp;
782  int scale_factor;
783  int max_order = 0;
784 
785  assert(coordinates != NULL);
786  assert(nnodes > 0);
787  assert(grid_dim > 1);
788 
789  SCIP_CALL( SCIPallocMemoryArray(scip, scaled_coords, grid_dim) );
790 
791  for( i = 0; i < grid_dim; i++ )
792  for( j = 0; j < nnodes; j++ )
793  {
794  tmp = get_scale_order(coordinates[i][j]);
795 
796  if( max_order < tmp )
797  {
798  max_order = tmp;
799  }
800  }
801 
802  *scale_order = max_order;
803  scale_factor = (int) pow(10.0, (double) max_order);
804 
805  for( i = 0; i < grid_dim; i++ )
806  {
807  SCIP_CALL( SCIPallocMemoryArray(scip, &((*scaled_coords)[i]), nnodes) ); /*lint !e866*/
808  for( j = 0; j < nnodes; j++ )
809  {
810  (*scaled_coords)[i][j] = (int) (coordinates[i][j] * scale_factor);
811  }
812  }
813  return SCIP_OKAY;
814 }
815 
816 /*---------------------------------------------------------------------------*/
817 /*--- Name : Steiner Tree Problem Load ---*/
818 /*--- Function : Reads a file in STP format and parses it. ---*/
819 /*--- Parameter: Pointer to filename, Pointer to presolve struct ---*/
820 /*---------------------------------------------------------------------------*/
822  SCIP* scip, /**< SCIP data structure */
823  GRAPH** graph, /**< pointer to store the graph */
824  const char* file, /**< file to load */
825  PRESOL* presol /**< presolving struct */
826  )
827 {
828  const char* err_unknown_s = "Unknown keyword [%s]";
829  const char* err_include_v = "Include in included file";
830  const char* err_missing_s = "Required section %s missing";
831  const char* msg_newsect_s = "Processing Section %s";
832  const char* msg_keyword_sd = "Found Keyword \"%s\", code = %d";
833  const char* err_badedge_ddd = "Bad edge %d-%d (%d nodes)";
834  const char* err_badroot_dd = "Bad root %d (%d nodes)";
835  const char* err_baddeg_dd = "More degree constraints (%d) than nodes (%d)";
836  const char* msg_finish_dddd = "Nodes: %d Edges: %d Terminals: %d Source=%d\n";
837 
838  const char* endofline = "#;\n\r";
839  const char* separator = " \t:=";
840 
841  static CURF curf_null = { "", 0, NULL, NULL };
842 
843  GRAPH* g = NULL;
844  CURF curf;
845  CURF save;
846  PARA para [MAX_ARGUMENTS];
847  double nodeweight;
848  char buffer [MAX_LINE_LEN];
849  char pathname[MAX_PATH_LEN];
850  char basename[MAX_PATH_LEN];
851  char keyword [MAX_KEYWORD_LEN];
852  int stop_input = FALSE;
853  int ret = FAILURE;
854  char* s;
855  char* t;
856  struct key* p;
857  double** coordinates = NULL;
858  int i;
859  int head;
860  int tail;
861  int tgroups = 0;
862  int grid_dim = -1;
863  int terms = 0;
864  int nodes = 0;
865  int edges = 0;
866  int nwcount = 0;
867  int degcount = 0;
868  int hoplimit = UNKNOWN;
869  int stp_type = -1;
870  int termcount = 0;
871  int nobstacles = -1;
872  int scale_order = 1;
873  int obstacle_counter = 0;
874  int** scaled_coordinates = NULL;
875  int** obstacle_coords = NULL;
876  int transformed = 0;
877 
878  assert(file != NULL);
879 
880  /* No section loaded so far.
881  */
882  for( i = 1; i < (int)(sizeof(section_table) / sizeof(section_table[0])); i++ )
883  section_table[i].mark = SECTION_MISSING;
884 
885  /* Get the names...
886  */
887  (void)strcpy(pathname, file);
888 
889  /* Did we get a path ?
890  */
891  if( (s = strrchr(pathname, DIRSEP[0])) == NULL )
892  {
893  /* No, no path.
894  */
895  (void)strcpy(basename, pathname);
896  pathname[0] = '\0';
897  }
898  else
899  {
900  /* Yes, there is a path in front.
901  */
902  s++;
903  (void)strcpy(basename, s);
904  *s = '\0';
905  }
906 
907  /* Strip of the extension
908  */
909  if ((s = strrchr(basename, EXTSEP)) != NULL)
910  *s = '\0';
911 
912  /* Build filename
913  */
914  curf.section = &section_table[0];
915  save = curf_null;
916 
917  (void) SCIPsnprintf(curf.filename, MAX_PATH_LEN, "%s%s", pathname, basename);
918 
919  /* Open the file...
920  */
921  if (!open_file(&curf, TRUE))
922  {
923  /* We read while a file is open...
924  */
925  while((curf.fp != NULL) && !stop_input)
926  {
927  /* Read a line.
928  */
929  if ((s = fgets(buffer, (int) sizeof(buffer), curf.fp)) == NULL)
930  {
931  /* No more lines available, so we can close the file.
932  */
933  (void)fclose(curf.fp);
934 
935  /* If we are in an included file, we come back to our
936  * main file. Otherwise fp_save is NULL and than fp will
937  * get NULL so we're finished.
938  */
939  curf = save;
940  save = curf_null;
941 
942  continue;
943  }
944  /* Count line number
945  */
946  curf.line++;
947 
948  /* Find the start of the interesting part of an inputline.
949  */
950  while(isspace(*s))
951  s++;
952 
953  /* Find the end of the interesting portion of an input line.
954  * Either the start of a comment or the final NL or CR.
955  * Since all lines but the last must have at least a NL
956  * t is nearly never NULL.
957  */
958  if ((t = strpbrk(s, endofline)) != NULL)
959  *t = '\0';
960 
961  /* Is there an interesting part left ?
962  */
963  if (*s == '\0')
964  continue;
965 
966  /* Build a keyword of form "sectionname.keyword"
967  */
968  (void)strcpy(keyword, curf.section->name);
969 
970  i = (int)strlen(keyword);
971  keyword[i] = '.';
972 
973  for(i++;
974  (i < MAX_KEYWORD_LEN - 1) && (isalpha(*s) || (*s == '_'));
975  i++, s++)
976  keyword[i] = (char)tolower(*s);
977 
978  keyword[i] = '\0';
979 
980  /* Skip junk following the keyword.
981  */
982  while((*s != '\0') && (strchr(separator, *s) != NULL))
983  s++;
984 
985  if( strcmp(keyword,"comments") == 0 )
986  keyword[i - 1] = '\0';
987 
988  /* Did we know the keyword ?
989  */
990  p = (struct key*)bsearch(keyword, keyword_table,
991  sizeof(keyword_table) / sizeof(struct key),
992  sizeof(struct key), key_cmp);
993 
994  if (p == NULL)
995  message(MSG_ERROR, &curf, err_unknown_s, keyword);
996  else
997  {
998  char newformat[5] = "";
999  assert(p != NULL);
1000 
1001  message(MSG_DEBUG, &curf, msg_keyword_sd, p->keyword, p->sw_code);
1002 
1003  /* Yes, so lets get the rest of the line if possible
1004  */
1005  if( (stp_type == STP_MWCSP || stp_type == STP_RMWCSP) && p->format != NULL && (p->sw_code == KEY_TERMINALS_T || p->sw_code == KEY_GRAPH_E) )
1006  strcpy(newformat, "nn");
1007  else if( stp_type == STP_SAP && p->sw_code == KEY_GRAPH_A )
1008  strcpy(newformat, "nnnn");
1009 
1010  if( p->format == NULL || !get_arguments(&curf, (const char*)( newformat[0] != '\0' ? newformat : p->format ), s, para) )
1011  {
1012  /* Now, what should we do ?
1013  */
1014  switch(p->sw_code)
1015  {
1016  case KEY_SECTION : /* a new Section starts. */
1017  if (save.fp == NULL)
1018  stop_input = start_section(pathname, basename,
1019  &curf, &save, s);
1020  else
1021  {
1022  message(MSG_FATAL, &curf, err_include_v);
1023  stop_input = TRUE;
1024  }
1025  if (!stop_input)
1026  message(MSG_INFO, &curf, msg_newsect_s, curf.section->name);
1027  break;
1028  case KEY_END : /* END found. */
1029  curf.section = &section_table[0];
1030  break;
1031  case KEY_TREE_S : /* fall through */
1032  case KEY_EOF : /* EOF found */
1033  ret = SUCCESS;
1034  stop_input = TRUE;
1035 
1036  /* Test if all required section were found.
1037  */
1038  for(i = 0; (unsigned)i < sizeof(section_table) / sizeof(struct section); i++)
1039  {
1040  if ((section_table[i].flag & FLAG_REQUIRED)
1041  && !(section_table[i].mark & SECTION_EXISTEND))
1042  {
1043  message(MSG_FATAL, &curf, err_missing_s, section_table[i].name);
1044  ret = FAILURE;
1045  }
1046  }
1047  break;
1048  case KEY_COMMENT_NAME :
1049  case KEY_COMMENT_DATE :
1050  case KEY_COMMENT_CREATOR :
1051  case KEY_COMMENT_PROBLEM :
1052  (void)printf("Problem: [%s]\n", para[0].s);
1053  if( strcmp(para[0].s, "SPG") == 0 )
1054  stp_type = STP_SPG;
1055  else if( strcmp(para[0].s, "PCSPG") == 0
1056  || strcmp(para[0].s, "Prize-Collecting Steiner Problem in Graphs") == 0 )
1057  stp_type = STP_PCSPG;
1058  else if( strcmp(para[0].s, "RPCST") == 0
1059  || strcmp(para[0].s, "Rooted Prize-Collecting Steiner Problem in Graphs") == 0 )
1060  stp_type = STP_RPCSPG;
1061  else if( strcmp(para[0].s, "NWSPG") == 0 )
1062  stp_type = STP_NWSPG;
1063  else if( strcmp(para[0].s, "DCST") == 0 )
1064  stp_type = STP_DCSTP;
1065  else if( strcmp(para[0].s, "RSMT") == 0 )
1066  stp_type = STP_RSMT;
1067  else if( strcmp(para[0].s, "OARSMT") == 0 )
1068  stp_type = STP_OARSMT;
1069  else if( strcmp(para[0].s, "Maximum Node Weight Connected Subgraph") == 0
1070  || strcmp(para[0].s, "MWCS") == 0 )
1071  stp_type = STP_MWCSP;
1072  else if( strcmp(para[0].s, "Rooted Maximum Node Weight Connected Subgraph") == 0
1073  || strcmp(para[0].s, "RMWCS") == 0 )
1074  stp_type = STP_RMWCSP;
1075  else if( strcmp(para[0].s, "HCDST") == 0 )
1076  stp_type = STP_DHCSTP;
1077  else if( strcmp(para[0].s, "SAP") == 0 )
1078  stp_type = STP_SAP;
1079  else if( strcmp(para[0].s, "GSTP") == 0 )
1080  stp_type = STP_GSTP;
1081  break;
1082  case KEY_COMMENT_REMARK :
1083  (void)printf("Comment: [%s]\n", para[0].s);
1084  if( strcmp(para[0].s, "Transformed") == 0 )
1085  transformed = 1;
1086  break;
1087  case KEY_GRAPH_NODES :
1088  assert(para != NULL);
1089  nodes = (int)para[0].n;
1090  break;
1091  case KEY_GRAPH_OBSTACLES :
1092  nobstacles = (int)para[0].n;
1093  if( nobstacles > 0 )
1094  stp_type = STP_OARSMT;
1095  break;
1096  case KEY_GRAPH_HOPLIMIT :
1097  hoplimit = (int)para[0].n;
1098  stp_type = STP_DHCSTP;
1099  break;
1100  case KEY_GRAPH_EDGES :
1101  edges = (int)para[0].n;
1102  break;
1103  case KEY_GRAPH_A :
1104  case KEY_GRAPH_AA :
1105  case KEY_GRAPH_E :
1106  if( (int)para[0].n > nodes || (int)para[1].n > nodes )
1107  {
1108  message(MSG_FATAL, &curf, err_badedge_ddd,
1109  (int)para[0].n, (int)para[1].n, nodes);
1110  ret = FAILURE;
1111  break;
1112  }
1113 
1114  if( g == NULL )
1115  {
1116  if( stp_type == STP_GSTP )
1117  SCIP_CALL( graph_init(scip, graph, nodes * 2, edges * 2 + nodes * nodes, 1) );
1118  else
1119  SCIP_CALL( graph_init(scip, graph, nodes, edges * 2, 1) );
1120 
1121  g = *graph;
1122  assert(g != NULL);
1123  assert(g->source == UNKNOWN);
1124  for( i = 0; i < nodes; i++ )
1125  graph_knot_add(g, -1);
1126 
1127  if( stp_type == STP_DHCSTP )
1128  {
1129  assert(hoplimit != UNKNOWN);
1130  g->hoplimit = hoplimit;
1131  }
1132  }
1133 
1134  if( stp_type == STP_DHCSTP )
1135  {
1136  tail = (int)para[0].n - 1;
1137  head = (int)para[1].n - 1;
1138  /* check whether the anti-parallel arc has already been added */
1139  for( i = g->inpbeg[head]; i != EAT_LAST; i = g->ieat[i] )
1140  if( g->tail[i] == tail )
1141  break;
1142  if( i == EAT_LAST )
1143  graph_edge_add(scip, g, tail, head, (double)para[2].n, FARAWAY);
1144  else
1145  g->cost[i] = (double)para[2].n;
1146 
1147  }
1148  else if( stp_type == STP_SAP )
1149  {
1150  graph_edge_add(scip, g, (int)para[0].n - 1, (int)para[1].n - 1, (double)para[2].n, (double)para[3].n);
1151  }
1152  else if( stp_type == STP_MWCSP || stp_type == STP_RMWCSP )
1153  {
1154  graph_edge_add(scip, g, (int)para[0].n - 1, (int)para[1].n - 1, 0.0, 0.0);
1155  }
1156  else
1157  {
1158  graph_edge_add(scip, g, (int)para[0].n - 1, (int)para[1].n - 1,
1159  (double)para[2].n,
1160  (p->sw_code == KEY_GRAPH_E)
1161  ? (double)para[2].n
1162  : (double)para[3].n);
1163  }
1164  break;
1165  case KEY_MAXDEGS_MD :
1166  assert(g != NULL);
1167  assert((int)para[0].n >= 0);
1168 
1169  if( degcount < nodes )
1170  {
1171  if( g->maxdeg == NULL )
1172  {
1173  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->maxdeg), nodes ) );
1174  stp_type = STP_DCSTP;
1175  }
1176  g->maxdeg[degcount++] = (int)para[0].n;
1177  }
1178  else
1179  {
1180  message(MSG_FATAL, &curf, err_baddeg_dd,
1181  degcount, nodes);
1182  ret = FAILURE;
1183  }
1184  break;
1185  case KEY_NODEWEIGHTS_NW :
1186  nodeweight = (double) para[0].n;
1187  assert(g != NULL);
1188  assert(presol != NULL);
1189 
1190  if( stp_type != STP_NWSPG )
1191  stp_type = STP_NWSPG;
1192 
1193  if( Is_term(g->term[nwcount]) )
1194  presol->fixed += nodeweight;
1195  else
1196  /* add node-weight to edge-weights of all incoming edges */
1197  for( i = g->inpbeg[nwcount]; i != EAT_LAST; i = g->ieat[i] )
1198  g->cost[i] += nodeweight;
1199  nwcount++;
1200  break;
1201  case KEY_NODEWEIGHTS_END :
1202  curf.section = &section_table[0];
1203  break;
1204  case KEY_OBSTACLES_RR :
1205  assert(nobstacles > 0);
1206  if( obstacle_coords == NULL )
1207  {
1208  assert(obstacle_counter == 0);
1209  SCIP_CALL( SCIPallocBufferArray(scip, &obstacle_coords, 4) );
1210  for( i = 0; i < 4; i++ )
1211  SCIP_CALL( SCIPallocBufferArray(scip, &(obstacle_coords[i]), nobstacles) ); /*lint !e866*/
1212  }
1213  for( i = 0; i < 4; i++ )
1214  obstacle_coords[i][obstacle_counter] = (int)para[i].n;
1215  obstacle_counter++;
1216  break;
1217  case KEY_OBSTACLES_END :
1218  curf.section = &section_table[0];
1219 
1220  if( obstacle_counter != nobstacles )
1221  {
1222  message(MSG_FATAL, &curf, "obstacle number does not match coordinates \n");
1223  ret = FAILURE;
1224  break;
1225  }
1226  if( scaled_coordinates == NULL )
1227  {
1228  message(MSG_FATAL, &curf, "coordinates not given \n");
1229  ret = FAILURE;
1230  break;
1231  }
1232  assert(g == NULL);
1233 
1234  // todo fix problem with edges over obstacles
1235  message(MSG_FATAL, &curf, "Obstacle avoiding RSMT problems are currently not supported in this format \n");
1236 
1237  SCIP_CALL( graph_obstgrid_create(scip, graph, scaled_coordinates, obstacle_coords, nodes, grid_dim, nobstacles, scale_order) );
1238  g = *graph;
1239  if( obstacle_coords != NULL )
1240  for( i = 3; i >= 0; i-- )
1241  SCIPfreeBufferArrayNull(scip, &(obstacle_coords[i]));
1242  SCIPfreeBufferArrayNull(scip, &(obstacle_coords));
1243  break;
1244  case KEY_TERMINALS_END :
1245  if( transformed == 0 )
1246  {
1247  if( stp_type == STP_RMWCSP )
1248  {
1249  assert(nodes == termcount);
1250  if( g != NULL )
1251  {
1252  SCIP_CALL( graph_pc_2rmw(scip, g) );
1253  }
1254  else
1255  {
1256  message(MSG_FATAL, &curf, "graph not initialized \n");
1257  ret = FAILURE;
1258  break;
1259  }
1260  }
1261  else if( stp_type == STP_MWCSP )
1262  {
1263  assert(nodes == termcount);
1264  if( g != NULL )
1265  {
1266  SCIP_CALL( graph_pc_2mw(scip, g, g->prize) );
1267  }
1268  else
1269  {
1270  message(MSG_FATAL, &curf, "graph not initialized \n");
1271  ret = FAILURE;
1272  break;
1273  }
1274  }
1275  else if( stp_type == STP_PCSPG )
1276  {
1277  SCIP_CALL( graph_pc_2pc(scip, g) );
1278  }
1279  else if( stp_type == STP_RPCSPG )
1280  {
1281  SCIP_CALL( graph_pc_2rpc(scip, g) );
1282  }
1283  }
1284  curf.section = &section_table[0];
1285  break;
1287  terms = (int)para[0].n;
1288  assert(terms > 0);
1289 
1290  if( stp_type == STP_MWCSP || stp_type == STP_RMWCSP )
1291  {
1292  assert(terms == nodes);
1293  assert(g != NULL);
1294  if( g->prize == NULL )
1295  SCIP_CALL( graph_pc_init(scip, g, terms, -1) );
1296  }
1297  break;
1298  case KEY_TERMINALS_GROUPS :
1299  assert(stp_type == STP_GSTP);
1300  tgroups = (int)para[0].n;
1301  presol->fixed -= tgroups * 1e+8;
1302  for( i = 0; i < tgroups; i++ )
1303  {
1304  graph_knot_add(g, 0);
1305  }
1306  break;
1307  case KEY_TERMINALS_ROOT :
1308  assert(g != NULL);
1309 
1310  if ((int)para[0].n <= nodes)
1311  {
1312  g->source = (int)para[0].n - 1;
1313  graph_knot_chg(g, (int)para[0].n - 1, 0);
1314  }
1315  else
1316  {
1317  message(MSG_FATAL, &curf, err_badroot_dd,
1318  (int)para[0].n, nodes);
1319  ret = FAILURE;
1320  }
1321  break;
1322  case KEY_TERMINALS_ROOTP :
1323  assert(g != NULL);
1324  assert(terms > 0);
1325  g->source = (int)para[0].n - 1;
1326  graph_knot_chg(g, (int)para[0].n - 1, 0);
1327  stp_type = STP_RPCSPG;
1328  if( g->prize == NULL )
1329  SCIP_CALL( graph_pc_init(scip, g, nodes, -1) );
1330 
1331  g->prize[(int)para[0].n - 1] = FARAWAY;
1332  break;
1333  case KEY_TERMINALS_T :
1334  if( stp_type == STP_MWCSP || stp_type == STP_RMWCSP )
1335  {
1336  assert(g != NULL);
1337  assert(g->prize != NULL);
1338  g->prize[(int)para[0].n - 1] = (double)para[1].n;
1339  if( SCIPisGT(scip, (double)para[1].n, 0.0) )
1340  presol->fixed -= (double)para[1].n;
1341  termcount++;
1342  }
1343  else
1344  graph_knot_chg(g, (int)para[0].n - 1, 0);
1345  break;
1346  case KEY_TERMINALS_TG :
1347  assert(g != NULL);
1348  assert(tgroups > 0);
1349  graph_edge_add(scip, g, (int)para[0].n - 1, g->knots - tgroups + (int)para[1].n - 1, 1e+8, 1e+8);
1350  assert(Is_term(g->term[g->knots - tgroups + (int)para[1].n - 1]));
1351  break;
1352  case KEY_TERMINALS_TP :
1353  assert(g != NULL);
1354  graph_knot_chg(g, (int)para[0].n - 1, 0);
1355  if( g->prize == NULL )
1356  {
1357  assert(stp_type != STP_RPCSPG);
1358  stp_type = STP_PCSPG;
1359  SCIP_CALL( graph_pc_init(scip, g, nodes, -1) );
1360  }
1361  g->prize[(int)para[0].n - 1] = (double)para[1].n;
1362  termcount++;
1363  break;
1364  case KEY_TERMINALS_TR :
1365  assert(stp_type == STP_RMWCSP);
1366  assert(g != NULL);
1367  assert(g->prize != NULL);
1368  g->prize[(int)para[0].n - 1] = FARAWAY;
1369  presol->fixed -= (double)para[1].n;
1370  graph_knot_chg(g, (int)para[0].n - 1, 0);
1371  termcount++;
1372  break;
1373  case KEY_COORDINATES_DD :
1374  /* in this case coordinates are not needed */
1375  if( terms > 0 )
1376  {
1377  ret = SUCCESS;
1378  stop_input = TRUE;
1379  break;
1380  }
1381  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 2, nodes) );
1382  break;
1383  case KEY_COORDINATES_DDD :
1384  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 3, nodes) );
1385  break;
1386  case KEY_COORDINATES_DDDD :
1387  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 4, nodes) );
1388  break;
1389  case KEY_COORDINATES_DDDDD :
1390  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 5, nodes) );
1391  break;
1392  case KEY_COORDINATES_DDDDDD :
1393  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 6, nodes) );
1394  break;
1396  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 7, nodes) );
1397  break;
1399  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 8, nodes) );
1400  break;
1401  case KEY_COORDINATES_END :
1402  assert(g == NULL);
1403  assert(grid_dim > 1);
1404 
1405  curf.section = &section_table[0];
1406  if( termcount != nodes )
1407  {
1408  message(MSG_FATAL, &curf, "node number does not match coordinates \n");
1409  ret = FAILURE;
1410  break;
1411  }
1412 
1413  /* scale all coordinates such that they are integers */
1414  SCIP_CALL( scale_coords(coordinates, &scaled_coordinates, &scale_order, nodes, grid_dim) );
1415 
1416  if( coordinates != NULL )
1417  for( i = 0; i < grid_dim; i++ )
1418  SCIPfreeMemoryArrayNull(scip, &(coordinates[i]));
1419 
1420  SCIPfreeMemoryArrayNull(scip, &coordinates);
1421 
1422  if( stp_type != STP_OARSMT )
1423  {
1424  SCIP_CALL( graph_grid_create(scip, graph, scaled_coordinates, nodes, grid_dim, scale_order) );
1425  g = *graph;
1426  }
1427 
1428  break;
1429  case KEY_COORDINATES_GRID :
1430  break;
1431  case KEY_PRESOLVE_FIXED :
1432  if (presol != NULL)
1433  presol->fixed += (double)para[0].n;
1434  break;
1435  case KEY_PRESOLVE_DATE :
1436  (void)printf("Found presolve information %s\n",
1437  para[0].s);
1438  break;
1439  case KEY_PRESOLVE_LOWER :
1440  if (presol != NULL)
1441  presol->lower = (double)para[0].n;
1442  break;
1443  case KEY_PRESOLVE_UPPER :
1444  if (presol != NULL)
1445  presol->upper = (double)para[0].n;
1446  break;
1447  case KEY_PRESOLVE_TIME :
1448  if (presol != NULL)
1449  presol->time = (int)para[0].n;
1450  break;
1451  case KEY_PRESOLVE_EA :
1452  break;
1453  case KEY_PRESOLVE_EC :
1454  break;
1455  case KEY_PRESOLVE_ED :
1456  break;
1457  case KEY_PRESOLVE_ES :
1458  break;
1459  default :
1460  /* CONSTCOND */
1461  assert(FALSE);
1462  break;
1463  }
1464  }
1465  }
1466  }
1467  }
1468  /* Was there an error in an included file ?
1469  * If so, close the main file.
1470  */
1471  if( save.fp != NULL )
1472  (void)fclose(save.fp);
1473 
1474  /* Close the actual file anyway. Since we stop at encountering
1475  * a line with "EOF" on it, this will be the normal case.
1476  */
1477  if( curf.fp != NULL )
1478  (void)fclose(curf.fp);
1479 
1480  if( ret == SUCCESS )
1481  {
1482  assert(g != NULL);
1483 
1484  if( g->source == UNKNOWN )
1485  {
1486  for( i = 0; i < g->knots; i++ )
1487  if ((g->term[i] == 0)
1488  && ((g->source < 0) || (g->grad[i] > g->grad[g->source])))
1489  g->source = i;
1490  }
1491 
1492  if( g->stp_type == UNKNOWN )
1493  {
1494  if( stp_type != UNKNOWN )
1495  g->stp_type = stp_type;
1496  else
1497  g->stp_type = STP_SPG;
1498  }
1499 
1500  (void)printf(msg_finish_dddd,
1501  g->knots, g->edges, g->terms, g->source);
1502 
1503  assert(graph_valid(g));
1504  return SCIP_OKAY;
1505  }
1506  else
1507  {
1508  if( obstacle_coords != NULL )
1509  {
1510  for( i = 0; i < 4; i++ )
1511  SCIPfreeBufferArrayNull(scip, &(obstacle_coords[i]));
1512  SCIPfreeBufferArrayNull(scip, &(obstacle_coords));
1513  }
1514  return SCIP_READERROR;
1515  }
1516 
1517 }
#define KEY_COMMENT_CREATOR
Definition: grphload.c:101
#define SECTION_EXISTEND
Definition: grphload.c:254
#define KEY_NODEWEIGHTS_NW
Definition: grphload.c:151
#define KEY_PRESOLVE_ES
Definition: grphload.c:148
SCIP_RETCODE graph_pc_2mw(SCIP *, GRAPH *, SCIP_Real *)
Definition: grphbase.c:1682
SCIP_RETCODE graph_pc_init(SCIP *, GRAPH *, int, int)
Definition: grphbase.c:766
#define KEY_PRESOLVE_EA
Definition: grphload.c:145
static SCIP_RETCODE scale_coords(double **coordinates, int ***scaled_coords, int *scale_order, int nnodes, int grid_dim)
Definition: grphload.c:771
Definition: grph.h:57
int source
Definition: grph.h:67
int sw_code
Definition: grphload.c:91
#define STP_MAGIC
Definition: grph.h:174
#define KEY_NODEWEIGHTS_END
Definition: grphload.c:152
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:70
static void message(unsigned int type, const CURF *curf, const char *msg,...)
Definition: grphload.c:317
#define MAX_KEYWORD_LEN
Definition: grphload.c:84
#define STP_GSTP
Definition: grph.h:49
#define KEY_GRAPH_A
Definition: grphload.c:108
#define MSG_DEBUG
Definition: grphload.c:59
#define SECTION_MISSING
Definition: grphload.c:253
SCIP_RETCODE graph_load(SCIP *scip, GRAPH **graph, const char *file, PRESOL *presol)
Definition: grphload.c:821
#define SCIP_MAXSTRLEN
Definition: def.h:279
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4328
int terms
Definition: grph.h:64
SCIP_Real upper
Definition: grph.h:136
SCIPInterval pow(const SCIPInterval &x, const SCIPInterval &y)
static int sec_cmp(const void *key, const void *section)
Definition: grphload.c:370
int mark
Definition: grphload.c:247
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
SCIP_RETCODE graph_obstgrid_create(SCIP *, GRAPH **, int **, int **, int, int, int, int)
Definition: grphbase.c:419
#define KEY_OBSTACLES_END
Definition: grphload.c:157
int *RESTRICT maxdeg
Definition: grph.h:78
#define KEY_TERMINALS_TG
Definition: grphload.c:119
#define EAT_LAST
Definition: grph.h:31
#define KEY_COMMENT_REMARK
Definition: grphload.c:103
static SCIP_RETCODE init_coordinates(SCIP *scip, GRAPH *g, PARA *para, double ***coordinates, int *grid_dim, int *termcount, int dim, int nodes)
Definition: grphload.c:695
#define KEY_SOLUTION_DATE
Definition: grphload.c:135
static char * strlower(char *s)
Definition: grphload.c:298
const char * format
Definition: grphload.c:92
#define FALSE
Definition: def.h:73
int *RESTRICT inpbeg
Definition: grph.h:74
#define MAX_ARGUMENTS
Definition: grphload.c:86
#define STP_RMWCSP
Definition: grph.h:50
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define DIRSEP
Definition: portab.h:79
#define STP_DHCSTP
Definition: grph.h:48
#define KEY_TERMINALS_ROOTP
Definition: grphload.c:118
#define KEY_GRAPH_E
Definition: grphload.c:107
#define MSG_INFO
Definition: grphload.c:58
SCIP_Real lower
Definition: grph.h:137
#define KEY_PRESOLVE_LOWER
Definition: grphload.c:142
#define FLAG_REQUIRED
Definition: grphload.c:251
char filename[MAX_PATH_LEN]
Definition: grphload.c:279
#define STP_PCSPG
Definition: grph.h:40
#define MSG_WARN
Definition: grphload.c:57
#define KEY_COORDINATES_END
Definition: grphload.c:131
const int flag
Definition: grphload.c:246
void graph_knot_chg(GRAPH *, int, int)
Definition: grphbase.c:2222
#define MAX_PATH_LEN
Definition: grphload.c:76
static int open_file(CURF *curf, unsigned char main_file)
Definition: grphload.c:501
#define KEY_SOLUTION_VALUE
Definition: grphload.c:134
SCIP_RETCODE graph_pc_2rmw(SCIP *, GRAPH *)
Definition: grphbase.c:1741
#define KEY_GRAPH_NODES
Definition: grphload.c:105
#define KEY_COMMENT_NAME
Definition: grphload.c:99
#define FLAG_OPTIONAL
Definition: grphload.c:250
#define KEY_GRAPH_EDGES
Definition: grphload.c:106
#define KEY_TERMINALS_T
Definition: grphload.c:115
#define KEY_EOF
Definition: grphload.c:96
#define KEY_TERMINALS_ROOT
Definition: grphload.c:117
#define KEY_MAXDEGS_MD
Definition: grphload.c:154
#define KEY_COORDINATES_DD
Definition: grphload.c:123
#define FAILURE
Definition: portab.h:44
#define MSG_FATAL
Definition: grphload.c:55
#define SUCCESS
Definition: portab.h:41
#define STP_SAP
Definition: grph.h:39
int stp_type
Definition: grph.h:127
#define KEY_PRESOLVE_DATE
Definition: grphload.c:140
#define KEY_PRESOLVE_ED
Definition: grphload.c:147
#define KEY_COORDINATES_DDDDDDDD
Definition: grphload.c:129
#define KEY_PRESOLVE_EC
Definition: grphload.c:146
#define VERSION_MINOR
Definition: grph.h:176
SCIP_RETCODE graph_pc_2rpc(SCIP *, GRAPH *)
Definition: grphbase.c:1601
#define STP_DCSTP
Definition: grph.h:43
#define KEY_HOPCONS_FACTOR
Definition: grphload.c:160
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIP_Real * prize
Definition: grph.h:82
FILE * fp
Definition: grphload.c:281
int *RESTRICT grad
Definition: grph.h:73
#define KEY_TERMINALS_TERMINALS
Definition: grphload.c:114
struct section * section
Definition: grphload.c:282
#define NULL
Definition: lpi_spx1.cpp:155
#define KEY_COORDINATES_DDDD
Definition: grphload.c:125
const char * extension
Definition: grphload.c:245
int knots
Definition: grph.h:62
#define SCIP_CALL(x)
Definition: def.h:370
static int get_scale_order(SCIP_Real number)
Definition: grphload.c:733
#define STP_NWSPG
Definition: grph.h:42
#define KEY_COORDINATES_DDDDD
Definition: grphload.c:126
Definition: grphload.c:88
#define KEY_PRESOLVE_UPPER
Definition: grphload.c:143
#define FARAWAY
Definition: grph.h:156
#define STP_SPG
Definition: grph.h:38
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
#define KEY_GRAPH_AA
Definition: grphload.c:109
#define KEY_SOLUTION_TIME
Definition: grphload.c:136
#define KEY_TERMINALS_TP
Definition: grphload.c:116
#define KEY_COORDINATES_DDDDDD
Definition: grphload.c:127
#define SCIP_Bool
Definition: def.h:70
int *RESTRICT ieat
Definition: grph.h:102
#define MAX_STRING_LEN
Definition: grphload.c:85
const char * keyword
Definition: grphload.c:90
#define STP_MWCSP
Definition: grph.h:47
double n
Definition: grphload.c:287
int *RESTRICT tail
Definition: grph.h:95
int time
Definition: grph.h:138
#define KEY_SOLUTION_STEINER
Definition: grphload.c:137
const char * name
Definition: grphload.c:244
static const struct key keyword_table[]
Definition: grphload.c:164
static struct section section_table[]
Definition: grphload.c:258
int *RESTRICT term
Definition: grph.h:68
#define KEY_GRAPH_HOPLIMIT
Definition: grphload.c:111
static int get_arguments(const CURF *curf, const char *format, const char *s, PARA *para)
Definition: grphload.c:388
static long * number
includes various files containing graph methods used for Steiner tree problems
#define EXTSEP
Definition: grphload.c:81
#define KEY_TERMINALS_END
Definition: grphload.c:113
Portable defintions.
static int start_section(const char *pathname, const char *basename, CURF *curf, CURF *save, const char *s)
Definition: grphload.c:597
#define KEY_SOLUTION_S
Definition: grphload.c:138
#define Is_term(a)
Definition: grph.h:168
#define KEY_END
Definition: grphload.c:97
union parameter PARA
SCIP_Real * cost
Definition: grph.h:94
#define KEY_PRESOLVE_TIME
Definition: grphload.c:144
#define KEY_COMMENT_DATE
Definition: grphload.c:100
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10604
char s[MAX_STRING_LEN]
Definition: grphload.c:288
#define SCIP_Real
Definition: def.h:163
#define KEY_COMMENT_PROBLEM
Definition: grphload.c:102
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define KEY_OBSTACLES_RR
Definition: grphload.c:156
#define KEY_PRESOLVE_FIXED
Definition: grphload.c:141
int edges
Definition: grph.h:92
void graph_knot_add(GRAPH *, int)
Definition: grphbase.c:2200
#define VERSION_MAJOR
Definition: grph.h:175
SCIP_Real fixed
Definition: grph.h:135
#define VERBOSE
Definition: grphload.c:61
#define KEY_GRAPH_OBSTACLES
Definition: grphload.c:110
#define KEY_COORDINATES_GRID
Definition: grphload.c:132
#define MAX_LINE_LEN
Definition: grphload.c:83
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define KEY_COORDINATES_DDDDDDD
Definition: grphload.c:128
#define STP_RSMT
Definition: grph.h:45
SCIP_RETCODE graph_pc_2pc(SCIP *, GRAPH *)
Definition: grphbase.c:1520
#define nnodes
Definition: gastrans.c:65
#define KEY_HOPCONS_LIM
Definition: grphload.c:159
#define STP_OARSMT
Definition: grph.h:46
#define KEY_COORDINATES_DDD
Definition: grphload.c:124
#define MSG_ERROR
Definition: grphload.c:56
#define KEY_TERMINALS_GROUPS
Definition: grphload.c:120
#define KEY_TREE_S
Definition: grphload.c:162
int hoplimit
Definition: grph.h:89
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
#define STP_RPCSPG
Definition: grph.h:41
#define KEY_TERMINALS_TR
Definition: grphload.c:121
static int key_cmp(const void *key, const void *elem)
Definition: grphload.c:353
SCIP_RETCODE graph_grid_create(SCIP *, GRAPH **, int **, int, int, int)
Definition: grphbase.c:582
#define KEY_SECTION
Definition: grphload.c:95
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: grphbase.c:3495
struct current_file CURF