reduce_sdcomp.c File Reference

Detailed Description

special distance (bottleneck distance) component reduction methods for Steiner problems

Author

Daniel Rehfeldt

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

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

Definition in file reduce_sdcomp.c.

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

Go to the source code of this file.

Data Structures
struct	bottleneck_distance_storage

Macros
#define	STP_BDK_WITH_EDGEREPLACINGS   FALSE
#define	STP_BDKIMP_MAXDEGREE   6
#define	STP_BDKIMP_MAXNEDGES   15

Typedefs
typedef struct bottleneck_distance_storage	BDK

Functions
static SCIP_RETCODE	bdkInit (SCIP *scip, SD *sdistance, BDK **bdk)
static void	bdkFree (SCIP *scip, BDK **bdk)
static void	bdkGetNeighborhood (const GRAPH *g, int starcenter, BDK *bdk)
static SCIP_Bool	bdkNodeIsInvalid (const GRAPH *g, int node, int degree, const BDK *bdk)
static SCIP_RETCODE	bdkGetCliqueSds (SCIP *scip, const GRAPH *g, int node, DIJK *dijkdata, BDK *bdk)
static void	bdkGetCutoffs (const GRAPH *g, const BDK *bdk, int node, SCIP_Real *cutoffs)
static void	bdkGetEdgeCutoffs (const GRAPH *g, const BDK *bdk, int edge, SCIP_Real *cutoffs)
static void	bdkStarLoadNext (const GRAPH *g, BDK *bdk)
static SCIP_Real	bdkStarGetCost (int starcenter, const GRAPH *g, const BDK *bdk)
static SCIP_Real	bdkStarGetCombinedSdCost (const GRAPH *g, BDK *bdk)
static void	bdkStarMarkCliqueNodes (BDK *bdk)
static int	bdkStarGetMstStartNode (const GRAPH *cliquegraph)
static void	bdkStarStoreMstsCosts (int startnode, BDK *bdk)
static SCIP_Bool	bdkStarIsSdMstReplacable (SCIP *scip, SCIP_Real starcost, const GRAPH *g, BDK *bdk)
static SCIP_Bool	bdkStarIsSdTreeReplacable (SCIP *scip, SCIP_Real starcost, const GRAPH *g, BDK *bdk)
static SCIP_Bool	bdkStarIsReplacableDeg3 (SCIP *scip, int i, const GRAPH *g, BDK *bdk)
static SCIP_Bool	bdkStarIsReplacableDegGe4 (SCIP *scip, int starcenter, const GRAPH *g, BDK *bdk)
static SCIP_RETCODE	bdkTryDeg3 (SCIP *scip, int node, GRAPH *g, BDK *bdk, int *nelims)
static SCIP_RETCODE	bdkTryDegGe4 (SCIP *scip, int node, GRAPH *g, BDK *bdk, int *nelims)
SCIP_RETCODE	reduce_bdk (SCIP *scip, int edgevisitlimit, GRAPH *g, int *nelims)
SCIP_RETCODE	reduce_bdkBiased (SCIP *scip, int edgevisitlimit, GRAPH *g, int *nelims)
SCIP_RETCODE	reduce_bdkWithSd (SCIP *scip, int edgevisitlimit, SD *sdistance, GRAPH *g, int *nelims)

Macro Definition Documentation

STP_BDK_WITH_EDGEREPLACINGS

#define STP_BDK_WITH_EDGEREPLACINGS   FALSE

Definition at line 38 of file reduce_sdcomp.c.

Referenced by bdkInit().

STP_BDKIMP_MAXDEGREE

#define STP_BDKIMP_MAXDEGREE   6

Definition at line 39 of file reduce_sdcomp.c.

Referenced by bdkGetCliqueSds(), bdkInit(), bdkStarGetMstStartNode(), bdkStarIsReplacableDegGe4(), bdkStarMarkCliqueNodes(), bdkStarStoreMstsCosts(), bdkTryDegGe4(), and reduce_bdkWithSd().

STP_BDKIMP_MAXNEDGES

#define STP_BDKIMP_MAXNEDGES   15

Definition at line 40 of file reduce_sdcomp.c.

Referenced by bdkInit(), and bdkTryDegGe4().

Typedef Documentation

BDK

typedef struct bottleneck_distance_storage BDK

BD_k storage

Function Documentation

