Scippy

SCIP

Solving Constraint Integer Programs

grphsave.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 grphsave.c
17  * @brief Saving routines for Steiner problems
18  * @author Gerald Gamrath
19  * @author Thorsten Koch
20  * @author Daniel Rehfeldt
21  *
22  * This file includes several saving routines for Steiner problems
23  *
24  * A list of all interface methods can be found in grph.h.
25  *
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include <stdio.h>
31 #include <string.h>
32 #include <assert.h>
33 #include <stdlib.h>
34 #include "portab.h"
35 #include "grph.h"
36 
37 
39  SCIP* scip,
40  const GRAPH* g,
41  FILE* fp,
42  SCIP_Real offset
43  )
44 {
45  int i;
46  int e;
47  int root = g->source;
48  int hopfactor;
49 
50  assert(g != NULL);
51  assert(fp != NULL);
52 
53  fprintf(fp, "%8x STP File, STP Format Version %2d.%02d\n",
55 
56  fprintf(fp, "Section Comment\n");
57  fprintf(fp, "Name ");
58  switch( g->stp_type )
59  {
60  case STP_SPG:
61  fprintf(fp, "\"%s\"\n", "SPG");
62  break;
63 
64  case STP_PCSPG:
65  fprintf(fp, "\"%s\"\n", "UNKNOWN");
66  break;
67 
68  case STP_RPCSPG:
69  fprintf(fp, "\"%s\"\n", "RPCST");
70  break;
71 
72  case STP_NWSPG:
73  fprintf(fp, "\"%s\"\n", "NWSPG");
74  break;
75 
76  case STP_DCSTP:
77  fprintf(fp, "\"%s\"\n", "UNKNOWN");
78  break;
79 
80  case STP_RSMT:
81  fprintf(fp, "\"%s\"\n", "RSMT");
82  break;
83 
84  case STP_OARSMT:
85  fprintf(fp, "\"%s\"\n", "OARSMT");
86  break;
87 
88  case STP_MWCSP:
89  fprintf(fp, "\"%s\"\n", "UNKNOWN");
90  break;
91 
92  case STP_DHCSTP:
93  fprintf(fp, "\"%s\"\n", "UNKNOWN");
94  break;
95 
96  default:
97  fprintf(fp, "\"%s\"\n", "UNKNOWN");
98  }
99  fprintf(fp, "Remark \"Transformed\"\n");
100  fprintf(fp, "End\n\n");
101 
102  if( !SCIPisEQ(scip, offset, 0.0) )
103  {
104  fprintf(fp, "Section Presolve\n");
105  fprintf(fp, "Fixed %f \n", offset);
106  fprintf(fp, "End\n\n");
107  }
108 
109  fprintf(fp, "Section Graph\n");
110  fprintf(fp, "Nodes %d\n", g->knots);
111  fprintf(fp, "Edges %d\n", g->edges / 2);
112 
113  for( i = 0; i < g->edges; i += 2 )
114  {
115  if (g->ieat[i] != EAT_FREE)
116  {
117  assert(g->oeat[i] != EAT_FREE);
118 
119  if( g->stp_type == STP_SPG || g->stp_type == STP_DCSTP || g->stp_type == STP_RSMT
120  || g->stp_type == STP_OARSMT )
121  fprintf(fp, "E ");
122  else
123  fprintf(fp, "AA ");
124 
125  fprintf(fp, "%d %d ", g->tail[i] + 1, g->head[i] + 1);
126 
127  if( g->stp_type == STP_SPG || g->stp_type == STP_DCSTP || g->stp_type == STP_RSMT
128  || g->stp_type == STP_OARSMT )
129  fprintf(fp, "%f\n", g->cost[i]);
130  else
131  fprintf(fp, "%f %f\n", g->cost[i], g->cost[Edge_anti(i)]);
132  }
133  }
134  fprintf(fp, "End\n\n");
135  fprintf(fp, "Section Terminals\n");
136  fprintf(fp, "Terminals %d\n", g->terms);
137 
138  if( g->stp_type == STP_RPCSPG )
139  fprintf(fp, "Root %d\n", g->source + 1);
140 
141  for(i = 0; i < g->knots; i++)
142  {
143  if (Is_term(g->term[i]) && (g->stp_type != STP_RPCSPG || i != g->source))
144  fprintf(fp, "T %d\n", i + 1);
145  }
146  fprintf(fp, "End\n\n");
147 /*
148  if (g->flags & GRAPH_HAS_COORDINATES)
149  {
150  fprintf(fp, "Section Coordinates\n");
151 
152  for(i = 0; i < g->knots; i++)
153  fprintf(fp, "DD %d %d %d\n", i + 1, g->xpos[i], g->ypos[i]);
154 
155  fprintf(fp, "End\n\n");
156  }
157 */
158  /* Hop-Constrained STP */
159  if( g->stp_type == STP_DHCSTP )
160  {
161  fprintf(fp, "Section Hop Constraint\n");
162  fprintf(fp, "limit %d\n", g->hoplimit);
163  for( e = 0; e < g->edges; e++ )
164  {
165  /* TODO: When presolving is used: MODIFY */
166  hopfactor = 1;
167  fprintf(fp, "HC %d %d\n", e + 1, hopfactor);
168  }
169  fprintf(fp, "End\n\n");
170  }
171 
172  /* Degree-Constrained STP */
173  /* It is just enough to know that the degree constraint is required */
174  if( g->stp_type == STP_DCSTP )
175  {
176  fprintf(fp, "Section Degree Constraint\n");
177  fprintf(fp, "End\n\n");
178  }
179 
180  /* PRIZECOLLECTING STP */
181  if( g->stp_type == STP_PCSPG || g->stp_type == STP_MWCSP )
182  {
183  fprintf(fp, "Section Prize Collecting Constraint\n");
184 
185  for( e = g->outbeg[root]; e != EAT_LAST; e = g->oeat[e] )
186  {
187  if( !Is_term(g->term[g->head[e]]) )
188  fprintf(fp, "PC %d\n", e + 1);
189  }
190 
191  fprintf(fp, "End\n\n");
192  }
193 
194  fprintf(fp, "EOF\n");
195 }
196 
197 
198 
199 
200 /*---------------------------------------------------------------------------*/
201 /*--- Name : STP Save Graph ---*/
202 /*--- Function : Writes a graph to a file in STP format. ---*/
203 /*--- Parameter: Graph and Filepointer. ---*/
204 /*--- Returns : Nothing. ---*/
205 /*---------------------------------------------------------------------------*/
206 static void stp_save(
207  const GRAPH* g,
208  FILE* fp
209  )
210 {
211  int i;
212 
213  assert(g != NULL);
214  assert(fp != NULL);
215 
216  fprintf(fp, "%8x STP File, STP Format Version %2d.%02d\n",
218 
219  fprintf(fp, "Section Comment\n");
220  fprintf(fp, "Name \"%s\"\n", "noname");
221  fprintf(fp, "End\n\n");
222 
223  fprintf(fp, "Section Graph\n");
224  fprintf(fp, "Nodes %d\n", g->knots);
225  fprintf(fp, "Edges %d\n", g->edges / 2);
226 
227  for(i = 0; i < g->edges; i += 2)
228  {
229  if (g->ieat[i] != EAT_FREE)
230  {
231  assert(g->oeat[i] != EAT_FREE);
232 
233  fprintf(fp, "E %d %d %g\n",
234  g->tail[i] + 1,
235  g->head[i] + 1,
236  g->cost[i]);
237  }
238  }
239  fprintf(fp, "End\n\n");
240  fprintf(fp, "Section Terminals\n");
241  fprintf(fp, "Terminals %d\n", g->terms);
242 
243  for(i = 0; i < g->knots; i++)
244  {
245  if (Is_term(g->term[i]))
246  fprintf(fp, "T %d\n", i + 1);
247  }
248  fprintf(fp, "End\n\n");
249 /*
250  if (g->flags & GRAPH_HAS_COORDINATES)
251  {
252  fprintf(fp, "Section Coordinates\n");
253 
254  for(i = 0; i < g->knots; i++)
255  fprintf(fp, "DD %d %d %d\n", i + 1, g->xpos[i], g->ypos[i]);
256 
257  fprintf(fp, "End\n\n");
258  }
259 */
260  fprintf(fp, "EOF\n");
261 }
262 
263 /*---------------------------------------------------------------------------*/
264 /*--- Name : Beasley Save Graph ---*/
265 /*--- Function : Writes a graph to a file in Beasleys format. ---*/
266 /*--- Parameter: Graph and Filepointer. ---*/
267 /*--- Returns : Nothing. ---*/
268 /*---------------------------------------------------------------------------*/
269 static void bea_save(
270  const GRAPH* g,
271  FILE* fp)
272 {
273  int i;
274 
275  assert(g != NULL);
276  assert(fp != NULL);
277 
278  fprintf(fp, "%d %d\n",
279  g->knots,
280  g->edges / 2);
281 
282  for(i = 0; i < g->edges; i += 2)
283  {
284  if (g->ieat[i] != EAT_FREE)
285  {
286  assert(g->oeat[i] != EAT_FREE);
287 
288  fprintf(fp, "%d %d %g\n",
289  g->tail[i] + 1,
290  g->head[i] + 1,
291  g->cost[i]);
292  }
293  }
294  fprintf(fp, "%d\n", g->terms);
295 
296  for(i = 0; i < g->knots; i++)
297  {
298  if (Is_term(g->term[i]))
299  fprintf(fp, "%d\n", i + 1);
300  }
301 }
302 
303 /*---------------------------------------------------------------------------*/
304 /*--- Name : Graph Save ---*/
305 /*--- Function : Write a graph to a file. ---*/
306 /*--- Parameter: Graph, Filename, Filetype (Fileformat). ---*/
307 /*--- Returns : Nothing. ---*/
308 /*---------------------------------------------------------------------------*/
310  const GRAPH* g,
311  const char* filename,
312  FILETYPE type)
313 {
314  const char* msg_writing_s = "Writing Graph to File %s:\n";
315 
316  FILE* fp;
317 
318  assert(g != NULL);
319  assert(graph_valid(g));
320  assert(filename != NULL);
321  assert(strlen(filename) > 0);
322  assert((type == FF_BEA) || (type == FF_STP));
323 
324  if ((fp = fopen(filename, "w")) == NULL)
325  perror(filename);
326  else
327  {
328  printf(msg_writing_s, filename);
329 
330  switch(type)
331  {
332  case FF_BEA :
333  bea_save(g, fp);
334  break;
335  case FF_STP :
336  stp_save(g, fp);
337  break;
338  case FF_PRB :
339  case FF_GRD :
340  default :
341  /* CONSTCOND */
342  assert(FALSE);
343  }
344  fclose(fp);
345  }
346 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define NULL
Definition: def.h:253
int *RESTRICT head
Definition: grph.h:96
Definition: grph.h:57
Definition: grph.h:178
int source
Definition: grph.h:67
#define STP_MAGIC
Definition: grph.h:174
Definition: grph.h:178
SCIP_Bool graph_valid(const GRAPH *)
Definition: grphbase.c:4324
int terms
Definition: grph.h:64
#define EAT_LAST
Definition: grph.h:31
#define Edge_anti(a)
Definition: grph.h:171
FILETYPE
Definition: grph.h:178
#define FALSE
Definition: def.h:73
Definition: grph.h:178
#define STP_DHCSTP
Definition: grph.h:48
static void bea_save(const GRAPH *g, FILE *fp)
Definition: grphsave.c:269
#define STP_PCSPG
Definition: grph.h:40
int *RESTRICT oeat
Definition: grph.h:103
static void stp_save(const GRAPH *g, FILE *fp)
Definition: grphsave.c:206
int stp_type
Definition: grph.h:127
#define VERSION_MINOR
Definition: grph.h:176
#define STP_DCSTP
Definition: grph.h:43
int knots
Definition: grph.h:62
#define STP_NWSPG
Definition: grph.h:42
#define STP_SPG
Definition: grph.h:38
int *RESTRICT ieat
Definition: grph.h:102
#define STP_MWCSP
Definition: grph.h:47
int *RESTRICT tail
Definition: grph.h:95
int *RESTRICT term
Definition: grph.h:68
includes various files containing graph methods used for Steiner tree problems
Portable defintions.
#define Is_term(a)
Definition: grph.h:168
#define EAT_FREE
Definition: grph.h:30
void graph_save(const GRAPH *g, const char *filename, FILETYPE type)
Definition: grphsave.c:309
void SCIPwriteStp(SCIP *scip, const GRAPH *g, FILE *fp, SCIP_Real offset)
Definition: grphsave.c:38
SCIP_Real * cost
Definition: grph.h:94
#define SCIP_Real
Definition: def.h:164
int *RESTRICT outbeg
Definition: grph.h:76
int edges
Definition: grph.h:92
#define VERSION_MAJOR
Definition: grph.h:175
#define STP_RSMT
Definition: grph.h:45
#define STP_OARSMT
Definition: grph.h:46
Definition: grph.h:178
int hoplimit
Definition: grph.h:89
#define STP_RPCSPG
Definition: grph.h:41