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 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
getNextNumber(char ** s)47 long getNextNumber(
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
readCol(SCIP * scip,const char * filename)65 SCIP_RETCODE readCol(
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");
233 SCIP_CALL( COLORprobSetUpArrayOfCons(scip) );
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
SCIP_DECL_READERCOPY(readerCopyCol)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
SCIP_DECL_READERREAD(readerReadCol)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 */
SCIPincludeReaderCol(SCIP * scip)291 SCIP_RETCODE SCIPincludeReaderCol(
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 */
302 SCIP_CALL( SCIPincludeReaderBasic(scip, &reader, READER_NAME, READER_DESC, READER_EXTENSION, readerdata) );
303
304 SCIP_CALL( SCIPsetReaderCopy(scip, reader, readerCopyCol) );
305 SCIP_CALL( SCIPsetReaderRead(scip, reader, readerReadCol) );
306
307 return SCIP_OKAY;
308 }
309