Scippy

SCIP

Solving Constraint Integer Programs

reduce_sd.c File Reference

Detailed Description

special distance (bottleneck distance) reduction methods for Steiner problems

Author
Daniel Rehfeldt

This file encompasses various special distance (aka bottleneck distance) based reduction methods for Steiner problems.

A list of all interface methods can be found in reduce.h.

Definition in file reduce_sd.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "misc_stp.h"
#include "probdata_stp.h"
#include "scip/scip.h"
#include "portab.h"

Go to the source code of this file.

Macros

#define STP_BD_MAXDEGREE   4
 
#define STP_BD_MAXDNEDGES   6
 
#define STP_SDWALK_MAXNPREVS   8
 

Functions

static SCIP_RETCODE sdStarInit (SCIP *scip, const GRAPH *g, int edgelimit, DIJK **dijkdata, int *RESTRICT *star_base, SCIP_Bool *RESTRICT *edge_deletable)
 
static void sdStarFinalize (SCIP *scip, GRAPH *g, DIJK **dijkdata, int *RESTRICT *star_base, SCIP_Bool *RESTRICT *edge_deletable)
 
static void sdStarReset (int nnodes, int nvisits, const int *visitlist, int *RESTRICT star_base, SCIP_Real *RESTRICT dist, STP_Bool *RESTRICT visited, DHEAP *RESTRICT dheap)
 
static SCIP_RETCODE sdStarBiasedProcessNode (SCIP *scip, int node, SCIP_Bool usestrongreds, const SDPROFIT *sdprofit, GRAPH *g, DIJK *dijkdata, int *RESTRICT star_base, SCIP_Bool *RESTRICT edge_deletable, int *nelims)
 
static void sdwalkReset (int nnodes, int nvisits, const int *visitlist, SCIP_Real *RESTRICT dist, int *RESTRICT state, STP_Bool *RESTRICT visited)
 
static void sdwalkResetExt (int nnodes, int nvisits, const int *visitlist, SCIP_Real *RESTRICT dist, int *RESTRICT nprevterms, int *RESTRICT state, STP_Bool *RESTRICT visited)
 
static void sdwalkResetExt2 (int nnodes, int nvisits, const int *visitlist, SCIP_Real *dist, int *nprevterms, int *nprevNPterms, int *nprevedges, int *state, STP_Bool *visited)
 
static SCIP_Bool sddeltable (SCIP *scip, GRAPH *g, PATH *path, int *vbase, int *forbidden, int tpos, int hpos, int tail, int head, int edge, int nnodes)
 
static int getcloseterms (SCIP *scip, const PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, const int *vbase, int *neighbterms, int i, int nnodes)
 
static int getcloseterms2term (SCIP *scip, const GRAPH *g, const GRAPH *netgraph, SCIP_Real *termdist, SCIP_Real ecost, int *neighbterms, int *nodesid, int *nodesorg, int i)
 
static int getlecloseterms (SCIP *scip, PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, int *vbase, int *neighbterms, int i, int nnodes)
 
static void pcBiasCostsDCSR (SCIP *scip, const GRAPH *g, SCIP_Bool biasreversed, SCIP_Real *costbiased, SCIP_Real *mincost_in)
 
static SCIP_Real getSd (SCIP *scip, GRAPH *g, SDGRAPH *sdgraph, PATH *vnoi, SCIP_Real sd_initial, int *vbase, int i, int i2, int limit)
 
static SCIP_Real sdGetSd (const GRAPH *g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SCIP_Bool onlyIntermedTerms, SD *sddata)
 
static SCIP_Real sdGetSdNeighbor (const GRAPH *g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SD *sddata)
 
static SCIP_Bool isPseudoDeletableDeg3 (SCIP *scip, const GRAPH *g, const SCIP_Real *sdsK3, const int *edgesK3, SCIP_Real costK3, SCIP_Bool allowEquality)
 
static SCIP_Bool isPseudoDeletable (SCIP *scip, const GRAPH *g, const GRAPH *auxg, const SCIP_Real *ecost, const int *edges, int degree)
 
static SCIP_RETCODE sdCliqueInitData (SCIP *scip, const GRAPH *g, int centernode, const GRAPH *cliquegraph, const int *cliqueNodeMap, DIJK *dijkdata, SDCLIQUE *sdclique)
 
static void sdCliqueFreeData (SCIP *scip, SDCLIQUE *sdclique)
 
static SCIP_RETCODE sdCliqueUpdateGraphWithStarWalks (SCIP *scip, const GRAPH *g, const SDPROFIT *sdprofit, GRAPH *cliquegraph, SDCLIQUE *sdclique)
 
static void sdGetSdsCliqueTermWalks (const GRAPH *g, SD *RESTRICT sddata, GRAPH *RESTRICT cliquegraph, SDCLIQUE *RESTRICT sdclique)
 
static SCIP_RETCODE ledgeFromNetgraph (SCIP *scip, const GRAPH *netgraph, const PATH *mst, const int *edgeorg, const PATH *vnoi, const int *vbase, GRAPH *g, int *nelims)
 
SCIP_RETCODE reduce_sdGetSdsCliquegraph (SCIP *scip, const GRAPH *g, int centernode, const int *cliqueNodeMap, DIJK *dijkdata, SD *sddata, GRAPH *cliquegraph)
 
