extreduce_bottleneck.c
Go to the documentation of this file.
20 * This file implements tree bottleneck algorithms for extended reduction techniques for Steiner problems.
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67 assert(bottleneckDist_node[vertex_unmarked] == -1.0 || vertex_unmarked == tree_root || tree_deg[vertex_unmarked] > 1);
85 for( currentNode = vertex_unmarked; bottleneckDist_node[currentNode] < -0.5; currentNode = parentNode[currentNode] )
134 for( int currentNode = path_start; currentNode != path_end; currentNode = parentNode[currentNode] )
188 assert(bottleneckDist_node[vertex_unmarked] == -1.0 || vertex_unmarked == tree_root || tree_deg[vertex_unmarked] > 1);
205 for( currentNode = vertex_unmarked; bottleneckDist_node[currentNode] < -0.5; currentNode = parentNode[currentNode] )
249 for( int currentNode = vertex_pathmarked; currentNode != ancestor; currentNode = parentNode[currentNode] )
387 assert(childNode == extdata->tree_starcenter || extInitialCompIsGenStar(extdata) || tree_deg[childNode] == 1);
447 for( int currentNode = parentNode[vertex]; currentNode != -1; currentNode = parentNode[currentNode] )
491 SCIPdebugMessage("domination test %d->%d: sd=%f bottleneck=%f \n", vertex_pathmarked, vertex_unmarked, specialDist, bottleneckDist);
500 assert(EQ(extreduce_extGetSdDouble(scip, graph, vertex_pathmarked, vertex_unmarked, extdata), specialDist));
502 assert(LE(extreduce_extGetSdDouble(scip, graph, vertex_pathmarked, vertex_unmarked, extdata), specialDist));
509 bottleneckMarkEqualityEdges(scip, graph, specialDist, vertex_pathmarked, vertex_unmarked, extdata);
525 SCIP_Real specialDistBiased, /**< best computed special distance approximation (-1.0 if unknown) */
546 SCIPdebugMessage("biased domination test %d->%d: sd=%f bottleneck=%f \n", vertex_pathmarked, vertex_unmarked, specialDistBiased, bottleneckDist);
607 SCIPdebugMessage("extedge domination test %d->%d: sd=%f bottleneck=%f \n", vertex_pathmarked, vertex_unmarked, specialDist, bottleneckDist);
620 assert(EQ(extreduce_extGetSdDouble(scip, graph, vertex1, vertex_unmarked, extdata), specialDist));
622 assert(LE(extreduce_extGetSdDouble(scip, graph, vertex1, vertex_unmarked, extdata), specialDist));
628 bottleneckMarkEqualityEdges(scip, graph, specialDist, vertex_pathmarked, vertex_unmarked, extdata);
646 SCIP_Real specialDistBiased, /**< best computed biased special distance approximation (-1.0 if unknown) */
671 SCIPdebugMessage("extedge biased domination test %d->%d: sd=%f bottleneck=%f \n", vertex_pathmarked, vertex_unmarked, specialDistBiased, bottleneckDist);
688 SCIP_Real specialDist, /**< best computed special distance approximation (FARAWAY if unknown) */
756 SCIP_Real specialDistBiased, /**< best computed special distance approximation (FARAWAY if unknown) */
821 if( extreduce_bottleneckWithExtedgeIsDominated(scip, graph, edge2neighbor, neighbor_base, cand, specialDist, extdata) )
860 if( extreduce_bottleneckWithExtedgeIsDominated(scip, graph, edge2neighbor, neighbor_base, node, specialDist, extdata) )
SCIP_Bool extreduce_bottleneckWithExtedgeIsDominated(SCIP *scip, const GRAPH *graph, int extedge, int vertex_pathmarked, int vertex_unmarked, SCIP_Real specialDist, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:561
void extreduce_bottleneckMarkRootPath(const GRAPH *graph, int vertex, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:354
static SCIP_Bool extInitialCompIsGenStar(const EXTDATA *extdata)
Definition: extreducedefs.h:293
Definition: graphdefs.h:184
Definition: extreducedefs.h:187
Definition: extreducedefs.h:161
Definition: struct_scip.h:59
void extreduce_bottleneckCheckNonLeaves(SCIP *scip, const GRAPH *graph, int edge2neighbor, EXTDATA *extdata, SCIP_Bool *ruledOut)
Definition: extreduce_bottleneck.c:833
SCIP_Bool extreduce_bottleneckIsDominatedBiased(SCIP *scip, const GRAPH *graph, int vertex_pathmarked, int vertex_unmarked, SCIP_Real specialDistBiased, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:520
includes various files containing graph methods used for Steiner tree problems
static SCIP_Bool extInitialCompIsEdge(const EXTDATA *extdata)
Definition: extreducedefs.h:264
void extreduce_bottleneckUnmarkRootPath(const GRAPH *graph, int vertex, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:422
static SCIP_Real bottleneckGetDist(const GRAPH *graph, const EXTDATA *extdata, int vertex_pathmarked, int vertex_unmarked)
Definition: extreduce_bottleneck.c:48
static void bottleneckMarkEqualityPath(SCIP *scip, const GRAPH *graph, int path_start, int path_end, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:118
SCIP_Bool extreduce_bottleneckToSiblingIsDominatedBiased(SCIP *scip, const GRAPH *graph, int extedge, int edge2sibling, SCIP_Real specialDistBiased, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:751
SCIP_Real extreduce_distDataGetSdDoubleForbiddenEq(SCIP *, const GRAPH *, SCIP_Real, int, int, int, EXTDATA *)
Definition: extreduce_dist.c:1609
SCIP_Bool graph_pc_termIsNonLeafTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1431
This file implements extended reduction techniques for several Steiner problems.
static SCIP_Real extSdIsNonTrivial(SCIP_Real specialDist)
Definition: extreducedefs.h:516
SCIP_Real extreduce_extGetSdDouble(SCIP *, const GRAPH *, int, int, EXTDATA *)
Definition: extreduce_extmst.c:2214
SCIP_Real extreduce_extGetSd(SCIP *, const GRAPH *, int, int, EXTDATA *)
Definition: extreduce_extmst.c:2200
static void bottleneckMarkEqualityEdge(SCIP *scip, const GRAPH *g, int edge, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:293
SCIP_Bool extreduce_bottleneckIsDominated(SCIP *scip, const GRAPH *graph, int vertex_pathmarked, int vertex_unmarked, SCIP_Real specialDist, int edge_forbidden, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:464
SCIP_Bool extreduce_bottleneckWithExtedgeIsDominatedBiased(SCIP *scip, const GRAPH *graph, int extedge, int vertex_pathmarked, int vertex_unmarked, SCIP_Real specialDistBiased, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:640
includes extended reductions definitions and inline methods used for Steiner tree problems ...
SCIP_Bool *const sdeq_edgesIsForbidden
Definition: extreducedefs.h:206
static void bottleneckMarkEqualityEdges(SCIP *scip, const GRAPH *graph, SCIP_Real dist_eq, int vertex_pathmarked, int vertex_unmarked, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:167
SCIP_Real *const tree_bottleneckDistNode
Definition: extreducedefs.h:197
Portable definitions.
SCIP_Bool sdeq_hasForbiddenEdges
Definition: extreducedefs.h:208
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1344
static SCIP_Bool ruledOut(SCIP *scip, const GRAPH *graph, EXTDATA *extdata)
Definition: extreduce_contract.c:446
static SCIP_Bool extIsAtInitialGenStar(const EXTDATA *extdata)
Definition: extreducedefs.h:315
static SCIP_Bool bottleneckIsEqualityDominated(SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int edge_forbidden, int vertex1, int vertex2, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:316
SCIP_Bool extreduce_bottleneckToSiblingIsDominated(SCIP *scip, const GRAPH *graph, int extedge, int edge2sibling, SCIP_Real specialDist, EXTDATA *extdata)
Definition: extreduce_bottleneck.c:683
Definition: objbenders.h:33
void extreduce_bottleneckCheckNonLeaves_pc(SCIP *scip, const GRAPH *graph, int edge2neighbor, EXTDATA *extdata, SCIP_Bool *ruledOut)
Definition: extreduce_bottleneck.c:787
SCIP_Real *const tree_parentEdgeCost
Definition: extreducedefs.h:199