60 fprintf(fp,
"%8x STP File, STP Format Version %2d.%02d\n",
63 fprintf(fp,
"Section Comment\n");
64 fprintf(fp,
"Name \"%s\"\n",
"noname");
65 fprintf(fp,
"End\n\n");
67 fprintf(fp,
"Section Graph\n");
68 fprintf(fp,
"Nodes %d\n", g->
knots);
69 fprintf(fp,
"Edges %d\n", g->
edges / 2);
71 for(i = 0; i < g->
edges; i += 2)
77 fprintf(fp,
"E %d %d %g\n",
83 fprintf(fp,
"End\n\n");
84 fprintf(fp,
"Section Terminals\n");
85 fprintf(fp,
"Terminals %d\n", g->
terms);
87 for(i = 0; i < g->
knots; i++)
90 fprintf(fp,
"T %d\n", i + 1);
92 fprintf(fp,
"End\n\n");
104 fprintf(fp,
"EOF\n");
122 fprintf(fp,
"%d %d\n",
126 for(i = 0; i < g->
edges; i += 2)
132 fprintf(fp,
"%d %d %g\n",
138 fprintf(fp,
"%d\n", g->
terms);
140 for(i = 0; i < g->
knots; i++)
143 fprintf(fp,
"%d\n", i + 1);
158 for(
int k = 0; k <
nnodes; ++k )
162 orgToNewNode[k] = -1;
166 if( g->
grad[k] > 0 || (isPcMw &&
GT(g->
prize[k], 0.0)) )
168 orgToNewNode[k] = nodecount;
173 orgToNewNode[k] = -1;
196 else if( graph->
term[k] == 0 )
227 if( edgemark !=
NULL && edgemark[edge / 2] )
228 SCIPgmlWriteEdge(file, (
unsigned int)tail_id, (
unsigned int)head_id, label,
"#ff0000");
258 const int nedges = graph->
edges;
266 assert(nnodes_real <= nnodes);
267 assert(nedges_real <= nedges);
268 assert(nedges % 2 == 0);
269 assert(nedges_real % 2 == 0);
287 const char* probname,
295 assert(filename && probname);
306 file = fopen(filename,
"a+");
308 fprintf(file,
"%s: %f %f \n", probname, ratio_nodes, ratio_edges);
332 assert(graph && probname);
337 time_start = clock();
353 file = fopen(filename,
"a+");
355 fprintf(file,
"%s: %f %f %f \n", probname, ratio_nodes, ratio_edges, (time_end - time_start) / CLOCKS_PER_SEC);
373 const char* filename,
376 const char* msg_writing_s =
"Writing Graph to File %s:\n";
380 assert(g && scip && filename);
382 assert(strlen(filename) > 0);
385 if ((fp = fopen(filename,
"w")) ==
NULL)
389 printf(msg_writing_s, filename);
414 const char* probname,
424 assert(filename && probname);
428 assert(nnodes_real <= nnodes);
429 assert(nedges_real <= nedges);
430 assert(nedges % 2 == 0);
431 assert(nedges_real % 2 == 0);
433 file = fopen(filename,
"a+");
435 fprintf(file,
"%s: %d %d %d %d \n", probname, nnodes, nedges / 2, nnodes_real, nedges_real / 2);
443 const char* filename,
449 assert(graph !=
NULL);
450 file = fopen((filename !=
NULL) ? filename :
"stpgraph.gml",
"w");
453 for(
int e = 0; e < graph->
edges; e += 2 )
455 assert(graph->
tail[e] == graph->
head[e + 1]);
456 assert(graph->
tail[e + 1] == graph->
head[e]);
463 for(
int k = 0; k < graph->
knots; k++ )
465 if( graph->
grad[k] > 0 || graph->
source == k )
472 for(
int e = 0; e < graph->
edges; e += 2 )
492 const char* filename,
500 assert(graph !=
NULL);
501 file = fopen((filename !=
NULL) ? filename :
"stpgraph.gml",
"w");
504 for( e = 0; e < graph->
edges; e += 2 )
506 assert(graph->
tail[e] == graph->
head[e + 1]);
507 assert(graph->
tail[e + 1] == graph->
head[e]);
515 for(
int k = 0; k < graph->
knots; k++ )
517 if( graph->
grad[k] > 0 || graph->
source == k )
519 if( !subnodesmark[k] )
526 for( e = 0; e < graph->
edges; e += 2 )
530 const int head = graph->
head[e];
531 const int tail = graph->
tail[e];
533 if( !subnodesmark[tail] || !subnodesmark[head] )
553 const char* filename,
560 fp = fopen(filename,
"a+");
586 fprintf(fp,
"%8x STP File, STP Format Version %2d.%02d\n",
589 fprintf(fp,
"Section Comment\n");
590 fprintf(fp,
"Problem ");
594 fprintf(fp,
"\"%s\"\n",
"SPG");
598 fprintf(fp,
"\"%s\"\n",
"UNKNOWN");
602 fprintf(fp,
"\"%s\"\n",
"RPCST");
606 fprintf(fp,
"\"%s\"\n",
"NWSPG");
610 fprintf(fp,
"\"%s\"\n",
"UNKNOWN");
614 fprintf(fp,
"\"%s\"\n",
"STP_NWPTSPG");
618 fprintf(fp,
"\"%s\"\n",
"RSMT");
622 fprintf(fp,
"\"%s\"\n",
"OARSMT");
626 fprintf(fp,
"\"%s\"\n",
"UNKNOWN");
630 fprintf(fp,
"\"%s\"\n",
"UNKNOWN");
634 fprintf(fp,
"\"%s\"\n",
"UNKNOWN");
636 fprintf(fp,
"End\n\n");
640 fprintf(fp,
"Section Presolve\n");
641 fprintf(fp,
"Fixed %f \n", offset);
642 fprintf(fp,
"End\n\n");
651 for(
int i = 0; i <
nnodes; i++ )
657 for(
int i = 0; i < g->
edges; i += 2 )
661 const int tail = g->
tail[i];
662 const int head = g->
head[i];
678 fprintf(fp,
"Section Graph\n");
679 fprintf(fp,
"Nodes %d\n", nnodes_curr);
680 fprintf(fp,
"Edges %d\n", nedges_curr / 2);
682 for(
int i = 0; i < g->
edges; i += 2 )
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];
699 assert(0 <= tail_curr && tail_curr < nnodes_curr);
700 assert(0 <= head_curr && head_curr < nnodes_curr);
708 fprintf(fp,
"%d %d ", tail_curr + 1, head_curr + 1);
711 fprintf(fp,
"%f\n", g->
cost[i]);
717 fprintf(fp,
"End\n\n");
718 fprintf(fp,
"Section Terminals\n");
719 fprintf(fp,
"Terminals %d\n", g->
terms);
723 assert(0 <= orgToNewNode[g->
source] && orgToNewNode[g->
source] < nnodes_curr);
724 fprintf(fp,
"RootP %d\n", orgToNewNode[g->
source] + 1);
727 for(
int i = 0; i < g->
knots; i++ )
729 const int i_curr = orgToNewNode[i];
731 if( g->
grad[i] == 0 )
735 assert(0 <= i_curr && i_curr < nnodes_curr);
737 fprintf(fp,
"TP %d %f\n", i_curr + 1, g->
prize[i]);
752 assert(0 <= i_curr && i_curr < nnodes_curr);
753 fprintf(fp,
"TP %d %f\n", i_curr + 1, g->
prize[i]);
758 assert(0 <= i_curr && i_curr < nnodes_curr);
760 fprintf(fp,
"TF %d\n", i_curr + 1);
764 assert(0 <= i_curr && i_curr < nnodes_curr);
767 fprintf(fp,
"T %d\n", i_curr + 1);
769 fprintf(fp,
"End\n\n");
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++ )
779 fprintf(fp,
"HC %d %d\n", e + 1, hopfactor);
781 fprintf(fp,
"End\n\n");
788 fprintf(fp,
"Section Degree Constraint\n");
789 fprintf(fp,
"End\n\n");
792 fprintf(fp,
"EOF\n");
807 assert(scip !=
NULL);
808 assert(graph !=
NULL);
810 fptr = fopen(filename,
"w");
811 assert(fptr !=
NULL);
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);
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");
824 fprintf(fptr,
"SECTION Terminals\n");
825 fprintf(fptr,
"Terminals %d\n", graph->
terms);
827 for(
int k = 0; k < graph->
knots; k++ )
829 fprintf(fptr,
"T %d\n", k + 1);
831 fprintf(fptr,
"END\n\n");
833 fprintf(fptr,
"EOF\n");
int graph_get_nEdges(const GRAPH *)
SCIP_RETCODE SCIPgetStringParam(SCIP *scip, const char *name, char **value)
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
SCIP_RETCODE reduce_solInit(SCIP *, const GRAPH *, SCIP_Bool, REDSOL **)
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
void graph_writeReductionRatioStats(const GRAPH *graph, const char *probname, const char *filename)
void graph_writeStpOrg(SCIP *scip, const GRAPH *graph, const char *filename)
void SCIPgmlWriteClosing(FILE *file)
int SCIPsnprintf(char *t, int len, const char *s,...)
enum SCIP_Retcode SCIP_RETCODE
includes various files containing graph methods used for Steiner tree problems
void graph_writeStp(SCIP *scip, const GRAPH *g, FILE *fp, SCIP_Real offset)
#define STP_FILE_VERSION_MAJOR
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
static void getReductionRatiosPcMw(const GRAPH *graph, SCIP_Real *ratio_nodes, SCIP_Real *ratio_edges)
static void bea_save(const GRAPH *g, FILE *fp)
void graph_save(SCIP *scip, const GRAPH *g, const char *filename, FILETYPE type)
static void gmlWriteEdge(const GRAPH *graph, int edge, int tail_id, int head_id, const SCIP_Bool *edgemark, FILE *file)
#define STP_REDUCTION_ADVANCED
void graph_writeStpByName(SCIP *scip, const GRAPH *g, const char *filename, SCIP_Real offset)
static void stp_save(const GRAPH *g, FILE *fp)
SCIP_RETCODE reduce_exec(SCIP *, GRAPH *, REDSOL *, int, int, SCIP_Bool)
void graph_get_nVET(const GRAPH *, int *, int *, int *)
void graph_writeReductionStats(const GRAPH *graph, const char *probname, const char *filename)
static void getReductionRatios(const GRAPH *graph, SCIP_Real *ratio_nodes, SCIP_Real *ratio_edges)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
void SCIPgmlWriteEdge(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
void reduce_solFree(SCIP *, REDSOL **)
static void getOrgNodeToNodeMap(const GRAPH *g, int *orgToNewNode)
SCIP_RETCODE graph_writeGmlSub(const GRAPH *graph, const char *filename, const SCIP_Bool *subnodesmark)
static void gmlWriteNode(const GRAPH *graph, int k, FILE *file)
#define SCIPallocBufferArray(scip, ptr, num)
void graph_pc_getReductionRatios(const GRAPH *, SCIP_Real *, SCIP_Real *)
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Bool graph_pc_knotIsFixedTerm(const GRAPH *, int)
SCIP_Bool graph_edge_isInRange(const GRAPH *, int)
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
int graph_get_nNodes(const GRAPH *)
SCIP_RETCODE graph_writeGml(const GRAPH *graph, const char *filename, const SCIP_Bool *edgemark)
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
SCIP_RETCODE graph_writeReductionRatioStatsLive(SCIP *scip, GRAPH *graph, const char *probname)
#define SCIP_CALL_ABORT(x)
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
includes various reduction methods for Steiner tree problems
#define STP_FILE_VERSION_MINOR