Detailed Description

several decomposition methods for Steiner tree problems

Author: Daniel Rehfeldt

#include "scip/scip.h"
#include "graph.h"
#include "stpvector.h"

Data Structures
struct	biconnected_component_decomposition

struct	cut_nodes

Typedefs
typedef struct biconnected_component_decomposition	BIDECOMP

typedef struct biconnected_stack_node	STACK_NODE

typedef struct cut_nodes	CUTNODES

Functions
SCIP_RETCODE	bidecomposition_cutnodesInit (SCIP , const GRAPH , CUTNODES **)

void	bidecomposition_cutnodesFree (SCIP , CUTNODES *)

void	bidecomposition_cutnodesCompute (const GRAPH , CUTNODES )

SCIP_RETCODE	bidecomposition_init (SCIP , const CUTNODES , const GRAPH , BIDECOMP *)

SCIP_RETCODE	bidecomposition_initSubInOut (SCIP , const GRAPH , BIDECOMP *)

void	bidecomposition_free (SCIP , BIDECOMP *)

void	bidecomposition_markSub (const BIDECOMP , int, GRAPH )

SCIP_Bool	bidecomposition_componentIsTrivial (const BIDECOMP *, int)

SCIP_Bool	bidecomposition_isPossible (const GRAPH *)

SCIP_RETCODE	bidecomposition_getMarkedSubRoot (SCIP , const BIDECOMP , const GRAPH , const GRAPH , int *)

SCIP_Real	bidecomposition_getCompNodeRatio (const BIDECOMP *, int)

SCIP_Real	bidecomposition_getMaxcompNodeRatio (const BIDECOMP *)

Typedef Documentation

◆ BIDECOMP

typedef struct biconnected_component_decomposition BIDECOMP

decompose

◆ STACK_NODE

typedef struct biconnected_stack_node STACK_NODE

for internal computation

Definition at line 53 of file bidecomposition.h.

◆ CUTNODES

typedef struct cut_nodes CUTNODES

cut nodes/ articulation points todo: hide

Function Documentation

◆ bidecomposition_cutnodesInit()