SCIP_RETCODE reduce_sdImpLongEdge (SCIP *scip, const int *edgestate, GRAPH *g, SD *sdistance, int *nelims)
 
SCIP_RETCODE reduce_sd (SCIP *scip, GRAPH *g, REDBASE *redbase, int *nelims)
 
SCIP_RETCODE reduce_sdBiased (SCIP *scip, SD *sdistance, GRAPH *g, int *nelims)
 
SCIP_RETCODE reduce_sdBiasedNeighbor (SCIP *scip, SD *sdistance, GRAPH *g, int *nelims)
 
SCIP_RETCODE reduce_sdPc (SCIP *scip, GRAPH *g, PATH *vnoi, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *nelims)
 
SCIP_RETCODE reduce_getSdByPaths (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, SCIP_Real *sdist, SCIP_Real distlimit, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int i, int i2, int limit, SCIP_Bool pc, SCIP_Bool mw)
 
SCIP_Real reduce_sdGetSd (const GRAPH *g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SD *sddata)
 
SCIP_Real reduce_sdGetSdIntermedTerms (const GRAPH *g, int i, int i2, SCIP_Real sd_upper, SCIP_Real sd_sufficient, SD *sddata)
 
static SCIP_Real sdGetSdPcMw (SCIP *scip, const GRAPH *g, SCIP_Real distlimit, int i, int i2, int edgelimit, SD1PC *sd1pc)
 
SCIP_RETCODE reduce_sdspSap (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
 
SCIP_RETCODE reduce_sdWalk_csr (SCIP *scip, int edgelimit, const int *edgestate, GRAPH *g, int *termmark, SCIP_Real *dist, int *visitlist, STP_Bool *visited, DHEAP *dheap, int *nelims)
 
SCIP_RETCODE reduce_sdEdgeCliqueStar (SCIP *scip, int edgelimit, GRAPH *g, int *nelims)
 
SCIP_RETCODE reduce_sdWalkTriangle (SCIP *scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH *g, int *termmark, SCIP_Real *dist, int *visitlist, STP_Bool *visited, DHEAP *dheap, int *nelims)
 
SCIP_RETCODE reduce_sdStar (SCIP *scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH *g, SCIP_Real *dist, int *star_base, int *visitlist, STP_Bool *visited, DHEAP *dheap, int *nelims)
 
SCIP_RETCODE reduce_sdStarBiased (SCIP *scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH *g, int *nelims)
 
SCIP_RETCODE reduce_sdStarBiasedWithProfit (SCIP *scip, int edgelimit, const SDPROFIT *sdprofit, SCIP_Bool usestrongreds, GRAPH *g, int *nelims)
 
SCIP_RETCODE reduce_sdStarPc2 (SCIP *scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH *g, SCIP_Real *dist, int *star_base, int *visitlist, STP_Bool *visited, DHEAP *dheap, int *nelims)
 
SCIP_RETCODE reduce_sdStarPc (SCIP *scip, int edgelimit, const int *edgestate, GRAPH *g, SCIP_Real *dist, int *star_base, int *visitlist, STP_Bool *visited, DHEAP *dheap, int *nelims)
 
SCIP_RETCODE reduce_sdWalk (SCIP *scip, int edgelimit, const int *edgestate, GRAPH *g, int *termmark, SCIP_Real *dist, int *heap, int *state, int *visitlist, STP_Bool *visited, int *nelims)
 
SCIP_RETCODE reduce_sdWalkExt (SCIP *scip, int edgelimit, SCIP_Bool usestrongreds, GRAPH *g, SCIP_Real *dist, int *heap, int *state, int *visitlist, STP_Bool *visited, int *nelims)
 
SCIP_RETCODE reduce_sdWalkExt2 (SCIP *scip, int edgelimit, const int *edgestate, GRAPH *g, int *termmark, SCIP_Real *dist, int *heap, int *state, int *visitlist, STP_Bool *visited, int *nelims)
 
SCIP_RETCODE reduce_sdsp (SCIP *scip, GRAPH *g, PATH *pathtail, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit, SCIP_Bool usestrongreds)
 
SCIP_RETCODE reduce_bd34WithSd (SCIP *scip, GRAPH *g, SDGRAPH *sdgraph, PATH *vnoi, int *vbase, int *nelims)
 
SCIP_RETCODE reduce_bd34 (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit, SCIP_Real *offset)
 

Macro Definition Documentation

◆ STP_BD_MAXDEGREE

#define STP_BD_MAXDEGREE   4

Definition at line 42 of file reduce_sd.c.

Referenced by isPseudoDeletable(), reduce_bd34(), and reduce_bd34WithSd().

◆ STP_BD_MAXDNEDGES

#define STP_BD_MAXDNEDGES   6

Definition at line 43 of file reduce_sd.c.

Referenced by reduce_bd34(), and reduce_bd34WithSd().

◆ STP_SDWALK_MAXNPREVS

#define STP_SDWALK_MAXNPREVS   8

Definition at line 44 of file reduce_sd.c.

Referenced by reduce_sdWalkExt(), and reduce_sdWalkExt2().

Function Documentation

◆ sdStarInit()

static SCIP_RETCODE sdStarInit ( SCIP scip,
const GRAPH g,
int  edgelimit,
DIJK **  dijkdata,
int *RESTRICT *  star_base,
SCIP_Bool *RESTRICT *  edge_deletable 
)
static

initializes data needed for SD star tests

Parameters
scipSCIP data structure
ggraph data structure
edgelimitlimit
dijkdatadata to be allocated
star_basedata to be allocated
edge_deletabledata to be allocated

Definition at line 53 of file reduce_sd.c.

References EQ, GRAPH::extended, FALSE, FARAWAY, graph_dijkLimited_init(), graph_get_nEdges(), graph_get_nNodes(), graph_heap_isClean(), graph_pc_isPcMw(), nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and SDSTAR_BASE_UNSET.

Referenced by reduce_sdStarBiasedWithProfit().

◆ sdStarFinalize()

static void sdStarFinalize ( SCIP scip,
GRAPH g,
DIJK **  dijkdata,
int *RESTRICT *  star_base,
SCIP_Bool *RESTRICT *  edge_deletable 
)
static

finalizes SD star tests

Parameters
scipSCIP data structure
ggraph data structure
dijkdatadata to be freed
star_basedata to be freed
edge_deletabledata to be freed

Definition at line 103 of file reduce_sd.c.

References GRAPH::dcsr_storage, EAT_FREE, graph_dijkLimited_free(), graph_edge_delBlocked(), graph_get_nEdges(), GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::mark, GRAPH::oeat, SCIP_Bool, SCIPfreeBufferArray, GRAPH::tail, and TRUE.

Referenced by reduce_sdStarBiasedWithProfit().

◆ sdStarReset()

static void sdStarReset ( int  nnodes,
int  nvisits,
const int *  visitlist,
int *RESTRICT  star_base,
SCIP_Real *RESTRICT  dist,
STP_Bool *RESTRICT  visited,
DHEAP *RESTRICT  dheap 
)
inlinestatic

resets data needed for SD star tests

Parameters
nnodesnumber of nodes
nvisitsnumber of visits
visitlistarray of visited nodes
star_basestar-bases
distnode distances
visitedvisit mark
dheapDijkstra heap

Definition at line 135 of file reduce_sd.c.

References FALSE, FARAWAY, graph_heap_clean(), nnodes, SDSTAR_BASE_UNSET, and UNKNOWN.

Referenced by reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), and sdStarBiasedProcessNode().

