reduce_simple.c File Reference

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

Go to the source code of this file.

Functions
static SCIP_Bool	maxprize (SCIP *scip, GRAPH *g, int i)
static SCIP_RETCODE	trydg1edgepc (SCIP *scip, GRAPH *g, SCIP_Real *offset, int *count, int i, int iout, SCIP_Bool *rerun)
static SCIP_RETCODE	traverseChain (SCIP *scip, GRAPH *g, int *length, int *final, int i, int i1, int i2, int e1)
int	deleteterm (SCIP *scip, GRAPH *g, int i)
SCIP_RETCODE	degree_test (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *nelims)
SCIP_RETCODE	degree_test_sap (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
SCIP_RETCODE	rptReduction (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
SCIP_RETCODE	degree_test_mw (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
SCIP_RETCODE	degree_test_hc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)
SCIP_RETCODE	degree_test_pc (SCIP *scip, GRAPH *g, SCIP_Real *fixed, int *count)

Function Documentation

SCIP_RETCODE degree_test	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real *	fixed,
		int *	nelims
	)

basic reduction tests for the STP

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offfset value
nelims	pointer to number of reductions

Definition at line 390 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, EQ, FALSE, FARAWAY, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by nvsl_reduction(), and reduceStp().

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

basic reduction tests for the HCDSTP

Parameters

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

Definition at line 968 of file reduce_simple.c.

References GRAPH::cost, EAT_LAST, FALSE, FARAWAY, flipedge, graph_edge_del(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, STP_HOP_CONS, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by reduceHc().

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

basic reduction tests for the MWCS problem

Parameters

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

Definition at line 811 of file reduce_simple.c.

References GRAPH::cost, deleteterm(), EAT_LAST, Edge_anti, GRAPH::edges, FALSE, GRAPH::grad, graph_edge_del(), graph_knot_contractpc(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, maxprize(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::source, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, traverseChain(), TRUE, and trydg1edgepc().

Referenced by reduceMwcs().

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

basic reductions for RPCSTP and PCSPG

Parameters

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

Definition at line 1048 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, deleteterm(), EAT_LAST, Edge_anti, EQ, FALSE, FARAWAY, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), graph_knot_contract(), graph_knot_contractpc(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, maxprize(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, trydg1edgepc(), and UNKNOWN.

Referenced by nvsl_reduction(), and reducePc().

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

basic reduction tests for the SAP

Parameters

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

Definition at line 566 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, Edge_anti, FALSE, FARAWAY, GRAPH::fixedges, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_contract(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, SCIPintListNodeAppendCopy(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduceSap().

int deleteterm	(	SCIP *	scip,
		GRAPH *	g,
		int	i
	)

delete a terminal for a (rooted) prize-collecting problem

Parameters

scip	SCIP data structure
g	graph data structure
i	index of the terminal

Definition at line 343 of file reduce_simple.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_edge_del(), graph_knot_chg(), GRAPH::head, Is_pterm, Is_term, GRAPH::mark, GRAPH::outbeg, GRAPH::source, GRAPH::term, TRUE, and UNKNOWN.

Referenced by bound_reduce(), degree_test_mw(), degree_test_pc(), and trydg1edgepc().

static SCIP_Bool maxprize ( SCIP *  scip, GRAPH *  g, int  i  )

static

is there no vertex of higher prize?

Parameters

scip	SCIP data structure
g	graph data structure
i	the terminal to be checked

Definition at line 40 of file reduce_simple.c.

References GRAPH::grad, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::prize, GRAPH::source, and GRAPH::term.

Referenced by ansadv2Reduction(), degree_test_mw(), degree_test_pc(), and trydg1edgepc().

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

root proximity terminal test (SAP)

Parameters

scip	SCIP data structure
g	graph data structure
fixed	pointer to offset value
count	pointer to number of reductions

Definition at line 739 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, GRAPH::fixedges, GRAPH::grad, graph_knot_contract(), graph_path_execX(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, SCIPintListNodeAppendCopy(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by reduceSap().

static SCIP_RETCODE traverseChain ( SCIP *  scip, GRAPH *  g, int *  length, int *  final, int  i, int  i1, int  i2, int  e1  )

static

traverse one side of a chain (MWCSP)

Parameters

scip	SCIP data structure
g	graph data structure
length	pointer to store length of chain
final	pointer to store final vertex
i	start vertex
i1	first vertex
i2	last vertex
e1	first edge

Definition at line 248 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, EAT_LAST, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_redirect(), GRAPH::head, Is_term, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::term, and TRUE.

Referenced by degree_test_mw().

static SCIP_RETCODE trydg1edgepc ( SCIP *  scip, GRAPH *  g, SCIP_Real *  offset, int *  count, int  i, int  iout, SCIP_Bool *  rerun  )

static

try to eliminate a terminal of degree one

Parameters

scip	SCIP data structure
g	graph data structure
offset	pointer to store the offset
count	pointer storing number of eliminated edges
i	the terminal to be checked
iout	outgoing arc
rerun	further eliminations possible?

Definition at line 73 of file reduce_simple.c.

References GRAPH::ancestors, GRAPH::cost, deleteterm(), EAT_LAST, flipedge, GRAPH::grad, graph_edge_del(), graph_knot_chg(), graph_knot_contractpc(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_pterm, Is_term, GRAPH::mark, maxprize(), GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, GRAPH::prize, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), GRAPH::source, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by degree_test_mw(), and degree_test_pc().