SCIP_RETCODE bidecomposition_cutnodesInit	(	SCIP *	scip,
		const GRAPH *	g,
		CUTNODES **	cutnodes
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
cutnodes	cut nodes

Definition at line 573 of file bidecomposition.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_ncomps, cut_nodes::biconn_nodesmark, cut_nodes::curr_hittime, cut_nodes::curr_lowpoint, cutNodesSetDfsRoot(), cut_nodes::dfsroot, graph_get_nNodes(), nnodes, cut_nodes::nodes_hittime, cut_nodes::nrootcomps, NULL, cut_nodes::scip, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, cut_nodes::stack_nodes, cut_nodes::stack_size, and StpVecReserve.

Referenced by initDecompose(), reduce_articulations(), reduce_bidecomposition(), and reduce_bidecompositionExact().

◆ bidecomposition_cutnodesFree()

void bidecomposition_cutnodesFree	(	SCIP *	scip,
		CUTNODES **	cutnodes
	)

exits

Parameters

scip	SCIP data structure
cutnodes	cut nodes

Definition at line 647 of file bidecomposition.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_nodesmark, cut_nodes::nodes_hittime, SCIPfreeMemory, SCIPfreeMemoryArray, cut_nodes::stack_nodes, and StpVecFree.

Referenced by freeDecompose(), reduce_articulations(), reduce_bidecomposition(), and reduce_bidecompositionExact().

◆ bidecomposition_cutnodesCompute()

void bidecomposition_cutnodesCompute	(	const GRAPH *	g,
		CUTNODES *	cutnodes
	)

computes cut-nodes and (implicitly) bi-connected components

Parameters

g	graph data structure
cutnodes	cut nodes

Definition at line 676 of file bidecomposition.c.

References cut_nodes::biconn_ncomps, cut_nodes::curr_hittime, cut_nodes::curr_lowpoint, cutNodesCompute(), cutNodesComputePostProcess(), cut_nodes::dfsroot, cut_nodes::nrootcomps, SCIPdebugMessage, and StpVecGetSize.

Referenced by initDecompose(), reduce_articulations(), reduce_bidecomposition(), and reduce_bidecompositionExact().

◆ bidecomposition_init()

SCIP_RETCODE bidecomposition_init	(	SCIP *	scip,
		const CUTNODES *	cutnodes,
		const GRAPH *	g,
		BIDECOMP **	bidecomposition
	)

initializes

Parameters

scip	SCIP data structure
cutnodes	cut nodes
g	graph data structure
bidecomposition	bidecomposition data structure

Definition at line 710 of file bidecomposition.c.

References cut_nodes::biconn_ncomps, decomposeBuildCsr(), graph_get_nNodes(), biconnected_component_decomposition::nbicomps, nnodes, biconnected_component_decomposition::nodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, biconnected_component_decomposition::starts, and biconnected_component_decomposition::subinout.

Referenced by decomposeExec(), decomposeExecExact(), and initDecompose().

◆ bidecomposition_initSubInOut()

SCIP_RETCODE bidecomposition_initSubInOut	(	SCIP *	scip,
		const GRAPH *	g,
		BIDECOMP *	bidecomposition
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
bidecomposition	bidecomposition data structure

Definition at line 743 of file bidecomposition.c.

References graph_subinoutInit(), SCIP_CALL, SCIP_OKAY, and biconnected_component_decomposition::subinout.

Referenced by decomposeExec(), decomposePartialExact(), and decomposeReduce().

◆ bidecomposition_free()

void bidecomposition_free	(	SCIP *	scip,
		BIDECOMP **	bidecomposition
	)

frees

Parameters

scip	SCIP data structure
bidecomposition	bidecomposition data structure

Definition at line 759 of file bidecomposition.c.

References graph_subinoutFree(), biconnected_component_decomposition::nodes, SCIPfreeMemory, SCIPfreeMemoryArray, biconnected_component_decomposition::starts, and biconnected_component_decomposition::subinout.

Referenced by decomposeExec(), decomposeExecExact(), and freeDecompose().

◆ bidecomposition_markSub()

void bidecomposition_markSub	(	const BIDECOMP *	bidecomp,
		int	compindex,
		GRAPH *	g
	)

marks subgraph of given component index

Parameters

bidecomp	all-components storage
compindex	component index
g	graph data structure

Definition at line 782 of file bidecomposition.c.

References FALSE, graph_get_nNodes(), graph_knot_getContractionRecordAncestor(), graph_knot_isInRange(), graph_knot_printInfo(), graph_subinoutGetContractionRecord(), GRAPH::mark, nnodes, biconnected_component_decomposition::nodes, SCIPdebugMessage, biconnected_component_decomposition::starts, biconnected_component_decomposition::subinout, and TRUE.

Referenced by decomposeExactSubTry(), decomposeGetSubgraph(), and decomposeReduceSub().

◆ bidecomposition_componentIsTrivial()

SCIP_Bool bidecomposition_componentIsTrivial	(	const BIDECOMP *	bidecomp,
		int	compindex
	)

component consisting of at most one node?

Parameters

bidecomp	all-components storage
compindex	component index

Definition at line 861 of file bidecomposition.c.

References FALSE, SCIPdebugMessage, biconnected_component_decomposition::starts, and TRUE.

Referenced by decomposeExactSubTry(), decomposeReduceSub(), and decomposeSolveSub().

◆ bidecomposition_isPossible()

SCIP_Bool bidecomposition_isPossible ( const GRAPH * g )

checks whether bidecomposition check is possible

Parameters

g	graph data structure

Definition at line 887 of file bidecomposition.c.

References graph_get_nNodes(), graph_isMarked(), GRAPH::mark, nnodes, and TRUE.

Referenced by initDecompose(), reduce_articulations(), reduce_bidecomposition(), and reduce_bidecompositionExact().

◆ bidecomposition_getMarkedSubRoot()

SCIP_RETCODE bidecomposition_getMarkedSubRoot	(	SCIP *	scip,
		const BIDECOMP *	bidecomp,
		const GRAPH *	orggraph,
		const GRAPH *	subgraph,
		int *	subroot
	)

gets root of marked sub-component bidecomposition_markSub needs to be called before!

Parameters

scip	SCIP data structure
bidecomp	all-components storage
orggraph	graph data structure
subgraph	graph data structure
subroot	the new root (out)

Definition at line 830 of file bidecomposition.c.

References decomposeGetFirstMarked(), graph_knot_isInRange(), graph_subinoutGetOrgToSubNodeMap(), Is_term, SCIP_CALL, SCIP_OKAY, biconnected_component_decomposition::subinout, and GRAPH::term.

Referenced by decomposeExactSubTry(), and decomposeGetSubgraph().

◆ bidecomposition_getCompNodeRatio()

SCIP_Real bidecomposition_getCompNodeRatio	(	const BIDECOMP *	bidecomp,
		int	compindex
	)

returns nodes ratio of component and the remaining graph

Parameters

bidecomp	bidecomposition data structure
compindex	component index

Definition at line 912 of file bidecomposition.c.

References GE, biconnected_component_decomposition::nbicomps, SCIP_Real, SCIPdebugMessage, and biconnected_component_decomposition::starts.

Referenced by decomposePartialExact().

◆ bidecomposition_getMaxcompNodeRatio()

SCIP_Real bidecomposition_getMaxcompNodeRatio ( const BIDECOMP * bidecomp )

returns ratio of nodes of maximum component and the remaining graph

Parameters

bidecomp bidecomposition data structure

Definition at line 938 of file bidecomposition.c.

References GT, biconnected_component_decomposition::nbicomps, SCIP_Real, SCIPdebugMessage, and biconnected_component_decomposition::starts.

Referenced by decomposeIsPromising(), and decomposePartialIsPromising().

SCIP

Detailed Description

Data Structures

Typedefs

Functions

Typedef Documentation

◆ BIDECOMP

◆ STACK_NODE

◆ CUTNODES

Function Documentation

◆ bidecomposition_cutnodesInit()

◆ bidecomposition_cutnodesFree()

◆ bidecomposition_cutnodesCompute()

◆ bidecomposition_init()

◆ bidecomposition_initSubInOut()

◆ bidecomposition_free()

◆ bidecomposition_markSub()

◆ bidecomposition_componentIsTrivial()

◆ bidecomposition_isPossible()

◆ bidecomposition_getMarkedSubRoot()

◆ bidecomposition_getCompNodeRatio()

◆ bidecomposition_getMaxcompNodeRatio()