reduce_termsepa.c File Reference

Detailed Description

base class for terminal-separator reductions for Steiner tree problems

Author

Daniel Rehfeldt

This file implements base classes for terminal-separator reduction techniques Steiner tree problems. The actual algorithms can be found in reduce_termsepada.c and reduce_termsepafull.c

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

Definition in file reduce_termsepa.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"
#include "extreduce.h"
#include "solstp.h"
#include "mincut.h"
#include "portab.h"
#include "stpvector.h"
#include "scip/scip.h"

Go to the source code of this file.

Data Structures
struct	tree_bottleneck_node
struct	terminal_separator_tree_bottleneck

Macros
#define	MARK_NONACTIVE   0
#define	MARK_SUBNODE   1
#define	MARK_SEPARATOR   2

Typedefs
typedef struct tree_bottleneck_node	TBNODE

Functions
static SCIP_RETCODE	tbottleneckInit (SCIP *scip, const GRAPH *g, const int *soledges, TBOTTLENECK **tbottleneck)
static void	tbottleneckGetMax (int node1, int node2, TBOTTLENECK *tbottleneck, SCIP_Real *maxlength)
static void	tbottleneckFree (SCIP *scip, TBOTTLENECK **tbottleneck)
static void	subgraphIdentify (SCIP *scip, GRAPH *g, TERMCOMP *termcomp)
static SCIP_RETCODE	subgraphBuild (SCIP *scip, const GRAPH *orggraph, SCIP_Bool useSd, EXTPERMA *extperma, TERMCOMP *termcomp)
static SCIP_Real	getExtBottleneckDist (const GRAPH *g, int term1, int term2, int term1_sub, int term2_sub, int mstsource, PATH *mst, TBOTTLENECK *subsolbottleneck, SCIP_Real *RESTRICT mstsdist)
SCIP_RETCODE	reduce_compbuilderInit (SCIP *scip, const GRAPH *g, COMPBUILDER **compbuilder)
void	reduce_compbuilderFree (SCIP *scip, COMPBUILDER **compbuilder)
SCIP_Real	reduce_compbuilderGetSubNodesRatio (const COMPBUILDER *compbuilder)
void	reduce_compbuilderPrintSeparators (const GRAPH *orggraph, const COMPBUILDER *compbuilder)
SCIP_RETCODE	reduce_termcompBuildSubgraphWithSds (SCIP *scip, GRAPH *orggraph, EXTPERMA *extperma, TERMCOMP *termcomp)
SCIP_RETCODE	reduce_termcompBuildSubgraph (SCIP *scip, GRAPH *orggraph, TERMCOMP *termcomp)
SCIP_RETCODE	reduce_termcompChangeSubgraphToBottleneck (SCIP *scip, GRAPH *g, TERMCOMP *termcomp, SCIP_Bool *success)
void	reduce_termcompChangeSubgraphToOrgCosts (const GRAPH *orggraph, TERMCOMP *termcomp)
SCIP_RETCODE	reduce_termcompInit (SCIP *scip, const GRAPH *g, COMPBUILDER *builder, TERMCOMP **termcomp)
SCIP_RETCODE	reduce_termcompInitTbottleneck (SCIP *scip, const int *subsoledges, TERMCOMP *termcomp)
void	reduce_termcompFree (SCIP *scip, TERMCOMP **termcomp)
void	reduce_termsepaGetNextComp (SCIP *scip, const GRAPH *g, TERMSEPAS *termsepas, COMPBUILDER *builder, SCIP_Bool *compWasFound)

Macro Definition Documentation

MARK_NONACTIVE

#define MARK_NONACTIVE   0

Definition at line 45 of file reduce_termsepa.c.

Referenced by reduce_termcompChangeSubgraphToBottleneck().

MARK_SUBNODE

#define MARK_SUBNODE   1

Definition at line 46 of file reduce_termsepa.c.

