extreduce_dist.c File Reference

Detailed Description

(special) distance computation methods for Steiner tree extended reductions

Author

Daniel Rehfeldt

This file implements methods for Steiner tree problem extended reduction techniques to compute and recompute (special) distances between vertices.

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

Definition in file extreduce_dist.c.

#include "extreduce.h"
#include "misc_stp.h"
#include "portab.h"

Go to the source code of this file.

Data Structures
struct	close_nodes_run

Macros
#define	EDGE_FORBIDDEN_NONE   -2

Typedefs
typedef struct close_nodes_run	CNODESRUN

Functions
Local methods
static int	findEntryFromSorted (const int *array, unsigned int arraysize, int element)
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)
static SCIP_Real	getCloseNodePath (const GRAPH *g, const DISTDATA *distdata, int node, int closenode, int *pathnodes, int *npathnodes)
static SCIP_Real	getCloseNodeDistance (const DISTDATA *distdata, int node, int closenode)
static SCIP_Real	getCloseNodeDistanceForbidden (const GRAPH *g, const DISTDATA *distdata, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int node, int closenode)
static SCIP_Real	getCloseNodeDistanceForbiddenLast (const GRAPH *g, const DISTDATA *distdata, int node, int closenode, int lastedge_node2close)
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)
static SCIP_RETCODE	distDataPathRootsInsertRoot (SCIP *scip, const GRAPH *g, int halfedge, int root, DISTDATA *distdata)
static SCIP_RETCODE	distDataPathRootsInitialize (SCIP *scip, const GRAPH *g, DISTDATA *distdata)
static SCIP_RETCODE	closeNodesRunInit (SCIP *scip, const GRAPH *g, DISTDATA *distdata, CNODESRUN *cnodesrun)
static SCIP_RETCODE	closeNodesRunCompute (SCIP *scip, const GRAPH *g, CNODESRUN *cnodesrun, DISTDATA *distdata)
static void	closeNodesRunSort (const GRAPH *g, int node, DISTDATA *distdata)
static void	closeNodesRunExit (SCIP *scip, CNODESRUN *cnodesrun)
static void	distDataPathRootsFree (SCIP *scip, const GRAPH *g, DISTDATA *distdata)
static SCIP_RETCODE	distDataComputeCloseNodes (SCIP *scip, const GRAPH *g, CNODESRUN *cnodesrun, DISTDATA *distdata)
static void	distDataInitSizes (const GRAPH *g, int maxnclosenodes, DISTDATA *distdata)
static SCIP_RETCODE	distDataAllocateNodesArrays (SCIP *scip, const GRAPH *g, DISTDATA *distdata)
static void	distDataRecomputeNormalDist (SCIP *scip, const GRAPH *g, int vertex1, DISTDATA *distdata)
static SCIP_Real	distDataGetSp (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int *pathnodes, int *npathnodes, DISTDATA *distdata)
static SCIP_Real	distDataGetNormalDist (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
static SCIP_Real	distDataGetNormalDistForbidden (SCIP *scip, const GRAPH *g, int edge_forbidden, const SCIP_Bool *edges_isForbidden, int vertex1, int vertex2, DISTDATA *distdata)
static SCIP_Real	distDataGetNormalDistForbiddenLast (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int lastedge12, DISTDATA *distdata)
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)
static SCIP_Real	distDataGetSpecialDist (const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
static SCIP_Real	distDataGetSpecialDistIntermedTerms (const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
Interface methods
SCIP_RETCODE	extreduce_distDataInit (SCIP *scip, GRAPH *g, int maxnclosenodes, SCIP_Bool computeSD, SCIP_Bool useBias, DISTDATA **distdata)
void	extreduce_distDataDeleteEdge (SCIP *scip, const GRAPH *g, int edge, DISTDATA *distdata)
void	extreduce_distDataRecomputeDirtyPaths (SCIP *scip, const GRAPH *g, DISTDATA *distdata)
SCIP_Real	extreduce_distDataGetSp (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int *pathnodes, int *npathnodes, DISTDATA *distdata)
SCIP_Real	extreduce_distDataGetSd (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
SCIP_Real	extreduce_distDataGetSdDouble (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, DISTDATA *distdata)
SCIP_Real	extreduce_distDataGetSdDoubleEq (SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int vertex1, int vertex2, DISTDATA *distdata)
SCIP_Real	extreduce_distDataGetSdDoubleForbidden (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, EXTDATA *extdata)
SCIP_Real	extreduce_distDataGetSdDoubleForbiddenEq (SCIP *scip, const GRAPH *g, SCIP_Real dist_eq, int edge_forbidden, int vertex1, int vertex2, EXTDATA *extdata)
SCIP_Real	extreduce_distDataGetSdDoubleForbiddenSingle (SCIP *scip, const GRAPH *g, int edge_forbidden, int vertex1, int vertex2, DISTDATA *distdata)
SCIP_Real	extreduce_distDataGetSdDoubleForbiddenLast (SCIP *scip, const GRAPH *g, int vertex1, int vertex2, int lastedge12, int lastedge21, DISTDATA *distdata)
void	extreduce_distDataFree (SCIP *scip, const GRAPH *graph, DISTDATA **distdata)

Macro Definition Documentation

EDGE_FORBIDDEN_NONE

#define EDGE_FORBIDDEN_NONE   -2

Definition at line 41 of file extreduce_dist.c.

Referenced by distDataGetNormalDistForbidden(), and extreduce_distDataGetSdDoubleForbidden().

Typedef Documentation

CNODESRUN

typedef struct close_nodes_run CNODESRUN

auxiliary data for (single) closenodes run

Function Documentation

findEntryFromSorted()

static int findEntryFromSorted ( const int *  array, unsigned int  arraysize, int  element  )

inlinestatic

returns entry of element within sorted array of size arraysize, or -1 if element could not be found NOTE: optimized binary search

Parameters

array	array
arraysize	size
element	element to look for

Definition at line 61 of file extreduce_dist.c.

Referenced by closeNodesPathIsForbidden(), getCloseNodeDistance(), getCloseNodeDistanceForbidden(), getCloseNodeDistanceForbiddenEq(), getCloseNodeDistanceForbiddenLast(), and getCloseNodePath().

closeNodesPathIsForbidden()

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  )

inlinestatic

it the path between node and the close node forbidden? todo better have an additional closenodes_ancestor that saves the previous node!

Parameters

g	graph data structure
distdata	to be initialized
edge_forbidden	forbidden edge
edges_isForbidden	blocked edges marked (half)
node	the node
closenode	the close node
closenode_pos	the close node position

Definition at line 96 of file extreduce_dist.c.

References distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, csr_range::end, FALSE, findEntryFromSorted(), graph_edge_isInRange(), GRAPH::head, SCIP_Bool, csr_range::start, GRAPH::tail, and TRUE.

Referenced by getCloseNodeDistanceForbidden(), and getCloseNodeDistanceForbiddenEq().

getCloseNodePath()

static SCIP_Real getCloseNodePath ( const GRAPH *  g, const DISTDATA *  distdata, int  node, int  closenode, int *  pathnodes, int *  npathnodes  )

inlinestatic

gets distance and path nodes

Parameters

g	graph data structure
distdata	distance data
node	the node
closenode	the close node whose position is to be found
pathnodes	inner nodes
npathnodes	number of inner nodes

Definition at line 164 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, csr_range::end, findEntryFromSorted(), graph_edge_isInRange(), GRAPH::head, SCIP_Real, csr_range::start, and GRAPH::tail.

Referenced by distDataGetSp().

getCloseNodeDistance()

static SCIP_Real getCloseNodeDistance ( const DISTDATA *  distdata, int  node, int  closenode  )

inlinestatic

returns distance of closenode from node, or -1.0 if this distance is not stored in close nodes list of node

Parameters

distdata	to be initialized
node	the node
closenode	the close node whose position is to be found

Definition at line 225 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_range, csr_range::end, findEntryFromSorted(), distance_data::hasPathReplacement, SCIP_Real, and csr_range::start.

Referenced by distDataGetNormalDist().

getCloseNodeDistanceForbidden()

static SCIP_Real getCloseNodeDistanceForbidden ( const GRAPH *  g, const DISTDATA *  distdata, int  edge_forbidden, const SCIP_Bool *  edges_isForbidden, int  node, int  closenode  )

inlinestatic

as above, but with forbidden edge

Parameters

g	graph data structure
distdata	to be initialized
edge_forbidden	forbidden edge
edges_isForbidden	blocked edges marked or NULL
node	the node
closenode	the close node whose position is to be found

Definition at line 261 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_range, closeNodesPathIsForbidden(), csr_range::end, findEntryFromSorted(), distance_data::hasPathReplacement, SCIP_Real, and csr_range::start.

Referenced by distDataGetNormalDistForbidden().

getCloseNodeDistanceForbiddenLast()

static SCIP_Real getCloseNodeDistanceForbiddenLast ( const GRAPH *  g, const DISTDATA *  distdata, int  node, int  closenode, int  lastedge_node2close  )

inlinestatic

as above, but with forbidden last edge

Parameters

g	graph data structure
distdata	to be initialized
node	the node
closenode	the close node whose position is to be found
lastedge_node2close	last edge

Definition at line 304 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, csr_range::end, findEntryFromSorted(), graph_edge_isInRange(), distance_data::hasPathReplacement, GRAPH::head, close_nodes_run::prededge, SCIP_Real, and csr_range::start.

Referenced by distDataGetNormalDistForbiddenLast().

getCloseNodeDistanceForbiddenEq()

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  )

inlinestatic

as above, but with forbidden edge/edges and known equality value

Parameters

g	graph data structure
distdata	to be initialized
dist_eq	critical distance or -1.0 if not known
edge_forbidden	forbidden edge
edges_isForbidden	blocked edges marked
node	the node
closenode	the close node whose position is to be found

Definition at line 355 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_range, closeNodesPathIsForbidden(), csr_range::end, EQ, findEntryFromSorted(), GT, distance_data::hasPathReplacement, SCIP_Real, and csr_range::start.

Referenced by distDataGetNormalDistForbiddenEq().

distDataPathRootsInsertRoot()

static SCIP_RETCODE distDataPathRootsInsertRoot ( SCIP *  scip, const GRAPH *  g, int  halfedge, int  root, DISTDATA *  distdata  )

inlinestatic

compute paths root list

Parameters

scip	SCIP
g	graph data structure
halfedge	halfedge to insert at
root	root to insert
distdata	distance data

Definition at line 408 of file extreduce_dist.c.

References NULL, distance_data::pathroot_blocks, distance_data::pathroot_blocksizes, distance_data::pathroot_blocksizesmax, pathroot_state::pathroot_id, pathroot_state::pathroot_nrecomps, distance_data::pathroot_nrecomps, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPreallocBlockMemoryArray.

Referenced by closeNodesRunCompute().

distDataPathRootsInitialize()

static SCIP_RETCODE distDataPathRootsInitialize ( SCIP *  scip, const GRAPH *  g, DISTDATA *  distdata  )

static

compute paths root list

Parameters

scip	SCIP
g	graph data structure
distdata	to be initialized

Definition at line 460 of file extreduce_dist.c.

References distance_data::closenodes_prededges, distance_data::closenodes_range, EAT_FREE, GRAPH::edges, csr_range::end, FALSE, GRAPH::grad, GRAPH::knots, nnodes, NULL, GRAPH::oeat, distance_data::pathroot_blocks, distance_data::pathroot_blocksizes, distance_data::pathroot_blocksizesmax, pathroot_state::pathroot_id, distance_data::pathroot_isdirty, pathroot_state::pathroot_nrecomps, distance_data::pathroot_nrecomps, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocMemoryArray, and SCIPfreeBufferArray.

Referenced by extreduce_distDataInit().

closeNodesRunInit()

static SCIP_RETCODE closeNodesRunInit ( SCIP *  scip, const GRAPH *  g, DISTDATA *  distdata, CNODESRUN *  cnodesrun  )

inlinestatic

initializes run from 'startvertex'

Parameters

scip	SCIP
g	graph data structure
distdata	distance data
cnodesrun	auxiliary data

Definition at line 568 of file extreduce_dist.c.

References distance_data::closenodes_maxnumber, distance_data::closenodes_range, dijkstra_data::dheap, distance_data::dijkdata, close_nodes_run::edgemark, GRAPH::edges, csr_range::end, FALSE, FARAWAY, graph_heap_correct(), graph_knot_isInRange(), GRAPH::knots, nnodes, dijkstra_data::node_distance, dijkstra_data::nvisits, dijkstra_heap::position, close_nodes_run::prededge, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, dijkstra_heap::size, csr_range::start, close_nodes_run::startvertex, UNKNOWN, and dijkstra_data::visitlist.

Referenced by distDataComputeCloseNodes().

closeNodesRunCompute()

static SCIP_RETCODE closeNodesRunCompute ( SCIP *  scip, const GRAPH *  g, CNODESRUN *  cnodesrun, DISTDATA *  distdata  )

inlinestatic

computes sorted shortest path list to constant number of neighbors

Parameters

scip	SCIP
g	graph data structure
cnodesrun	auxiliary data
distdata	to be initialized

Definition at line 614 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_maxnumber, distance_data::closenodes_prededges, distance_data::closenodes_range, CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, dijkstra_data::dheap, distance_data::dijkdata, distDataPathRootsInsertRoot(), dynamic_csr_storage::edgeid, close_nodes_run::edgemark, csr_range::end, FALSE, GE, graph_edge_isInRange(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPc(), dynamic_csr_storage::head, close_nodes_run::is_buildphase, LT, GRAPH::mark, dijkstra_data::node_bias, dijkstra_data::node_distance, dijkstra_data::node_visited, NULL, dijkstra_data::nvisits, dijkstra_heap::position, close_nodes_run::prededge, dynamic_csr_storage::range, reduce_sdprofitGetProfit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, distance_data::sdistdata, special_distance_storage::sdprofit, dijkstra_heap::size, close_nodes_run::startvertex, GRAPH::tail, TRUE, and dijkstra_data::visitlist.

Referenced by distDataComputeCloseNodes().

closeNodesRunSort()

static void closeNodesRunSort ( const GRAPH *  g, int  node, DISTDATA *  distdata  )

inlinestatic

sort close nodes list of node

Parameters

g	graph data structure
node	the node to sort for
distdata	to be initialized

Definition at line 745 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, csr_range::end, GRAPH::grad, SCIP_Real, SCIPsortIntIntReal(), and csr_range::start.

Referenced by distDataComputeCloseNodes().

closeNodesRunExit()

static void closeNodesRunExit ( SCIP *  scip, CNODESRUN *  cnodesrun  )

inlinestatic

exits

Parameters

scip	SCIP
cnodesrun	auxiliary data

Definition at line 774 of file extreduce_dist.c.

References EAT_FREE, close_nodes_run::edgemark, NULL, GRAPH::oeat, close_nodes_run::prededge, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocMemoryArray, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by distDataComputeCloseNodes().

distDataPathRootsFree()

static void distDataPathRootsFree ( SCIP *  scip, const GRAPH *  g, DISTDATA *  distdata  )

static

frees paths root list

Parameters

scip	SCIP
g	graph data structure
distdata	to be initialized

Definition at line 881 of file extreduce_dist.c.

References GRAPH::edges, NULL, distance_data::pathroot_blocks, distance_data::pathroot_blocksizes, distance_data::pathroot_blocksizesmax, distance_data::pathroot_isdirty, distance_data::pathroot_nrecomps, SCIPfreeBlockMemoryArray, and SCIPfreeMemoryArray.

Referenced by extreduce_distDataFree().

distDataComputeCloseNodes()

static SCIP_RETCODE distDataComputeCloseNodes ( SCIP *  scip, const GRAPH *  g, CNODESRUN *  cnodesrun, DISTDATA *  distdata  )

static

computes sorted shortest path list to constant number of neighbors

Parameters

scip	SCIP
g	graph data structure
cnodesrun	auxiliary data
distdata	to be initialized

Definition at line 923 of file extreduce_dist.c.

References closeNodesRunCompute(), closeNodesRunExit(), closeNodesRunInit(), closeNodesRunSort(), SCIP_CALL, SCIP_OKAY, and close_nodes_run::startvertex.

Referenced by distDataRecomputeNormalDist(), and extreduce_distDataInit().

distDataInitSizes()

static void distDataInitSizes ( const GRAPH *  g, int  maxnclosenodes, DISTDATA *  distdata  )

static

sets sizes

Parameters

g	graph data structure
maxnclosenodes	maximum number of close nodes to each node
distdata	to be initialized

Definition at line 947 of file extreduce_dist.c.

References distance_data::closenodes_maxnumber, distance_data::closenodes_totalsize, graph_get_nVET(), and NULL.

Referenced by extreduce_distDataInit().

distDataAllocateNodesArrays()

static SCIP_RETCODE distDataAllocateNodesArrays ( SCIP *  scip, const GRAPH *  g, DISTDATA *  distdata  )

static

allocates memory for some distance data members

Parameters

scip	SCIP
g	graph data structure
distdata	to be initialized

Definition at line 970 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, distance_data::closenodes_totalsize, GRAPH::knots, nnodes, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by extreduce_distDataInit().

distDataRecomputeNormalDist()

static void distDataRecomputeNormalDist ( SCIP *  scip, const GRAPH *  g, int  vertex1, DISTDATA *  distdata  )

inlinestatic

re-compute close nodes for default distance from vertex1

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
distdata	distance data

Definition at line 993 of file extreduce_dist.c.

References distance_data::dijkdata, distDataComputeCloseNodes(), close_nodes_run::edgemark, FALSE, graph_dijkLimited_reset(), NULL, distance_data::pathroot_isdirty, distance_data::pathroot_nrecomps, SCIP_CALL_ABORT, SCIPdebugMessage, distance_data::sdistdata, and special_distance_storage::sdprofit.

Referenced by distDataGetNormalDist(), distDataGetNormalDistForbidden(), distDataGetNormalDistForbiddenEq(), distDataGetNormalDistForbiddenLast(), distDataGetSp(), and extreduce_distDataRecomputeDirtyPaths().

distDataGetSp()

static SCIP_Real distDataGetSp ( SCIP *  scip, const GRAPH *  g, int  vertex1, int  vertex2, int *  pathnodes, int *  npathnodes, DISTDATA *  distdata  )

inlinestatic

returns (normal) shortest path distance between vertex1 and vertex2 and provides inner shortest path vertices. Returns -1.0 if no shortest path was found

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
pathnodes	inner nodes
npathnodes	number of inner nodes
distdata	distance data

Definition at line 1020 of file extreduce_dist.c.

References distDataRecomputeNormalDist(), getCloseNodePath(), distance_data::pathroot_isdirty, and SCIP_Real.

Referenced by extreduce_distDataGetSp().

distDataGetNormalDist()

static SCIP_Real distDataGetNormalDist ( SCIP *  scip, const GRAPH *  g, int  vertex1, int  vertex2, DISTDATA *  distdata  )

inlinestatic

Gets shortest v1->v2 (standard) distance. Returns -1.0 if the distance is not known.

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1047 of file extreduce_dist.c.

References distDataRecomputeNormalDist(), getCloseNodeDistance(), distance_data::pathroot_isdirty, and SCIP_Real.

Referenced by extreduce_distDataGetSd(), extreduce_distDataGetSdDouble(), and extreduce_distDataGetSdDoubleEq().

distDataGetNormalDistForbidden()

static SCIP_Real distDataGetNormalDistForbidden ( SCIP *  scip, const GRAPH *  g, int  edge_forbidden, const SCIP_Bool *  edges_isForbidden, int  vertex1, int  vertex2, DISTDATA *  distdata  )

inlinestatic

as above, but with forbidden edge

Parameters

scip	SCIP
g	graph data structure
edge_forbidden	forbidden edge
edges_isForbidden	blocked edges marked or NULL
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1076 of file extreduce_dist.c.

References distDataRecomputeNormalDist(), EDGE_FORBIDDEN_NONE, getCloseNodeDistanceForbidden(), graph_edge_isInRange(), distance_data::pathroot_isdirty, and SCIP_Real.

Referenced by extreduce_distDataGetSdDoubleForbidden(), and extreduce_distDataGetSdDoubleForbiddenSingle().

distDataGetNormalDistForbiddenLast()

static SCIP_Real distDataGetNormalDistForbiddenLast ( SCIP *  scip, const GRAPH *  g, int  vertex1, int  vertex2, int  lastedge12, DISTDATA *  distdata  )

inlinestatic

as above, but with forbidden last edge

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
lastedge12	forbidden last edge for v1->v2 path
distdata	distance data

Definition at line 1106 of file extreduce_dist.c.

References distDataRecomputeNormalDist(), getCloseNodeDistanceForbiddenLast(), graph_edge_isInRange(), distance_data::pathroot_isdirty, and SCIP_Real.

Referenced by extreduce_distDataGetSdDoubleForbiddenLast().

distDataGetNormalDistForbiddenEq()

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  )

inlinestatic

as above, but with forbidden edges and known equality value

Parameters

scip	SCIP
g	graph data structure
dist_eq	critical distance
edge_forbidden	forbidden edge
edges_isForbidden	blocked edges marked, or NULL
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1134 of file extreduce_dist.c.

References distDataRecomputeNormalDist(), getCloseNodeDistanceForbiddenEq(), graph_edge_isInRange(), distance_data::pathroot_isdirty, and SCIP_Real.

Referenced by extreduce_distDataGetSdDoubleForbiddenEq().

distDataGetSpecialDist()

static SCIP_Real distDataGetSpecialDist ( const GRAPH *  g, int  vertex1, int  vertex2, DISTDATA *  distdata  )

inlinestatic

returns v1->v2 special distance

Parameters

g	graph data structure
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1167 of file extreduce_dist.c.

References FARAWAY, reduce_sdGetSd(), SCIP_Real, and distance_data::sdistdata.

Referenced by extreduce_distDataGetSd(), extreduce_distDataGetSdDouble(), and extreduce_distDataGetSdDoubleEq().

distDataGetSpecialDistIntermedTerms()

static SCIP_Real distDataGetSpecialDistIntermedTerms ( const GRAPH *  g, int  vertex1, int  vertex2, DISTDATA *  distdata  )

inlinestatic

returns v1->v2 special distance, but only for SDs with intermediate terms

Parameters

g	graph data structure
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1188 of file extreduce_dist.c.

References FARAWAY, reduce_sdGetSdIntermedTerms(), SCIP_Real, and distance_data::sdistdata.

Referenced by extreduce_distDataGetSdDoubleForbidden(), extreduce_distDataGetSdDoubleForbiddenEq(), extreduce_distDataGetSdDoubleForbiddenLast(), and extreduce_distDataGetSdDoubleForbiddenSingle().

extreduce_distDataInit()

SCIP_RETCODE extreduce_distDataInit	(	SCIP *	scip,
		GRAPH *	g,
		int	maxnclosenodes,
		SCIP_Bool	computeSD,
		SCIP_Bool	useBias,
		DISTDATA **	distdata
	)

initializes distance data

Parameters

scip	SCIP
g	graph data structure
maxnclosenodes	maximum number of close nodes to each node
computeSD	also compute special distances?
useBias	use bias?
distdata	to be initialized

Definition at line 1218 of file extreduce_dist.c.

References distance_data::closenodes_prededges, distance_data::closenodes_range, GRAPH::dcsr_storage, distance_data::dheap, distance_data::dijkdata, distDataAllocateNodesArrays(), distDataComputeCloseNodes(), distDataInitSizes(), distDataPathRootsInitialize(), csr_range::end, GRAPH::extended, extreduce_distCloseNodesAreValid(), FALSE, GRAPH::grad, graph_dijkLimited_init(), graph_dijkLimited_initPcShifts(), graph_dijkLimited_reset(), graph_heap_create(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), graph_valid_dcsr(), distance_data::hasPathReplacement, close_nodes_run::is_buildphase, GRAPH::knots, GRAPH::mark, nnodes, NULL, reduce_sdInit(), reduce_sdInitBiasedBottleneck(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, distance_data::sdistdata, csr_range::start, close_nodes_run::startvertex, and TRUE.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extInit(), extreduce_init(), extreduce_pseudoDeleteNodes(), fixVarsRedbased(), reduce_termsepaDa(), sepafullInitDistdata(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().

extreduce_distDataDeleteEdge()

void extreduce_distDataDeleteEdge	(	SCIP *	scip,
		const GRAPH *	g,
		int	edge,
		DISTDATA *	distdata
	)

updates data for edge deletion

Parameters

scip	SCIP
g	graph data structure
edge	edge to be deleted
distdata	distance data

Definition at line 1315 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_range, csr_range::end, FARAWAY, NULL, distance_data::pathroot_blocks, distance_data::pathroot_blocksizes, distance_data::pathroot_blocksizesmax, pathroot_state::pathroot_id, distance_data::pathroot_isdirty, pathroot_state::pathroot_nrecomps, distance_data::pathroot_nrecomps, SCIP_Bool, SCIPfreeBlockMemoryArray, csr_range::start, and TRUE.

Referenced by removeEdge(), replaceEdgeByPath(), and testDistDistancesAreValid().

extreduce_distDataRecomputeDirtyPaths()

void extreduce_distDataRecomputeDirtyPaths	(	SCIP *	scip,
		const GRAPH *	g,
		DISTDATA *	distdata
	)

recomputes shortest paths for dirty nodes

Parameters

scip	SCIP
g	graph data structure
distdata	distance data

Definition at line 1370 of file extreduce_dist.c.

References distDataRecomputeNormalDist(), FALSE, GRAPH::grad, graph_get_nNodes(), graph_isMarked(), GRAPH::mark, nnodes, distance_data::pathroot_isdirty, and SCIP_Bool.

Referenced by pseudodeleteExecute().

extreduce_distDataGetSp()

SCIP_Real extreduce_distDataGetSp	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		int *	pathnodes,
		int *	npathnodes,
		DISTDATA *	distdata
	)

returns (normal) shortest path distance between vertex1 and vertex2 and provides inner shortest path vertices. Returns -1.0 if no shortest path was found

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
pathnodes	inner nodes
npathnodes	number of inner nodes
distdata	distance data

Definition at line 1400 of file extreduce_dist.c.

References distDataGetSp(), EQ, graph_knot_isInRange(), and SCIP_Real.

Referenced by spg4VerticesRuleOut().

extreduce_distDataGetSd()

SCIP_Real extreduce_distDataGetSd	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

Gets bottleneck (or special) distance between v1 and v2. Will check shortest known v1->v2 path, but NOT shortest known v2->v1 path. Returns -1.0 if no distance is known. (might only happen for RPC or PC)

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1426 of file extreduce_dist.c.

References distDataGetNormalDist(), distDataGetSpecialDist(), EQ, GE, SCIP_Real, and distance_data::sdistdata.

Referenced by extGetSd(), and testDistDistancesAreValid().

extreduce_distDataGetSdDouble()

SCIP_Real extreduce_distDataGetSdDouble	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

Gets bottleneck (or special) distance between v1 and v2. Will check shortest known v1->v2 path, and also shortest known v2->v1 path if no v1-v2 path is known. Returns -1.0 if no distance is known. (might only happen for RPC or PC)

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1463 of file extreduce_dist.c.

References distDataGetNormalDist(), distDataGetSpecialDist(), EQ, GE, SCIP_Real, and distance_data::sdistdata.

Referenced by extGetSdDouble(), extGetSdDoubleFromDistdata(), extreduce_mstbiased3LeafTreeRuleOut(), extreduce_mstbiasedCheck3NodeSimple(), mst3LeafTreeGetSds(), pseudodeleteDeleteComputeCutoffs(), sepafullAddSingleSolcandEdges(), spg3StarNeighborRuleOut(), spg4VerticesRuleOut(), and subgraphBuild().

extreduce_distDataGetSdDoubleEq()

SCIP_Real extreduce_distDataGetSdDoubleEq	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real	dist_eq,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

As 'extreduce_distDataGetSdDouble', but with critial value for early abort

Parameters

scip	SCIP
g	graph data structure
dist_eq	critical distance
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1506 of file extreduce_dist.c.

References distDataGetNormalDist(), distDataGetSpecialDist(), EQ, GE, LT, SCIP_Real, and distance_data::sdistdata.

Referenced by ruleOutFromHead(), ruleOutFromTailCombs(), and ruleOutFromTailSingle().

extreduce_distDataGetSdDoubleForbidden()

SCIP_Real extreduce_distDataGetSdDoubleForbidden	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

Same as extreduce_distDataGetSdDouble, but only takes paths that do not include any edges marked as blocked.

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 1557 of file extreduce_dist.c.

References extension_data::distdata, distDataGetNormalDistForbidden(), distDataGetSpecialDistIntermedTerms(), EDGE_FORBIDDEN_NONE, EQ, extInitialCompIsEdge(), extInitialCompIsGenStar(), GE, Is_term, SCIP_Bool, SCIP_Real, extension_data::sdeq_edgesIsForbidden, distance_data::sdistdata, and GRAPH::term.

Referenced by mstEqComp3RuleOut().

extreduce_distDataGetSdDoubleForbiddenEq()

SCIP_Real extreduce_distDataGetSdDoubleForbiddenEq	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Real	dist_eq,
		int	edge_forbidden,
		int	vertex1,
		int	vertex2,
		EXTDATA *	extdata
	)

Same as extreduce_distDataGetSdDouble, but only takes paths that do not include given edge or any edges marked as blocked. User needs to provide (known) equality value

Parameters

scip	SCIP
g	graph data structure
dist_eq	critical distance
edge_forbidden	forbidden edge
vertex1	first vertex
vertex2	second vertex
extdata	extension data

Definition at line 1609 of file extreduce_dist.c.

References extension_data::distdata, distDataGetNormalDistForbiddenEq(), distDataGetSpecialDistIntermedTerms(), EQ, extInitialCompIsEdge(), extInitialCompIsGenStar(), GE, graph_edge_isInRange(), Is_term, SCIP_Bool, SCIP_Real, extension_data::sdeq_edgesIsForbidden, distance_data::sdistdata, and GRAPH::term.

Referenced by bottleneckIsEqualityDominated().

extreduce_distDataGetSdDoubleForbiddenSingle()

SCIP_Real extreduce_distDataGetSdDoubleForbiddenSingle	(	SCIP *	scip,
		const GRAPH *	g,
		int	edge_forbidden,
		int	vertex1,
		int	vertex2,
		DISTDATA *	distdata
	)

Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given edge

Parameters

scip	SCIP
g	graph data structure
edge_forbidden	edge
vertex1	first vertex
vertex2	second vertex
distdata	distance data

Definition at line 1669 of file extreduce_dist.c.

References distDataGetNormalDistForbidden(), distDataGetSpecialDistIntermedTerms(), EQ, GE, graph_edge_isInRange(), Is_term, LT, NULL, SCIP_Real, distance_data::sdistdata, and GRAPH::term.

Referenced by generalStarSetUp(), ruleOutFromHead(), ruleOutFromTailCombs(), and ruleOutFromTailSingle().

extreduce_distDataGetSdDoubleForbiddenLast()

SCIP_Real extreduce_distDataGetSdDoubleForbiddenLast	(	SCIP *	scip,
		const GRAPH *	g,
		int	vertex1,
		int	vertex2,
		int	lastedge12,
		int	lastedge21,
		DISTDATA *	distdata
	)

Same as extreduce_distDataGetSdDouble, but only takes paths that do not contain given last edges. NOTE: Behaves peculiarly for terminal-paths!

Parameters

scip	SCIP
g	graph data structure
vertex1	first vertex
vertex2	second vertex
lastedge12	forbidden last edge on v1->v2 path; needs to be in-edge of v2
lastedge21	forbidden last edge on v2->v1 path; needs to be in-edge of v1
distdata	distance data

Definition at line 1727 of file extreduce_dist.c.

References distDataGetNormalDistForbiddenLast(), distDataGetSpecialDistIntermedTerms(), EQ, GE, graph_edge_isInRange(), Is_term, LT, SCIP_Real, distance_data::sdistdata, and GRAPH::term.

Referenced by pseudodeleteDeleteComputeCutoffs().

extreduce_distDataFree()

void extreduce_distDataFree	(	SCIP *	scip,
		const GRAPH *	graph,
		DISTDATA **	distdata
	)

frees distance data

Parameters

scip	SCIP
graph	graph data structure
distdata	to be freed

Definition at line 1784 of file extreduce_dist.c.

References distance_data::closenodes_distances, distance_data::closenodes_indices, distance_data::closenodes_prededges, distance_data::closenodes_range, distance_data::dheap, distance_data::dijkdata, distDataPathRootsFree(), graph_dijkLimited_free(), graph_heap_free(), reduce_sdFree(), SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, distance_data::sdistdata, and TRUE.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extFree(), extreduce_exit(), fixVarsRedbased(), sepafullFree(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().