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