◆ sdStarBiasedProcessNode()

static SCIP_RETCODE sdStarBiasedProcessNode ( SCIP scip,
int  node,
SCIP_Bool  usestrongreds,
const SDPROFIT sdprofit,
GRAPH g,
DIJK dijkdata,
int *RESTRICT  star_base,
SCIP_Bool *RESTRICT  edge_deletable,
int *  nelims 
)
static

checks node

Parameters
scipSCIP data structure
nodenode to process
usestrongredsallow strong reductions?
sdprofitSD profit
ggraph data structure
dijkdatadata
star_basedata to be freed
edge_deletabledata to be freed
nelimspoint to store number of deleted edges

Definition at line 172 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, dijkstra_data::dheap, dynamic_csr_storage::edgeid, FALSE, graph_dcsr_deleteEdgeBi(), graph_get_nNodes(), graph_sdStarBiased(), dynamic_csr_storage::head, GRAPH::mark, nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPisEQ(), SCIPisLE(), SDSTAR_BASE_KILLED, SDSTAR_BASE_UNSET, sdStarReset(), TRUE, and dijkstra_data::visitlist.

Referenced by reduce_sdStarBiasedWithProfit().

◆ sdwalkReset()

static void sdwalkReset ( int  nnodes,
int  nvisits,
const int *  visitlist,
SCIP_Real *RESTRICT  dist,
int *RESTRICT  state,
STP_Bool *RESTRICT  visited 
)
inlinestatic

resets data needed for SD walk tests

Definition at line 253 of file reduce_sd.c.

References FALSE, FARAWAY, nnodes, and UNKNOWN.

Referenced by reduce_sdWalk(), reduce_sdWalk_csr(), and reduce_sdWalkTriangle().

◆ sdwalkResetExt()

static void sdwalkResetExt ( int  nnodes,
int  nvisits,
const int *  visitlist,
SCIP_Real *RESTRICT  dist,
int *RESTRICT  nprevterms,
int *RESTRICT  state,
STP_Bool *RESTRICT  visited 
)
inlinestatic

Definition at line 281 of file reduce_sd.c.

References FALSE, FARAWAY, nnodes, and UNKNOWN.

Referenced by reduce_sdWalkExt().

◆ sdwalkResetExt2()

static void sdwalkResetExt2 ( int  nnodes,
int  nvisits,
const int *  visitlist,
SCIP_Real dist,
int *  nprevterms,
int *  nprevNPterms,
int *  nprevedges,
int *  state,
STP_Bool visited 
)
inlinestatic

Definition at line 312 of file reduce_sd.c.

References FALSE, FARAWAY, nnodes, and UNKNOWN.

Referenced by reduce_sdWalkExt2().

◆ sddeltable()

static SCIP_Bool sddeltable ( SCIP scip,
GRAPH g,
PATH path,
int *  vbase,
int *  forbidden,
int  tpos,
int  hpos,
int  tail,
int  head,
int  edge,
int  nnodes 
)
static