bdkInit()

static SCIP_RETCODE bdkInit ( SCIP *  scip, SD *  sdistance, BDK **  bdk  )

static

initializes data for bdk test

Parameters

scip	SCIP data structure
sdistance	special distance storage
bdk	storage

Definition at line 66 of file reduce_sdcomp.c.

References bottleneck_distance_storage::clique_mst, bottleneck_distance_storage::cliquegraph, bottleneck_distance_storage::doEdgeReplacement, bottleneck_distance_storage::edgehalf_isblocked, GRAPH::edges, graph_buildCompleteGraph(), graph_path_init(), special_distance_storage::isBiased, GRAPH::mark, bottleneck_distance_storage::node_degree, bottleneck_distance_storage::node_neighbors, bottleneck_distance_storage::node_outedges, NULL, reduce_sdgraphGetMstHalfMark(), reduce_sdgraphHasMstHalfMark(), reduce_starInit(), SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, special_distance_storage::sdgraph, bottleneck_distance_storage::sdistance, bottleneck_distance_storage::sdprofit, special_distance_storage::sdprofit, bottleneck_distance_storage::star, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_mstsds, bottleneck_distance_storage::star_outedges, bottleneck_distance_storage::star_outedges_pos, STP_BDK_WITH_EDGEREPLACINGS, STP_BDKIMP_MAXDEGREE, STP_BDKIMP_MAXNEDGES, and TRUE.

Referenced by reduce_bdkWithSd().

bdkFree()

static void bdkFree ( SCIP *  scip, BDK **  bdk  )

static

frees data for bdk test

Parameters

scip	SCIP data structure
bdk	storage

Definition at line 109 of file reduce_sdcomp.c.

References bottleneck_distance_storage::clique_mst, bottleneck_distance_storage::cliquegraph, graph_free(), graph_path_exit(), bottleneck_distance_storage::node_neighbors, bottleneck_distance_storage::node_outedges, reduce_starFree(), SCIPfreeMemory, SCIPfreeMemoryArray, bottleneck_distance_storage::star, bottleneck_distance_storage::star_mstsds, bottleneck_distance_storage::star_outedges_pos, and TRUE.

Referenced by reduce_bdkWithSd().

bdkGetNeighborhood()

static void bdkGetNeighborhood ( const GRAPH *  g, int  starcenter, BDK *  bdk  )

inlinestatic

gets neighborhood information for bdk test

Parameters

g	graph data structure
starcenter	the node
bdk	storage

Definition at line 134 of file reduce_sdcomp.c.

References EAT_LAST, GRAPH::grad, GRAPH::head, bottleneck_distance_storage::node_degree, bottleneck_distance_storage::node_neighbors, bottleneck_distance_storage::node_outedges, GRAPH::oeat, and GRAPH::outbeg.

Referenced by reduce_bdkWithSd().

bdkNodeIsInvalid()

static SCIP_Bool bdkNodeIsInvalid ( const GRAPH *  g, int  node, int  degree, const BDK *  bdk  )

inlinestatic

is the node invalid?

Parameters

g	graph data structure
node	the node
degree	current degree
bdk	storage

Definition at line 158 of file reduce_sdcomp.c.

References EAT_LAST, bottleneck_distance_storage::edgehalf_isblocked, EQ, FALSE, GRAPH::grad, Is_term, GRAPH::oeat, GRAPH::outbeg, reduce_sdprofitGetProfit(), SCIP_Bool, bottleneck_distance_storage::sdprofit, GRAPH::term, and TRUE.

Referenced by reduce_bdkWithSd().

bdkGetCliqueSds()

static SCIP_RETCODE bdkGetCliqueSds ( SCIP *  scip, const GRAPH *  g, int  node, DIJK *  dijkdata, BDK *  bdk  )

inlinestatic

gets SDs bdk test; stored in cliquegraph

Parameters

scip	SCIP data structure
g	graph data structure
node	the node
dijkdata	data for repeated path computations
bdk	storage

Definition at line 199 of file reduce_sdcomp.c.

References bottleneck_distance_storage::cliquegraph, FALSE, GRAPH::grad, GRAPH::knots, GRAPH::mark, bottleneck_distance_storage::node_degree, bottleneck_distance_storage::node_neighbors, reduce_sdGetSdsCliquegraph(), SCIP_CALL, SCIP_OKAY, bottleneck_distance_storage::sdistance, STP_BDKIMP_MAXDEGREE, and TRUE.

