Scippy

SCIP

Solving Constraint Integer Programs

grphload.c File Reference

Detailed Description

Methods for loading Steiner problems in .stp format.

Author
Thorsten Koch
Daniel Rehfeldt

This file includes methods for reading a Steiner problem in .stp format.

A list of all interface methods can be found in grph.h.

Definition in file grphload.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <errno.h>
#include <assert.h>
#include <stdarg.h>
#include <unistd.h>
#include "portab.h"
#include "grph.h"

Go to the source code of this file.

Data Structures

struct  key
 
struct  section
 
struct  current_file
 
union  parameter
 

Macros

#define GRPHLOAD_C
 
#define MSG_FATAL   0
 
#define MSG_ERROR   1
 
#define MSG_WARN   2
 
#define MSG_INFO   3
 
#define MSG_DEBUG   4
 
#define VERBOSE   MSG_INFO
 
#define MAX_PATH_LEN   1024
 
#define EXTSEP   '.'
 
#define MAX_LINE_LEN   1024
 
#define MAX_KEYWORD_LEN   64
 
#define MAX_STRING_LEN   256
 
#define MAX_ARGUMENTS   8
 
#define KEY_SECTION   0001
 
#define KEY_EOF   9999
 
#define KEY_END   9998
 
#define KEY_COMMENT_NAME   1001
 
#define KEY_COMMENT_DATE   1002
 
#define KEY_COMMENT_CREATOR   1003
 
#define KEY_COMMENT_PROBLEM   1004
 
#define KEY_COMMENT_REMARK   1005
 
#define KEY_GRAPH_NODES   2001
 
#define KEY_GRAPH_EDGES   2002
 
#define KEY_GRAPH_E   2003
 
#define KEY_GRAPH_A   2004
 
#define KEY_GRAPH_AA   2005
 
#define KEY_GRAPH_OBSTACLES   2006
 
#define KEY_GRAPH_HOPLIMIT   2007
 
#define KEY_TERMINALS_END   3001
 
#define KEY_TERMINALS_TERMINALS   3002
 
#define KEY_TERMINALS_T   3003
 
#define KEY_TERMINALS_TP   3004
 
#define KEY_TERMINALS_ROOT   3005
 
#define KEY_TERMINALS_ROOTP   3006
 
#define KEY_TERMINALS_TG   3007
 
#define KEY_TERMINALS_GROUPS   3008
 
#define KEY_TERMINALS_TR   3009
 
#define KEY_COORDINATES_DD   4001
 
#define KEY_COORDINATES_DDD   4002
 
#define KEY_COORDINATES_DDDD   4003
 
#define KEY_COORDINATES_DDDDD   4004
 
#define KEY_COORDINATES_DDDDDD   4005
 
#define KEY_COORDINATES_DDDDDDD   4006
 
#define KEY_COORDINATES_DDDDDDDD   4007
 
#define KEY_COORDINATES_END   4011
 
#define KEY_COORDINATES_GRID   4012
 
#define KEY_SOLUTION_VALUE   4021
 
#define KEY_SOLUTION_DATE   4022
 
#define KEY_SOLUTION_TIME   4023
 
#define KEY_SOLUTION_STEINER   4024
 
#define KEY_SOLUTION_S   4025
 
#define KEY_PRESOLVE_DATE   5001
 
#define KEY_PRESOLVE_FIXED   5002
 
#define KEY_PRESOLVE_LOWER   5003
 
#define KEY_PRESOLVE_UPPER   5004
 
#define KEY_PRESOLVE_TIME   5005
 
#define KEY_PRESOLVE_EA   5006
 
#define KEY_PRESOLVE_EC   5007
 
#define KEY_PRESOLVE_ED   5008
 
#define KEY_PRESOLVE_ES   5009
 
#define KEY_NODEWEIGHTS_NW   6000
 
#define KEY_NODEWEIGHTS_END   6001
 
#define KEY_MAXDEGS_MD   8000
 
#define KEY_OBSTACLES_RR   9000
 
#define KEY_OBSTACLES_END   9001
 
#define KEY_HOPCONS_LIM   10000
 
#define KEY_HOPCONS_FACTOR   10001
 
#define KEY_TREE_S   11000
 
#define FLAG_OPTIONAL   1
 
#define FLAG_REQUIRED   2
 
#define SECTION_MISSING   0
 
#define SECTION_EXISTEND   1
 

Typedefs

typedef struct current_file CURF
 
typedef union parameter PARA
 

Functions

static char * strlower (char *s)
 
