extreduce_extspg.c File Reference

Detailed Description

extended-reduction specific SPG algorithms for Steiner tree problems

Author

Daniel Rehfeldt

This file implements special distance Steiner tree algorithms for extended reduction techniques for Steiner problems. Allows one to efficiently compute and store special distance (SD) Steiner trees between the leaves of extension tree.

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

Definition in file extreduce_extspg.c.

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "graph.h"
#include "portab.h"
#include "extreduce.h"

Go to the source code of this file.

Macros
#define	STP_EXTSPG_MAXNCHECKS_EQ   8
#define	STP_EXTSPG_MAXNCHECKS   4

Functions
Local methods
static SCIP_Bool	spg4VerticesRuleOut (SCIP *scip, const GRAPH *graph, int node_pathstart, int node_pathend, int node_other, SCIP_Real tree_cost, int *pathnodes, EXTDATA *extdata)
static SCIP_Bool	spg3StarNeighborRuleOut (SCIP *scip, const GRAPH *graph, SCIP_Real starcost, int node, SCIP_Bool allowEquality, const int neighbors[3], DISTDATA *distdata)
Interface methods
SCIP_Bool	extreduce_spg3LeafTreeRuleOut (SCIP *scip, const GRAPH *graph, SCIP_Real tree_cost, EXTDATA *extdata)
SCIP_RETCODE	extreduce_spgCheck3ComponentSimple (SCIP *scip, const GRAPH *graph, int node, const EXTCOMP *extcomp, SCIP_Bool allowEquality, DISTDATA *distdata, SCIP_Bool *isPseudoDeletable)
SCIP_RETCODE	extreduce_spgCheck3NodeSimple (SCIP *scip, const GRAPH *graph, int node, DISTDATA *distdata, SCIP_Bool *isPseudoDeletable)

Macro Definition Documentation

STP_EXTSPG_MAXNCHECKS_EQ

#define STP_EXTSPG_MAXNCHECKS_EQ   8

Definition at line 40 of file extreduce_extspg.c.

Referenced by spg3StarNeighborRuleOut().

STP_EXTSPG_MAXNCHECKS

#define STP_EXTSPG_MAXNCHECKS   4

Definition at line 41 of file extreduce_extspg.c.

Referenced by spg3StarNeighborRuleOut().

Function Documentation

spg4VerticesRuleOut()

static SCIP_Bool spg4VerticesRuleOut ( SCIP *  scip, const GRAPH *  graph, int  node_pathstart, int  node_pathend, int  node_other, SCIP_Real  tree_cost, int *  pathnodes, EXTDATA *  extdata  )

inlinestatic

ruled out possible by using interior point on path between 'pathstart' and 'pathend'?

Parameters

scip	SCIP
graph	graph data structure
node_pathstart	start of path
node_pathend	end of path
node_other	other node
tree_cost	tree cost
pathnodes	buffer
extdata	extension data

Definition at line 53 of file extreduce_extspg.c.

References extension_data::distdata, EQ, extreduce_distDataGetSdDouble(), extreduce_distDataGetSp(), FALSE, GE, graph_pc_isPc(), LT, SCIP_Bool, SCIP_Real, SCIPdebugMessage, extension_data::tree_deg, and TRUE.

Referenced by extreduce_spg3LeafTreeRuleOut().

spg3StarNeighborRuleOut()

static SCIP_Bool spg3StarNeighborRuleOut ( SCIP *  scip, const GRAPH *  graph, SCIP_Real  starcost, int  node, SCIP_Bool  allowEquality, const int  neighbors[3], DISTDATA *  distdata  )

static

Can we (peripherally) rule out simple star of degree 3? Works by using simple Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
starcost	cost of the star
node	the node
allowEquality	allow equality?
neighbors	the neighbors
distdata	data for distance computations

Definition at line 121 of file extreduce_extspg.c.

References GRAPH::cost, EAT_LAST, EQ, extreduce_distDataGetSdDouble(), FALSE, GE, graph_pc_isPc(), GT, GRAPH::head, Is_pseudoTerm, isPseudoDeletable(), LE, LT, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, SCIPdebugMessage, STP_EXTSPG_MAXNCHECKS, STP_EXTSPG_MAXNCHECKS_EQ, GRAPH::term, and TRUE.

Referenced by extreduce_spgCheck3ComponentSimple(), and extreduce_spgCheck3NodeSimple().

extreduce_spg3LeafTreeRuleOut()

SCIP_Bool extreduce_spg3LeafTreeRuleOut	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real	tree_cost,
		EXTDATA *	extdata
	)

can current 3-leaf tree be ruled-out?

Parameters

scip	SCIP
graph	graph data structure
tree_cost	tree cost
extdata	extension data

Definition at line 207 of file extreduce_extspg.c.

References extInitialCompIsEdge(), FALSE, GE, GRAPH::knots, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, spg4VerticesRuleOut(), extension_data::tree_leaves, extension_data::tree_nleaves, and TRUE.

Referenced by mstCompRuleOut().

extreduce_spgCheck3ComponentSimple()

SCIP_RETCODE extreduce_spgCheck3ComponentSimple	(	SCIP *	scip,
		const GRAPH *	graph,
		int	node,
		const EXTCOMP *	extcomp,
		SCIP_Bool	allowEquality,
		DISTDATA *	distdata,
		SCIP_Bool *	isPseudoDeletable
	)

checks component for possible pseudo-elimination by using simple Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
node	the node
extcomp	component to be checked
allowEquality	allow equality?
distdata	data for distance computations
isPseudoDeletable	is component pseudo-deletable?

Definition at line 252 of file extreduce_extspg.c.

References initial_extension_component::compedges, initial_extension_component::comproot, GRAPH::cost, EQ, initial_extension_component::extleaves, FALSE, flipedge, GE, graph_edge_isInRange(), graph_knot_isInRange(), graph_pc_isPc(), GRAPH::head, Is_term, initial_extension_component::ncompedges, initial_extension_component::nextleaves, GRAPH::prize, SCIP_OKAY, SCIP_Real, spg3StarNeighborRuleOut(), GRAPH::tail, and GRAPH::term.

Referenced by extreduce_checkNode().

extreduce_spgCheck3NodeSimple()

SCIP_RETCODE extreduce_spgCheck3NodeSimple	(	SCIP *	scip,
		const GRAPH *	graph,
		int	node,
		DISTDATA *	distdata,
		SCIP_Bool *	isPseudoDeletable
	)

checks node of degree 3 for possible pseudo-elimination by using simple Steiner tree

Parameters

scip	SCIP data structure
graph	graph data structure
node	the node
distdata	data for distance computations
isPseudoDeletable	is node pseudo-deletable?

Definition at line 310 of file extreduce_extspg.c.

References GRAPH::cost, EAT_LAST, EQ, FALSE, flipedge, GRAPH::grad, graph_knot_isInRange(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, spg3StarNeighborRuleOut(), GRAPH::term, and TRUE.