Referenced by reduce_bdkWithSd().

bdkGetCutoffs()

static void bdkGetCutoffs ( const GRAPH *  g, const BDK *  bdk, int  node, SCIP_Real *  cutoffs  )

inlinestatic

gets SDs for bdk node test; stored in clique-graph

Parameters

g	graph data structure
bdk	storage
node	the node
cutoffs	cutoffs

Definition at line 230 of file reduce_sdcomp.c.

References bottleneck_distance_storage::cliquegraph, GRAPH::cost, EAT_LAST, GRAPH::head, bottleneck_distance_storage::node_degree, GRAPH::oeat, and GRAPH::outbeg.

Referenced by bdkTryDeg3(), and bdkTryDegGe4().

bdkGetEdgeCutoffs()

static void bdkGetEdgeCutoffs ( const GRAPH *  g, const BDK *  bdk, int  edge, SCIP_Real *  cutoffs  )

inlinestatic

gets SDs for bdk edge test; stored in clique-graph

Parameters

g	graph data structure
bdk	storage
edge	the edge; replacement goes towards the head!
cutoffs	cutoffs

Definition at line 264 of file reduce_sdcomp.c.

References bottleneck_distance_storage::cliquegraph, GRAPH::cost, EAT_LAST, EQ, GRAPH::head, bottleneck_distance_storage::node_degree, bottleneck_distance_storage::node_neighbors, GRAPH::oeat, GRAPH::outbeg, SCIPdebugMessage, and GRAPH::tail.

Referenced by bdkTryDegGe4().

bdkStarLoadNext()

static void bdkStarLoadNext ( const GRAPH *  g, BDK *  bdk  )

inlinestatic

gets next star

Parameters

g	graph data structure
bdk	storage

Definition at line 317 of file reduce_sdcomp.c.

References graph_edge_printInfo(), reduce_starGetNextAndPosition(), SCIPdebugMessage, bottleneck_distance_storage::star, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_outedges, and bottleneck_distance_storage::star_outedges_pos.

Referenced by bdkTryDegGe4().

bdkStarGetCost()

static SCIP_Real bdkStarGetCost ( int  starcenter, const GRAPH *  g, const BDK *  bdk  )

inlinestatic

return cost of star

Parameters

starcenter	the star center node
g	graph data structure
bdk	storage

Definition at line 336 of file reduce_sdcomp.c.

References GRAPH::cost, SCIP_Real, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_outedges, and GRAPH::tail.

Referenced by bdkStarIsReplacableDegGe4().

bdkStarGetCombinedSdCost()

static SCIP_Real bdkStarGetCombinedSdCost ( const GRAPH *  g, BDK *  bdk  )

inlinestatic

Returns SD replacement cost of star. Chooses best combinations of SD clique MST costs and SD distance graph MST costs.

Parameters

g	graph data structure
bdk	storage

Definition at line 360 of file reduce_sdcomp.c.

References FARAWAY, GE, LE_FEAS, LT, reduce_sdgraphGetOrderedMstCosts(), SCIP_Real, SCIPsortDownReal(), special_distance_storage::sdgraph, bottleneck_distance_storage::sdistance, bottleneck_distance_storage::star_degree, and bottleneck_distance_storage::star_mstsds.

Referenced by bdkStarIsSdMstReplacable().

bdkStarMarkCliqueNodes()

static void bdkStarMarkCliqueNodes ( BDK *  bdk )

inlinestatic

marks nodes that are in current star

Parameters

bdk

storage

Definition at line 406 of file reduce_sdcomp.c.

References bottleneck_distance_storage::cliquegraph, FALSE, GRAPH::mark, bottleneck_distance_storage::node_degree, bottleneck_distance_storage::node_outedges, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_outedges, bottleneck_distance_storage::star_outedges_pos, STP_BDKIMP_MAXDEGREE, and TRUE.

Referenced by bdkStarIsSdMstReplacable().

bdkStarGetMstStartNode()

static int bdkStarGetMstStartNode ( const GRAPH *  cliquegraph )

inlinestatic

gets start node for MSt

Parameters

cliquegraph

graph data structure

Definition at line 441 of file reduce_sdcomp.c.

