Detailed Description
several basic reductions for Steiner tree problems
This file implements basic reduction techniques for several Steiner problems. All tests are described in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.
A list of all interface methods can be found in grph.h.
Definition in file reduce_simple.c.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "grph.h"
#include "portab.h"
#include "scip/scip.h"
Go to the source code of this file.
Functions | |
static SCIP_Bool | adjterms (const GRAPH *g) |
static unsigned | nchains (const GRAPH *g) |
static SCIP_Bool | is_maxprize (SCIP *scip, const GRAPH *g, int i, SCIP_Real *maxprize) |
static SCIP_RETCODE | trydg1edgepc (SCIP *scip, GRAPH *g, SCIP_Real *offset, int *solnode, int *count, int i, int iout, SCIP_Bool *rerun, SCIP_Real *maxprize) |
static SCIP_RETCODE | traverseChain (SCIP *scip, GRAPH *g, int *length, int *final, int i, int i1, int i2, int e1) |
static void | adjust0term (SCIP *scip, GRAPH *g, int i) |
SCIP_RETCODE | reduce_contractZeroEdges (SCIP *scip, GRAPH *g, SCIP_Bool savehistory) |
SCIP_RETCODE | reduce_simple (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *solnode, int *nelims, int *edgestate) |
SCIP_RETCODE | reduce_simple_sap (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count) |
SCIP_RETCODE | reduce_rpt (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count) |
SCIP_RETCODE | reduce_simple_mw (SCIP *scip, GRAPH *g, int *solnode, SCIP_Real *fixed, int *count) |
SCIP_RETCODE | reduce_simple_hc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count) |
SCIP_RETCODE | reduce_simple_pc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count, int *solnode, SCIP_Bool contractroot) |
Function Documentation
◆ adjterms()
check whether problem has adjacent terminals
- Parameters
-
g graph data structure
Definition at line 39 of file reduce_simple.c.
References EAT_FREE, GRAPH::edges, FALSE, GRAPH::head, Is_term, GRAPH::mark, GRAPH::oeat, GRAPH::tail, GRAPH::term, and TRUE.
Referenced by reduce_simple_mw().
◆ nchains()
|
static |
count numbers of chains
- Parameters
-
g graph data structure
Definition at line 60 of file reduce_simple.c.
References EAT_FREE, GRAPH::edges, GRAPH::grad, GRAPH::head, Is_term, GRAPH::oeat, GRAPH::tail, and GRAPH::term.
Referenced by reduce_simple_mw().
◆ is_maxprize()
is there no vertex of higher prize?
- Parameters
-
scip SCIP data structure g graph data structure i the terminal to be checked maxprize stores incumbent prize (can be updated)
Definition at line 80 of file reduce_simple.c.
References FALSE, GRAPH::grad, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::prize, SCIP_Real, SCIPdebugMessage, GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, and TRUE.
Referenced by reduce_simple_mw(), reduce_simple_pc(), and trydg1edgepc().
◆ trydg1edgepc()
|
static |
try to eliminate a terminal of degree one
- Parameters
-
scip SCIP data structure g graph data structure offset pointer to store the offset solnode solution nodes or NULL count pointer storing number of eliminated edges i the terminal to be checked iout outgoing arc rerun further eliminations possible? maxprize stores incumbent prize (can be updated)
Definition at line 129 of file reduce_simple.c.
References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knot2nonTerm(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGE(), SCIPisGT(), SCIPisLE(), GRAPH::source, STP_MWCSP, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.
Referenced by reduce_simple_mw(), and reduce_simple_pc().
◆ traverseChain()
|
static |
traverse one side of a chain (MWCSP)
- Parameters
-
scip SCIP data structure g graph data structure length pointer to store length of chain final pointer to store final vertex i start vertex i1 first vertex i2 last vertex e1 first edge
Definition at line 306 of file reduce_simple.c.
References GRAPH::ancestors, GRAPH::cost, EAT_LAST, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), GRAPH::head, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGE(), SCIPisLE(), GRAPH::term, and TRUE.
Referenced by reduce_simple_mw().
◆ adjust0term()
adjust for a (rooted) PC or MW problem
- Parameters
-
scip SCIP data structure g graph data structure i index of the terminal
Definition at line 402 of file reduce_simple.c.
References EAT_LAST, GRAPH::grad, graph_edge_del(), graph_pc_knot2nonTerm(), GRAPH::head, Is_pterm, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), SCIPisZero(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TRUE, and UNKNOWN.
Referenced by reduce_simple_mw(), and reduce_simple_pc().
◆ reduce_contractZeroEdges()
SCIP_RETCODE reduce_contractZeroEdges | ( | SCIP * | scip, |
GRAPH * | g, | ||
SCIP_Bool | savehistory | ||
) |
contract edges of weight zero
- Parameters
-
scip SCIP data structure g graph data structure savehistory save the history?
Definition at line 453 of file reduce_simple.c.
References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::fixedges, flipedge, graph_knot_contract(), GRAPH::head, NULL, GRAPH::oeat, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), SCIPisZero(), and GRAPH::tail.
Referenced by redbasedVarfixing(), and redLoopStp().
◆ reduce_simple()
SCIP_RETCODE reduce_simple | ( | SCIP * | scip, |
GRAPH * | g, | ||
SCIP_Real * | fixed, | ||
int * | solnode, | ||
int * | nelims, | ||
int * | edgestate | ||
) |
basic reduction tests for the STP
- Parameters
-
scip SCIP data structure g graph data structure fixed pointer to offset value solnode node array to mark whether an node is part of a given solution (CONNECT), or NULL nelims pointer to number of reductions edgestate array to store status of (directed) edge (for propagation, can otherwise be set to NULL)
Definition at line 489 of file reduce_simple.c.
References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, EDGE_BLOCKED, EQ, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_knot_contractLowdeg2High(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisLE(), SCIPisLT(), GRAPH::term, TRUE, and UNKNOWN.
Referenced by nvreduce_sl(), and redLoopStp().
◆ reduce_simple_sap()
SCIP_RETCODE reduce_simple_sap | ( | SCIP * | scip, |
GRAPH * | g, | ||
SCIP_Real * | fixed, | ||
int * | count | ||
) |
basic reduction tests for the SAP
- Parameters
-
scip SCIP data structure g graph data structure fixed pointer to offfset value count pointer to number of reductions
Definition at line 684 of file reduce_simple.c.
References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPisGT(), SCIPisLT(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.
Referenced by reduceSap().
◆ reduce_rpt()
SCIP_RETCODE reduce_rpt | ( | SCIP * | scip, |
GRAPH * | g, | ||
SCIP_Real * | fixed, | ||
int * | count | ||
) |
root proximity terminal test (SAP)
- Parameters
-
scip SCIP data structure g graph data structure fixed pointer to offset value count pointer to number of reductions
Definition at line 884 of file reduce_simple.c.
References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_path_execX(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPintListNodeAppendCopy(), SCIPisGT(), GRAPH::source, GRAPH::tail, and GRAPH::term.
Referenced by reduceSap().
◆ reduce_simple_mw()
SCIP_RETCODE reduce_simple_mw | ( | SCIP * | scip, |
GRAPH * | g, | ||
int * | solnode, | ||
SCIP_Real * | fixed, | ||
int * | count | ||
) |
basic reduction tests for the MWCS problem
- Parameters
-
scip SCIP data structure g graph data structure solnode array to indicate whether a node is part of the current solution (==CONNECT) fixed pointer to offset value count pointer to number of reductions
Definition at line 953 of file reduce_simple.c.
References adjterms(), adjust0term(), GRAPH::cost, EAT_LAST, Edge_anti, FALSE, flipedge_Uint, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_contractEdgeAncestors(), graph_pc_deleteTerm(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::knots, level0save(), GRAPH::mark, nchains(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisLE(), SCIPisZero(), GRAPH::source, STP_MWCSP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, traverseChain(), TRUE, and trydg1edgepc().
Referenced by redLoopMw().
◆ reduce_simple_hc()
SCIP_RETCODE reduce_simple_hc | ( | SCIP * | scip, |
GRAPH * | g, | ||
SCIP_Real * | fixed, | ||
int * | count | ||
) |
basic reduction tests for the HCDSTP
- Parameters
-
scip SCIP data structure g graph data structure fixed pointer to offfset value count pointer to number of reductions
Definition at line 1252 of file reduce_simple.c.
References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_DHCSTP, GRAPH::stp_type, GRAPH::term, and TRUE.
Referenced by reduceHc().
◆ reduce_simple_pc()
SCIP_RETCODE reduce_simple_pc | ( | SCIP * | scip, |
GRAPH * | g, | ||
SCIP_Real * | fixed, | ||
int * | count, | ||
int * | solnode, | ||
SCIP_Bool | contractroot | ||
) |
basic reductions for RPCSTP and PCSPG
- Parameters
-
scip SCIP data structure g graph data structure fixed pointer to offset value count pointer to number of reductions solnode solution nodes contractroot contract vertices into root (for rooted prize-collecting)
Definition at line 1330 of file reduce_simple.c.
References adjust0term(), GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, GRAPH::extended, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), graph_knot_contract(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_knot2nonTerm(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, is_maxprize(), Is_pterm, Is_term, GRAPH::knots, level0save(), GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisEQ(), SCIPisLE(), SCIPisLT(), SCIPisZero(), GRAPH::source, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, trydg1edgepc(), and UNKNOWN.
Referenced by nvreduce_sl(), and redLoopPc().