static void message (unsigned int type, const CURF *curf, const char *msg,...)
 
static int key_cmp (const void *key, const void *elem)
 
static int sec_cmp (const void *key, const void *section)
 
static int get_arguments (const CURF *curf, const char *format, const char *s, PARA *para)
 
static int open_file (CURF *curf, unsigned char main_file)
 
static int start_section (const char *pathname, const char *basename, CURF *curf, CURF *save, const char *s)
 
static SCIP_RETCODE init_coordinates (SCIP *scip, GRAPH *g, PARA *para, double ***coordinates, int *grid_dim, int *termcount, int dim, int nodes)
 
static int get_scale_order (SCIP_Real number)
 
static SCIP_RETCODE scale_coords (double **coordinates, int ***scaled_coords, int *scale_order, int nnodes, int grid_dim)
 
SCIP_RETCODE graph_load (SCIP *scip, GRAPH **graph, const char *file, PRESOL *presol)
 

Variables

static const struct key keyword_table []
 
static struct section section_table []
 

Macro Definition Documentation

◆ GRPHLOAD_C

#define GRPHLOAD_C

Definition at line 30 of file grphload.c.

◆ MSG_FATAL

#define MSG_FATAL   0

Definition at line 55 of file grphload.c.

Referenced by graph_load(), open_file(), and start_section().

◆ MSG_ERROR

#define MSG_ERROR   1

Definition at line 56 of file grphload.c.

Referenced by get_arguments(), and graph_load().

◆ MSG_WARN

#define MSG_WARN   2

Definition at line 57 of file grphload.c.

Referenced by open_file().

◆ MSG_INFO

#define MSG_INFO   3

Definition at line 58 of file grphload.c.

Referenced by graph_load().

◆ MSG_DEBUG

#define MSG_DEBUG   4

Definition at line 59 of file grphload.c.

Referenced by get_arguments(), and graph_load().

◆ VERBOSE

#define VERBOSE   MSG_INFO

Definition at line 61 of file grphload.c.

Referenced by message().

◆ MAX_PATH_LEN

#define MAX_PATH_LEN   1024

Definition at line 76 of file grphload.c.

Referenced by graph_load(), and start_section().

◆ EXTSEP

#define EXTSEP   '.'

Definition at line 81 of file grphload.c.

Referenced by graph_load(), and start_section().

◆ MAX_LINE_LEN

#define MAX_LINE_LEN   1024

Definition at line 83 of file grphload.c.

Referenced by graph_load().

◆ MAX_KEYWORD_LEN

#define MAX_KEYWORD_LEN   64

Definition at line 84 of file grphload.c.

Referenced by graph_load(), and start_section().

◆ MAX_STRING_LEN

#define MAX_STRING_LEN   256

Definition at line 85 of file grphload.c.

Referenced by get_arguments(), and open_file().

◆ MAX_ARGUMENTS

#define MAX_ARGUMENTS   8

Definition at line 86 of file grphload.c.

Referenced by graph_load().

◆ KEY_SECTION

#define KEY_SECTION   0001

Definition at line 95 of file grphload.c.

Referenced by graph_load().

◆ KEY_EOF

#define KEY_EOF   9999

Definition at line 96 of file grphload.c.

Referenced by graph_load().

◆ KEY_END

#define KEY_END   9998

Definition at line 97 of file grphload.c.

Referenced by graph_load().

◆ KEY_COMMENT_NAME

#define KEY_COMMENT_NAME   1001

Definition at line 99 of file grphload.c.

Referenced by graph_load().

◆ KEY_COMMENT_DATE

#define KEY_COMMENT_DATE   1002

Definition at line 100 of file grphload.c.

Referenced by graph_load().

◆ KEY_COMMENT_CREATOR

#define KEY_COMMENT_CREATOR   1003

Definition at line 101 of file grphload.c.

Referenced by graph_load().

◆ KEY_COMMENT_PROBLEM

#define KEY_COMMENT_PROBLEM   1004

Definition at line 102 of file grphload.c.

Referenced by graph_load().

◆ KEY_COMMENT_REMARK

#define KEY_COMMENT_REMARK   1005

Definition at line 103 of file grphload.c.

Referenced by graph_load().

◆ KEY_GRAPH_NODES

#define KEY_GRAPH_NODES   2001

Definition at line 105 of file grphload.c.

Referenced by graph_load().

◆ KEY_GRAPH_EDGES

#define KEY_GRAPH_EDGES   2002

Definition at line 106 of file grphload.c.