◆ getcloseterms()

static int getcloseterms ( SCIP scip,
const PATH vnoi,
SCIP_Real termdist,
SCIP_Real  ecost,
const int *  vbase,
int *  neighbterms,
int  i,
int  nnodes 
)
static

gets distances to close terminals

Definition at line 464 of file reduce_sd.c.

References shortest_path::dist, nnodes, NULL, and SCIPisLT().

Referenced by getSd(), and reduce_sdPc().

◆ getcloseterms2term()

static int getcloseterms2term ( SCIP scip,
const GRAPH g,
const GRAPH netgraph,
SCIP_Real termdist,
SCIP_Real  ecost,
int *  neighbterms,
int *  nodesid,
int *  nodesorg,
int  i 
)
static

◆ getlecloseterms()

static int getlecloseterms ( SCIP scip,
PATH vnoi,
SCIP_Real termdist,
SCIP_Real  ecost,
int *  vbase,
int *  neighbterms,
int  i,
int  nnodes 
)
static

Definition at line 554 of file reduce_sd.c.

References shortest_path::dist, nnodes, NULL, and SCIPisLE().

Referenced by reduce_sd().

◆ pcBiasCostsDCSR()

static void pcBiasCostsDCSR ( SCIP scip,
const GRAPH g,
SCIP_Bool  biasreversed,
SCIP_Real costbiased,
SCIP_Real mincost_in 
)
static

bias DCSR costs for PCMW

Parameters
scipSCIP data structure
ggraph data structure
biasreversedbias reversed
costbiasedbiased edge cost
mincost_invertex distances

Definition at line 595 of file reduce_sd.c.

References BMScopyMemoryArray, dynamic_csr_storage::cost, GRAPH::dcsr_storage, GRAPH::edges, csr_range::end, GRAPH::extended, FARAWAY, graph_pc_isPcMw(), dynamic_csr_storage::head, Is_term, GRAPH::knots, LT, GRAPH::mark, dynamic_csr_storage::nedges, nnodes, GRAPH::prize, dynamic_csr_storage::range, SCIP_Real, SCIPisNegative(), and GRAPH::term.

Referenced by reduce_sdStarPc(), and reduce_sdStarPc2().

◆ getSd()

static SCIP_Real getSd ( SCIP scip,
GRAPH g,
SDGRAPH sdgraph,
PATH vnoi,
SCIP_Real  sd_initial,
int *  vbase,
int  i,
int  i2,
int  limit 
)
static

get special distance to a single edge

Parameters
scipSCIP data structure
ggraph structure
sdgraphspecial distance graph
vnoipath structure
sd_initialinitial sd or -1.0
vbasebases for nearest terminals
ifirst vertex
i2second vertex
limitlimit for incident edges to consider

Definition at line 703 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, FARAWAY, GE, getcloseterms(), graph_get_nNodes(), GT, GRAPH::head, Is_term, LT, MAX, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetSd(), SCIP_Real, SCIPisGT(), and GRAPH::term.

Referenced by reduce_bd34WithSd().

◆ sdGetSd()

static SCIP_Real sdGetSd ( const GRAPH g,
int  i,
int  i2,
SCIP_Real  sd_upper,
SCIP_Real  sd_sufficient,
SCIP_Bool  onlyIntermedTerms,
SD sddata 
)
inlinestatic

gets special distance to a pair of nodes

Parameters
ggraph structure
ifirst vertex
i2second vertex
sd_upperupper bound on special distance that is accepted (can be FARAWAY)
sd_sufficientbound below which to terminate (can be 0.0)
onlyIntermedTermsallow only paths with intermediate terms
sddataSD

Definition at line 815 of file reduce_sd.c.

References EQ, GE, graph_tpathsGet4CloseTerms(), GT, Is_term, LT, MAX, NULL, reduce_sdgraphGetSd(), SCIP_Bool, SCIP_Real, special_distance_storage::sdgraph, GRAPH::term, and special_distance_storage::terminalpaths.

Referenced by reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdGetSd(), reduce_sdGetSdIntermedTerms(), and sdGetSdsCliqueTermWalks().

◆ sdGetSdNeighbor()

static SCIP_Real sdGetSdNeighbor ( const GRAPH g,
int  i,
int  i2,
SCIP_Real  sd_upper,
SCIP_Real  sd_sufficient,
SD sddata 
)
static

gets special distance to a pair of nodes

Parameters
ggraph structure
ifirst vertex
i2second vertex
sd_upperupper bound on special distance that is accepted (can be FARAWAY)
sd_sufficientbound below which to terminate (can be 0.0)
sddataSD

Definition at line 912 of file reduce_sd.c.

References GT, Is_term, LT, MAX, reduce_sdgraphGetSd(), reduce_sdneighborGetCloseTerms(), SCIP_Bool, SCIP_Real, special_distance_storage::sdgraph, special_distance_storage::sdneighbors, and GRAPH::term.

Referenced by reduce_sdBiasedNeighbor().

◆ isPseudoDeletableDeg3()

static SCIP_Bool isPseudoDeletableDeg3 ( SCIP scip,
const GRAPH g,
const SCIP_Real sdsK3,
const int *  edgesK3,
SCIP_Real  costK3,
SCIP_Bool  allowEquality 
)
inlinestatic

