reduce_sdutil.c
Go to the documentation of this file.
20 * This file implements utility methods for Steiner tree problem special distance reduction techniques.
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
393 graph_tpathsGet4CloseTerms(g, sddata->terminalpaths, sourcenode, FARAWAY, neighbterms1, NULL, termdist1, &nnterms1);
565 //graph_knot_printInfo(g, term); graph_knot_printInfo(g, i); printf("term %d->%d: new=%f vs org=%f \n", term, i, nodes_maxdist[i], sdorg);
800 SCIP_CALL( reduce_sdgraphInitBiasedFromTpaths(scip, g, s->sdprofit, s->terminalpaths, &(s->sdgraph)) );
1096 printf("Steiner nodes: profitable=%d non-profitable=%d .... Profit: sum=%f avg=%f\n", nnodes_profit, nnodes_nonprofit,
Definition: reduce_sdutil.c:38
void reduce_sdprofitPrintStats(const GRAPH *g, const SDPROFIT *sdprofit)
Definition: reduce_sdutil.c:1065
SCIP_RETCODE reduce_sdgraphMstBuild(SCIP *, const GRAPH *, SDGRAPH *)
Definition: reduce_sdgraph.c:2032
SCIP_RETCODE reduce_sdgraphInit(SCIP *, const GRAPH *, SDGRAPH **)
Definition: reduce_sdgraph.c:1764
SCIP_RETCODE reduce_sdRepair(SCIP *scip, int edge, SCIP_Bool withEdgeReplacement, GRAPH *g, SD *sd)
Definition: reduce_sdutil.c:811
static SCIP_RETCODE sdneighborUpdateInit(SCIP *scip, GRAPH *g, SDN *sdn)
Definition: reduce_sdutil.c:474
SCIP_RETCODE reduce_sdInit(SCIP *scip, GRAPH *g, SD **sd)
Definition: reduce_sdutil.c:724
Definition: graphdefs.h:184
Definition: struct_scip.h:59
void reduce_blctreeGetMstEdges(const GRAPH *, const BLCTREE *, int *)
Definition: reduce_util.c:1230
SCIP_RETCODE reduce_sdInitBiasedBottleneck(SCIP *scip, GRAPH *g, SD **sd)
Definition: reduce_sdutil.c:779
static void sdneighborUpdateFree(SCIP *scip, GRAPH *g, SDN *sdn)
Definition: reduce_sdutil.c:523
int *RESTRICT nodes_biassource2
Definition: reducedefs.h:140
static void sdgraphInsertEdge(SCIP *scip, int term1, int term2, SCIP_Real edgecost, SDGRAPH *sdgraph)
Definition: reduce_sdutil.c:62
void reduce_sdneighborGetCloseTerms(const GRAPH *g, const SDN *sdneighbor, int node, SCIP_Real maxdist_strict, int *RESTRICT closeterms, SCIP_Real *RESTRICT closeterms_dist, int *RESTRICT ncloseterms)
Definition: reduce_sdutil.c:926
static void sdprofitBuild(const GRAPH *g, SDPROFIT *sdprofit)
Definition: reduce_sdutil.c:114
SCIP_Real reduce_sdgraphGetSd(int, int, SDGRAPH *)
Definition: reduce_sdgraph.c:1958
SCIP_RETCODE reduce_sdprofitBuildFromBLC(SCIP *scip, const GRAPH *g, const BLCTREE *blctree, SCIP_Bool blctree_isUpdated, SDPROFIT *sdprofit)
Definition: reduce_sdutil.c:1179
void reduce_sdgraphInitOrderedMstCosts(SDGRAPH *)
Definition: reduce_sdgraph.c:1938
void reduce_sdneighborFree(SCIP *scip, SDN **sdn)
Definition: reduce_sdutil.c:1000
SCIP_RETCODE reduce_sdgraphInitBiased(SCIP *, const GRAPH *, const SDPROFIT *, SDGRAPH **)
Definition: reduce_sdgraph.c:1811
static SCIP_RETCODE sdneighborMarkCloseNodes(SCIP *scip, const GRAPH *g, int sourcenode, SD *sddata)
Definition: reduce_sdutil.c:419
const SCIP_Bool * reduce_sdneighborGetBlocked(const SDN *sdneighbors)
Definition: reduce_sdutil.c:915
SCIP_RETCODE reduce_blctreeInit(SCIP *, GRAPH *, BLCTREE **)
Definition: reduce_util.c:1168
SCIP_RETCODE reduce_sdprofitUpdateFromBLC(SCIP *scip, const GRAPH *g, const BLCTREE *blctree, SCIP_Bool blctree_isUpdated, SDPROFIT *sdprofit)
Definition: reduce_sdutil.c:1123
void graph_dijkLimited_reset(const GRAPH *, DIJK *)
Definition: graph_util.c:2105
SCIP_RETCODE graph_tpathsInitBiased(SCIP *, const SDPROFIT *, GRAPH *, TPATHS **)
Definition: graph_tpath.c:1700
SCIP_RETCODE reduce_sdUpdateWithSdNeighbors(SCIP *scip, GRAPH *g, SD *sddata, int *nupdates)
Definition: reduce_sdutil.c:1015
Definition: reducedefs.h:135
static void sdprofitUpdateNode(const GRAPH *g, int node, int sourceterm, SCIP_Real edgecost, SCIP_Real bdist, SCIP_Bool blctree_isUpdated, SDPROFIT *sdprofit)
Definition: reduce_sdutil.c:333
void reduce_sdgraphMstSortCosts(SDGRAPH *)
Definition: reduce_sdgraph.c:2046
SCIP_RETCODE graph_tpathsRepair(SCIP *, int, SCIP_Bool, const GRAPH *, TPATHS *)
Definition: graph_tpath.c:1744
static SCIP_RETCODE sdneighborUpdate(SCIP *scip, GRAPH *g, SD *sddata, int *nupdates)
Definition: reduce_sdutil.c:670
Definition: type_retcode.h:33
void reduce_sdprofitFree(SCIP *scip, SDPROFIT **sdprofit)
Definition: reduce_sdutil.c:1102
Definition: reduce_sdgraph.c:46
void reduce_sdgraphInsertEdge(SCIP *, int, int, SCIP_Real, int, int *RESTRICT, SDGRAPH *, SCIP_Bool *)
SCIP_RETCODE graph_tpathsRepairSetUp(const GRAPH *, TPATHS *)
Definition: graph_tpath.c:1719
SCIP_RETCODE reduce_sdInitBiased(SCIP *scip, GRAPH *g, SD **sd)
Definition: reduce_sdutil.c:751
SCIP_RETCODE graph_dijkLimited_init(SCIP *, const GRAPH *, DIJK **)
Definition: graph_util.c:1989
SCIP_RETCODE reduce_sdprofitInit(SCIP *scip, const GRAPH *g, SDPROFIT **sdprofit)
Definition: reduce_sdutil.c:1032
SCIP_RETCODE reduce_sdRepairSetUp(SCIP *scip, const GRAPH *g, SD *sd)
Definition: reduce_sdutil.c:853
SCIP_RETCODE reduce_sdAddNeighborSd(SCIP *scip, const GRAPH *g, SD *sd)
Definition: reduce_sdutil.c:868
SCIP_Real *RESTRICT nodes_bias2
Definition: reducedefs.h:138
void graph_tpathsGet4CloseTerms(const GRAPH *, const TPATHS *, int, SCIP_Real, int *RESTRICT, int *RESTRICT, SCIP_Real *RESTRICT, int *RESTRICT)
SCIP_Bool reduce_sdgraphEdgeIsInMst(const SDGRAPH *, int)
Definition: reduce_sdgraph.c:1909
SCIP_Real * closeterms_distN
Definition: reduce_sdutil.c:40
SCIP_RETCODE reduce_sdgraphInitBiasedFromTpaths(SCIP *, GRAPH *, const SDPROFIT *, const TPATHS *, SDGRAPH **)
Definition: reduce_sdgraph.c:1836
Portable definitions.
SCIP_RETCODE graph_sdCloseNodesBiased(SCIP *, const GRAPH *, const SDPROFIT *, int, DIJK *)
Definition: graph_sdpath.c:1461
Definition: reducedefs.h:122
SCIP_RETCODE reduce_sdneighborInit(SCIP *scip, const GRAPH *g, SDN **sdn)
Definition: reduce_sdutil.c:970
Definition: reduce_util.c:84
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1344
SCIP_Real *RESTRICT nodes_bias
Definition: reducedefs.h:137
const int * reduce_sdgraphGetOrgnodesToSdMap(const SDGRAPH *)
Definition: reduce_sdgraph.c:2001
int reduce_blctreeGetMstNedges(const BLCTREE *)
Definition: reduce_util.c:1218
SCIP_Bool graph_pc_isUnrootedPcMw(const GRAPH *)
Definition: graph_pcbase.c:2669
SCIP_RETCODE graph_tpathsInit(SCIP *, GRAPH *, TPATHS **)
Definition: graph_tpath.c:1682
static SCIP_RETCODE sdprofitAlloc(SCIP *scip, const GRAPH *g, SCIP_Bool useSecond, SDPROFIT **sdprofit)
Definition: reduce_sdutil.c:81
Definition: graphdefs.h:311
static void sdneighborUpdateNode(SCIP *scip, const GRAPH *g, int node, int term, SDN *sdn, SDGRAPH *sdgraph, int *nupdates)
Definition: reduce_sdutil.c:540
SCIP_RETCODE reduce_sdprofitInit1stOnly(SCIP *scip, const GRAPH *g, const SCIP_Real *edgecosts, SDPROFIT **sdprofit)
Definition: reduce_sdutil.c:1048
int *RESTRICT nodes_biassource
Definition: reducedefs.h:139
SCIP_Bool * nodes_isBlocked
Definition: reduce_sdutil.c:42
static void sdprofitBuild1stOnly(const GRAPH *g, const SCIP_Real *edgecosts, SDPROFIT *sdprofit)
Definition: reduce_sdutil.c:238
Definition: objbenders.h:33
static SCIP_RETCODE sdneighborUpdateExec(SCIP *scip, GRAPH *g, SD *sddata, int *nupdates)
Definition: reduce_sdutil.c:604
includes various reduction methods for Steiner tree problems
void reduce_blctreeGetMstBottlenecks(const GRAPH *, const BLCTREE *, SCIP_Real *)
Definition: reduce_util.c:1349