Detailed Description

several decomposition methods for Steiner tree problems

Author: Daniel Rehfeldt

This file implements bi-connected components decomposition methods for several Steiner problems.

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "bidecomposition.h"
#include "stpvector.h"
#include "portab.h"

Go to the source code of this file.

Data Structures
struct	biconnected_stack_node

Functions
static void	cutNodesSetDfsRoot (const GRAPH g, CUTNODES cutnodes)

static void	cutNodesProcessComponent (int root, int stack_start, CUTNODES *cutnodes)

static void	cutNodesProcessNext (const GRAPH g, CUTNODES cutnodes)

static void	cutNodesCompute (const GRAPH g, CUTNODES cutnodes)

static void	cutNodesComputePostProcess (const GRAPH g, CUTNODES cutnodes)

static SCIP_Bool	decomposeCsrIsValid (const CUTNODES cutnodes, const GRAPH g, const BIDECOMP *bidecomp)

static void	decomposeBuildCsr (const CUTNODES cutnodes, const GRAPH g, BIDECOMP *bidecomp)

static SCIP_RETCODE	decomposeGetFirstMarked (SCIP scip, const GRAPH orggraph, int *subroot)

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

void	bidecomposition_cutnodesFree (SCIP scip, CUTNODES *cutnodes)

void	bidecomposition_cutnodesCompute (const GRAPH g, CUTNODES cutnodes)

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

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

void	bidecomposition_free (SCIP scip, BIDECOMP *bidecomposition)

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

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

SCIP_Bool	bidecomposition_componentIsTrivial (const BIDECOMP *bidecomp, int compindex)

SCIP_Bool	bidecomposition_isPossible (const GRAPH *g)

SCIP_Real	bidecomposition_getCompNodeRatio (const BIDECOMP *bidecomp, int compindex)

SCIP_Real	bidecomposition_getMaxcompNodeRatio (const BIDECOMP *bidecomp)

Function Documentation

◆ cutNodesSetDfsRoot()

static void cutNodesSetDfsRoot	(	const GRAPH *	g,
		CUTNODES *	cutnodes
	)

inlinestatic

sets root

Parameters

g	graph data structure
cutnodes	cut nodes

Definition at line 58 of file bidecomposition.c.

References cut_nodes::dfsroot, GRAPH::extended, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), Is_term, nnodes, GRAPH::source, and GRAPH::term.

Referenced by bidecomposition_cutnodesInit().

◆ cutNodesProcessComponent()

static void cutNodesProcessComponent	(	int	root,
		int	stack_start,
		CUTNODES *	cutnodes
	)

static

processes bi-connected component

Parameters

root	root of component
stack_start	start of component in the stack
cutnodes	cut nodes

Definition at line 92 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, EAT_LAST, FALSE, GRAPH::head, Is_term, GRAPH::mark, cut_nodes::nodes_hittime, GRAPH::oeat, GRAPH::outbeg, biconnected_stack_node::parent, cut_nodes::scip, SCIP_Bool, SCIPdebugMessage, STP_Vectype, StpVecGetSize, StpVecPopBack, StpVecPushBack, GRAPH::term, and TRUE.

Referenced by cutNodesProcessNext().

◆ cutNodesProcessNext()

static void cutNodesProcessNext	(	const GRAPH *	g,
		CUTNODES *	cutnodes
	)

static

non-recursive DFS-based biconnected components helper

Parameters

g	graph data structure
cutnodes	cut nodes

Definition at line 218 of file bidecomposition.c.

References biconnected_stack_node::biconnStart, cut_nodes::curr_hittime, cut_nodes::curr_lowpoint, cutNodesProcessComponent(), cut_nodes::dfsroot, EAT_LAST, FALSE, GRAPH::head, biconnected_stack_node::id, biconnected_stack_node::isArtPoint, GRAPH::knots, biconnected_stack_node::lowpoint, GRAPH::mark, biconnected_stack_node::nextEdge, cut_nodes::nodes_hittime, cut_nodes::nrootcomps, GRAPH::oeat, GRAPH::outbeg, biconnected_stack_node::parent, cut_nodes::scip, SCIP_Bool, SCIPdebugMessage, cut_nodes::stack_nodes, cut_nodes::stack_size, StpVecGetcapacity, StpVecGetSize, StpVecPushBack, and TRUE.

