reduce_alt.c File Reference

Detailed Description

Altenative based reduction tests for Steiner problems.

Author

Thorsten Koch

Stephen Maher

Daniel Rehfeldt

This file implements alternative-based reduction techniques for several Steiner problems. All tests can be found in "A Generic Approach to Solving the Steiner Tree Problem and Variants" by Daniel Rehfeldt.

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

Definition in file reduce_alt.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "grph.h"
#include "probdata_stp.h"
#include "scip/scip.h"

Go to the source code of this file.

Macros
#define	CNSNN   25
#define	KNOTFREQ   100
#define	KNOTLIMIT   1e+20

Functions
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, PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, int *vbase, int *neighbterms, int i, int nnodes)
static int	getlecloseterms (SCIP *scip, PATH *vnoi, SCIP_Real *termdist, SCIP_Real ecost, int *vbase, int *neighbterms, int i, int nnodes)
static int	issmaller (SCIP *scip, const double *pathdist, const double *pathtran, int a, int b)
static int	islarger (SCIP *scip, const double *pathdist, const double *pathtran, int a, int b)
static int	nearest (SCIP *scip, int *heap, int *state, int *count, const double *pathdist, const double *pathtran)
static void	correct (SCIP *scip, int *heap, int *state, int *count, double *pathdist, double *pathtran, int l)
static void	compute_sd (SCIP *scip, const GRAPH *p, int start, const double *cost, const double *randarr, int *heap, int *state, int *count, double *pathdist, double *pathtran, double *pathrand)
SCIP_RETCODE	sd_red (SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *edgepreds, SCIP_Real *mstsdist, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *forbidden, int *nelims)
SCIP_RETCODE	sdpc_reduction (SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *boundedges, int *heap, int *state, int *vbase, int *nodesid, int *nodesorg, int *nelims)
static SCIP_Real	getRSD (SCIP *scip, GRAPH *g, GRAPH *netgraph, PATH *mst, PATH *vnoi, SCIP_Real *mstsdist, SCIP_Real *termdist1, SCIP_Real *termdist2, int *vbase, int *nodesid, int *neighbterms1, int *neighbterms2, int i, int i2, int limit)
SCIP_RETCODE	getSD (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_RETCODE	sd2_reduction (SCIP *scip, GRAPH *g, SCIP_Real *nodecost, int *nelims, int *adjacent)
SCIP_RETCODE	sdsp_sap_reduction (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
SCIP_RETCODE	sdsp_reduction (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
SCIP_RETCODE	sd_reduction (SCIP *scip, GRAPH *g, SCIP_Real *sddist, SCIP_Real *sdtrans, SCIP_Real *sdrand, SCIP_Real *cost, SCIP_Real *randarr, int *heap, int *state, int *knotexamined, int *elimins, int runnum, unsigned int *seed)
SCIP_RETCODE	bdr_reduction (SCIP *scip, GRAPH *g, GRAPH *netgraph, PATH *netmst, PATH *vnoi, SCIP_Real *mstsdist, SCIP_Real *termdist1, SCIP_Real *termdist2, int *vbase, int *nodesid, int *neighbterms1, int *neighbterms2, int *nelims)
SCIP_RETCODE	bd3_reduction (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
SCIP_RETCODE	sl_reduction (SCIP *scip, GRAPH *g, PATH *vnoi, double *fixed, int *heap, int *state, int *vbase, int *vrnodes, char *visited, int *nelims)
SCIP_RETCODE	nv_reduction (SCIP *scip, GRAPH *g, PATH *vnoi, double *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *nelims)
SCIP_RETCODE	nv_reductionAdv (SCIP *scip, GRAPH *g, PATH *vnoi, SCIP_Real *distance, double *fixed, int *edgearrint, int *heap, int *state, int *vbase, int *neighb, int *distnode, int *nelims)
SCIP_RETCODE	ledge_reduction (SCIP *scip, GRAPH *g, PATH *vnoi, int *heap, int *state, int *vbase, int *nelims)
SCIP_RETCODE	ansReduction (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *marked, int *count)
SCIP_RETCODE	cnsAdvReduction (SCIP *scip, GRAPH *g, int *marked, int *count)
SCIP_RETCODE	ansadvReduction (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *marked, int *count)
SCIP_RETCODE	ansadv2Reduction (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *marked, int *count)
SCIP_RETCODE	npvReduction (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
SCIP_RETCODE	chain2Reduction (SCIP *scip, GRAPH *g, PATH *pathtail, PATH *pathhead, int *heap, int *statetail, int *statehead, int *memlbltail, int *memlblhead, int *nelims, int limit)
SCIP_RETCODE	nnpReduction (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *mem, int *marked, int *visited, int *count, int maxniter, char *positive)

Macro Definition Documentation

#define CNSNN   25

Definition at line 39 of file reduce_alt.c.

Referenced by ansadv2Reduction(), ansadvReduction(), and cnsAdvReduction().

#define KNOTFREQ   100

Definition at line 40 of file reduce_alt.c.

Referenced by bd3_reduction(), and sd_reduction().

#define KNOTLIMIT   1e+20

Definition at line 41 of file reduce_alt.c.

Referenced by bd3_reduction(), and sd_reduction().

Function Documentation

SCIP_RETCODE ansadv2Reduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	marked,
		int *	count
	)

alternative advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
marked	nodes array
count	pointer to number of reductions

Definition at line 4991 of file reduce_alt.c.

References CNSNN, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, maxprize(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

SCIP_RETCODE ansadvReduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	marked,
		int *	count
	)

advanced adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
marked	nodes array
count	pointer to number of reductions

Definition at line 4867 of file reduce_alt.c.

References CNSNN, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduceMwcs().

SCIP_RETCODE ansReduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	marked,
		int *	count
	)

adjacent neighbourhood reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
marked	nodes array
count	pointer to number of reductions

Definition at line 4579 of file reduce_alt.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, and TRUE.

Referenced by reduceMwcs().

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

Definition at line 2817 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, EQ, FALSE, FARAWAY, GRAPH::fixedges, flipedge, FSP_MODE, GE, getSD(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_edge_redirect(), graph_edge_reinsert(), graph_free(), graph_init(), graph_knot_add(), graph_knot_contract(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GT, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, Is_term, KNOTFREQ, KNOTLIMIT, GRAPH::knots, LE, LT, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_DIRECTED, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_term().

Referenced by reducePc(), and reduceStp().

SCIP_RETCODE bdr_reduction	(	SCIP *	scip,
		GRAPH *	g,
		GRAPH *	netgraph,
		PATH *	netmst,
		PATH *	vnoi,
		SCIP_Real *	mstsdist,
		SCIP_Real *	termdist1,
		SCIP_Real *	termdist2,
		int *	vbase,
		int *	nodesid,
		int *	neighbterms1,
		int *	neighbterms2,
		int *	nelims
	)

Parameters

scip	SCIP data structure
g	graph structure
netgraph	auxiliary graph structure
netmst	MST structure
vnoi	path structure
mstsdist	MST distance in aux-graph
termdist1	dist array
termdist2	second dist array
vbase	bases for nearest terminals
nodesid	nodes identification array
neighbterms1	neighbour terminals array
neighbterms2	second neighbour terminals array
nelims	number of eliminations

Definition at line 2538 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, Edge_anti, FALSE, flipedge, getRSD(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_edge_reinsert(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by sd_red().

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

chain reduction (NPV_2) for the MWCSP

Definition at line 5484 of file reduce_alt.c.

References shortest_path::dist, shortest_path::edge, FALSE, FARAWAY, getSD(), GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

SCIP_RETCODE cnsAdvReduction	(	SCIP *	scip,
		GRAPH *	g,
		int *	marked,
		int *	count
	)

advanced connected neighbourhood subset reduction test for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
marked	nodes array
count	pointer to number of reductions

Definition at line 4675 of file reduce_alt.c.

References CNSNN, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

static void compute_sd ( SCIP *  scip, const GRAPH *  p, int  start, const double *  cost, const double *  randarr, int *  heap, int *  state, int *  count, double *  pathdist, double *  pathtran, double *  pathrand  )

static

Dijkstra's algorithm for shortest path or minimum spanning tree

Definition at line 462 of file reduce_alt.c.

References CONNECT, correct(), EAT_LAST, FARAWAY, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and UNKNOWN.

Referenced by sd_reduction().

static void correct ( SCIP *  scip, int *  heap, int *  state, int *  count, double *  pathdist, double *  pathtran, int  l  )

inlinestatic

insert respectively change element in heap

Definition at line 420 of file reduce_alt.c.

References islarger(), and UNKNOWN.

Referenced by compute_sd().

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

static

Definition at line 272 of file reduce_alt.c.

References shortest_path::dist.

Referenced by getRSD(), sd_red(), and sdpc_reduction().

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 311 of file reduce_alt.c.

References shortest_path::dist.

Referenced by sd_red().

static SCIP_Real getRSD ( SCIP *  scip, GRAPH *  g, GRAPH *  netgraph, PATH *  mst, PATH *  vnoi, SCIP_Real *  mstsdist, SCIP_Real *  termdist1, SCIP_Real *  termdist2, int *  vbase, int *  nodesid, int *  neighbterms1, int *  neighbterms2, int  i, int  i2, int  limit  )

static

get RSD to a single edge

Parameters

scip	SCIP data structure
g	graph structure
netgraph	auxiliary graph structure
mst	MST structure
vnoi	path structure
mstsdist	MST distance in aux-graph
termdist1	dist array
termdist2	second dist array
vbase	bases for nearest terminals
nodesid	nodes identification array
neighbterms1	neighbour terminals array
neighbterms2	second neighbour terminals array
i	first vertex
i2	second vertex
limit	limit for incident edges to consider

Definition at line 1472 of file reduce_alt.c.

References GRAPH::cost, EAT_LAST, shortest_path::edge, FARAWAY, getcloseterms(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and GRAPH::term.

Referenced by bdr_reduction().

SCIP_RETCODE getSD	(	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
	)

get SD to a single edge

Definition at line 1658 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, sdpaths(), GRAPH::term, and UNKNOWN.

Referenced by bd3_reduction(), chain2Reduction(), and npvReduction().

static int islarger ( SCIP *  scip, const double *  pathdist, const double *  pathtran, int  a, int  b  )

static

Definition at line 359 of file reduce_alt.c.

Referenced by correct(), and nearest().

static int issmaller ( SCIP *  scip, const double *  pathdist, const double *  pathtran, int  a, int  b  )

static

Definition at line 350 of file reduce_alt.c.

Referenced by nearest().

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

Definition at line 4372 of file reduce_alt.c.

References CONNECT, GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), graph_valid(), GRAPH::head, Is_term, GRAPH::knots, level0(), GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_state, GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, and voronoi_terms().

Referenced by reduceStp().

static int nearest ( SCIP *  scip, int *  heap, int *  state, int *  count, const double *  pathdist, const double *  pathtran  )

inlinestatic

Definition at line 375 of file reduce_alt.c.

References islarger(), and issmaller().

Referenced by compute_sd().

SCIP_RETCODE nnpReduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	mem,
		int *	marked,
		int *	visited,
		int *	count,
		int	maxniter,
		char *	positive
	)

non-negative path reduction for the MWCSP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
mem	nodes array
marked	nodes array
visited	nodes array
count	pointer to number of reductions
maxniter	max number of edges to check
positive	nodes array

Definition at line 5564 of file reduce_alt.c.

References EAT_LAST, FALSE, flipedge, graph_edge_del(), GRAPH::head, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, and TRUE.

Referenced by reduceMwcs().

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

non-positive vertex reduction for the MWCSP

Definition at line 5146 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, flipedge, getSD(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_path_exec(), graph_path_exit(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduceMwcs().

SCIP_RETCODE nv_reduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		double *	fixed,
		int *	edgearrint,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nelims
	)

Definition at line 3892 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, UNKNOWN, and voronoi_dist().

SCIP_RETCODE nv_reductionAdv	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	distance,
		double *	fixed,
		int *	edgearrint,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	neighb,
		int *	distnode,
		int *	nelims
	)

Definition at line 4083 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, UNKNOWN, and voronoi_dist().

Referenced by nvsl_reduction().

SCIP_RETCODE sd2_reduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	nodecost,
		int *	nelims,
		int *	adjacent
	)

SD test using only two edges

Definition at line 1799 of file reduce_alt.c.

References GRAPH::cost, EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, and TRUE.

SCIP_RETCODE sd_red	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		SCIP_Real *	edgepreds,
		SCIP_Real *	mstsdist,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	nodesid,
		int *	nodesorg,
		int *	forbidden,
		int *	nelims
	)

Special distance test

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
edgepreds	array to store edge predecessors of auxiliary graph
mstsdist	array to store mst distances in auxiliary graph
heap	array representing a heap
state	array to indicate whether a node has been scanned during SP calculation
vbase	Voronoi base to each vertex
nodesid	array to map nodes in auxiliary graph to original ones
nodesorg	array to map terminals of original graph vertices of auxiliary graph
forbidden	array to mark whether an edge may be eliminated
nelims	point to store number of deleted edges

Definition at line 598 of file reduce_alt.c.

References bdr_reduction(), GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, flipedge, getcloseterms(), getlecloseterms(), getnext4terms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_path_exec(), graph_path_execX(), graph_path_exit(), graph_path_init(), GRAPH::head, GRAPH::ieat, Is_term, GRAPH::knots, GRAPH::mark, MST_MODE, GRAPH::oeat, GRAPH::outbeg, SCIPprobdataPrintGraph2(), sddeltable(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduceStp().

SCIP_RETCODE sd_reduction	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	sddist,
		SCIP_Real *	sdtrans,
		SCIP_Real *	sdrand,
		SCIP_Real *	cost,
		SCIP_Real *	randarr,
		int *	heap,
		int *	state,
		int *	knotexamined,
		int *	elimins,
		int	runnum,
		unsigned int *	seed
	)

Definition at line 2227 of file reduce_alt.c.

References compute_sd(), GRAPH::cost, EAT_LAST, Edge_anti, GRAPH::edges, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_valid(), GT, GRAPH::head, Is_term, KNOTFREQ, KNOTLIMIT, GRAPH::knots, LT, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduceStp().

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

Definition at line 129 of file reduce_alt.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, shortest_path::edge, FALSE, flipedge, GRAPH::head, GRAPH::ieat, Is_term, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by sd_red().

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

SD test for PC

Parameters

scip	SCIP data structure
g	graph data structure
vnoi	Voronoi data structure
boundedges	array to store bound edges
heap	heap array
state	array to store state of a node during Voronoi computation
vbase	Voronoi base to each node
nodesid	array
nodesorg	array
nelims	pointer to store number of eliminated edges

Definition at line 1144 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_FREE, EAT_LAST, Edge_anti, GRAPH::edges, FARAWAY, getcloseterms(), getnext4terms(), getnext4tterms(), GRAPH::grad, graph_edge_add(), graph_edge_del(), graph_free(), graph_init(), graph_knot_add(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reducePc().

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

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

Definition at line 2058 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::grad, graph_edge_del(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, sdpaths(), STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reducePc(), and reduceStp().

SCIP_RETCODE sdsp_sap_reduction	(	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

Definition at line 1900 of file reduce_alt.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_edge_del(), GRAPH::head, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, sdpaths(), TRUE, and UNKNOWN.

Referenced by reduceSap().

SCIP_RETCODE sl_reduction	(	SCIP *	scip,
		GRAPH *	g,
		PATH *	vnoi,
		double *	fixed,
		int *	heap,
		int *	state,
		int *	vbase,
		int *	vrnodes,
		char *	visited,
		int *	nelims
	)

Definition at line 3656 of file reduce_alt.c.

References GRAPH::ancestors, GRAPH::cost, shortest_path::dist, EAT_LAST, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, UNKNOWN, and voronoi_terms().

Referenced by nvsl_reduction().