extreduce_dist.c
Go to the documentation of this file.
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
58 /** returns entry of element within sorted array of size arraysize, or -1 if element could not be found
223 /** returns distance of closenode from node, or -1.0 if this distance is not stored in close nodes list of node */
292 if( !closeNodesPathIsForbidden(g, distdata, edge_forbidden, edges_isForbidden, node, closenode, start + position) )
442 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(distdata->pathroot_blocks[halfedge]), oldsize, newsize) );
452 distdata->pathroot_blocks[halfedge][pathroot_blocksizes[halfedge]++].pathroot_nrecomps = distdata->pathroot_nrecomps[root];
583 assert(distdata->closenodes_range[startvertex].start == distdata->closenodes_range[startvertex].end);
644 const SCIP_Bool withProfit = (distdata->sdistdata != NULL && distdata->sdistdata->sdprofit != NULL);
671 assert(cnodesrun->edgemark[prededge[k] / 2] == FALSE); /* make sure that the edge is not marked twice */
763 SCIPsortIntIntReal(&closenodes_indices[start], &(distdata->closenodes_prededges[start]), &closenodes_distances[start], length);
984 SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->closenodes_distances), closenodes_totalsize) );
985 SCIP_CALL( SCIPallocMemoryArray(scip, &(distdata->closenodes_prededges), closenodes_totalsize) );
1098 dist = getCloseNodeDistanceForbidden(g, distdata, edge_forbidden, edges_isForbidden, vertex1, vertex2);
1159 dist = getCloseNodeDistanceForbiddenEq(g, distdata, dist_eq, edge_forbidden, edges_isForbidden, vertex1, vertex2);
1357 SCIPfreeBlockMemoryArray(scip, &(distdata->pathroot_blocks[halfedge]), distdata->pathroot_blocksizesmax[halfedge]);
1461 * Will check shortest known v1->v2 path, and also shortest known v2->v1 path if no v1-v2 path is known.
1556 /** Same as extreduce_distDataGetSdDouble, but only takes paths that do not include any edges marked as blocked. */
1574 dist = distDataGetNormalDistForbidden(scip, g, EDGE_FORBIDDEN_NONE, edges_isForbidden, vertex1, vertex2, distdata);
1580 dist = distDataGetNormalDistForbidden(scip, g, EDGE_FORBIDDEN_NONE, edges_isForbidden, vertex1, vertex2, distdata);
1584 const SCIP_Real distrev = distDataGetNormalDistForbidden(scip, g, EDGE_FORBIDDEN_NONE, edges_isForbidden, vertex1, vertex2, distdata);
1629 dist = distDataGetNormalDistForbiddenEq(scip, g, dist_eq, edge_forbidden, edges_isForbidden, vertex1, vertex2, distdata);
1638 dist = distDataGetNormalDistForbiddenEq(scip, g, dist_eq, edge_forbidden, edges_isForbidden, vertex2, vertex1, distdata);
1642 const SCIP_Real distrev = distDataGetNormalDistForbiddenEq(scip, g, dist_eq, edge_forbidden, edges_isForbidden, vertex2, vertex1, distdata);
1668 /** Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given edge */
1685 dist = distDataGetNormalDistForbidden(scip, g, edge_forbidden, NULL, vertex1, vertex2, distdata);
1692 dist = distDataGetNormalDistForbidden(scip, g, edge_forbidden, NULL, vertex2, vertex1, distdata);
1696 const SCIP_Real distrev = distDataGetNormalDistForbidden(scip, g, edge_forbidden, NULL, vertex2, vertex1, distdata);
1725 /** Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given last edges.
1754 const SCIP_Real distrev = distDataGetNormalDistForbiddenLast(scip, g, vertex2, vertex1, lastedge21, distdata);
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
SCIP_Real extreduce_distDataGetSdDoubleForbidden(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, EXTDATA *extdata)
Definition: extreduce_dist.c:1557
static SCIP_Bool extInitialCompIsGenStar(const EXTDATA *extdata)
Definition: extreducedefs.h:293
Definition: graphdefs.h:184
static SCIP_Real getCloseNodeDistanceForbidden(const GRAPH *g, const DISTDATA *distdata, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int node, int closenode)
Definition: extreduce_dist.c:261
Definition: extreducedefs.h:187
Definition: struct_scip.h:59
static void closeNodesRunSort(const GRAPH *g, int node, DISTDATA *distdata)
Definition: extreduce_dist.c:745
static SCIP_Real getCloseNodePath(const GRAPH *g, const DISTDATA *distdata, int node, int closenode, int *pathnodes, int *npathnodes)
Definition: extreduce_dist.c:164
Definition: extreduce_dist.c:44
SCIP_Real extreduce_distDataGetSdDouble(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1463
SCIP_Real extreduce_distDataGetSdDoubleEq(SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1506
static SCIP_Real distDataGetNormalDistForbidden(SCIP *scip, const GRAPH *g, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1076
struct close_nodes_run CNODESRUN
Definition: graphdefs.h:301
SCIP_Real extreduce_distDataGetSdDoubleForbiddenLast(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int lastedge12, int lastedge21, DISTDATA *distdata)
Definition: extreduce_dist.c:1727
static void distDataPathRootsFree(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
Definition: extreduce_dist.c:881
static SCIP_Bool extInitialCompIsEdge(const EXTDATA *extdata)
Definition: extreducedefs.h:264
void extreduce_distDataDeleteEdge(SCIP *scip, const GRAPH *g, int edge, DISTDATA *distdata)
Definition: extreduce_dist.c:1315
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
static void distDataInitSizes(const GRAPH *g, int maxnclosenodes, DISTDATA *distdata)
Definition: extreduce_dist.c:947
SCIP_Real extreduce_distDataGetSd(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1426
static SCIP_RETCODE closeNodesRunCompute(SCIP *scip, const GRAPH *g, CNODESRUN *cnodesrun, DISTDATA *distdata)
Definition: extreduce_dist.c:614
void graph_dijkLimited_reset(const GRAPH *, DIJK *)
Definition: graph_util.c:2105
This file implements extended reduction techniques for several Steiner problems.
Definition: reducedefs.h:135
miscellaneous methods used for solving Steiner problems
void extreduce_distDataRecomputeDirtyPaths(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
Definition: extreduce_dist.c:1370
static SCIP_Real distDataGetNormalDist(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1047
SCIP_Real reduce_sdGetSd(const GRAPH *, int, int, SCIP_Real, SCIP_Real, SD *)
Definition: reduce_sd.c:2428
SCIP_Real extreduce_distDataGetSdDoubleForbiddenSingle(SCIP *scip, const GRAPH *g, int edge_forbidden, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1669
static SCIP_Real distDataGetSp(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int *pathnodes, int *npathnodes, DISTDATA *distdata)
Definition: extreduce_dist.c:1020
SCIP_Real reduce_sdGetSdIntermedTerms(const GRAPH *, int, int, SCIP_Real, SCIP_Real, SD *)
Definition: reduce_sd.c:2444
void extreduce_distDataFree(SCIP *scip, const GRAPH *graph, DISTDATA **distdata)
Definition: extreduce_dist.c:1784
static SCIP_RETCODE closeNodesRunInit(SCIP *scip, const GRAPH *g, DISTDATA *distdata, CNODESRUN *cnodesrun)
Definition: extreduce_dist.c:568
Definition: type_retcode.h:33
static SCIP_RETCODE distDataComputeCloseNodes(SCIP *scip, const GRAPH *g, CNODESRUN *cnodesrun, DISTDATA *distdata)
Definition: extreduce_dist.c:923
static SCIP_RETCODE distDataAllocateNodesArrays(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
Definition: extreduce_dist.c:970
static SCIP_Real reduce_sdprofitGetProfit(const SDPROFIT *sdprofit, int node, int nonsource1, int nonsource2)
Definition: reducedefs.h:178
SCIP_RETCODE graph_dijkLimited_init(SCIP *, const GRAPH *, DIJK **)
Definition: graph_util.c:1989
static SCIP_Real distDataGetSpecialDist(const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1167
Definition: extreducedefs.h:72
SCIP_Bool graph_valid_dcsr(const GRAPH *, SCIP_Bool verbose)
Definition: graph_util.c:1919
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
static void closeNodesRunExit(SCIP *scip, CNODESRUN *cnodesrun)
Definition: extreduce_dist.c:774
SCIP_Bool *const sdeq_edgesIsForbidden
Definition: extreducedefs.h:206
SCIP_RETCODE extreduce_distDataInit(SCIP *scip, GRAPH *g, int maxnclosenodes, SCIP_Bool computeSD, SCIP_Bool useBias, DISTDATA **distdata)
Definition: extreduce_dist.c:1218
SCIP_Bool extreduce_distCloseNodesAreValid(SCIP *, const GRAPH *, const DISTDATA *)
Definition: extreduce_dbg.c:1125
static int findEntryFromSorted(const int *array, unsigned int arraysize, int element)
Definition: extreduce_dist.c:61
SCIP_RETCODE reduce_sdInitBiasedBottleneck(SCIP *, GRAPH *, SD **)
Definition: reduce_sdutil.c:779
Definition: extreducedefs.h:79
static void distDataRecomputeNormalDist(SCIP *scip, const GRAPH *g, int vertex1, DISTDATA *distdata)
Definition: extreduce_dist.c:993
SCIP_Bool graph_pc_knotIsNonLeafTerm(const GRAPH *, int)
Definition: graph_pcbase.c:1383
static SCIP_Real getCloseNodeDistance(const DISTDATA *distdata, int node, int closenode)
Definition: extreduce_dist.c:225
SCIP_RETCODE graph_dijkLimited_initPcShifts(SCIP *, const GRAPH *, DIJK *)
Definition: graph_util.c:2031
Definition: graphdefs.h:150
Portable definitions.
static SCIP_Bool closeNodesPathIsForbidden(const GRAPH *g, const DISTDATA *distdata, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int node, int closenode, int closenode_pos)
Definition: extreduce_dist.c:96
Definition: graphdefs.h:158
SCIP_Real extreduce_distDataGetSdDoubleForbiddenEq(SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int edge_forbidden, int vertex1, int vertex2, EXTDATA *extdata)
Definition: extreduce_dist.c:1609
static SCIP_Real distDataGetSpecialDistIntermedTerms(const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1188
static SCIP_Real getCloseNodeDistanceForbiddenLast(const GRAPH *g, const DISTDATA *distdata, int node, int closenode, int lastedge_node2close)
Definition: extreduce_dist.c:304
static SCIP_Real getCloseNodeDistanceForbiddenEq(const GRAPH *g, const DISTDATA *distdata, SCIP_Real dist_eq, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int node, int closenode)
Definition: extreduce_dist.c:355
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
int graph_heap_deleteMinReturnNode(DHEAP *)
Definition: graph_util.c:1076
Definition: graphdefs.h:311
static SCIP_RETCODE distDataPathRootsInitialize(SCIP *scip, const GRAPH *g, DISTDATA *distdata)
Definition: extreduce_dist.c:460
Definition: objbenders.h:33
SCIP_Real extreduce_distDataGetSp(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int *pathnodes, int *npathnodes, DISTDATA *distdata)
Definition: extreduce_dist.c:1400
static SCIP_RETCODE distDataPathRootsInsertRoot(SCIP *scip, const GRAPH *g, int halfedge, int root, DISTDATA *distdata)
Definition: extreduce_dist.c:408
static SCIP_Real distDataGetNormalDistForbiddenEq(SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int vertex1, int vertex2, DISTDATA *distdata)
Definition: extreduce_dist.c:1134
static SCIP_Real distDataGetNormalDistForbiddenLast(SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int lastedge12, DISTDATA *distdata)
Definition: extreduce_dist.c:1106