Referenced by cutNodesCompute().

◆ cutNodesCompute()

static void cutNodesCompute	(	const GRAPH *	g,
		CUTNODES *	cutnodes
	)

static

non-recursive DFS

Parameters

g	graph data structure
cutnodes	cut nodes

Definition at line 331 of file bidecomposition.c.

References cutNodesProcessNext(), cut_nodes::dfsroot, FALSE, graph_knot_isInRange(), biconnected_stack_node::id, GRAPH::outbeg, SCIPdebugMessage, cut_nodes::stack_nodes, and cut_nodes::stack_size.

Referenced by bidecomposition_cutnodesCompute().

◆ cutNodesComputePostProcess()

static void cutNodesComputePostProcess	(	const GRAPH *	g,
		CUTNODES *	cutnodes
	)

static

post-process

Parameters

g	graph data structure
cutnodes	cut nodes

Definition at line 351 of file bidecomposition.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_ncomps, and StpVecGetSize.

Referenced by bidecomposition_cutnodesCompute().

◆ decomposeCsrIsValid()

static SCIP_Bool decomposeCsrIsValid	(	const CUTNODES *	cutnodes,
		const GRAPH *	g,
		const BIDECOMP *	bidecomp
	)

static

builds CSR like arrays for biconnected components

Parameters

cutnodes	cut nodes
g	graph data structure
bidecomp	bi-decomposition structure

Definition at line 366 of file bidecomposition.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_ncomps, cut_nodes::biconn_nodesmark, FALSE, graph_knot_isInRange(), graph_knot_printInfo(), biconnected_component_decomposition::nodes, SCIP_Bool, SCIPdebugMessage, biconnected_component_decomposition::starts, and TRUE.

Referenced by decomposeBuildCsr().

◆ decomposeBuildCsr()

static void decomposeBuildCsr	(	const CUTNODES *	cutnodes,
		const GRAPH *	g,
		BIDECOMP *	bidecomp
	)

static

builds CSR like arrays for biconnected components

Parameters

cutnodes	cut nodes
g	graph data structure
bidecomp	bidecomposition data structure

Definition at line 428 of file bidecomposition.c.

References cut_nodes::biconn_comproots, cut_nodes::biconn_ncomps, cut_nodes::biconn_nodesmark, decomposeCsrIsValid(), GRAPH::grad, graph_get_nNodes(), GRAPH::mark, nnodes, biconnected_component_decomposition::nodes, and biconnected_component_decomposition::starts.

Referenced by bidecomposition_init().

◆ decomposeGetFirstMarked()

static SCIP_RETCODE decomposeGetFirstMarked	(	SCIP *	scip,
		const GRAPH *	orggraph,
		int *	subroot
	)

static

gets first marked component

Parameters

scip	SCIP data structure
orggraph	graph data structure
subroot	the new root (out)

Definition at line 502 of file bidecomposition.c.

References a, EAT_LAST, FALSE, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_Vectype, StpVecFree, StpVecGetSize, StpVecIsEmpty, StpVecPopBack, StpVecPushBack, and TRUE.

Referenced by bidecomposition_getMarkedSubRoot().

◆ 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_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_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_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

Functions

Function Documentation

◆ cutNodesSetDfsRoot()

◆ cutNodesProcessComponent()

◆ cutNodesProcessNext()

◆ cutNodesCompute()

◆ cutNodesComputePostProcess()

◆ decomposeCsrIsValid()

◆ decomposeBuildCsr()

◆ decomposeGetFirstMarked()

◆ bidecomposition_cutnodesInit()

◆ bidecomposition_cutnodesFree()

◆ bidecomposition_cutnodesCompute()

◆ bidecomposition_init()

◆ bidecomposition_initSubInOut()

◆ bidecomposition_free()

◆ bidecomposition_markSub()

◆ bidecomposition_getMarkedSubRoot()

◆ bidecomposition_componentIsTrivial()

◆ bidecomposition_isPossible()

◆ bidecomposition_getCompNodeRatio()

◆ bidecomposition_getMaxcompNodeRatio()