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-2018 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 scip.zib.de. */
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_STRING_LEN];
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_STRING_LEN];
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)sprintf(curf.filename, "%s%s",
918  pathname,
919  basename);
920 
921  /* Open the file...
922  */
923  if (!open_file(&curf, TRUE))
924  {
925  /* We read while a file is open...
926  */
927  while((curf.fp != NULL) && !stop_input)
928  {
929  /* Read a line.
930  */
931  if ((s = fgets(buffer, (int) sizeof(buffer), curf.fp)) == NULL)
932  {
933  /* No more lines available, so we can close the file.
934  */
935  (void)fclose(curf.fp);
936 
937  /* If we are in an included file, we come back to our
938  * main file. Otherwise fp_save is NULL and than fp will
939  * get NULL so we're finished.
940  */
941  curf = save;
942  save = curf_null;
943 
944  continue;
945  }
946  /* Count line number
947  */
948  curf.line++;
949 
950  /* Find the start of the interesting part of an inputline.
951  */
952  while(isspace(*s))
953  s++;
954 
955  /* Find the end of the interesting portion of an input line.
956  * Either the start of a comment or the final NL or CR.
957  * Since all lines but the last must have at least a NL
958  * t is nearly never NULL.
959  */
960  if ((t = strpbrk(s, endofline)) != NULL)
961  *t = '\0';
962 
963  /* Is there an interesting part left ?
964  */
965  if (*s == '\0')
966  continue;
967 
968  /* Build a keyword of form "sectionname.keyword"
969  */
970  (void)strcpy(keyword, curf.section->name);
971 
972  i = (int)strlen(keyword);
973  keyword[i] = '.';
974 
975  for(i++;
976  (i < MAX_KEYWORD_LEN - 1) && (isalpha(*s) || (*s == '_'));
977  i++, s++)
978  keyword[i] = (char)tolower(*s);
979 
980  keyword[i] = '\0';
981 
982  /* Skip junk following the keyword.
983  */
984  while((*s != '\0') && (strchr(separator, *s) != NULL))
985  s++;
986 
987  if( strcmp(keyword,"comments") == 0 )
988  keyword[i - 1] = '\0';
989 
990  /* Did we know the keyword ?
991  */
992  p = (struct key*)bsearch(keyword, keyword_table,
993  sizeof(keyword_table) / sizeof(struct key),
994  sizeof(struct key), key_cmp);
995 
996  if (p == NULL)
997  message(MSG_ERROR, &curf, err_unknown_s, keyword);
998  else
999  {
1000  char newformat[5] = "";
1001  assert(p != NULL);
1002 
1003  message(MSG_DEBUG, &curf, msg_keyword_sd, p->keyword, p->sw_code);
1004 
1005  /* Yes, so lets get the rest of the line if possible
1006  */
1007  if( (stp_type == STP_MWCSP || stp_type == STP_RMWCSP) && p->format != NULL && (p->sw_code == KEY_TERMINALS_T || p->sw_code == KEY_GRAPH_E) )
1008  strcpy(newformat, "nn");
1009  else if( stp_type == STP_SAP && p->sw_code == KEY_GRAPH_A )
1010  strcpy(newformat, "nnnn");
1011 
1012  if( p->format == NULL || !get_arguments(&curf, (const char*)( newformat[0] != '\0' ? newformat : p->format ), s, para) )
1013  {
1014  /* Now, what should we do ?
1015  */
1016  switch(p->sw_code)
1017  {
1018  case KEY_SECTION : /* a new Section starts. */
1019  if (save.fp == NULL)
1020  stop_input = start_section(pathname, basename,
1021  &curf, &save, s);
1022  else
1023  {
1024  message(MSG_FATAL, &curf, err_include_v);
1025  stop_input = TRUE;
1026  }
1027  if (!stop_input)
1028  message(MSG_INFO, &curf, msg_newsect_s, curf.section->name);
1029  break;
1030  case KEY_END : /* END found. */
1031  curf.section = &section_table[0];
1032  break;
1033  case KEY_TREE_S : /* fall through */
1034  case KEY_EOF : /* EOF found */
1035  ret = SUCCESS;
1036  stop_input = TRUE;
1037 
1038  /* Test if all required section were found.
1039  */
1040  for(i = 0; (unsigned)i < sizeof(section_table) / sizeof(struct section); i++)
1041  {
1042  if ((section_table[i].flag & FLAG_REQUIRED)
1043  && !(section_table[i].mark & SECTION_EXISTEND))
1044  {
1045  message(MSG_FATAL, &curf, err_missing_s, section_table[i].name);
1046  ret = FAILURE;
1047  }
1048  }
1049  break;
1050  case KEY_COMMENT_NAME :
1051  case KEY_COMMENT_DATE :
1052  case KEY_COMMENT_CREATOR :
1053  case KEY_COMMENT_PROBLEM :
1054  (void)printf("Problem: [%s]\n", para[0].s);
1055  if( strcmp(para[0].s, "SPG") == 0 )
1056  stp_type = STP_SPG;
1057  else if( strcmp(para[0].s, "PCSPG") == 0
1058  || strcmp(para[0].s, "Prize-Collecting Steiner Problem in Graphs") == 0 )
1059  stp_type = STP_PCSPG;
1060  else if( strcmp(para[0].s, "RPCST") == 0
1061  || strcmp(para[0].s, "Rooted Prize-Collecting Steiner Problem in Graphs") == 0 )
1062  stp_type = STP_RPCSPG;
1063  else if( strcmp(para[0].s, "NWSPG") == 0 )
1064  stp_type = STP_NWSPG;
1065  else if( strcmp(para[0].s, "DCST") == 0 )
1066  stp_type = STP_DCSTP;
1067  else if( strcmp(para[0].s, "RSMT") == 0 )
1068  stp_type = STP_RSMT;
1069  else if( strcmp(para[0].s, "OARSMT") == 0 )
1070  stp_type = STP_OARSMT;
1071  else if( strcmp(para[0].s, "Maximum Node Weight Connected Subgraph") == 0
1072  || strcmp(para[0].s, "MWCS") == 0 )
1073  stp_type = STP_MWCSP;
1074  else if( strcmp(para[0].s, "Rooted Maximum Node Weight Connected Subgraph") == 0
1075  || strcmp(para[0].s, "RMWCS") == 0 )
1076  stp_type = STP_RMWCSP;
1077  else if( strcmp(para[0].s, "HCDST") == 0 )
1078  stp_type = STP_DHCSTP;
1079  else if( strcmp(para[0].s, "SAP") == 0 )
1080  stp_type = STP_SAP;
1081  else if( strcmp(para[0].s, "GSTP") == 0 )
1082  stp_type = STP_GSTP;
1083  break;
1084  case KEY_COMMENT_REMARK :
1085  (void)printf("Comment: [%s]\n", para[0].s);
1086  if( strcmp(para[0].s, "Transformed") == 0 )
1087  transformed = 1;
1088  break;
1089  case KEY_GRAPH_NODES :
1090  assert(para != NULL);
1091  nodes = (int)para[0].n;
1092  break;
1093  case KEY_GRAPH_OBSTACLES :
1094  nobstacles = (int)para[0].n;
1095  if( nobstacles > 0 )
1096  stp_type = STP_OARSMT;
1097  break;
1098  case KEY_GRAPH_HOPLIMIT :
1099  hoplimit = (int)para[0].n;
1100  stp_type = STP_DHCSTP;
1101  break;
1102  case KEY_GRAPH_EDGES :
1103  edges = (int)para[0].n;
1104  break;
1105  case KEY_GRAPH_A :
1106  case KEY_GRAPH_AA :
1107  case KEY_GRAPH_E :
1108  if( (int)para[0].n > nodes || (int)para[1].n > nodes )
1109  {
1110  message(MSG_FATAL, &curf, err_badedge_ddd,
1111  (int)para[0].n, (int)para[1].n, nodes);
1112  ret = FAILURE;
1113  break;
1114  }
1115 
1116  if( g == NULL )
1117  {
1118  if( stp_type == STP_GSTP )
1119  SCIP_CALL( graph_init(scip, graph, nodes * 2, edges * 2 + nodes * nodes, 1) );
1120  else
1121  SCIP_CALL( graph_init(scip, graph, nodes, edges * 2, 1) );
1122 
1123  g = *graph;
1124  assert(g != NULL);
1125  assert(g->source == UNKNOWN);
1126  for( i = 0; i < nodes; i++ )
1127  graph_knot_add(g, -1);
1128 
1129  if( stp_type == STP_DHCSTP )
1130  {
1131  assert(hoplimit != UNKNOWN);
1132  g->hoplimit = hoplimit;
1133  }
1134  }
1135 
1136  if( stp_type == STP_DHCSTP )
1137  {
1138  tail = (int)para[0].n - 1;
1139  head = (int)para[1].n - 1;
1140  /* check whether the anti-parallel arc has already been added */
1141  for( i = g->inpbeg[head]; i != EAT_LAST; i = g->ieat[i] )
1142  if( g->tail[i] == tail )
1143  break;
1144  if( i == EAT_LAST )
1145  graph_edge_add(scip, g, tail, head, (double)para[2].n, FARAWAY);
1146  else
1147  g->cost[i] = (double)para[2].n;
1148 
1149  }
1150  else if( stp_type == STP_SAP )
1151  {
1152  graph_edge_add(scip, g, (int)para[0].n - 1, (int)para[1].n - 1, (double)para[2].n, (double)para[3].n);
1153  }
1154  else if( stp_type == STP_MWCSP || stp_type == STP_RMWCSP )
1155  {
1156  graph_edge_add(scip, g, (int)para[0].n - 1, (int)para[1].n - 1, 0.0, 0.0);
1157  }
1158  else
1159  {
1160  graph_edge_add(scip, g, (int)para[0].n - 1, (int)para[1].n - 1,
1161  (double)para[2].n,
1162  (p->sw_code == KEY_GRAPH_E)
1163  ? (double)para[2].n
1164  : (double)para[3].n);
1165  }
1166  break;
1167  case KEY_MAXDEGS_MD :
1168  assert(g != NULL);
1169  assert((int)para[0].n >= 0);
1170 
1171  if( degcount < nodes )
1172  {
1173  if( g->maxdeg == NULL )
1174  {
1175  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->maxdeg), nodes ) );
1176  stp_type = STP_DCSTP;
1177  }
1178  g->maxdeg[degcount++] = (int)para[0].n;
1179  }
1180  else
1181  {
1182  message(MSG_FATAL, &curf, err_baddeg_dd,
1183  degcount, nodes);
1184  ret = FAILURE;
1185  }
1186  break;
1187  case KEY_NODEWEIGHTS_NW :
1188  nodeweight = (double) para[0].n;
1189  assert(g != NULL);
1190  assert(presol != NULL);
1191 
1192  if( stp_type != STP_NWSPG )
1193  stp_type = STP_NWSPG;
1194 
1195  if( Is_term(g->term[nwcount]) )
1196  presol->fixed += nodeweight;
1197  else
1198  /* add node-weight to edge-weights of all incoming edges */
1199  for( i = g->inpbeg[nwcount]; i != EAT_LAST; i = g->ieat[i] )
1200  g->cost[i] += nodeweight;
1201  nwcount++;
1202  break;
1203  case KEY_NODEWEIGHTS_END :
1204  curf.section = &section_table[0];
1205  break;
1206  case KEY_OBSTACLES_RR :
1207  assert(nobstacles > 0);
1208  if( obstacle_coords == NULL )
1209  {
1210  assert(obstacle_counter == 0);
1211  SCIP_CALL( SCIPallocBufferArray(scip, &obstacle_coords, 4) );
1212  for( i = 0; i < 4; i++ )
1213  SCIP_CALL( SCIPallocBufferArray(scip, &(obstacle_coords[i]), nobstacles) ); /*lint !e866*/
1214  }
1215  for( i = 0; i < 4; i++ )
1216  obstacle_coords[i][obstacle_counter] = (int)para[i].n;
1217  obstacle_counter++;
1218  break;
1219  case KEY_OBSTACLES_END :
1220  curf.section = &section_table[0];
1221 
1222  if( obstacle_counter != nobstacles )
1223  {
1224  message(MSG_FATAL, &curf, "obstacle number does not match coordinates \n");
1225  ret = FAILURE;
1226  break;
1227  }
1228  if( scaled_coordinates == NULL )
1229  {
1230  message(MSG_FATAL, &curf, "coordinates not given \n");
1231  ret = FAILURE;
1232  break;
1233  }
1234  assert(g == NULL);
1235 
1236  // todo fix problem with edges over obstacles
1237  message(MSG_FATAL, &curf, "Obstacle avoiding RSMT problems are currently not supported in this format \n");
1238 
1239  SCIP_CALL( graph_obstgrid_create(scip, graph, scaled_coordinates, obstacle_coords, nodes, grid_dim, nobstacles, scale_order) );
1240  g = *graph;
1241  if( obstacle_coords != NULL )
1242  for( i = 3; i >= 0; i-- )
1243  SCIPfreeBufferArrayNull(scip, &(obstacle_coords[i]));
1244  SCIPfreeBufferArrayNull(scip, &(obstacle_coords));
1245  break;
1246  case KEY_TERMINALS_END :
1247  if( transformed == 0 )
1248  {
1249  if( stp_type == STP_RMWCSP )
1250  {
1251  assert(nodes == termcount);
1252  if( g != NULL )
1253  {
1254  SCIP_CALL( graph_pc_2rmw(scip, g) );
1255  }
1256  else
1257  {
1258  message(MSG_FATAL, &curf, "graph not initialized \n");
1259  ret = FAILURE;
1260  break;
1261  }
1262  }
1263  else if( stp_type == STP_MWCSP )
1264  {
1265  assert(nodes == termcount);
1266  if( g != NULL )
1267  {
1268  SCIP_CALL( graph_pc_2mw(scip, g, g->prize) );
1269  }
1270  else
1271  {
1272  message(MSG_FATAL, &curf, "graph not initialized \n");
1273  ret = FAILURE;
1274  break;
1275  }
1276  }
1277  else if( stp_type == STP_PCSPG )
1278  {
1279  SCIP_CALL( graph_pc_2pc(scip, g) );
1280  }
1281  else if( stp_type == STP_RPCSPG )
1282  {
1283  SCIP_CALL( graph_pc_2rpc(scip, g) );
1284  }
1285  }
1286  curf.section = &section_table[0];
1287  break;
1289  terms = (int)para[0].n;
1290  assert(terms > 0);
1291 
1292  if( stp_type == STP_MWCSP || stp_type == STP_RMWCSP )
1293  {
1294  assert(terms == nodes);
1295  assert(g != NULL);
1296  if( g->prize == NULL )
1297  SCIP_CALL( graph_pc_init(scip, g, terms, -1) );
1298  }
1299  break;
1300  case KEY_TERMINALS_GROUPS :
1301  assert(stp_type == STP_GSTP);
1302  tgroups = (int)para[0].n;
1303  presol->fixed -= tgroups * 1e+8;
1304  for( i = 0; i < tgroups; i++ )
1305  {
1306  graph_knot_add(g, 0);
1307  }
1308  break;
1309  case KEY_TERMINALS_ROOT :
1310  assert(g != NULL);
1311 
1312  if ((int)para[0].n <= nodes)
1313  {
1314  g->source = (int)para[0].n - 1;
1315  graph_knot_chg(g, (int)para[0].n - 1, 0);
1316  }
1317  else
1318  {
1319  message(MSG_FATAL, &curf, err_badroot_dd,
1320  (int)para[0].n, nodes);
1321  ret = FAILURE;
1322  }
1323  break;
1324  case KEY_TERMINALS_ROOTP :
1325  assert(g != NULL);
1326  assert(terms > 0);
1327  g->source = (int)para[0].n - 1;
1328  graph_knot_chg(g, (int)para[0].n - 1, 0);
1329  stp_type = STP_RPCSPG;
1330  if( g->prize == NULL )
1331  SCIP_CALL( graph_pc_init(scip, g, nodes, -1) );
1332 
1333  g->prize[(int)para[0].n - 1] = FARAWAY;
1334  break;
1335  case KEY_TERMINALS_T :
1336  if( stp_type == STP_MWCSP || stp_type == STP_RMWCSP )
1337  {
1338  assert(g != NULL);
1339  assert(g->prize != NULL);
1340  g->prize[(int)para[0].n - 1] = (double)para[1].n;
1341  if( SCIPisGT(scip, (double)para[1].n, 0.0) )
1342  presol->fixed -= (double)para[1].n;
1343  termcount++;
1344  }
1345  else
1346  graph_knot_chg(g, (int)para[0].n - 1, 0);
1347  break;
1348  case KEY_TERMINALS_TG :
1349  assert(g != NULL);
1350  assert(tgroups > 0);
1351  graph_edge_add(scip, g, (int)para[0].n - 1, g->knots - tgroups + (int)para[1].n - 1, 1e+8, 1e+8);
1352  assert(Is_term(g->term[g->knots - tgroups + (int)para[1].n - 1]));
1353  break;
1354  case KEY_TERMINALS_TP :
1355  assert(g != NULL);
1356  graph_knot_chg(g, (int)para[0].n - 1, 0);
1357  if( g->prize == NULL )
1358  {
1359  assert(stp_type != STP_RPCSPG);
1360  stp_type = STP_PCSPG;
1361  SCIP_CALL( graph_pc_init(scip, g, nodes, -1) );
1362  }
1363  g->prize[(int)para[0].n - 1] = (double)para[1].n;
1364  termcount++;
1365  break;
1366  case KEY_TERMINALS_TR :
1367  assert(stp_type == STP_RMWCSP);
1368  assert(g != NULL);
1369  assert(g->prize != NULL);
1370  g->prize[(int)para[0].n - 1] = FARAWAY;
1371  presol->fixed -= (double)para[1].n;
1372  graph_knot_chg(g, (int)para[0].n - 1, 0);
1373  termcount++;
1374  break;
1375  case KEY_COORDINATES_DD :
1376  /* in this case coordinates are not needed */
1377  if( terms > 0 )
1378  {
1379  ret = SUCCESS;
1380  stop_input = TRUE;
1381  break;
1382  }
1383  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 2, nodes) );
1384  break;
1385  case KEY_COORDINATES_DDD :
1386  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 3, nodes) );
1387  break;
1388  case KEY_COORDINATES_DDDD :
1389  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 4, nodes) );
1390  break;
1391  case KEY_COORDINATES_DDDDD :
1392  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 5, nodes) );
1393  break;
1394  case KEY_COORDINATES_DDDDDD :
1395  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 6, nodes) );
1396  break;
1398  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 7, nodes) );
1399  break;
1401  SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 8, nodes) );
1402  break;
1403  case KEY_COORDINATES_END :
1404  assert(g == NULL);
1405  assert(grid_dim > 1);
1406 
1407  curf.section = &section_table[0];
1408  if( termcount != nodes )
1409  {
1410  message(MSG_FATAL, &curf, "node number does not match coordinates \n");
1411  ret = FAILURE;
1412  break;
1413  }
1414 
1415  /* scale all coordinates such that they are integers */
1416  SCIP_CALL( scale_coords(coordinates, &scaled_coordinates, &scale_order, nodes, grid_dim) );
1417 
1418  if( coordinates != NULL )
1419  for( i = 0; i < grid_dim; i++ )
1420  SCIPfreeMemoryArrayNull(scip, &(coordinates[i]));
1421 
1422  SCIPfreeMemoryArrayNull(scip, &coordinates);
1423 
1424  if( stp_type != STP_OARSMT )
1425  {
1426  SCIP_CALL( graph_grid_create(scip, graph, scaled_coordinates, nodes, grid_dim, scale_order) );
1427  g = *graph;
1428  }
1429 
1430  break;
1431  case KEY_COORDINATES_GRID :
1432  break;
1433  case KEY_PRESOLVE_FIXED :
1434  if (presol != NULL)
1435  presol->fixed += (double)para[0].n;
1436  break;
1437  case KEY_PRESOLVE_DATE :
1438  (void)printf("Found presolve information %s\n",
1439  para[0].s);
1440  break;
1441  case KEY_PRESOLVE_LOWER :
1442  if (presol != NULL)
1443  presol->lower = (double)para[0].n;
1444  break;
1445  case KEY_PRESOLVE_UPPER :
1446  if (presol != NULL)
1447  presol->upper = (double)para[0].n;
1448  break;
1449  case KEY_PRESOLVE_TIME :
1450  if (presol != NULL)
1451  presol->time = (int)para[0].n;
1452  break;
1453  case KEY_PRESOLVE_EA :
1454  break;
1455  case KEY_PRESOLVE_EC :
1456  break;
1457  case KEY_PRESOLVE_ED :
1458  break;
1459  case KEY_PRESOLVE_ES :
1460  break;
1461  default :
1462  /* CONSTCOND */
1463  assert(FALSE);
1464  break;
1465  }
1466  }
1467  }
1468  }
1469  }
1470  /* Was there an error in an included file ?
1471  * If so, close the main file.
1472  */
1473  if( save.fp != NULL )
1474  (void)fclose(save.fp);
1475 
1476  /* Close the actual file anyway. Since we stop at encountering
1477  * a line with "EOF" on it, this will be the normal case.
1478  */
1479  if( curf.fp != NULL )
1480  (void)fclose(curf.fp);
1481 
1482  if( ret == SUCCESS )
1483  {
1484  assert(g != NULL);
1485 
1486  if( g->source == UNKNOWN )
1487  {
1488  for( i = 0; i < g->knots; i++ )
1489  if ((g->term[i] == 0)
1490  && ((g->source < 0) || (g->grad[i] > g->grad[g->source])))
1491  g->source = i;
1492  }
1493 
1494  if( g->stp_type == UNKNOWN )
1495  {
1496  if( stp_type != UNKNOWN )
1497  g->stp_type = stp_type;
1498  else
1499  g->stp_type = STP_SPG;
1500  }
1501 
1502  (void)printf(msg_finish_dddd,
1503  g->knots, g->edges, g->terms, g->source);
1504 
1505  assert(graph_valid(g));
1506  return SCIP_OKAY;
1507  }
1508  else
1509  {
1510  if( obstacle_coords != NULL )
1511  {
1512  for( i = 0; i < 4; i++ )
1513  SCIPfreeBufferArrayNull(scip, &(obstacle_coords[i]));
1514  SCIPfreeBufferArrayNull(scip, &(obstacle_coords));
1515  }
1516  return SCIP_READERROR;
1517  }
1518 
1519 }
#define KEY_COMMENT_CREATOR
Definition: grphload.c:101
#define SECTION_EXISTEND
Definition: grphload.c:254
#define KEY_NODEWEIGHTS_NW
Definition: grphload.c:151
#define NULL
Definition: def.h:239
#define KEY_PRESOLVE_ES
Definition: grphload.c:148
SCIP_RETCODE graph_pc_2mw(SCIP *, GRAPH *, SCIP_Real *)
Definition: grphbase.c:1678
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:89
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:260
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4324
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:72
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:65
int *RESTRICT inpbeg
Definition: grph.h:74
#define MAX_ARGUMENTS
Definition: grphload.c:86
#define STP_RMWCSP
Definition: grph.h:50
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10017
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#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:2218
#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:1737
#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:1597
#define STP_DCSTP
Definition: grph.h:43
#define KEY_HOPCONS_FACTOR
Definition: grphload.c:160
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:143
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 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:351
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:130
#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:62
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
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#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
char s[MAX_STRING_LEN]
Definition: grphload.c:288
#define SCIP_Real
Definition: def.h:150
#define KEY_COMMENT_PROBLEM
Definition: grphload.c:102
#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:2196
#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:4081
#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:1516
#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:3491
struct current_file CURF