Scippy

SCIP

Solving Constraint Integer Programs

graph_save.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-2022 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 graph_save.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 graph.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 <time.h>
35 #include "portab.h"
36 #include "graph.h"
37 #include "reduce.h"
38 
39 
40 
41 
42 
43 
44 /*---------------------------------------------------------------------------*/
45 /*--- Name : STP Save Graph ---*/
46 /*--- Function : Writes a graph to a file in STP format. ---*/
47 /*--- Parameter: Graph and Filepointer. ---*/
48 /*--- Returns : Nothing. ---*/
49 /*---------------------------------------------------------------------------*/
50 static void stp_save(
51  const GRAPH* g,
52  FILE* fp
53  )
54 {
55  int i;
56 
57  assert(g != NULL);
58  assert(fp != NULL);
59 
60  fprintf(fp, "%8x STP File, STP Format Version %2d.%02d\n",
62 
63  fprintf(fp, "Section Comment\n");
64  fprintf(fp, "Name \"%s\"\n", "noname");
65  fprintf(fp, "End\n\n");
66 
67  fprintf(fp, "Section Graph\n");
68  fprintf(fp, "Nodes %d\n", g->knots);
69  fprintf(fp, "Edges %d\n", g->edges / 2);
70 
71  for(i = 0; i < g->edges; i += 2)
72  {
73  if (g->ieat[i] != EAT_FREE)
74  {
75  assert(g->oeat[i] != EAT_FREE);
76 
77  fprintf(fp, "E %d %d %g\n",
78  g->tail[i] + 1,
79  g->head[i] + 1,
80  g->cost[i]);
81  }
82  }
83  fprintf(fp, "End\n\n");
84  fprintf(fp, "Section Terminals\n");
85  fprintf(fp, "Terminals %d\n", g->terms);
86 
87  for(i = 0; i < g->knots; i++)
88  {
89  if (Is_term(g->term[i]))
90  fprintf(fp, "T %d\n", i + 1);
91  }
92  fprintf(fp, "End\n\n");
93 /*
94  if (g->flags & GRAPH_HAS_COORDINATES)
95  {
96  fprintf(fp, "Section Coordinates\n");
97 
98  for(i = 0; i < g->knots; i++)
99  fprintf(fp, "DD %d %d %d\n", i + 1, g->xpos[i], g->ypos[i]);
100 
101  fprintf(fp, "End\n\n");
102  }
103 */
104  fprintf(fp, "EOF\n");
105 }
106 
107 /*---------------------------------------------------------------------------*/
108 /*--- Name : Beasley Save Graph ---*/
109 /*--- Function : Writes a graph to a file in Beasleys format. ---*/
110 /*--- Parameter: Graph and Filepointer. ---*/
111 /*--- Returns : Nothing. ---*/
112 /*---------------------------------------------------------------------------*/
113 static void bea_save(
114  const GRAPH* g,
115  FILE* fp)
116 {
117  int i;
118 
119  assert(g != NULL);
120  assert(fp != NULL);
121 
122  fprintf(fp, "%d %d\n",
123  g->knots,
124  g->edges / 2);
125 
126  for(i = 0; i < g->edges; i += 2)
127  {
128  if (g->ieat[i] != EAT_FREE)
129  {
130  assert(g->oeat[i] != EAT_FREE);
131 
132  fprintf(fp, "%d %d %g\n",
133  g->tail[i] + 1,
134  g->head[i] + 1,
135  g->cost[i]);
136  }
137  }
138  fprintf(fp, "%d\n", g->terms);
139 
140  for(i = 0; i < g->knots; i++)
141  {
142  if (Is_term(g->term[i]))
143  fprintf(fp, "%d\n", i + 1);
144  }
145 }
146 
147 /** gets node map */
148 static
150  const GRAPH* g,
151  int* orgToNewNode
152  )
153 {
154  const SCIP_Bool isPcMw = graph_pc_isPcMw(g);
155  const int nnodes = graph_get_nNodes(g);
156  int nodecount = 0;
157 
158  for( int k = 0; k < nnodes; ++k )
159  {
160  if( isPcMw && graph_pc_knotIsDummyTerm(g, k) )
161  {
162  orgToNewNode[k] = -1;
163  continue;
164  }
165 
166  if( g->grad[k] > 0 || (isPcMw && GT(g->prize[k], 0.0)) )
167  {
168  orgToNewNode[k] = nodecount;
169  nodecount++;
170  }
171  else
172  {
173  orgToNewNode[k] = -1;
174  }
175  }
176 }
177 
178 
179 
180 /** Writes node to gml file.
181  * Discriminates between root, terminals and Steiner nodes */
182 static inline
184  const GRAPH* graph, /**< Graph to be printed */
185  int k, /**< the node */
186  FILE* file /**> the gml file */
187 )
188 {
189  char label[SCIP_MAXSTRLEN];
190 
191  if( k == graph->source )
192  {
193  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Root", k);
194  SCIPgmlWriteNode(file, (unsigned int) k, label, "rectangle", "#666666", NULL);
195  }
196  else if( graph->term[k] == 0 )
197  {
198  (void) SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Terminal", k);
199  SCIPgmlWriteNode(file, (unsigned int) k, label, "circle", "#ff0000", NULL);
200  }
201  else
202  {
203  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "(%d) Node", k);
204  SCIPgmlWriteNode(file, (unsigned int)k, label, "circle", "#336699", NULL);
205  }
206 }
207 
208 /** Writes edge to gml file */
209 static inline
211  const GRAPH* graph, /**< Graph to be printed */
212  int edge, /**< the edge */
213  int tail_id, /**< tail ID for gml file */
214  int head_id, /**< head ID for gml file */
215  const SCIP_Bool* edgemark, /**< Array of (undirected) edges to highlight or NULL */
216  FILE* file /**> the gml file */
217 )
218 {
219  char label[SCIP_MAXSTRLEN];
220 
221  assert(graph_edge_isInRange(graph, edge));
222  assert(graph_knot_isInRange(graph, tail_id));
223  assert(graph_knot_isInRange(graph, head_id));
224 
225  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "%8.2f", graph->cost[edge]);
226 
227  if( edgemark != NULL && edgemark[edge / 2] )
228  SCIPgmlWriteEdge(file, (unsigned int)tail_id, (unsigned int)head_id, label, "#ff0000");
229  else
230  SCIPgmlWriteEdge(file, (unsigned int)tail_id, (unsigned int)head_id, label, NULL);
231 }
232 
233 
234 /** gets ratios of remaining nodes/edges */
235 static
237  const GRAPH* graph, /**< graph */
238  SCIP_Real* ratio_nodes, /**< nodes ratio */
239  SCIP_Real* ratio_edges /**< edges ratio */
240 )
241 {
242  assert(graph_pc_isPcMw(graph));
243  assert(graph->extended);
244 
245  graph_pc_getReductionRatios(graph, ratio_nodes, ratio_edges);
246 }
247 
248 
249 /** Call before graph packing! */
250 static
252  const GRAPH* graph, /**< graph */
253  SCIP_Real* ratio_nodes, /**< nodes ratio */
254  SCIP_Real* ratio_edges /**< edges ratio */
255 )
256 {
257  const int nnodes = graph->knots;
258  const int nedges = graph->edges;
259  int nnodes_real;
260  int nedges_real;
261 
262  assert(!graph_pc_isPcMw(graph));
263 
264  graph_get_nVET(graph, &nnodes_real, &nedges_real, NULL);
265 
266  assert(nnodes_real <= nnodes);
267  assert(nedges_real <= nedges);
268  assert(nedges % 2 == 0);
269  assert(nedges_real % 2 == 0);
270  assert(nnodes >= 1);
271  assert(nedges >= 2);
272 
273  *ratio_nodes = (SCIP_Real) nnodes_real / (SCIP_Real) nnodes;
274  *ratio_edges = (SCIP_Real) nedges_real / (SCIP_Real) nedges;
275 }
276 
277 /*
278  * Interface methods
279  */
280 
281 
282 
283 /** Write (append) reduction ratio statistics of current graph to file.
284  * Call before graph packing!*/
286  const GRAPH* graph, /**< Graph to be printed */
287  const char* probname, /**< Name of the problem */
288  const char* filename /**< Name of the output file */
289 )
290 {
291  FILE* file;
292  SCIP_Real ratio_nodes;
293  SCIP_Real ratio_edges;
294 
295  assert(filename && probname);
296 
297  if( graph_pc_isPcMw(graph) )
298  {
299  getReductionRatiosPcMw(graph, &ratio_nodes, &ratio_edges);
300  }
301  else
302  {
303  getReductionRatios(graph, &ratio_nodes, &ratio_edges);
304  }
305 
306  file = fopen(filename, "a+");
307 
308  fprintf(file, "%s: %f %f \n", probname, ratio_nodes, ratio_edges);
309  fclose(file);
310 }
311 
312 
313 /** Write (append) reduction ratio statistics of current graph to file.
314  * NOTE: Only for testing! Graph will be killed */
315 // todo to properly, copy graph etc.
317  SCIP* scip, /**< SCIP data */
318  GRAPH* graph, /**< Graph to be printed */
319  const char* probname /**< Name of the problem */
320 )
321 {
322  REDSOL* redsol;
323  FILE* file;
324  char* filename;
325  SCIP_Real ratio_nodes;
326  SCIP_Real ratio_edges;
327  int minelims;
328  const SCIP_Bool useNodeSol = (graph_pc_isPcMw(graph) || graph_typeIsSpgLike(graph));
329  SCIP_Real time_start;
330  SCIP_Real time_end;
331 
332  assert(graph && probname);
333 
334  SCIP_CALL( reduce_solInit(scip, graph, useNodeSol, &redsol) );
335  SCIP_CALL( SCIPgetIntParam(scip, "stp/minelims", &(minelims)) );
336 
337  time_start = clock();
338  SCIP_CALL( reduce_exec(scip, graph, redsol, STP_REDUCTION_ADVANCED, minelims, TRUE) );
339  time_end = clock();
340 
341  SCIP_CALL( SCIPgetStringParam(scip, "stp/redstatsfile", &filename) );
342  assert(filename);
343 
344  if( graph_pc_isPcMw(graph) )
345  {
346  getReductionRatiosPcMw(graph, &ratio_nodes, &ratio_edges);
347  }
348  else
349  {
350  getReductionRatios(graph, &ratio_nodes, &ratio_edges);
351  }
352 
353  file = fopen(filename, "a+");
354 
355  fprintf(file, "%s: %f %f %f \n", probname, ratio_nodes, ratio_edges, (time_end - time_start) / CLOCKS_PER_SEC);
356  fclose(file);
357 
358  reduce_solFree(scip, &redsol);
359 
360  return SCIP_OKAY;
361 }
362 
363 
364 /*---------------------------------------------------------------------------*/
365 /*--- Name : Graph Save ---*/
366 /*--- Function : Write a graph to a file. ---*/
367 /*--- Parameter: Graph, Filename, Filetype (Fileformat). ---*/
368 /*--- Returns : Nothing. ---*/
369 /*---------------------------------------------------------------------------*/
371  SCIP* scip,
372  const GRAPH* g,
373  const char* filename,
374  FILETYPE type)
375 {
376  const char* msg_writing_s = "Writing Graph to File %s:\n";
377 
378  FILE* fp;
379 
380  assert(g && scip && filename);
381  assert(graph_valid(scip, g));
382  assert(strlen(filename) > 0);
383  assert((type == FF_BEA) || (type == FF_STP));
384 
385  if ((fp = fopen(filename, "w")) == NULL)
386  perror(filename);
387  else
388  {
389  printf(msg_writing_s, filename);
390 
391  switch(type)
392  {
393  case FF_BEA :
394  bea_save(g, fp);
395  break;
396  case FF_STP :
397  stp_save(g, fp);
398  break;
399  case FF_PRB :
400  case FF_GRD :
401  default :
402  /* CONSTCOND */
403  assert(FALSE);
404  }
405  fclose(fp);
406  }
407 }
408 
409 
410 /** Write (append) reduction statistics of current graph to file.
411  * Call before graph packing!*/
413  const GRAPH* graph, /**< Graph to be printed */
414  const char* probname, /**< Name of the problem */
415  const char* filename /**< Name of the output file */
416 )
417 {
418  FILE* file;
419  int nnodes_real;
420  int nedges_real;
421  const int nnodes = graph_get_nNodes(graph);
422  const int nedges = graph_get_nEdges(graph);
423 
424  assert(filename && probname);
425 
426  graph_get_nVET(graph, &nnodes_real, &nedges_real, NULL);
427 
428  assert(nnodes_real <= nnodes);
429  assert(nedges_real <= nedges);
430  assert(nedges % 2 == 0);
431  assert(nedges_real % 2 == 0);
432 
433  file = fopen(filename, "a+");
434 
435  fprintf(file, "%s: %d %d %d %d \n", probname, nnodes, nedges / 2, nnodes_real, nedges_real / 2);
436  fclose(file);
437 }
438 
439 
440 /** print graph (in undirected form) in GML format */
442  const GRAPH* graph, /**< Graph to be printed */
443  const char* filename, /**< Name of the output file */
444  const SCIP_Bool* edgemark /**< Array of (undirected) edges to highlight */
445  )
446 {
447  FILE* file;
448 
449  assert(graph != NULL);
450  file = fopen((filename != NULL) ? filename : "stpgraph.gml", "w");
451 
452 #ifndef NDEBUG
453  for( int e = 0; e < graph->edges; e += 2 )
454  {
455  assert(graph->tail[e] == graph->head[e + 1]);
456  assert(graph->tail[e + 1] == graph->head[e]);
457  }
458 #endif
459 
460  /* write GML format opening, undirected */
461  SCIPgmlWriteOpening(file, FALSE);
462 
463  for( int k = 0; k < graph->knots; k++ )
464  {
465  if( graph->grad[k] > 0 || graph->source == k )
466  {
467  gmlWriteNode(graph, k, file);
468  }
469  }
470 
471  /* write all edges (undirected) */
472  for( int e = 0; e < graph->edges; e += 2 )
473  {
474  if( graph->oeat[e] != EAT_FREE )
475  {
476  gmlWriteEdge(graph, e, graph->tail[e], graph->head[e], edgemark, file);
477  }
478  }
479 
480  /* write GML format closing */
481  SCIPgmlWriteClosing(file);
482 
483  fclose(file);
484 
485  return SCIP_OKAY;
486 }
487 
488 
489 /** prints subgraph of given graph (in undirected form) in GML format */
491  const GRAPH* graph, /**< Graph to be printed */
492  const char* filename, /**< Name of the output file */
493  const SCIP_Bool* subnodesmark /**< Array to mark the nodes of the subgraph*/
494  )
495 {
496  char label[SCIP_MAXSTRLEN];
497  FILE* file;
498  int e;
499 
500  assert(graph != NULL);
501  file = fopen((filename != NULL) ? filename : "stpgraph.gml", "w");
502 
503 #ifndef NDEBUG
504  for( e = 0; e < graph->edges; e += 2 )
505  {
506  assert(graph->tail[e] == graph->head[e + 1]);
507  assert(graph->tail[e + 1] == graph->head[e]);
508  }
509 #endif
510 
511  /* write GML format opening, undirected */
512  SCIPgmlWriteOpening(file, FALSE);
513 
514  /* write all nodes, discriminate between root, terminals and the other nodes */
515  for( int k = 0; k < graph->knots; k++ )
516  {
517  if( graph->grad[k] > 0 || graph->source == k )
518  {
519  if( !subnodesmark[k] )
520  continue;
521  gmlWriteNode(graph, k, file);
522  }
523  }
524 
525  /* write all edges (undirected) */
526  for( e = 0; e < graph->edges; e += 2 )
527  {
528  if( graph->oeat[e] != EAT_FREE )
529  {
530  const int head = graph->head[e];
531  const int tail = graph->tail[e];
532 
533  if( !subnodesmark[tail] || !subnodesmark[head] )
534  continue;
535 
536  (void)SCIPsnprintf(label, SCIP_MAXSTRLEN, "%8.2f", graph->cost[e]);
537 
538  SCIPgmlWriteEdge(file, (unsigned int)graph->tail[e], (unsigned int)graph->head[e], label, NULL);
539  }
540  }
541 
542  /* write GML format closing */
543  SCIPgmlWriteClosing(file);
544 
545  return SCIP_OKAY;
546 }
547 
548 
549 /** writes graph in .stp format to file */
551  SCIP* scip,
552  const GRAPH* g,
553  const char* filename,
554  SCIP_Real offset
555  )
556 {
557  FILE *fp;
558  assert(filename);
559 
560  fp = fopen(filename, "a+");
561  graph_writeStp(scip, g, fp, offset);
562 
563  fclose(fp);
564 }
565 
566 
567 /** writes graph in .stp format to file */
569  SCIP* scip,
570  const GRAPH* g,
571  FILE* fp,
572  SCIP_Real offset
573  )
574 {
575  const int nnodes = graph_get_nNodes(g);
576  int nnodes_curr;
577  int nedges_curr;
578  int hopfactor;
579  int* orgToNewNode;
580 
581  assert(fp != NULL);
582 
583  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &orgToNewNode, nnodes) );
584  getOrgNodeToNodeMap(g, orgToNewNode);
585 
586  fprintf(fp, "%8x STP File, STP Format Version %2d.%02d\n",
588 
589  fprintf(fp, "Section Comment\n");
590  fprintf(fp, "Problem ");
591  switch( g->stp_type )
592  {
593  case STP_SPG:
594  fprintf(fp, "\"%s\"\n", "SPG");
595  break;
596 
597  case STP_PCSPG:
598  fprintf(fp, "\"%s\"\n", "UNKNOWN");
599  break;
600 
601  case STP_RPCSPG:
602  fprintf(fp, "\"%s\"\n", "RPCST");
603  break;
604 
605  case STP_NWSPG:
606  fprintf(fp, "\"%s\"\n", "NWSPG");
607  break;
608 
609  case STP_DCSTP:
610  fprintf(fp, "\"%s\"\n", "UNKNOWN");
611  break;
612 
613  case STP_NWPTSPG:
614  fprintf(fp, "\"%s\"\n", "STP_NWPTSPG");
615  break;
616 
617  case STP_RSMT:
618  fprintf(fp, "\"%s\"\n", "RSMT");
619  break;
620 
621  case STP_OARSMT:
622  fprintf(fp, "\"%s\"\n", "OARSMT");
623  break;
624 
625  case STP_MWCSP:
626  fprintf(fp, "\"%s\"\n", "UNKNOWN");
627  break;
628 
629  case STP_DHCSTP:
630  fprintf(fp, "\"%s\"\n", "UNKNOWN");
631  break;
632 
633  default:
634  fprintf(fp, "\"%s\"\n", "UNKNOWN");
635  }
636  fprintf(fp, "End\n\n");
637 
638  if( !SCIPisEQ(scip, offset, 0.0) )
639  {
640  fprintf(fp, "Section Presolve\n");
641  fprintf(fp, "Fixed %f \n", offset);
642  fprintf(fp, "End\n\n");
643  }
644 
645  if( graph_pc_isPcMw(g) )
646  {
647  nnodes_curr = 0;
648  nedges_curr = 0;
649  assert(!g->extended);
650 
651  for( int i = 0; i < nnodes; i++ )
652  {
653  if( !graph_pc_knotIsDummyTerm(g, i) && (g->grad[i] > 0 || GT(g->prize[i], 0.0)) )
654  nnodes_curr++;
655  }
656 
657  for( int i = 0; i < g->edges; i += 2 )
658  {
659  if( g->ieat[i] != EAT_FREE )
660  {
661  const int tail = g->tail[i];
662  const int head = g->head[i];
663 
664  if( graph_pc_knotIsDummyTerm(g, tail) || graph_pc_knotIsDummyTerm(g, head) )
665  continue;
666 
667  assert(EQ(g->cost[i], g->cost[i + 1]));
668 
669  nedges_curr += 2;
670  }
671  }
672  }
673  else
674  {
675  graph_get_nVET(g, &nnodes_curr, &nedges_curr, NULL);
676  }
677 
678  fprintf(fp, "Section Graph\n");
679  fprintf(fp, "Nodes %d\n", nnodes_curr);
680  fprintf(fp, "Edges %d\n", nedges_curr / 2);
681 
682  for( int i = 0; i < g->edges; i += 2 )
683  {
684  if (g->ieat[i] != EAT_FREE)
685  {
686  const int tail = g->tail[i];
687  const int head = g->head[i];
688  const int tail_curr = orgToNewNode[tail];
689  const int head_curr = orgToNewNode[head];
690 
691  if( graph_pc_isPcMw(g) )
692  {
693  if( graph_pc_knotIsDummyTerm(g, tail) || graph_pc_knotIsDummyTerm(g, head) )
694  continue;
695 
696  assert(EQ(g->cost[i], g->cost[i + 1]));
697  }
698 
699  assert(0 <= tail_curr && tail_curr < nnodes_curr);
700  assert(0 <= head_curr && head_curr < nnodes_curr);
701  assert(g->oeat[i] != EAT_FREE);
702 
703  if( g->stp_type == STP_SPG || g->stp_type == STP_DCSTP || g->stp_type == STP_RSMT || g->stp_type == STP_OARSMT || graph_pc_isPcMw(g) )
704  fprintf(fp, "E ");
705  else
706  fprintf(fp, "AA ");
707 
708  fprintf(fp, "%d %d ", tail_curr + 1, head_curr + 1);
709 
710  if( graph_typeIsSpgLike(g) || g->stp_type == STP_DCSTP || graph_pc_isPcMw(g) )
711  fprintf(fp, "%f\n", g->cost[i]);
712  else
713  fprintf(fp, "%f %f\n", g->cost[i], g->cost[Edge_anti(i)]);
714  }
715  }
716 
717  fprintf(fp, "End\n\n");
718  fprintf(fp, "Section Terminals\n");
719  fprintf(fp, "Terminals %d\n", g->terms);
720 
721  if( g->stp_type == STP_RPCSPG )
722  {
723  assert(0 <= orgToNewNode[g->source] && orgToNewNode[g->source] < nnodes_curr);
724  fprintf(fp, "RootP %d\n", orgToNewNode[g->source] + 1);
725  }
726 
727  for( int i = 0; i < g->knots; i++ )
728  {
729  const int i_curr = orgToNewNode[i];
730 
731  if( g->grad[i] == 0 )
732  {
733  if( graph_pc_isPcMw(g) && GT(g->prize[i], 0.0) )
734  {
735  assert(0 <= i_curr && i_curr < nnodes_curr);
736  assert(graph_pc_knotIsNonLeafTerm(g, i));
737  fprintf(fp, "TP %d %f\n", i_curr + 1, g->prize[i]);
738  }
739  continue;
740  }
741 
742  if( graph_pc_isPcMw(g) )
743  {
744  if( graph_pc_knotIsDummyTerm(g, i) )
745  continue;
746 
747  if( !Is_anyTerm(g->term[i]) )
748  continue;
749 
750  if( !graph_pc_knotIsFixedTerm(g, i) )
751  {
752  assert(0 <= i_curr && i_curr < nnodes_curr);
753  fprintf(fp, "TP %d %f\n", i_curr + 1, g->prize[i]);
754  continue;
755  }
756 
757  assert(Is_term(g->term[i]) && g->stp_type == STP_RPCSPG);
758  assert(0 <= i_curr && i_curr < nnodes_curr);
759 
760  fprintf(fp, "TF %d\n", i_curr + 1);
761  continue;
762  }
763 
764  assert(0 <= i_curr && i_curr < nnodes_curr);
765 
766  if (Is_term(g->term[i]) )
767  fprintf(fp, "T %d\n", i_curr + 1);
768  }
769  fprintf(fp, "End\n\n");
770 
771  /* Hop-Constrained STP */
772  if( g->stp_type == STP_DHCSTP )
773  {
774  fprintf(fp, "Section Hop Constraint\n");
775  fprintf(fp, "limit %d\n", g->hoplimit);
776  for( int e = 0; e < nedges_curr / 2; e++ )
777  {
778  hopfactor = 1;
779  fprintf(fp, "HC %d %d\n", e + 1, hopfactor);
780  }
781  fprintf(fp, "End\n\n");
782  }
783 
784  /* Degree-Constrained STP */
785  /* It is just enough to know that the degree constraint is required */
786  if( g->stp_type == STP_DCSTP )
787  {
788  fprintf(fp, "Section Degree Constraint\n");
789  fprintf(fp, "End\n\n");
790  }
791 
792  fprintf(fp, "EOF\n");
793 
794  SCIPfreeBufferArray(scip, &orgToNewNode);
795 }
796 
797 
798 /** writes SPG (no variant!) to a file; deprecated */
800  SCIP* scip, /**< SCIP data structure */
801  const GRAPH* graph, /**< graph data structure */
802  const char* filename /**< file name */
803  )
804 {
805  FILE *fptr;
806 
807  assert(scip != NULL);
808  assert(graph != NULL);
809 
810  fptr = fopen(filename, "w");
811  assert(fptr != NULL);
812 
813  fprintf(fptr, "33D32945 STP File, STP Format Version 1.0\n");
814  fprintf(fptr, "SECTION Comment\n");
815  fprintf(fptr, "END\n\n");
816  fprintf(fptr, "SECTION Graph\n");
817  fprintf(fptr, "Nodes %d\n", graph->knots);
818  fprintf(fptr, "Edges %d\n", graph->edges);
819 
820  for( int e = 0; e < graph->edges; e += 2 )
821  fprintf(fptr, "E %d %d %f\n", graph->tail[e] + 1, graph->head[e] + 1, graph->cost[e]);
822  fprintf(fptr, "END\n\n");
823 
824  fprintf(fptr, "SECTION Terminals\n");
825  fprintf(fptr, "Terminals %d\n", graph->terms);
826 
827  for( int k = 0; k < graph->knots; k++ )
828  if( Is_term(graph->term[k]) )
829  fprintf(fptr, "T %d\n", k + 1);
830 
831  fprintf(fptr, "END\n\n");
832 
833  fprintf(fptr, "EOF\n");
834 
835  fclose(fptr);
836 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
Definition: scip_param.c:336
int *RESTRICT head
Definition: graphdefs.h:224
FILETYPE
Definition: graphdefs.h:115
int source
Definition: graphdefs.h:195
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
Definition: graph_base.c:1480
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
Definition: reduce_sol.c:687
int terms
Definition: graphdefs.h:192
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:487
void graph_writeReductionRatioStats(const GRAPH *graph, const char *probname, const char *filename)
Definition: graph_save.c:285
void graph_writeStpOrg(SCIP *scip, const GRAPH *graph, const char *filename)
Definition: graph_save.c:799
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:689
#define EAT_FREE
Definition: graphdefs.h:57
#define FALSE
Definition: def.h:87
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
#define STP_DCSTP
Definition: graphdefs.h:47
void graph_writeStp(SCIP *scip, const GRAPH *g, FILE *fp, SCIP_Real offset)
Definition: graph_save.c:568
#define STP_SPG
Definition: graphdefs.h:42
#define STP_FILE_VERSION_MAJOR
Definition: graphdefs.h:112
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
static void getReductionRatiosPcMw(const GRAPH *graph, SCIP_Real *ratio_nodes, SCIP_Real *ratio_edges)
Definition: graph_save.c:236
#define STP_FILE_MAGIC
Definition: graphdefs.h:111
static void bea_save(const GRAPH *g, FILE *fp)
Definition: graph_save.c:113
void graph_save(SCIP *scip, const GRAPH *g, const char *filename, FILETYPE type)
Definition: graph_save.c:370
static void gmlWriteEdge(const GRAPH *graph, int edge, int tail_id, int head_id, const SCIP_Bool *edgemark, FILE *file)
Definition: graph_save.c:210
#define STP_RSMT
Definition: graphdefs.h:49
int *RESTRICT oeat
Definition: graphdefs.h:231
#define STP_REDUCTION_ADVANCED
Definition: reducedefs.h:41
void graph_writeStpByName(SCIP *scip, const GRAPH *g, const char *filename, SCIP_Real offset)
Definition: graph_save.c:550
static void stp_save(const GRAPH *g, FILE *fp)
Definition: graph_save.c:50
SCIP_Bool extended
Definition: graphdefs.h:267
int stp_type
Definition: graphdefs.h:264
SCIP_RETCODE reduce_exec(SCIP *, GRAPH *, REDSOL *, int, int, SCIP_Bool)
Definition: reduce_base.c:2192
void graph_get_nVET(const GRAPH *, int *, int *, int *)
Definition: graph_stats.c:571
void graph_writeReductionStats(const GRAPH *graph, const char *probname, const char *filename)
Definition: graph_save.c:412
static void getReductionRatios(const GRAPH *graph, SCIP_Real *ratio_nodes, SCIP_Real *ratio_edges)
Definition: graph_save.c:251
SCIP_Real * prize
Definition: graphdefs.h:210
int *RESTRICT grad
Definition: graphdefs.h:201
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_DHCSTP
Definition: graphdefs.h:52
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
#define Edge_anti(a)
Definition: graphdefs.h:106
#define EQ(a, b)
Definition: portab.h:79
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:585
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
void reduce_solFree(SCIP *, REDSOL **)
Definition: reduce_sol.c:818
static void getOrgNodeToNodeMap(const GRAPH *g, int *orgToNewNode)
Definition: graph_save.c:149
#define STP_PCSPG
Definition: graphdefs.h:44
#define STP_OARSMT
Definition: graphdefs.h:50
SCIP_RETCODE graph_writeGmlSub(const GRAPH *graph, const char *filename, const SCIP_Bool *subnodesmark)
Definition: graph_save.c:490
static void gmlWriteNode(const GRAPH *graph, int k, FILE *file)
Definition: graph_save.c:183
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
void graph_pc_getReductionRatios(const GRAPH *, SCIP_Real *, SCIP_Real *)
#define SCIP_Bool
Definition: def.h:84
int *RESTRICT ieat
Definition: graphdefs.h:230
#define STP_NWPTSPG
Definition: graphdefs.h:48
int *RESTRICT tail
Definition: graphdefs.h:223
int *RESTRICT term
Definition: graphdefs.h:196
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
Portable definitions.
#define STP_NWSPG
Definition: graphdefs.h:46
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Real * cost
Definition: graphdefs.h:221
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
Definition: graph_stats.c:110
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
#define SCIP_Real
Definition: def.h:177
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
SCIP_RETCODE graph_writeGml(const GRAPH *graph, const char *filename, const SCIP_Bool *edgemark)
Definition: graph_save.c:441
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
Definition: graph_node.c:52
#define nnodes
Definition: gastrans.c:65
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:673
SCIP_RETCODE graph_writeReductionRatioStatsLive(SCIP *scip, GRAPH *graph, const char *probname)
Definition: graph_save.c:316
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
#define Is_anyTerm(a)
Definition: graphdefs.h:105
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
int hoplimit
Definition: graphdefs.h:216
includes various reduction methods for Steiner tree problems
#define STP_RPCSPG
Definition: graphdefs.h:45
#define STP_MWCSP
Definition: graphdefs.h:51
#define STP_FILE_VERSION_MINOR
Definition: graphdefs.h:113