is node of degree 3 pseudo-deletable?

Parameters
scipSCIP data structure
ggraph structure
sdsK3(unordered) special distances of K3
edgesK3(unordered) edges of K3
costK3total edge cost
allowEqualityallow equality?

Definition at line 989 of file reduce_sd.c.

References FALSE, graph_pseudoAncestors_edgesInConflict(), SCIPisLE(), SCIPisLT(), and TRUE.

Referenced by isPseudoDeletable(), reduce_bd34(), and reduce_bd34WithSd().

◆ isPseudoDeletable()

static SCIP_Bool isPseudoDeletable ( SCIP scip,
const GRAPH g,
const GRAPH auxg,
const SCIP_Real ecost,
const int *  edges,
int  degree 
)
static

is given graph not part of at least one optimal solution?

Parameters
scipSCIP data structure
ggraph structure
auxgauxiliary graph structure
ecostadjacent edges costs
edgesadjacent edges of node
degreedegree of the node to be checked

Definition at line 1033 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EQ, FALSE, graph_isMarked(), graph_path_exec(), graph_pseudoAncestors_edgesInConflict(), GRAPH::head, isPseudoDeletableDeg3(), MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPisGT(), STP_BD_MAXDEGREE, TRUE, and UNKNOWN.

Referenced by bdkTryDegGe4(), reduce_bd34(), reduce_bd34WithSd(), and spg3StarNeighborRuleOut().

◆ sdCliqueInitData()

static SCIP_RETCODE sdCliqueInitData ( SCIP scip,
const GRAPH g,
int  centernode,
const GRAPH cliquegraph,
const int *  cliqueNodeMap,
DIJK dijkdata,
SDCLIQUE sdclique 
)
inlinestatic

initializes data

Parameters
scipSCIP
gthe graph
centernodecenter node or - 1
cliquegraphclique graph
cliqueNodeMapmaps clique graph vertices to original ones
dijkdatadata for repeated path computations
sdcliqueclique

Definition at line 1122 of file reduce_sd.c.

References special_distance_clique::centernode, special_distance_clique::cliquenodes, special_distance_clique::cliqueToNodeMap, special_distance_clique::dijkdata, GRAPH::edges, graph_get_nNodes(), GRAPH::mark, special_distance_clique::ncliquenodes, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, and special_distance_clique::sds.

Referenced by reduce_sdGetSdsCliquegraph().

◆ sdCliqueFreeData()

static void sdCliqueFreeData ( SCIP scip,
SDCLIQUE sdclique 
)
inlinestatic

frees data

Parameters
scipSCIP
sdcliqueclique

Definition at line 1166 of file reduce_sd.c.

References special_distance_clique::cliquenodes, SCIPfreeBufferArray, and special_distance_clique::sds.

Referenced by reduce_sdGetSdsCliquegraph().

◆ sdCliqueUpdateGraphWithStarWalks()

static SCIP_RETCODE sdCliqueUpdateGraphWithStarWalks ( SCIP scip,
const GRAPH g,
const SDPROFIT sdprofit,
GRAPH cliquegraph,
SDCLIQUE sdclique 
)
inlinestatic

tries to improve SDs of clique-graph by using the star SD clique algorithm

Parameters
scipSCIP
gthe graph
sdprofitprofit or NULL
cliquegraphclique graph
sdcliqueclique

Definition at line 1179 of file reduce_sd.c.

References special_distance_clique::cliqueToNodeMap, GRAPH::cost, EAT_LAST, EQ, flipedge, graph_get_nNodes(), graph_sdComputeCliqueStar(), GT, GRAPH::head, LE, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, and special_distance_clique::sds.

Referenced by reduce_sdGetSdsCliquegraph().

◆ sdGetSdsCliqueTermWalks()

static void sdGetSdsCliqueTermWalks ( const GRAPH g,
SD *RESTRICT  sddata,
GRAPH *RESTRICT  cliquegraph,
SDCLIQUE *RESTRICT  sdclique 
)
static

get SDs between all pairs of marked vertices of given clique graph by using terminal-to-terminal special distances

Parameters
gthe graph
sddataSD
cliquegraphclique graph to be filled
sdcliqueclique

Definition at line 1242 of file reduce_sd.c.

References EAT_LAST, FALSE, FARAWAY, flipedge, graph_get_nNodes(), reduce_sdgraphGetMaxCost(), SCIP_Real, and sdGetSd().

Referenced by reduce_sdGetSdsCliquegraph().

◆ ledgeFromNetgraph()

static SCIP_RETCODE ledgeFromNetgraph ( SCIP scip,
const GRAPH netgraph,
const PATH mst,
const int *  edgeorg,
const PATH vnoi,
const int *  vbase,
GRAPH g,
int *  nelims 
)
static

◆ reduce_sdGetSdsCliquegraph()

SCIP_RETCODE reduce_sdGetSdsCliquegraph ( SCIP scip,
const GRAPH g,
int  centernode,
const int *  cliqueNodeMap,
DIJK dijkdata,
SD sddata,
GRAPH cliquegraph 
)

get SDs between all pairs of marked vertices of given clique graph