References GRAPH::mark, and STP_BDKIMP_MAXDEGREE.

Referenced by bdkStarIsSdMstReplacable().

bdkStarStoreMstsCosts()

static void bdkStarStoreMstsCosts ( int  startnode, BDK *  bdk  )

inlinestatic

stores MST costs for later use

Parameters

startnode	start node
bdk	storage

Definition at line 464 of file reduce_sdcomp.c.

References bottleneck_distance_storage::clique_mst, bottleneck_distance_storage::cliquegraph, shortest_path::dist, FARAWAY, GE, LT, GRAPH::mark, SCIP_Real, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_mstsds, and STP_BDKIMP_MAXDEGREE.

Referenced by bdkStarIsSdMstReplacable().

bdkStarIsSdMstReplacable()

static SCIP_Bool bdkStarIsSdMstReplacable ( SCIP *  scip, SCIP_Real  starcost, const GRAPH *  g, BDK *  bdk  )

inlinestatic

can star be replaced by SD MST?

Parameters

scip	SCIP data structure
starcost	cost of star
g	graph data structure
bdk	storage

Definition at line 494 of file reduce_sdcomp.c.

References bdkStarGetCombinedSdCost(), bdkStarGetMstStartNode(), bdkStarMarkCliqueNodes(), bdkStarStoreMstsCosts(), bottleneck_distance_storage::clique_mst, bottleneck_distance_storage::cliquegraph, GRAPH::cost, FALSE, graph_path_exec(), MST_MODE, SCIP_Real, SCIPdebugMessage, SCIPisLE(), and TRUE.

Referenced by bdkStarIsReplacableDeg3(), and bdkStarIsReplacableDegGe4().

bdkStarIsSdTreeReplacable()

static SCIP_Bool bdkStarIsSdTreeReplacable ( SCIP *  scip, SCIP_Real  starcost, const GRAPH *  g, BDK *  bdk  )

inlinestatic

can star be replaced by SD MST?

Parameters

scip	SCIP data structure
starcost	cost of star
g	graph data structure
bdk	storage

Definition at line 533 of file reduce_sdcomp.c.

References FALSE, GE, reduce_sdgraphGetOrderedMstCosts(), SCIP_Real, SCIPdebugMessage, SCIPisLE(), special_distance_storage::sdgraph, bottleneck_distance_storage::sdistance, bottleneck_distance_storage::star_degree, and TRUE.

Referenced by bdkStarIsReplacableDegGe4().

bdkStarIsReplacableDeg3()

static SCIP_Bool bdkStarIsReplacableDeg3 ( SCIP *  scip, int  i, const GRAPH *  g, BDK *  bdk  )

inlinestatic

can vertex of degree 3 be replaced?

Parameters

scip	SCIP data structure
i	the node
g	graph data structure
bdk	storage

Definition at line 567 of file reduce_sdcomp.c.

References bdkStarIsSdMstReplacable(), GRAPH::cost, FALSE, GE, graph_pseudoAncestors_edgesInConflict(), reduce_sdgraphGetOrderedMstCosts(), SCIP_Real, SCIPdebugMessage, SCIPisLE(), special_distance_storage::sdgraph, bottleneck_distance_storage::sdistance, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_outedges, and TRUE.

Referenced by bdkTryDeg3(), and bdkTryDegGe4().

bdkStarIsReplacableDegGe4()

static SCIP_Bool bdkStarIsReplacableDegGe4 ( SCIP *  scip, int  starcenter, const GRAPH *  g, BDK *  bdk  )

inlinestatic

can star of degree 4 or greater be replaced?

Parameters

scip	SCIP data structure
starcenter	the node
g	graph data structure
bdk	storage

Definition at line 603 of file reduce_sdcomp.c.

References bdkStarGetCost(), bdkStarIsSdMstReplacable(), bdkStarIsSdTreeReplacable(), FALSE, graph_pseudoAncestors_edgesInConflict(), SCIP_Real, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_outedges, STP_BDKIMP_MAXDEGREE, GRAPH::terms, and TRUE.

Referenced by bdkTryDegGe4().

bdkTryDeg3()

static SCIP_RETCODE bdkTryDeg3 ( SCIP *  scip, int  node, GRAPH *  g, BDK *  bdk, int *  nelims  )

inlinestatic

does bdk test for vertex of degree 3 NOTE: one could also use DegGe4 instead, but this method is slightly more efficient