Referenced by reduce_termcompChangeSubgraphToBottleneck(), subgraphBuild(), and subgraphIdentify().

MARK_SEPARATOR

#define MARK_SEPARATOR   2

Definition at line 47 of file reduce_termsepa.c.

Referenced by reduce_termcompChangeSubgraphToBottleneck(), subgraphBuild(), and subgraphIdentify().

Typedef Documentation

TBNODE

typedef struct tree_bottleneck_node TBNODE

tree bottleneck node

Function Documentation

tbottleneckInit()

static SCIP_RETCODE tbottleneckInit ( SCIP *  scip, const GRAPH *  g, const int *  soledges, TBOTTLENECK **  tbottleneck  )

static

initializes

Parameters

scip	SCIP data structure
g	graph data structure
soledges	solution tree to be represented
tbottleneck	to initialize

Definition at line 82 of file reduce_termsepa.c.

References tree_bottleneck_node::bottleneck, CONNECT, GRAPH::cost, tree_bottleneck_node::degree, tree_bottleneck_node::edgecost, EQ, FARAWAY, GE, graph_edge_printInfo(), graph_get_nEdges(), graph_get_nNodes(), graph_printInfo(), GRAPH::head, Is_term, nnodes, terminal_separator_tree_bottleneck::nnodes, tree_bottleneck_node::parent, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, SCIPdebugMessage, solstp_isValid(), GRAPH::source, GRAPH::tail, GRAPH::term, terminal_separator_tree_bottleneck::tree, and UNKNOWN.

Referenced by reduce_termcompInitTbottleneck().

tbottleneckGetMax()

static void tbottleneckGetMax ( int  node1, int  node2, TBOTTLENECK *  tbottleneck, SCIP_Real *  maxlength  )

static

gets tree bottleneck cost

Parameters

node1	first node
node2	second node
tbottleneck	tree bottleneck structure
maxlength	IN/OUT! user needs to provide a maximum that is to be surpassed

Definition at line 219 of file reduce_termsepa.c.

References tree_bottleneck_node::bottleneck, tree_bottleneck_node::degree, tree_bottleneck_node::edgecost, EQ, GE, GT, MAX, nnodes, tree_bottleneck_node::parent, SCIP_Real, SCIPdebugMessage, terminal_separator_tree_bottleneck::tree, and UNKNOWN.

Referenced by getExtBottleneckDist().

tbottleneckFree()

static void tbottleneckFree ( SCIP *  scip, TBOTTLENECK **  tbottleneck  )

static

frees

Parameters

scip	SCIP data structure
tbottleneck	to initialize

Definition at line 310 of file reduce_termsepa.c.

References SCIPfreeMemory, SCIPfreeMemoryArray, and terminal_separator_tree_bottleneck::tree.

Referenced by reduce_termcompFree().

subgraphIdentify()

static void subgraphIdentify ( SCIP *  scip, GRAPH *  g, TERMCOMP *  termcomp  )

static

identifies subgraph

Parameters

scip	SCIP data structure
g	graph data structure
termcomp	component

Definition at line 325 of file reduce_termsepa.c.

References BMSclearMemoryArray, terminal_separator_component::builder, EAT_LAST, GRAPH::grad, graph_knot_isInRange(), GRAPH::head, Is_term, GRAPH::knots, MARK_SEPARATOR, MARK_SUBNODE, terminal_separator_component::nodemap_orgToSub, terminal_separator_component::nodes_mark, terminial_component_initializer::nsepatterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPdebugMessage, terminial_component_initializer::sepaterms, terminial_component_initializer::sourceterm, STP_Vectype, StpVecGetSize, StpVecPushBack, StpVecReserve, terminal_separator_component::subnedges, terminal_separator_component::subnnodes, GRAPH::term, and UNKNOWN.

Referenced by reduce_termcompBuildSubgraph(), and reduce_termcompBuildSubgraphWithSds().