Parameters
scipSCIP
gthe graph
centernodecenter node or - 1
cliqueNodeMapmaps clique graph vertices to original ones
dijkdatadata for repeated path computations
sddataSD
cliquegraphclique graph to be filled

Definition at line 1394 of file reduce_sd.c.

References GRAPH::edges, GRAPH::knots, SCIP_CALL, SCIP_OKAY, sdCliqueFreeData(), sdCliqueInitData(), sdCliqueUpdateGraphWithStarWalks(), sdGetSdsCliqueTermWalks(), and special_distance_storage::sdprofit.

Referenced by bdkGetCliqueSds(), and testSdGetterReturnsCorrectSds().

◆ reduce_sdImpLongEdge()

SCIP_RETCODE reduce_sdImpLongEdge ( SCIP scip,
const int *  edgestate,
GRAPH g,
SD sdistance,
int *  nelims 
)

long edge implied special distance test

Parameters
scipSCIP data structure
edgestatearray to store status of (directed) edge (for propagation, can otherwise be set to NULL)
ggraph data structure
sdistancespecial distances storage
nelimspoint to store number of deleted edges

Definition at line 1421 of file reduce_sd.c.

References GRAPH::cost, deleteEdge(), EAT_LAST, EDGE_BLOCKED, FALSE, graph_edge_del(), graph_edge_printInfo(), graph_get_nNodes(), special_distance_storage::hasNeigborUpdate, GRAPH::head, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_sdgraphGetMaxCost(), reduce_sdgraphGetMstHalfMark(), reduce_sdgraphHasMstHalfMark(), reduce_sdneighborGetBlocked(), reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), special_distance_storage::sdgraph, special_distance_storage::sdneighbors, and TRUE.

Referenced by reduce_sdBiased(), and reduce_sdBiasedNeighbor().

◆ reduce_sd()

◆ reduce_sdBiased()

◆ reduce_sdBiasedNeighbor()

SCIP_RETCODE reduce_sdBiasedNeighbor ( SCIP scip,
SD sdistance,
GRAPH g,
int *  nelims 
)

◆ reduce_sdPc()

SCIP_RETCODE reduce_sdPc ( SCIP scip,
GRAPH g,
PATH vnoi,
int *  heap,
int *  state,
int *  vbase,
int *  nodesid,
int *  nodesorg,
int *  nelims 
)

SD test for PC

Parameters
scipSCIP data structure
ggraph data structure
vnoiVoronoi data structure
heapheap array
statearray to store state of a node during Voronoi computation
vbaseVoronoi base to each node
nodesidarray
nodesorgarray
nelimspointer to store number of eliminated edges

Definition at line 2023 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, GRAPH::edges, GRAPH::extended, FARAWAY, flipedge, getcloseterms(), getcloseterms2term(), graph_edge_add(), graph_edge_del(), graph_free(), graph_get4nextTermPaths(), graph_get4nextTTerms(), graph_init(), graph_knot_add(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by execPc_SD().

◆ reduce_getSdByPaths()

SCIP_RETCODE reduce_getSdByPaths ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
SCIP_Real sdist,
SCIP_Real  distlimit,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int  i,
int  i2,
int  limit,
SCIP_Bool  pc,
SCIP_Bool  mw 
)

◆ reduce_sdGetSd()

SCIP_Real reduce_sdGetSd ( const GRAPH g,
int  i,
int  i2,
SCIP_Real  sd_upper,
SCIP_Real  sd_sufficient,
SD sddata 
)

gets special distance to a pair of nodes

Parameters
ggraph structure
ifirst vertex
i2second vertex
sd_upperupper bound on special distance that is accepted (can be FARAWAY)
sd_sufficientbound below which to terminate (can be 0.0)
sddataSD

Definition at line 2433 of file reduce_sd.c.

References FALSE, and sdGetSd().

Referenced by distDataGetSpecialDist(), and testSdRepair().

◆ reduce_sdGetSdIntermedTerms()

SCIP_Real reduce_sdGetSdIntermedTerms ( const GRAPH g,
int  i,
int  i2,
SCIP_Real  sd_upper,
SCIP_Real  sd_sufficient,
SD sddata 
)

gets special distance to a pair of nodes, but only allows SDs with intermediate terminals

Parameters
ggraph structure
ifirst vertex
i2second vertex
sd_upperupper bound on special distance that is accepted (can be FARAWAY)
sd_sufficientbound below which to terminate (can be 0.0)
sddataSD

Definition at line 2449 of file reduce_sd.c.

References sdGetSd(), and TRUE.

Referenced by distDataGetSpecialDistIntermedTerms().

◆ sdGetSdPcMw()

◆ reduce_sdspSap()

SCIP_RETCODE reduce_sdspSap ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit 
)

SDC test for the SAP using a limited version of Dijkstra's algorithm from both endpoints of an arc

Parameters
scipSCIP data structure
ggraph data structure
pathtailpath tails
pathheadpath heads
heapheap
statetailstates of tails
stateheadstates of heads
memlbltailstorage for tails
memlblheadstorage for heads
nelimsnumber of eliminations
limitlimit for number of visits

Definition at line 2661 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), graph_sdPaths(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), TRUE, and UNKNOWN.

Referenced by reduce_sap().

◆ reduce_sdWalk_csr()

