Scippy

SCIP

Solving Constraint Integer Programs

reader_col.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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file reader_col.c
26  * @brief file reader for vertex coloring instances
27  * @author Gerald Gamrath
28  *
29  * This file implements the reader for vertex coloring problems in DIMACS standard format.
30  *
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 #include <assert.h>
35 #include <string.h>
36 #include <ctype.h>
37 #include <stdlib.h>
38 
39 #include "reader_col.h"
40 
41 
42 #define READER_NAME "colreader"
43 #define READER_DESC "file reader for a .col-file representing a graph that should be colored"
44 #define READER_EXTENSION "col"
45 
46 #define COL_MAX_LINELEN 1024
47 
48 
49 
50 /*
51  * Local methods
52  */
53 
54 /** get next number from string s */
55 static
57  char** s /**< pointer to the pointer of the current position in the string */
58  )
59 {
60  long tmp;
61  /* skip whitespaces */
62  while ( isspace(**s) )
63  ++(*s);
64  /* read number */
65  tmp = atol(*s);
66  /* skip whitespaces */
67  while ( (**s != 0) && (!isspace(**s)) )
68  ++(*s);
69  return tmp;
70 }
71 
72 /** read LP in "COL File Format" */
73 static
75  SCIP* scip, /**< SCIP data structure */
76  const char* filename /**< name of the input file */
77  )
78 {
79  SCIP_FILE* fp; /* file-reader */
80  char buf[COL_MAX_LINELEN]; /* maximal length of line */
81  int nedges;
82  int nnodes;
83  char* char_p;
84  char* probname;
85  int** edges;
86  int i;
87  int j;
88  int begin;
89  int end;
90  int nduplicateedges;
91  SCIP_Bool duplicateedge;
92 
93 
94  assert(scip != NULL);
95  assert(filename != NULL);
96 
97  if (NULL == (fp = SCIPfopen(filename, "r")))
98  {
99  SCIPerrorMessage("cannot open file <%s> for reading\n", filename);
100  perror(filename);
101  return SCIP_NOFILE;
102  }
103 
104  /* Get problem name from filename and save it */
105  if( SCIPfgets(buf, (int) sizeof(buf), fp) == NULL)
106  return SCIP_READERROR;
107 
108  i = 1;
109  while ( (filename[i] != '/') && (filename[i] != '\0') )
110  {
111  i++;
112  }
113  if ( filename[i] != '/' )
114  {
115  j = i;
116  i = -1;
117  }
118  else
119  {
120  j = i+1;
121  while ( filename[i] == '/' && filename[j] != '\0' )
122  {
123  j = i+1;
124  while ( filename[j] != '\0' )
125  {
126  j++;
127  if ( filename[j] == '/' )
128  {
129  i = j;
130  break;
131  }
132  }
133  }
134  }
135 
136  if( j-i-4 <= 0 )
137  return SCIP_READERROR;
138 
139  SCIP_CALL( SCIPallocBufferArray(scip, &probname, (j-i-4)) );
140  (void) strncpy(probname, &filename[i+1], (j-i-5)); /*lint !e732 !e776*/
141  probname[j-i-5]= '\0';
142 
143  /* Read until information about graph starts */
144  while( !SCIPfeof(fp) && (buf[0] != 'p') )
145  {
146  SCIPfgets(buf, (int) sizeof(buf), fp); /*lint !e534*/
147  }
148 
149  /* no graph information in file! */
150  if ( SCIPfeof(fp) )
151  {
152  SCIPerrorMessage("Error! Could not find line starting with 'p'.\n");
153  return SCIP_READERROR;
154  }
155 
156  /* wrong format of the line containig number of nodes and edges */
157  if ( buf[2] != 'e' || buf[3] != 'd' || buf[4] != 'g' || buf[5] != 'e' )
158  {
159  SCIPerrorMessage("Line starting with 'p' must continue with 'edge'!\n");
160  return SCIP_READERROR;
161  }
162  char_p = &buf[6];
163 
164  /* if line reads 'edges' (non-standard!), instead of 'edge'. */
165  if ( *char_p == 's' )
166  ++(char_p);
167 
168  /* read out number of nodes and edges, the pointer char_p will be changed */
169  nduplicateedges = 0;
170  nnodes = (int) getNextNumber(&char_p);
171  nedges = (int) getNextNumber(&char_p);
172 
173  if ( nnodes <= 0 )
174  {
175  SCIPerrorMessage("Number of vertices must be positive!\n");
176  return SCIP_READERROR;
177  }
178 
179  if ( nedges < 0 )
180  {
181  SCIPerrorMessage("Number of edges must be nonnegative!\n");
182  return SCIP_READERROR;
183  }
184 
185  /* create array for edges */
186  SCIP_CALL( SCIPallocBufferArray(scip, &edges, nedges) );
187  for( i = 0; i < nedges; i++)
188  {
189  SCIP_CALL( SCIPallocBufferArray(scip, &(edges[i]), 2) ); /*lint !e866*/
190  }
191 
192  /* fill array for edges */
193  i = 0;
194  while ( !SCIPfeof(fp) )
195  {
196  SCIPfgets(buf, (int) sizeof(buf), fp); /*lint !e534*/
197  if ( buf[0] == 'e')
198  {
199  duplicateedge = FALSE;
200  char_p = &buf[2];
201 
202  begin = (int) getNextNumber(&char_p);
203  end = (int) getNextNumber(&char_p);
204  for ( j = 0; j < i; j++)
205  {
206  if ( ((edges[j][0] == begin) && (edges[j][1] == end))
207  || ((edges[j][1] == begin) && (edges[j][0] == end)) )
208  {
209  duplicateedge = TRUE;
210  nduplicateedges++;
211  break;
212  }
213  }
214  if ( !duplicateedge )
215  {
216  if( i >= nedges )
217  {
218  SCIPerrorMessage("more edges than expected: expected %d many, but got already %d'th (non-duplicate) edge", nedges, i+1);
219  return SCIP_READERROR;
220  }
221  edges[i][0] = begin;
222  edges[i][1] = end;
223  assert((edges[i][0] > 0) && (edges[i][0] <= nnodes));
224  assert((edges[i][1] > 0) && (edges[i][1] <= nnodes));
225  i++;
226  }
227  }
228  }
229  if( i + nduplicateedges != nedges )
230  {
231  SCIPerrorMessage("incorrect number of edges: expected %d many, but got %d many\n", nedges, i + nduplicateedges);
232  return SCIP_ERROR;
233  }
234 
235  printf("Read graph: %d nodes, %d edges (%d duplicates)\n", nnodes, nedges, nduplicateedges);
236 
237  /* create problem data */
238  SCIP_CALL( SCIPcreateProbColoring(scip, probname, nnodes, nedges-nduplicateedges, edges) );
239 
240  /* create LP */
241  SCIPdebugMessage("Create LP...\n");
243 
244  /* activate the pricer */
245  SCIP_CALL( SCIPactivatePricer(scip, SCIPfindPricer(scip, "coloring")) );
246  SCIP_CALL( SCIPsetObjIntegral(scip) );
247  for ( i = nedges-1; i >= 0; i--)
248  {
249  SCIPfreeBufferArray(scip, &(edges[i]));
250  }
251  SCIPfreeBufferArray(scip, &edges);
252  SCIPfreeBufferArray(scip, &probname);
253  SCIPfclose(fp);
254 
255  return SCIP_OKAY;
256 }
257 
258 
259 
260 
261 /*
262  * Callback methods of reader
263  */
264 
265 /** copy method for reader plugins (called when SCIP copies plugins) */
266 static
267 SCIP_DECL_READERCOPY(readerCopyCol)
268 { /*lint --e{715}*/
269  assert(scip != NULL);
270  assert(reader != NULL);
271  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
272 
273  return SCIP_OKAY;
274 }
275 
276 /** problem reading method of reader */
277 static
278 SCIP_DECL_READERREAD(readerReadCol)
279 { /*lint --e{715}*/
280  assert(reader != NULL);
281  assert(strcmp(SCIPreaderGetName(reader), READER_NAME) == 0);
282  assert(scip != NULL);
283  assert(result != NULL);
284 
285  SCIP_CALL( readCol(scip, filename) );
286 
287  *result = SCIP_SUCCESS;
288 
289  return SCIP_OKAY;
290 }
291 
292 
293 
294 
295 /*
296  * col file reader specific interface methods
297  */
298 
299 /** includes the col file reader in SCIP */
301  SCIP* scip /**< SCIP data structure */
302  )
303 {
304  SCIP_READERDATA* readerdata;
305  SCIP_READER* reader;
306 
307  /* create col reader data */
308  readerdata = NULL;
309 
310  /* include col reader */
312 
313  SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCol) );
314  SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadCol) );
315 
316  return SCIP_OKAY;
317 }
static SCIP_RETCODE readCol(SCIP *scip, const char *filename)
Definition: reader_col.c:74
const char * SCIPreaderGetName(SCIP_READER *reader)
Definition: reader.c:557
#define FALSE
Definition: def.h:96
#define READER_DESC
Definition: reader_col.c:43
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
Definition: scip_pricer.c:311
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
file reader for vertex coloring instances
#define SCIPdebugMessage
Definition: pub_message.h:96
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_FILE * SCIPfopen(const char *path, const char *mode)
Definition: fileio.c:153
SCIP_RETCODE SCIPsetObjIntegral(SCIP *scip)
Definition: scip_prob.c:1527
#define SCIPerrorMessage
Definition: pub_message.h:64
int SCIPfeof(SCIP_FILE *stream)
Definition: fileio.c:227
static long getNextNumber(char **s)
Definition: reader_col.c:56
struct SCIP_File SCIP_FILE
Definition: pub_fileio.h:43
char * SCIPfgets(char *s, int size, SCIP_FILE *stream)
Definition: fileio.c:200
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_CALL(x)
Definition: def.h:393
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
Definition: scip_pricer.c:384
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
struct SCIP_ReaderData SCIP_READERDATA
Definition: type_reader.h:53
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPincludeReaderBasic(SCIP *scip, SCIP_READER **readerptr, const char *name, const char *desc, const char *extension, SCIP_READERDATA *readerdata)
Definition: scip_reader.c:109
#define READER_EXTENSION
Definition: reader_col.c:44
SCIP_RETCODE SCIPsetReaderCopy(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERCOPY((*readercopy)))
Definition: scip_reader.c:147
SCIP_RETCODE SCIPincludeReaderCol(SCIP *scip)
Definition: reader_col.c:300
SCIP_RETCODE SCIPcreateProbColoring(SCIP *scip, const char *name, int nnodes, int nedges, int **edges)
#define COL_MAX_LINELEN
Definition: reader_col.c:46
#define READER_NAME
Definition: reader_col.c:42
SCIP_RETCODE SCIPsetReaderRead(SCIP *scip, SCIP_READER *reader, SCIP_DECL_READERREAD((*readerread)))
Definition: scip_reader.c:195
SCIP_RETCODE COLORprobSetUpArrayOfCons(SCIP *scip)
static SCIP_DECL_READERCOPY(readerCopyCol)
Definition: reader_col.c:267
#define nnodes
Definition: gastrans.c:74
int SCIPfclose(SCIP_FILE *fp)
Definition: fileio.c:232
static SCIP_DECL_READERREAD(readerReadCol)
Definition: reader_col.c:278