subgraphBuild()

static SCIP_RETCODE subgraphBuild ( SCIP *  scip, const GRAPH *  orggraph, SCIP_Bool  useSd, EXTPERMA *  extperma, TERMCOMP *  termcomp  )

static

creates subgraph

Parameters

scip	SCIP data structure
orggraph	graph data structure
useSd	use special distances
extperma	extension data or NULL
termcomp	component

Definition at line 409 of file reduce_termsepa.c.

References BLOCKED, terminal_separator_component::builder, GRAPH::cost, extension_data_permanent::distdata_default, EAT_LAST, terminal_separator_component::edgemap_subToOrg, GRAPH::edges, EQ, extreduce_distDataGetSdDouble(), flipedge, GE, graph_edge_addBi(), graph_edge_printInfo(), graph_init(), graph_knot_add(), graph_knot_isInRange(), graph_path_init(), GRAPH::head, Is_term, GRAPH::knots, MARK_SEPARATOR, MARK_SUBNODE, terminal_separator_component::nodemap_orgToSub, terminal_separator_component::nodemap_subToOrg, terminal_separator_component::nodes_mark, terminial_component_initializer::nsepatterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, terminial_component_initializer::sepaterms, GRAPH::source, terminial_component_initializer::sourceterm, STP_TERM, GRAPH::stp_type, STP_Vectype, StpVecGetSize, terminal_separator_component::subgraph, terminal_separator_component::subnedges, terminal_separator_component::subnnodes, GRAPH::term, and UNKNOWN.

Referenced by reduce_termcompBuildSubgraph(), and reduce_termcompBuildSubgraphWithSds().

getExtBottleneckDist()

static SCIP_Real getExtBottleneckDist ( const GRAPH *  g, int  term1, int  term2, int  term1_sub, int  term2_sub, int  mstsource, PATH *  mst, TBOTTLENECK *  subsolbottleneck, SCIP_Real *RESTRICT  mstsdist  )

static

gets extended bottleneck distances

Parameters

g	graph data structure
term1	first terminal
term2	second terminal
term1_sub	corresponding terminal in subgraph
term2_sub	corresponding terminal in subgraph
mstsource	source node of minimum spanning tree
mst	minimum spanning tree
subsolbottleneck	tree bottleneck
mstsdist	node distance helper

Definition at line 613 of file reduce_termsepa.c.

References GRAPH::cost, shortest_path::edge, EQ, GRAPH::head, Is_term, GRAPH::knots, SCIP_Real, GRAPH::tail, tbottleneckGetMax(), and GRAPH::term.

Referenced by reduce_termcompChangeSubgraphToBottleneck().

reduce_compbuilderInit()