SCIP_RETCODE reduce_sdWalk_csr ( SCIP scip,
int  edgelimit,
const int *  edgestate,
GRAPH g,
int *  termmark,
SCIP_Real dist,
int *  visitlist,
STP_Bool visited,
DHEAP dheap,
int *  nelims 
)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters
scipSCIP data structure
edgelimitedge limit
edgestateper edge: state
ggraph data structure
termmarkper node: terminal property
distper node: distance
visitlistarray to store visited nodes
visitedper node: was visited?
dheaphead data structure
nelimspointer to store number of eliminations

Definition at line 2818 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, EDGE_BLOCKED, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalks_csr(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkReset(), csr_range::start, GRAPH::tail, and TRUE.

◆ reduce_sdEdgeCliqueStar()

◆ reduce_sdWalkTriangle()

SCIP_RETCODE reduce_sdWalkTriangle ( SCIP scip,
int  edgelimit,
SCIP_Bool  usestrongreds,
GRAPH g,
int *  termmark,
SCIP_Real dist,
int *  visitlist,
STP_Bool visited,
DHEAP dheap,
int *  nelims 
)

SD test for PcMw using limited Dijkstra-like walk from both endpoints of an edge

Parameters
scipSCIP data structure
edgelimitedge limit
usestrongredsallow strong reductions?
ggraph data structure
termmarkterminal mark
distdistances
visitlistarray to store visited nodes
visitedper node: was visited?
dheapheap data structure
nelimsnumber of eliminations

Definition at line 3011 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalksTriangle(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), sdwalkReset(), csr_range::start, GRAPH::tail, TRUE, and UNKNOWN.

Referenced by checkSdWalk(), and redLoopInnerPc().

◆ reduce_sdStar()

SCIP_RETCODE reduce_sdStar ( SCIP scip,
int  edgelimit,
SCIP_Bool  usestrongreds,
GRAPH g,
SCIP_Real dist,
int *  star_base,
int *  visitlist,
STP_Bool visited,
DHEAP dheap,
int *  nelims 
)

SD star test for PcMw and SPG

Parameters
scipSCIP data structure
edgelimitlimit
usestrongredsallow strong reductions?
ggraph data structure
distvertex distances
star_basearray of size nnodes
visitlistarray of size nnodes
visitedarray of size nnodes
dheapDijkstra heap
nelimspoint to store number of deleted edges

Definition at line 3202 of file reduce_sd.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, EAT_FREE, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_dcsr_deleteEdgeBi(), graph_edge_delBlocked(), graph_free_dcsr(), graph_heap_clean(), graph_init_dcsr(), graph_pc_isPcMw(), graph_sdStar(), dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::oeat, dynamic_csr_storage::range, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisLE(), SDSTAR_BASE_KILLED, SDSTAR_BASE_UNSET, sdStarReset(), GRAPH::source, csr_range::start, GRAPH::tail, and TRUE.

◆ reduce_sdStarBiased()

SCIP_RETCODE reduce_sdStarBiased ( SCIP scip,
int  edgelimit,
SCIP_Bool  usestrongreds,
GRAPH g,
int *  nelims 
)

SD star test for PcMw and SPG

Parameters
scipSCIP data structure
edgelimitlimit
usestrongredsallow strong reductions?
ggraph data structure
nelimspoint to store number of deleted edges

Definition at line 3332 of file reduce_sd.c.

References reduce_sdprofitFree(), reduce_sdprofitInit(), reduce_sdStarBiasedWithProfit(), SCIP_CALL, and SCIP_OKAY.

Referenced by redLoopInnerPc(), redLoopInnerStp(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), and testSdStarBiasedDeletesEdge3().

◆ reduce_sdStarBiasedWithProfit()

SCIP_RETCODE reduce_sdStarBiasedWithProfit ( SCIP scip,
int  edgelimit,
const SDPROFIT sdprofit,
SCIP_Bool  usestrongreds,
GRAPH g,
int *  nelims 
)

SD star test for PcMw and SPG

Parameters
scipSCIP data structure
edgelimitlimit
sdprofitwith profit given
usestrongredsallow strong reductions?
ggraph data structure
nelimspoint to store number of deleted edges

Definition at line 3353 of file reduce_sd.c.

References GRAPH::grad, graph_free_dcsr(), graph_get_nNodes(), graph_init_dcsr(), GRAPH::mark, nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, sdStarBiasedProcessNode(), sdStarFinalize(), sdStarInit(), and GRAPH::source.

Referenced by reduce_impliedProfitBased(), and reduce_sdStarBiased().

◆ reduce_sdStarPc2()

SCIP_RETCODE reduce_sdStarPc2 ( SCIP scip,
int  edgelimit,
SCIP_Bool  usestrongreds,
GRAPH g,
SCIP_Real dist,
int *  star_base,
int *  visitlist,
STP_Bool visited,
DHEAP dheap,
int *  nelims 
)

◆ reduce_sdStarPc()

SCIP_RETCODE reduce_sdStarPc ( SCIP scip,
int  edgelimit,
const int *  edgestate,
GRAPH g,
SCIP_Real dist,
int *  star_base,
int *  visitlist,
STP_Bool visited,
DHEAP dheap,
int *  nelims 
)

◆ reduce_sdWalk()

SCIP_RETCODE reduce_sdWalk ( SCIP scip,
int  edgelimit,
const int *  edgestate,
GRAPH g,
int *  termmark,
SCIP_Real dist,
int *  heap,
int *  state,
int *  visitlist,
STP_Bool visited,
int *  nelims 
)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Definition at line 3743 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalks(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIP_Real, sdwalkReset(), TRUE, and UNKNOWN.

◆ reduce_sdWalkExt()

SCIP_RETCODE reduce_sdWalkExt ( SCIP scip,
int  edgelimit,
SCIP_Bool  usestrongreds,
GRAPH g,
SCIP_Real dist,
int *  heap,
int *  state,
int *  visitlist,
STP_Bool visited,
int *  nelims 
)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters
scipSCIP data structure
edgelimitedge limit
usestrongredsallow strong reductions?
ggraph data structure
distper node: distances
heapheap
statestate
visitlistarray to store visited nodes
visitednumber of visited nodes
nelimsnumber of eliminations

Definition at line 3827 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_sdWalksExt(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkResetExt(), STP_SDWALK_MAXNPREVS, TRUE, and UNKNOWN.

Referenced by checkSdWalk(), and redLoopInnerPc().

◆ reduce_sdWalkExt2()

SCIP_RETCODE reduce_sdWalkExt2 ( SCIP scip,
int  edgelimit,
const int *  edgestate,
GRAPH g,
int *  termmark,
SCIP_Real dist,
int *  heap,
int *  state,
int *  visitlist,
STP_Bool visited,
int *  nelims 
)

SD test for PcMw using only limited Dijkstra-like walk from both endpoints of an edge

Parameters
scipSCIP data structure
edgelimitedge limit
edgestateper edge: state
ggraph data structure
termmarkper node: terminal state
distper node: distance
heapheap
statestate
visitlistvisited nodes
visitednumber of visited nodes
nelimsnumber of eliminations

Definition at line 3910 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, EDGE_BLOCKED, GRAPH::extended, FALSE, FARAWAY, graph_edge_del(), graph_pc_isPcMw(), graph_pc_termMarkProper(), graph_sdWalksExt2(), GRAPH::head, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, sdwalkResetExt2(), STP_SDWALK_MAXNPREVS, TRUE, and UNKNOWN.

◆ reduce_sdsp()

SCIP_RETCODE reduce_sdsp ( SCIP scip,
GRAPH g,
PATH pathtail,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit,
SCIP_Bool  usestrongreds 
)

SD test using only limited Dijkstra from both endpoints of an edge

Parameters
scipSCIP data structure
ggraph data structure
pathtailpath tails
heapheap
statetailtails
stateheadheads
memlbltailto save changed tails
memlblheadto save changed heads
nelimsnumber of eliminations
limitlimit for number checks
usestrongredsallow strong reductions?

Definition at line 4020 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_get_nNodes(), graph_path_PcMwSd(), graph_sdPaths(), graph_valid(), GRAPH::head, Is_term, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisNegative(), SCIPisPositive(), STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by redLoopInnerStp().

◆ reduce_bd34WithSd()

SCIP_RETCODE reduce_bd34WithSd ( SCIP scip,
GRAPH g,
SDGRAPH sdgraph,
PATH vnoi,
int *  vbase,
int *  nelims 
)

bd_k test for given Steiner bottleneck distances

Parameters
scipSCIP data structure
ggraph structure
sdgraphauxiliary graph structure
vnoipath structure
vbasebases for nearest terminals
nelimsnumber of eliminations

Definition at line 4310 of file reduce_sd.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, flipedge, getSd(), GRAPH::grad, graph_buildCompleteGraph(), graph_free(), graph_knot_delPseudo(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_isPcMw(), graph_valid(), GRAPH::head, Is_term, isPseudoDeletable(), isPseudoDeletableDeg3(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, reduce_unconnected(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, GRAPH::term, and TRUE.

Referenced by reduce_sd().

◆ reduce_bd34()

SCIP_RETCODE reduce_bd34 ( SCIP scip,
GRAPH g,
PATH pathtail,
PATH pathhead,
int *  heap,
int *  statetail,
int *  statehead,
int *  memlbltail,
int *  memlblhead,
int *  nelims,
int  limit,
SCIP_Real offset 
)
Parameters
scipSCIP data structure
ggraph structure
pathtailarray for internal use
pathheadarray for internal use
heaparray for internal use
statetailarray for internal use
stateheadarray for internal use
memlbltailarray for internal use
memlblheadarray for internal use
nelimspoint to return number of eliminations
limitlimit for edges to consider for each vertex
offsetoffset

Definition at line 4516 of file reduce_sd.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, EQ, GRAPH::extended, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_buildCompleteGraph(), graph_free(), graph_knot_delPseudo(), graph_mark(), graph_path_exit(), graph_path_init(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_realDegree(), graph_pc_termIsNonLeafTerm(), graph_valid(), GRAPH::head, Is_term, isPseudoDeletable(), isPseudoDeletableDeg3(), GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, single_special_distance_pc::pathtail, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, sdGetSdPcMw(), STP_BD_MAXDEGREE, STP_BD_MAXDNEDGES, GRAPH::term, TRUE, and UNKNOWN.

Referenced by execPc_BDk().