Referenced by graph_load().

◆ KEY_GRAPH_E

#define KEY_GRAPH_E   2003

Definition at line 107 of file grphload.c.

Referenced by graph_load().

◆ KEY_GRAPH_A

#define KEY_GRAPH_A   2004

Definition at line 108 of file grphload.c.

Referenced by graph_load().

◆ KEY_GRAPH_AA

#define KEY_GRAPH_AA   2005

Definition at line 109 of file grphload.c.

Referenced by graph_load().

◆ KEY_GRAPH_OBSTACLES

#define KEY_GRAPH_OBSTACLES   2006

Definition at line 110 of file grphload.c.

Referenced by graph_load().

◆ KEY_GRAPH_HOPLIMIT

#define KEY_GRAPH_HOPLIMIT   2007

Definition at line 111 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_END

#define KEY_TERMINALS_END   3001

Definition at line 113 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_TERMINALS

#define KEY_TERMINALS_TERMINALS   3002

Definition at line 114 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_T

#define KEY_TERMINALS_T   3003

Definition at line 115 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_TP

#define KEY_TERMINALS_TP   3004

Definition at line 116 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_ROOT

#define KEY_TERMINALS_ROOT   3005

Definition at line 117 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_ROOTP

#define KEY_TERMINALS_ROOTP   3006

Definition at line 118 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_TG

#define KEY_TERMINALS_TG   3007

Definition at line 119 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_GROUPS

#define KEY_TERMINALS_GROUPS   3008

Definition at line 120 of file grphload.c.

Referenced by graph_load().

◆ KEY_TERMINALS_TR

#define KEY_TERMINALS_TR   3009

Definition at line 121 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_DD

#define KEY_COORDINATES_DD   4001

Definition at line 123 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_DDD

#define KEY_COORDINATES_DDD   4002

Definition at line 124 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_DDDD

#define KEY_COORDINATES_DDDD   4003

Definition at line 125 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_DDDDD

#define KEY_COORDINATES_DDDDD   4004

Definition at line 126 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_DDDDDD

#define KEY_COORDINATES_DDDDDD   4005

Definition at line 127 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_DDDDDDD

#define KEY_COORDINATES_DDDDDDD   4006

Definition at line 128 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_DDDDDDDD

#define KEY_COORDINATES_DDDDDDDD   4007

Definition at line 129 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_END

#define KEY_COORDINATES_END   4011

Definition at line 131 of file grphload.c.

Referenced by graph_load().

◆ KEY_COORDINATES_GRID

#define KEY_COORDINATES_GRID   4012

Definition at line 132 of file grphload.c.

Referenced by graph_load().

◆ KEY_SOLUTION_VALUE

#define KEY_SOLUTION_VALUE   4021

Definition at line 134 of file grphload.c.

◆ KEY_SOLUTION_DATE

#define KEY_SOLUTION_DATE   4022

Definition at line 135 of file grphload.c.

◆ KEY_SOLUTION_TIME

#define KEY_SOLUTION_TIME   4023

Definition at line 136 of file grphload.c.

◆ KEY_SOLUTION_STEINER

#define KEY_SOLUTION_STEINER   4024

Definition at line 137 of file grphload.c.

◆ KEY_SOLUTION_S

#define KEY_SOLUTION_S   4025

Definition at line 138 of file grphload.c.

◆ KEY_PRESOLVE_DATE

#define KEY_PRESOLVE_DATE   5001

Definition at line 140 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_FIXED

#define KEY_PRESOLVE_FIXED   5002

Definition at line 141 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_LOWER

#define KEY_PRESOLVE_LOWER   5003

Definition at line 142 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_UPPER

#define KEY_PRESOLVE_UPPER   5004

Definition at line 143 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_TIME

#define KEY_PRESOLVE_TIME   5005

Definition at line 144 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_EA

#define KEY_PRESOLVE_EA   5006

Definition at line 145 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_EC

#define KEY_PRESOLVE_EC   5007

Definition at line 146 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_ED

#define KEY_PRESOLVE_ED   5008

Definition at line 147 of file grphload.c.

Referenced by graph_load().

◆ KEY_PRESOLVE_ES

#define KEY_PRESOLVE_ES   5009

Definition at line 148 of file grphload.c.

Referenced by graph_load().

◆ KEY_NODEWEIGHTS_NW

#define KEY_NODEWEIGHTS_NW   6000

Definition at line 151 of file grphload.c.

Referenced by graph_load().

◆ KEY_NODEWEIGHTS_END