SCIP_RETCODE reduce_compbuilderInit	(	SCIP *	scip,
		const GRAPH *	g,
		COMPBUILDER **	compbuilder
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
compbuilder	to initialize

Definition at line 716 of file reduce_termsepa.c.

References terminial_component_initializer::componentnumber, FALSE, graph_get_nNodes(), graph_get_nVET(), terminial_component_initializer::maxncompchecks, terminial_component_initializer::maxsepasize, terminial_component_initializer::ncomponentnodes, terminial_component_initializer::ngraphnodes, nnodes, terminial_component_initializer::nodes_bdist, terminial_component_initializer::nsepatterms, NULL, terminial_component_initializer::rootcompIsProcessed, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, terminial_component_initializer::sepaterms, and terminial_component_initializer::sourceterm.

Referenced by initHelpers().

reduce_compbuilderFree()

void reduce_compbuilderFree	(	SCIP *	scip,
		COMPBUILDER **	compbuilder
	)

frees

Parameters

scip	SCIP data structure
compbuilder	to free

Definition at line 751 of file reduce_termsepa.c.

References terminial_component_initializer::nodes_bdist, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by freeHelpers().

reduce_compbuilderGetSubNodesRatio()

SCIP_Real reduce_compbuilderGetSubNodesRatio

(

const COMPBUILDER *

compbuilder

)

gets nodes ratio of subgraph

Parameters

compbuilder

builder

Definition at line 765 of file reduce_termsepa.c.

References GT, LE, terminial_component_initializer::ncomponentnodes, terminial_component_initializer::ngraphnodes, and SCIP_Real.

Referenced by sepafullSolcandsArePromising(), termcompComputeSubgraphSol(), termcompIsPromising(), and termcompReduce().

reduce_compbuilderPrintSeparators()

void reduce_compbuilderPrintSeparators	(	const GRAPH *	orggraph,
		const COMPBUILDER *	compbuilder
	)

prints

Parameters

orggraph	graph data structure
compbuilder	builder

Definition at line 779 of file reduce_termsepa.c.

References graph_knot_isInRange(), graph_knot_printInfo(), terminial_component_initializer::nsepatterms, and terminial_component_initializer::sepaterms.

Referenced by processComponent().

reduce_termcompBuildSubgraphWithSds()

SCIP_RETCODE reduce_termcompBuildSubgraphWithSds	(	SCIP *	scip,
		GRAPH *	orggraph,
		EXTPERMA *	extperma,
		TERMCOMP *	termcomp
	)

builds extended subgraph with SD weighted edges between terminal-separator nodes

Parameters

scip	SCIP data structure
orggraph	graph data structure
extperma	extension data
termcomp	component

Definition at line 799 of file reduce_termsepa.c.

References SCIP_Bool, SCIP_CALL, SCIP_OKAY, subgraphBuild(), subgraphIdentify(), and TRUE.

Referenced by processComponent().

reduce_termcompBuildSubgraph()

SCIP_RETCODE reduce_termcompBuildSubgraph	(	SCIP *	scip,
		GRAPH *	orggraph,
		TERMCOMP *	termcomp
	)

builds extended subgraph with BLOCKED weighted edges between terminal-separator nodes

Parameters

scip	SCIP data structure
orggraph	graph data structure
termcomp	component

Definition at line 818 of file reduce_termsepa.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, subgraphBuild(), and subgraphIdentify().

Referenced by processComponent().

reduce_termcompChangeSubgraphToBottleneck()

SCIP_RETCODE reduce_termcompChangeSubgraphToBottleneck	(	SCIP *	scip,
		GRAPH *	g,
		TERMCOMP *	termcomp,
		SCIP_Bool *	success
	)

Changes weights between terminal separator nodes to bottlenecks. NOTE: also computes the bottleneck distances, so potentially expensive!

Parameters

scip	SCIP data structure
g	graph data structure
termcomp	component
success	pointer to store whether computation was successful (OUT)

Definition at line 837 of file reduce_termsepa.c.

References b, terminal_separator_component::builder, GRAPH::cost, EAT_LAST, FALSE, flipedge, getExtBottleneckDist(), graph_get_nNodes(), graph_knot_isInRange(), graph_mark(), graph_path_exec(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, MARK_NONACTIVE, MARK_SEPARATOR, MARK_SUBNODE, MST_MODE, nnodes, terminal_separator_component::nodemap_orgToSub, terminal_separator_component::nodemap_subToOrg, terminial_component_initializer::nodes_bdist, terminal_separator_component::nodes_mark, terminial_component_initializer::nsepatterms, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, terminial_component_initializer::sepaterms, terminal_separator_component::subgraph, terminal_separator_component::subsolbottleneck, GRAPH::term, and TRUE.

Referenced by processComponent(), and sepafullBuildSolcands().

reduce_termcompChangeSubgraphToOrgCosts()

void reduce_termcompChangeSubgraphToOrgCosts	(	const GRAPH *	orggraph,
		TERMCOMP *	termcomp
	)

changes weights between terminal separator nodes to original costs (or BLOCKED)

Parameters

orggraph	graph data structure
termcomp	component

Definition at line 930 of file reduce_termsepa.c.

References BLOCKED, terminal_separator_component::builder, GRAPH::cost, EAT_LAST, terminal_separator_component::edgemap_subToOrg, GRAPH::edges, EQ, GRAPH::head, Is_term, terminial_component_initializer::nsepatterms, GRAPH::oeat, GRAPH::outbeg, terminal_separator_component::subgraph, GRAPH::tail, and GRAPH::term.

Referenced by sepafullBuildSolcands().

reduce_termcompInit()

SCIP_RETCODE reduce_termcompInit	(	SCIP *	scip,
		const GRAPH *	g,
		COMPBUILDER *	builder,
		TERMCOMP **	termcomp
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
builder	initializer
termcomp	to initialize

Definition at line 982 of file reduce_termsepa.c.

References terminal_separator_component::builder, terminal_separator_component::edgemap_subToOrg, FARAWAY, GRAPH::knots, terminal_separator_component::nodemap_orgToSub, terminal_separator_component::nodemap_subToOrg, terminal_separator_component::nodes_mark, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, terminal_separator_component::subgraph, terminal_separator_component::subnedges, terminal_separator_component::subnnodes, terminal_separator_component::subprimalobj, terminal_separator_component::subsolbottleneck, terminal_separator_component::subsolution, and UNKNOWN.

Referenced by processComponent().

reduce_termcompInitTbottleneck()

SCIP_RETCODE reduce_termcompInitTbottleneck	(	SCIP *	scip,
		const int *	subsoledges,
		TERMCOMP *	termcomp
	)

initializes tree bottleneck for terminal component

Parameters

scip	SCIP data structure
subsoledges	solution tree to be represented
termcomp	to initialize for

Definition at line 1019 of file reduce_termsepa.c.

References SCIP_CALL, SCIP_OKAY, terminal_separator_component::subgraph, terminal_separator_component::subsolbottleneck, and tbottleneckInit().

Referenced by termcompComputeSubgraphSol().

reduce_termcompFree()

void reduce_termcompFree	(	SCIP *	scip,
		TERMCOMP **	termcomp
	)

frees

Parameters

scip	SCIP data structure
termcomp	to initialize

Definition at line 1039 of file reduce_termsepa.c.

References terminal_separator_component::edgemap_subToOrg, graph_free(), terminal_separator_component::nodemap_orgToSub, terminal_separator_component::nodemap_subToOrg, terminal_separator_component::nodes_mark, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, StpVecFree, terminal_separator_component::subgraph, terminal_separator_component::subsolbottleneck, terminal_separator_component::subsolution, tbottleneckFree(), and TRUE.

Referenced by processComponent().

reduce_termsepaGetNextComp()

void reduce_termsepaGetNextComp	(	SCIP *	scip,
		const GRAPH *	g,
		TERMSEPAS *	termsepas,
		COMPBUILDER *	builder,
		SCIP_Bool *	compWasFound
	)

gets next separator component

Parameters

scip	SCIP data structure
g	graph data structure
termsepas	terminal separator store
builder	builder
compWasFound	was new component found?

Definition at line 1072 of file reduce_termsepa.c.

References terminial_component_initializer::componentnumber, FALSE, graph_knot_isInRange(), terminial_component_initializer::maxncompchecks, terminial_component_initializer::maxsepasize, mincut_termsepasGetNext(), mincut_termsepasGetSource(), terminial_component_initializer::ncomponentnodes, terminial_component_initializer::ngraphnodes, terminial_component_initializer::nsepatterms, NULL, terminial_component_initializer::rootcompIsProcessed, SCIPdebugMessage, terminial_component_initializer::sepaterms, terminial_component_initializer::sourceterm, and TRUE.

Referenced by reduce_termsepaDaWithExperma(), and reduce_termsepaFull().