Parameters

scip	SCIP data structure
node	the node
g	graph data structure
bdk	storage
nelims	number of eliminations

Definition at line 632 of file reduce_sdcomp.c.

References bdkGetCutoffs(), bdkStarIsReplacableDeg3(), GRAPH::cost, GRAPH::grad, graph_knot_delPseudo(), bottleneck_distance_storage::node_degree, bottleneck_distance_storage::node_outedges, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, bottleneck_distance_storage::star_degree, bottleneck_distance_storage::star_outedges, and GRAPH::terms.

Referenced by reduce_bdkWithSd().

bdkTryDegGe4()

static SCIP_RETCODE bdkTryDegGe4 ( SCIP *  scip, int  node, GRAPH *  g, BDK *  bdk, int *  nelims  )

inlinestatic

does bdk test for vertex of degree 4 or more

Parameters

scip	SCIP data structure
node	the node
g	graph data structure
bdk	storage
nelims	number of eliminations

Definition at line 668 of file reduce_sdcomp.c.

References bdkGetCutoffs(), bdkGetEdgeCutoffs(), bdkStarIsReplacableDeg3(), bdkStarIsReplacableDegGe4(), bdkStarLoadNext(), GRAPH::cost, bottleneck_distance_storage::doEdgeReplacement, FALSE, flipedge, GRAPH::grad, graph_edge_delPseudo(), graph_edge_isInRange(), graph_knot_delPseudo(), GRAPH::head, isPseudoDeletable(), bottleneck_distance_storage::node_degree, NULL, reduce_starAllAreChecked(), reduce_starCurrentSetFailed(), reduce_starGetRuledOutEdges(), reduce_starHasPromisingEdges(), reduce_starReset(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, bottleneck_distance_storage::star, bottleneck_distance_storage::star_degree, STP_BDKIMP_MAXDEGREE, STP_BDKIMP_MAXNEDGES, and TRUE.

Referenced by reduce_bdkWithSd().

reduce_bdk()

SCIP_RETCODE reduce_bdk	(	SCIP *	scip,
		int	edgevisitlimit,
		GRAPH *	g,
		int *	nelims
	)

bd_k test without given Steiner bottleneck distances

Parameters

scip	SCIP data structure
edgevisitlimit	maximum edge visited per iteration
g	graph structure
nelims	number of eliminations

Definition at line 774 of file reduce_sdcomp.c.

References reduce_bdkWithSd(), reduce_sdFree(), reduce_sdInit(), SCIP_CALL, SCIP_OKAY, bottleneck_distance_storage::sdistance, and GRAPH::terms.

Referenced by redLoopInnerStp(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), and testBdkTreeDistDeletesNodeDeg4().

reduce_bdkBiased()

SCIP_RETCODE reduce_bdkBiased	(	SCIP *	scip,
		int	edgevisitlimit,
		GRAPH *	g,
		int *	nelims
	)

biased bd_k test without given Steiner bottleneck distances

Parameters

scip	SCIP data structure
edgevisitlimit	maximum edge visited per iteration
g	graph structure
nelims	number of eliminations

Definition at line 796 of file reduce_sdcomp.c.

References reduce_bdkWithSd(), reduce_sdFree(), reduce_sdInitBiased(), SCIP_CALL, SCIP_OKAY, bottleneck_distance_storage::sdistance, and GRAPH::terms.

reduce_bdkWithSd()

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

bd_k test for given Steiner bottleneck distances

Parameters

scip	SCIP data structure
edgevisitlimit	maximum edge visited per iteration
sdistance	special distances storage
g	graph structure
nelims	number of eliminations

Definition at line 818 of file reduce_sdcomp.c.

References bdkFree(), bdkGetCliqueSds(), bdkGetNeighborhood(), bdkInit(), bdkNodeIsInvalid(), bdkTryDeg3(), bdkTryDegGe4(), dijkstra_data::edgelimit, graph_dijkLimited_clean(), graph_dijkLimited_free(), graph_dijkLimited_init(), graph_dijkLimited_reset(), graph_get_nNodes(), graph_mark(), graph_pc_isPcMw(), nnodes, reduce_unconnected(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, STP_BDKIMP_MAXDEGREE, and GRAPH::terms.

Referenced by reduce_bdk(), and reduce_bdkBiased().