#define KEY_NODEWEIGHTS_END   6001

Definition at line 152 of file grphload.c.

Referenced by graph_load().

◆ KEY_MAXDEGS_MD

#define KEY_MAXDEGS_MD   8000

Definition at line 154 of file grphload.c.

Referenced by graph_load().

◆ KEY_OBSTACLES_RR

#define KEY_OBSTACLES_RR   9000

Definition at line 156 of file grphload.c.

Referenced by graph_load().

◆ KEY_OBSTACLES_END

#define KEY_OBSTACLES_END   9001

Definition at line 157 of file grphload.c.

Referenced by graph_load().

◆ KEY_HOPCONS_LIM

#define KEY_HOPCONS_LIM   10000

Definition at line 159 of file grphload.c.

◆ KEY_HOPCONS_FACTOR

#define KEY_HOPCONS_FACTOR   10001

Definition at line 160 of file grphload.c.

◆ KEY_TREE_S

#define KEY_TREE_S   11000

Definition at line 162 of file grphload.c.

Referenced by graph_load().

◆ FLAG_OPTIONAL

#define FLAG_OPTIONAL   1

Definition at line 250 of file grphload.c.

◆ FLAG_REQUIRED

#define FLAG_REQUIRED   2

Definition at line 251 of file grphload.c.

Referenced by graph_load(), and start_section().

◆ SECTION_MISSING

#define SECTION_MISSING   0

Definition at line 253 of file grphload.c.

Referenced by graph_load().

◆ SECTION_EXISTEND

#define SECTION_EXISTEND   1

Definition at line 254 of file grphload.c.

Referenced by graph_load(), and start_section().

Typedef Documentation

◆ CURF

typedef struct current_file CURF

◆ PARA

typedef union parameter PARA

Function Documentation

◆ strlower()

static char* strlower ( char *  s)
static

Definition at line 298 of file grphload.c.

Referenced by open_file(), and start_section().

◆ message()

static void message ( unsigned int  type,
const CURF curf,
const char *  msg,
  ... 
)
static

◆ key_cmp()

static int key_cmp ( const void *  key,
const void *  elem 
)
static

Definition at line 353 of file grphload.c.

References key::keyword, and NULL.

◆ sec_cmp()

static int sec_cmp ( const void *  key,
const void *  section 
)
static

Definition at line 370 of file grphload.c.

References NULL.

Referenced by start_section().

◆ get_arguments()

static int get_arguments ( const CURF curf,
const char *  format,
const char *  s,
PARA para 
)
static

Definition at line 388 of file grphload.c.

References FAILURE, FALSE, MAX_STRING_LEN, message(), MSG_DEBUG, MSG_ERROR, parameter::n, NULL, pow(), parameter::s, SCIP_Bool, SUCCESS, and TRUE.

Referenced by graph_load().

◆ open_file()

static int open_file ( CURF curf,
unsigned char  main_file 
)
static

◆ start_section()

static int start_section ( const char *  pathname,
const char *  basename,
CURF curf,
CURF save,
const char *  s 
)
static

◆ init_coordinates()

static SCIP_RETCODE init_coordinates ( SCIP scip,
GRAPH g,
PARA para,
double ***  coordinates,
int *  grid_dim,
int *  termcount,
int  dim,
int  nodes 
)
static

Definition at line 695 of file grphload.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by graph_load().

◆ get_scale_order()

static int get_scale_order ( SCIP_Real  number)
static

Definition at line 733 of file grphload.c.

References SCIP_MAXSTRLEN, and SCIPsnprintf().

Referenced by scale_coords().

◆ scale_coords()

static SCIP_RETCODE scale_coords ( double **  coordinates,
int ***  scaled_coords,
int *  scale_order,
int  nnodes,
int  grid_dim 
)
static

Definition at line 771 of file grphload.c.

References get_scale_order(), nnodes, NULL, pow(), SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by graph_load().

◆ graph_load()

SCIP_RETCODE graph_load ( SCIP scip,
GRAPH **  graph,
const char *  file,
PRESOL presol 
)
Parameters
scipSCIP data structure
graphpointer to store the graph
filefile to load
presolpresolving struct

Definition at line 821 of file grphload.c.

