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
strlower(char * s)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 /*---------------------------------------------------------------------------*/
message(unsigned int type,const CURF * curf,const char * msg,...)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 /*---------------------------------------------------------------------------*/
key_cmp(const void * key,const void * elem)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 /*---------------------------------------------------------------------------*/
sec_cmp(const void * key,const void * section)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 /*---------------------------------------------------------------------------*/
get_arguments(const CURF * curf,const char * format,const char * s,PARA * para)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 /*---------------------------------------------------------------------------*/
open_file(CURF * curf,unsigned char main_file)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 /*---------------------------------------------------------------------------*/
start_section(const char * pathname,const char * basename,CURF * curf,CURF * save,const char * s)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 §ion_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 = §ion_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
init_coordinates(SCIP * scip,GRAPH * g,PARA * para,double *** coordinates,int * grid_dim,int * termcount,int dim,int nodes)695 SCIP_RETCODE init_coordinates(
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
get_scale_order(SCIP_Real number)733 int get_scale_order(
734 SCIP_Real number
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
scale_coords(double ** coordinates,int *** scaled_coords,int * scale_order,int nnodes,int grid_dim)771 SCIP_RETCODE scale_coords(
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 /*---------------------------------------------------------------------------*/
graph_load(SCIP * scip,GRAPH ** graph,const char * file,PRESOL * presol)821 SCIP_RETCODE graph_load(
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 = §ion_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 = §ion_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 = §ion_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 = §ion_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 = §ion_table[0];
1285 break;
1286 case KEY_TERMINALS_TERMINALS :
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;
1395 case KEY_COORDINATES_DDDDDDD :
1396 SCIP_CALL( init_coordinates(scip, g, para, &coordinates, &grid_dim, &termcount, 7, nodes) );
1397 break;
1398 case KEY_COORDINATES_DDDDDDDD :
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 = §ion_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 }
1518