Scippy

SCIP

Solving Constraint Integer Programs

bidecomposition.h File Reference

Detailed Description

several decomposition methods for Steiner tree problems

Author
Daniel Rehfeldt

Definition in file bidecomposition.h.

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

Go to the source code of this file.

Data Structures

struct  biconnected_component_decomposition
 
struct  cut_nodes
 

Typedefs

typedef struct biconnected_component_decomposition BIDECOMP
 
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

◆ CUTNODES

typedef struct cut_nodes CUTNODES

cut nodes/ articulation points todo: hide

Function Documentation

◆ bidecomposition_cutnodesInit()

◆ bidecomposition_cutnodesFree()

void bidecomposition_cutnodesFree ( SCIP scip,
CUTNODES **  cutnodes 
)

◆ bidecomposition_cutnodesCompute()

void bidecomposition_cutnodesCompute ( const GRAPH g,
CUTNODES cutnodes 
)

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

Parameters
ggraph data structure
cutnodescut nodes

Definition at line 540 of file bidecomposition.c.

References cut_nodes::biconn_ncomps, cut_nodes::curr_hittime, cutNodesComputeDfs(), cutNodesComputePostProcess(), cut_nodes::dfsroot, 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 
)

◆ bidecomposition_initSubInOut()

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

initializes

Parameters
scipSCIP data structure
ggraph data structure
bidecompositionbidecomposition data structure

Definition at line 600 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
scipSCIP data structure
bidecompositionbidecomposition data structure

Definition at line 616 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 
)

◆ bidecomposition_componentIsTrivial()

SCIP_Bool bidecomposition_componentIsTrivial ( const BIDECOMP bidecomp,
int  compindex 
)

component consisting of at most one node?

Parameters
bidecompall-components storage
compindexcomponent index

Definition at line 718 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)

todo remove once bigger graphs can be handled

Parameters
ggraph data structure

Definition at line 744 of file bidecomposition.c.

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

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
scipSCIP data structure
bidecompall-components storage
orggraphgraph data structure
subgraphgraph data structure
subrootthe new root (out)

Definition at line 687 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
bidecompbidecomposition data structure
compindexcomponent index

Definition at line 765 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
bidecompbidecomposition data structure

Definition at line 791 of file bidecomposition.c.

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

Referenced by decomposeIsPromising(), and decomposePartialIsPromising().