References GRAPH::cost, DIRSEP, EAT_LAST, GRAPH::edges, EXTSEP, FAILURE, FALSE, FARAWAY, current_file::filename, presolve_info::fixed, section::flag, FLAG_REQUIRED, key::format, current_file::fp, get_arguments(), GRAPH::grad, graph_edge_add(), graph_grid_create(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_obstgrid_create(), graph_pc_2mw(), graph_pc_2pc(), graph_pc_2rmw(), graph_pc_2rpc(), graph_pc_init(), graph_valid(), GRAPH::hoplimit, GRAPH::ieat, init_coordinates(), GRAPH::inpbeg, Is_term, KEY_COMMENT_CREATOR, KEY_COMMENT_DATE, KEY_COMMENT_NAME, KEY_COMMENT_PROBLEM, KEY_COMMENT_REMARK, KEY_COORDINATES_DD, KEY_COORDINATES_DDD, KEY_COORDINATES_DDDD, KEY_COORDINATES_DDDDD, KEY_COORDINATES_DDDDDD, KEY_COORDINATES_DDDDDDD, KEY_COORDINATES_DDDDDDDD, KEY_COORDINATES_END, KEY_COORDINATES_GRID, KEY_END, KEY_EOF, KEY_GRAPH_A, KEY_GRAPH_AA, KEY_GRAPH_E, KEY_GRAPH_EDGES, KEY_GRAPH_HOPLIMIT, KEY_GRAPH_NODES, KEY_GRAPH_OBSTACLES, KEY_MAXDEGS_MD, KEY_NODEWEIGHTS_END, KEY_NODEWEIGHTS_NW, KEY_OBSTACLES_END, KEY_OBSTACLES_RR, KEY_PRESOLVE_DATE, KEY_PRESOLVE_EA, KEY_PRESOLVE_EC, KEY_PRESOLVE_ED, KEY_PRESOLVE_ES, KEY_PRESOLVE_FIXED, KEY_PRESOLVE_LOWER, KEY_PRESOLVE_TIME, KEY_PRESOLVE_UPPER, KEY_SECTION, KEY_TERMINALS_END, KEY_TERMINALS_GROUPS, KEY_TERMINALS_ROOT, KEY_TERMINALS_ROOTP, KEY_TERMINALS_T, KEY_TERMINALS_TERMINALS, KEY_TERMINALS_TG, KEY_TERMINALS_TP, KEY_TERMINALS_TR, KEY_TREE_S, key::keyword, GRAPH::knots, current_file::line, presolve_info::lower, section::mark, MAX_ARGUMENTS, MAX_KEYWORD_LEN, MAX_LINE_LEN, MAX_PATH_LEN, GRAPH::maxdeg, message(), MSG_DEBUG, MSG_ERROR, MSG_FATAL, MSG_INFO, parameter::n, section::name, NULL, open_file(), GRAPH::prize, scale_coords(), SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArrayNull, SCIPfreeMemoryArrayNull, SCIPisGT(), current_file::section, SECTION_EXISTEND, SECTION_MISSING, GRAPH::source, start_section(), STP_DCSTP, STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_NWSPG, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SAP, STP_SPG, GRAPH::stp_type, SUCCESS, key::sw_code, GRAPH::tail, GRAPH::term, GRAPH::terms, presolve_info::time, TRUE, UNKNOWN, and presolve_info::upper.

Referenced by SCIPprobdataCreate().

Variable Documentation

◆ keyword_table

const struct key keyword_table[]
static

Definition at line 164 of file grphload.c.

◆ section_table

struct section section_table[]
static
Initial value:
=
{
{ "coordinates", "crd", FLAG_OPTIONAL, SECTION_MISSING },
{ "graph", "grp", FLAG_REQUIRED, SECTION_MISSING },
{ "maximumdegrees", "mdg", FLAG_OPTIONAL, SECTION_MISSING },
{ "nodeweights", "nwg", FLAG_OPTIONAL, SECTION_MISSING },
{ "obstacles", "obs", FLAG_OPTIONAL, SECTION_MISSING },
{ "presolve", "prs", FLAG_OPTIONAL, SECTION_MISSING },
{ "solution", "slt", FLAG_OPTIONAL, SECTION_MISSING },
{ "terminals", "trm", FLAG_OPTIONAL, SECTION_MISSING },
{ "tree", "tre", FLAG_OPTIONAL, SECTION_MISSING },
}
#define SECTION_EXISTEND
Definition: grphload.c:254
#define NULL
Definition: def.h:239
#define SECTION_MISSING
Definition: grphload.c:253
#define FLAG_REQUIRED
Definition: grphload.c:251
#define FLAG_OPTIONAL
Definition: grphload.c:250

Definition at line 258 of file grphload.c.

Referenced by start_section().