extreduce_core.c File Reference

Detailed Description

extended reduction techniques for Steiner tree problems

Author

Daniel Rehfeldt

This file implements the core algorithms for the extended reduction techniques, namely for the tree search. Starting from a given component (e.g. a single edge), a number of possible extensions are checked to be able to verify that this component is not part of at least one optimal solution.

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

Definition in file extreduce_core.c.

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

Go to the source code of this file.

Macros
#define	EXT_COSTS_RECOMPBOUND   10

Functions
static SCIP_Bool	ksubsetGetNext (int k, int n, SCIP_Bool isFirstSubset, int *ksubset)
static SCIP_Bool	extensionHasImplicationConflict (const GRAPH *graph, const STP_Vectype(int) implications, const int *tree_deg, int tree_root, const int *extedges, int nextedges)
static int	extStackGetPrevMarked (const EXTDATA *extdata)
static SCIP_Bool	extStackIsExtendable (int nextedges, int nnewcomps, int stack_datasize, const EXTDATA *extdata)
static void	extStackAddCompsNonExpanded (const GRAPH *graph, const int *extedgesstart, const int *extedges, int nextendable_leaves, EXTDATA *extdata)
static void	extLeafAdd (int leaf, EXTDATA *extdata)
static void	extLeafRemove (int leaf, EXTDATA *extdata)
static void	extLeafRemoveTop (const GRAPH *graph, int topsize, int toproot, EXTDATA *extdata)
static void	extInnerNodeAdd (const GRAPH *graph, int innernode, EXTDATA *extdata)
static void	extInnerNodeRemoveTop (const GRAPH *graph, int innernode, EXTDATA *extdata)
static void	extTreeAddEdge (const GRAPH *graph, int edge, EXTDATA *extdata)
static void	extTreeStackTopRootRemove (const GRAPH *graph, EXTDATA *extdata)
static void	extTreeStackTopAdd (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *conflict)
static void	extTreeStackTopRemove (const GRAPH *graph, SCIP_Bool ancestor_conflict, EXTDATA *extdata)
static SCIP_Bool	extTreeRuleOutEdgeSimple (const GRAPH *graph, EXTDATA *extdata, int edge)
static SCIP_Bool	extTreeRuleOutSingletonFull (SCIP *scip, const GRAPH *graph, EXTDATA *extdata)
static SCIP_Bool	extTreeRuleOutSingletonImplied (SCIP *scip, const GRAPH *graph, EXTDATA *extdata)
static SCIP_Bool	extTreeRuleOutPeriph (SCIP *scip, const GRAPH *graph, EXTDATA *extdata)
static void	extTreeFindExtensions (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, int *extedgesstart, int *extedges, int *nextensions, int *nextendableleaves, SCIP_Bool *with_ruledout_leaf)
static void	extTreeSyncWithStack (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *conflict)
static SCIP_Bool	extTruncate (const GRAPH *graph, const EXTDATA *extdata)
static void	extBacktrack (SCIP *scip, const GRAPH *graph, SCIP_Bool success, SCIP_Bool ancestor_conflict, EXTDATA *extdata)
static void	extStackAddCompsExpanded (SCIP *scip, const GRAPH *graph, int nextedges, const int *extedges, EXTDATA *extdata, SCIP_Bool *success, SCIP_Bool *ruledOut)
static void	extStackAddCompsExpandedSing (SCIP *scip, const GRAPH *graph, int nextedges, const int *extedges, EXTDATA *extdata, SCIP_Bool *success, SCIP_Bool *ruledOut)
static void	extStackAddCompInitialExpanded (SCIP *scip, const GRAPH *graph, EXTDATA *extdata)
static void	extStackTopCollectExtEdges (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, int *extedges, int *nextedges)
static void	extStackTopCollectExtEdgesSing (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, int *extedges, int *nextedges)
static int	extStackTopGetInitalDataStart (const EXTDATA *extdata)
static void	extStackTopProcessInitialEdges (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *initialRuleOut)
static void	extStackTopExpandSingletons (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *success)
static void	extStackTopExpandWrapped (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *success)
static void	extStackTopExpand (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *success)
static void	extStackTopExpandInitial (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *initialRuleOut)
static void	extExtend (SCIP *scip, const GRAPH *graph, EXTDATA *extdata, SCIP_Bool *success)
static void	extPreprocessInitialEdge (SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, EXTDATA *extdata)
static void	extPreprocessInitialStar (SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, EXTDATA *extdata)
static void	extPreprocessInitialGenStar (SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, EXTDATA *extdata)
static void	extPreprocessInitialComponent (SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, EXTDATA *extdata)
static void	extUnhashInitialComponent (const GRAPH *graph, const EXTCOMP *extcomp, EXTDATA *extdata)
static void	extProcessInitialComponent (SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, EXTDATA *extdata, SCIP_Bool *ruledOut, SCIP_Bool *isExtendable)
static void	extProcessComponent (SCIP *scip, const GRAPH *graph, const EXTCOMP *extcomp, EXTDATA *extdata, SCIP_Bool *deletable)
SCIP_RETCODE	extreduce_checkComponent (SCIP *scip, const GRAPH *graph, const REDCOST *redcostdata, EXTCOMP *extcomp, EXTPERMA *extpermanent, SCIP_Bool *compIsDeletable)

Macro Definition Documentation

EXT_COSTS_RECOMPBOUND

#define EXT_COSTS_RECOMPBOUND   10

Definition at line 41 of file extreduce_core.c.

Referenced by extTreeSyncWithStack().

Function Documentation

ksubsetGetNext()

static SCIP_Bool ksubsetGetNext ( int  k, int  n, SCIP_Bool  isFirstSubset, int *  ksubset  )

inlinestatic

gets next subset of given size, returns FALSE if no further subset possible, otherwise TRUE

Parameters

k	size of subset
n	size of underlying set
isFirstSubset	first call?
ksubset	the k-subset IN/OUT

Definition at line 50 of file extreduce_core.c.

References FALSE, and TRUE.

Referenced by extStackAddCompsExpanded().

extensionHasImplicationConflict()

static SCIP_Bool extensionHasImplicationConflict ( const GRAPH *  graph, const STP_Vectype(int)  implications, const int *  tree_deg, int  tree_root, const int *  extedges, int  nextedges  )

inlinestatic

are the given extension vertices in conflict with the extension conditions?

Parameters

graph	graph data structure
implications	implications for extroot
tree_deg	tree degree or NULL
tree_root	tree root
extedges	extension edges
nextedges	number of extension edges

Definition at line 88 of file extreduce_core.c.

References FALSE, graph_knot_isInRange(), GRAPH::head, Is_term, StpVecGetSize, GRAPH::term, and TRUE.

Referenced by extStackAddCompsExpanded(), extStackTopProcessInitialEdges(), and extTreeRuleOutSingletonImplied().

extStackGetPrevMarked()

static int extStackGetPrevMarked ( const EXTDATA *  extdata )

inlinestatic

returns position of last marked component before the current one

Parameters

extdata

extension data

Definition at line 136 of file extreduce_core.c.

References EXT_STATE_MARKED, extension_data::extstack_state, and extStackGetPosition().

Referenced by extLeafRemoveTop().

extStackIsExtendable()

static SCIP_Bool extStackIsExtendable ( int  nextedges, int  nnewcomps, int  stack_datasize, const EXTDATA *  extdata  )

inlinestatic

can the extension stack hold new components?

Parameters

nextedges	number of edges for extension
nnewcomps	number of new components
stack_datasize	datasize of stack
extdata	extension data

Definition at line 157 of file extreduce_core.c.

References EXT_STATE_NONE, extension_data::extstack_maxncomponents, extension_data::extstack_maxsize, extension_data::extstack_ncomponents, extension_data::extstack_state, extStackGetPosition(), FALSE, SCIPdebugMessage, and TRUE.

Referenced by extStackAddCompsExpanded(), and extStackAddCompsExpandedSing().

extStackAddCompsNonExpanded()

static void extStackAddCompsNonExpanded ( const GRAPH *  graph, const int *  extedgesstart, const int *  extedges, int  nextendable_leaves, EXTDATA *  extdata  )

inlinestatic

Adds non-expanded components (i.e. sets of edges extending at a certain leaf) to the stack. Components are ordered such that smallest component is added last.

Parameters

graph	graph data structure
extedgesstart	starts of extension edges for one components
extedges	extensions edges
nextendable_leaves	number of leaves that can be extended
extdata	extension data

Definition at line 183 of file extreduce_core.c.

References EXT_STATE_NONE, extension_data::extstack_data, extension_data::extstack_maxncomponents, extension_data::extstack_maxsize, extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), graph_edge_printInfo(), SCIPsortDownIntInt(), and STP_EXT_MAXGRAD.

Referenced by extExtend().

extLeafAdd()

static void extLeafAdd ( int  leaf, EXTDATA *  extdata  )

inlinestatic

adds a new leaf

Parameters

leaf	leaf to add
extdata	extension data

Definition at line 259 of file extreduce_core.c.

References extension_data::tree_deg, extension_data::tree_leaves, and extension_data::tree_nleaves.

Referenced by extPreprocessInitialComponent(), extTreeAddEdge(), and extTreeRuleOutSingletonFull().

extLeafRemove()

static void extLeafRemove ( int  leaf, EXTDATA *  extdata  )

inlinestatic

remove entry from leaves list

Parameters

leaf	leaf to remove
extdata	extension data

Definition at line 273 of file extreduce_core.c.

References extLeafFindPos(), extension_data::tree_deg, extension_data::tree_leaves, and extension_data::tree_nleaves.

Referenced by extTreeRuleOutSingletonFull(), and extTreeStackTopRootRemove().

extLeafRemoveTop()

static void extLeafRemoveTop ( const GRAPH *  graph, int  topsize, int  toproot, EXTDATA *  extdata  )

inlinestatic

Remove top component from leaves, and restore the root of the component as a leaf NOTE: assumes that the tree_deg has already been adapted

Parameters

graph	graph data structure
topsize	size of top to remove
toproot	root of the top component
extdata	extension data

Definition at line 304 of file extreduce_core.c.

References extLeafFindPos(), extension_data::extstack_data, extStackGetOutEdgesEnd(), extStackGetOutEdgesStart(), extStackGetPrevMarked(), GRAPH::head, extension_data::tree_deg, extension_data::tree_leaves, and extension_data::tree_nleaves.

Referenced by extTreeRuleOutSingletonFull(), and extTreeStackTopRemove().

extInnerNodeAdd()

static void extInnerNodeAdd ( const GRAPH *  graph, int  innernode, EXTDATA *  extdata  )

inlinestatic

adds a new inner node

Parameters

graph	graph data structure
innernode	node to add
extdata	extension data

Definition at line 369 of file extreduce_core.c.

References graph_pc_isPc(), NULL, extension_data::pcdata, GRAPH::prize, SCIP_Bool, extension_data::tree_deg, extension_data::tree_innerNodes, pcmw_specific_data::tree_innerPrize, and extension_data::tree_ninnerNodes.

Referenced by extPreprocessInitialGenStar(), extPreprocessInitialStar(), extTreeRuleOutSingletonFull(), and extTreeStackTopRootRemove().

extInnerNodeRemoveTop()

static void extInnerNodeRemoveTop ( const GRAPH *  graph, int  innernode, EXTDATA *  extdata  )

inlinestatic

removes a new inner node

Parameters

graph	graph data structure
innernode	(top) node to remove
extdata	extension data

Definition at line 393 of file extreduce_core.c.

References extInitialCompIsEdge(), extInitialCompIsGenStar(), extInitialCompIsStar(), GE, graph_pc_isPc(), NULL, extension_data::pcdata, GRAPH::prize, SCIP_Bool, extension_data::tree_innerNodes, pcmw_specific_data::tree_innerPrize, extension_data::tree_ninnerNodes, and extension_data::tree_root.

Referenced by extTreeRuleOutSingletonFull(), and extTreeStackTopRemove().

extTreeAddEdge()

static void extTreeAddEdge ( const GRAPH *  graph, int  edge, EXTDATA *  extdata  )

inlinestatic

adds edge to tree

Parameters

graph	graph data structure
edge	edge to be added
extdata	extension data

Definition at line 431 of file extreduce_core.c.

References GRAPH::cost, extInitialCompIsGenStar(), extInitialCompIsStar(), extIsAtInitialComp(), extLeafAdd(), extension_data::genstar_centeredge, GRAPH::head, SCIP_Real, GRAPH::tail, extension_data::tree_cost, extension_data::tree_deg, extension_data::tree_edges, extension_data::tree_nedges, extension_data::tree_parentEdgeCost, extension_data::tree_parentNode, extension_data::tree_root, and extension_data::tree_starcenter.

Referenced by extTreeStackTopAdd().

extTreeStackTopRootRemove()

static void extTreeStackTopRootRemove ( const GRAPH *  graph, EXTDATA *  extdata  )

inlinestatic

removes root of stack top component from tree

Parameters

graph	graph data structure
extdata	extension data

Definition at line 472 of file extreduce_core.c.

References extInitialCompIsGenStar(), extInitialCompIsStar(), extInnerNodeAdd(), extIsAtInitialComp(), extLeafRemove(), extStackGetTopRoot(), extension_data::genstar_centeredge, graph_edge_isInRange(), graph_knot_isInRange(), GRAPH::head, GRAPH::tail, extension_data::tree_deg, extension_data::tree_nleaves, extension_data::tree_root, and extension_data::tree_starcenter.

Referenced by extTreeStackTopAdd().

extTreeStackTopAdd()

static void extTreeStackTopAdd ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  conflict  )

static

adds top component of stack to tree

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data
conflict	conflict found?

Definition at line 521 of file extreduce_core.c.

References EXT_STATE_EXPANDED, extreduce_redcostAddEdge(), extreduce_redcostInitExpansion(), extreduce_treeIsFlawed(), extension_data::extstack_data, extension_data::extstack_maxsize, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), extTreeAddEdge(), extTreeStackTopRootRemove(), FALSE, graph_pseudoAncestors_hashEdgeDirty(), graph_pseudoAncestors_unhashEdge(), reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, extension_data::reddata, SCIPdebugMessage, extension_data::tree_depth, extension_data::tree_nedges, and TRUE.

Referenced by extProcessInitialComponent(), and extTreeSyncWithStack().

extTreeStackTopRemove()

static void extTreeStackTopRemove ( const GRAPH *  graph, SCIP_Bool  ancestor_conflict, EXTDATA *  extdata  )

inlinestatic

removes top component of stack from tree

Parameters

graph	graph data structure
ancestor_conflict	with ancestor conflict?
extdata	extension data

Definition at line 590 of file extreduce_core.c.

References GRAPH::cost, EXT_STATE_NONE, extInnerNodeRemoveTop(), extLeafRemoveTop(), extreduce_mstCompRemove(), extreduce_redcostRemoveEdge(), extension_data::extstack_data, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), extStackGetTopRoot(), graph_pseudoAncestors_unhashEdge(), GRAPH::head, reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, extension_data::reddata, GRAPH::tail, extension_data::tree_cost, extension_data::tree_deg, extension_data::tree_depth, and extension_data::tree_nedges.

Referenced by extBacktrack().

extTreeRuleOutEdgeSimple()

static SCIP_Bool extTreeRuleOutEdgeSimple ( const GRAPH *  graph, EXTDATA *  extdata, int  edge  )

inlinestatic

can any extension via edge be ruled out by using simple test??

Parameters

graph	graph data structure
extdata	extension data
edge	edge to be tested

Definition at line 647 of file extreduce_core.c.

References FALSE, graph_edge_printInfo(), graph_pseudoAncestors_edgeIsHashed(), GRAPH::head, reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, extension_data::reddata, SCIP_Bool, SCIPdebugMessage, extension_data::tree_deg, and TRUE.

Referenced by extStackTopCollectExtEdgesSing(), extStackTopProcessInitialEdges(), and extTreeFindExtensions().

extTreeRuleOutSingletonFull()

static SCIP_Bool extTreeRuleOutSingletonFull ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata  )

inlinestatic

Can current singleton extension be ruled out? NOTE: Also stores vertical SDs for this singleton if not ruled out!

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 699 of file extreduce_core.c.

References extInnerNodeAdd(), extInnerNodeRemoveTop(), extLeafAdd(), extLeafRemove(), extLeafRemoveTop(), extreduce_mstLevelVerticalAddLeaf(), extreduce_mstLevelVerticalClose(), extreduce_mstLevelVerticalReopen(), extension_data::extstack_data, extension_data::extstack_start, extStackGetPosition(), FALSE, GRAPH::head, extension_data::reddata, SCIP_Bool, SCIPdebugMessage, GRAPH::tail, and extension_data::tree_deg.

Referenced by extTreeRuleOutPeriph().

extTreeRuleOutSingletonImplied()

static SCIP_Bool extTreeRuleOutSingletonImplied ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata  )

inlinestatic

Can current singleton extension be ruled out by implication argument?

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 739 of file extreduce_core.c.

References extensionHasImplicationConflict(), extension_data::extstack_data, extension_data::extstack_start, extStackGetPosition(), FALSE, graph_pc_isPc(), NULL, extension_data::reddata, SCIPdebugMessage, STP_Vectype, GRAPH::tail, extension_data::tree_deg, extension_data::tree_root, and TRUE.

Referenced by extTreeRuleOutPeriph().

extTreeRuleOutPeriph()

static SCIP_Bool extTreeRuleOutPeriph ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata  )

inlinestatic

Can current tree be peripherally ruled out? NOTE: If tree cannot be ruled-out, the current component will be put into the MST storage 'reddata->msts'

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data

Definition at line 764 of file extreduce_core.c.

References extIsAtInitialComp(), extreduce_contractionRuleOutPeriph(), extreduce_mstRuleOutPeriph(), extreduce_redcostRuleOutPeriph(), extStackTopIsSingleton(), extTreeRuleOutSingletonFull(), extTreeRuleOutSingletonImplied(), FALSE, SCIP_Bool, SCIP_Longint, and TRUE.

Referenced by extProcessComponent(), and extProcessInitialComponent().

extTreeFindExtensions()

static void extTreeFindExtensions ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, int *  extedgesstart, int *  extedges, int *  nextensions, int *  nextendableleaves, SCIP_Bool *  with_ruledout_leaf  )

inlinestatic

Stores extensions of tree from current (expanded and marked) stack top that cannot be ruled-out.

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data
extedgesstart	starts of extension edges for one components
extedges	extensions edges
nextensions	number of all extensions
nextendableleaves	number of leaves that can be extended
with_ruledout_leaf	one leaf could already be ruled out?

Definition at line 843 of file extreduce_core.c.

References EAT_LAST, GRAPH::edges, EXT_STATE_MARKED, extension_data::extcomp, extIsAtInitialStar(), extLeafIsExtendable(), initial_extension_component::extleaves, extreduce_extendInitDebug(), extension_data::extstack_data, extension_data::extstack_state, extStackGetPosition(), extStackGetTopOutEdgesEnd(), extStackGetTopOutEdgesStart(), extTreeRuleOutEdgeSimple(), GRAPH::head, initial_extension_component::nextleaves, extension_data::node_isterm, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, STP_EXT_MAXGRAD, and TRUE.

Referenced by extExtend().

extTreeSyncWithStack()

static void extTreeSyncWithStack ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  conflict  )

inlinestatic

synchronize tree with the stack

Parameters

scip	SCIP
graph	graph data structure
extdata	extension data
conflict	conflict found?

Definition at line 918 of file extreduce_core.c.

References EXT_COSTS_RECOMPBOUND, EXT_STATE_EXPANDED, extreduce_printStack(), extreduce_treeIsHashed(), extreduce_treeRecompCosts(), extension_data::extstack_state, extStackGetPosition(), extStackTopIsWrapped(), extTreeStackTopAdd(), and extension_data::ncostupdatestalls.

Referenced by extProcessComponent().

extTruncate()

static SCIP_Bool extTruncate ( const GRAPH *  graph, const EXTDATA *  extdata  )

static

should we truncate from current component?

Parameters

graph	graph data structure
extdata	extension data

Definition at line 959 of file extreduce_core.c.

References EXT_STATE_MARKED, extLeafIsExtendable(), extension_data::extstack_data, extension_data::extstack_maxncomponents, extension_data::extstack_maxsize, extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), FALSE, GRAPH::head, extension_data::node_isterm, SCIP_Bool, SCIPdebugMessage, extension_data::tree_deg, extension_data::tree_depth, extension_data::tree_maxdepth, extension_data::tree_maxnedges, extension_data::tree_maxnleaves, extension_data::tree_nedges, extension_data::tree_nleaves, and TRUE.

Referenced by extProcessComponent().

extBacktrack()

static void extBacktrack ( SCIP *  scip, const GRAPH *  graph, SCIP_Bool  success, SCIP_Bool  ancestor_conflict, EXTDATA *  extdata  )

static

top component is rebuilt, and if success == TRUE: goes back to first marked component if success == FALSE: goes back to first marked or non-expanded component

Parameters

scip	SCIP data structure
graph	graph data structure
success	backtrack from success?
ancestor_conflict	backtrack triggered by ancestor conflict?
extdata	extension data

Definition at line 1019 of file extreduce_core.c.

References EXT_STATE_EXPANDED, EXT_STATE_MARKED, EXT_STATE_NONE, extreduce_mstLevelRemove(), extreduce_treeIsFlawed(), extension_data::extstack_maxncomponents, extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), extTreeStackTopRemove(), extension_data::reddata, and SCIPdebugMessage.

Referenced by extExtend(), extProcessComponent(), extStackAddCompsExpanded(), extStackAddCompsExpandedSing(), and extStackTopExpandWrapped().

extStackAddCompsExpanded()

static void extStackAddCompsExpanded ( SCIP *  scip, const GRAPH *  graph, int  nextedges, const int *  extedges, EXTDATA *  extdata, SCIP_Bool *  success, SCIP_Bool *  ruledOut  )

inlinestatic

Builds components from top edges and adds them. Backtracks if stack is too full. Helper method for 'extStackTopExpand'

Parameters

scip	SCIP data structure
graph	graph data structure
nextedges	number of edges for extension
extedges	array of edges for extension
extdata	extension data
success	success pointer
ruledOut	all ruled out?

Definition at line 1085 of file extreduce_core.c.

References EXT_EDGE_WRAPPED, EXT_STATE_EXPANDED, extBacktrack(), extensionHasImplicationConflict(), extreduce_mstLevelHorizontalAdd(), extreduce_mstLevelHorizontalRemove(), extension_data::extstack_data, extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), extStackIsExtendable(), FALSE, graph_pc_isPc(), GRAPH::head, ksubsetGetNext(), NULL, extension_data::reddata, SCIP_Bool, SCIPdebugMessage, STP_EXT_MAXGRAD, STP_Vectype, GRAPH::tail, extension_data::tree_deg, extension_data::tree_root, and TRUE.

Referenced by extStackTopExpandWrapped().

extStackAddCompsExpandedSing()

static void extStackAddCompsExpandedSing ( SCIP *  scip, const GRAPH *  graph, int  nextedges, const int *  extedges, EXTDATA *  extdata, SCIP_Bool *  success, SCIP_Bool *  ruledOut  )

inlinestatic

Builds singleton components from top edges and adds them. Backtracks if stack is too full

Parameters

scip	SCIP data structure
graph	graph data structure
nextedges	number of edges for extension
extedges	array of edges for extension
extdata	extension data
success	success pointer
ruledOut	all ruled out?

Definition at line 1189 of file extreduce_core.c.

References EXT_EDGE_WRAPPED, EXT_STATE_EXPANDED, extBacktrack(), extreduce_mstLevelClose(), extreduce_mstLevelHorizontalAddEmpty(), extension_data::extstack_data, extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, extStackGetPosition(), extStackIsExtendable(), FALSE, GRAPH::head, SCIPdebugMessage, STP_EXT_MAXGRAD, GRAPH::tail, and TRUE.

Referenced by extStackTopExpandSingletons().

extStackAddCompInitialExpanded()

static void extStackAddCompInitialExpanded ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata  )

inlinestatic

adds initial component as 'expanded' to stack (including computation of horizontal SDs)

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data

Definition at line 1260 of file extreduce_core.c.

References EXT_STATE_EXPANDED, extInitialCompIsGenStar(), extInitialCompIsStar(), extreduce_mstLevelClose(), extreduce_mstLevelHorizontalAdd(), extension_data::extstack_data, extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, GRAPH::tail, and extension_data::tree_root.

Referenced by extStackTopExpandInitial().

extStackTopCollectExtEdges()

static void extStackTopCollectExtEdges ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, int *  extedges, int *  nextedges  )

inlinestatic

Collects edges top component of stack that we need to consider for extension (i.e. which cannot be ruled out). Helper method for 'extStackTopExpand'

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
extedges	array of collected edges
nextedges	number of edges

Definition at line 1303 of file extreduce_core.c.

References EAT_LAST, extreduce_mldistsLevelContainsBase(), extreduce_mldistsTopLevel(), extreduce_mstTopCompInSync(), extension_data::extstack_data, extension_data::extstack_start, extStackGetPosition(), GRAPH::head, GRAPH::oeat, GRAPH::outbeg, extension_data::reddata, SCIPdebugMessage, reduction_data::sds_vertical, GRAPH::tail, and extension_data::tree_deg.

Referenced by extStackTopExpandWrapped().

extStackTopCollectExtEdgesSing()

static void extStackTopCollectExtEdgesSing ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, int *  extedges, int *  nextedges  )

inlinestatic

Collects edges top component of stack that we need to consider for singletons extension

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
extedges	array of collected edges
nextedges	number of edges

Definition at line 1337 of file extreduce_core.c.

References extreduce_mstTopCompInSync(), extension_data::extstack_data, extension_data::extstack_start, extStackGetPosition(), extTreeRuleOutEdgeSimple(), GRAPH::head, STP_EXT_MAXGRAD, and extension_data::tree_deg.

Referenced by extStackTopExpandSingletons().

extStackTopGetInitalDataStart()

static int extStackTopGetInitalDataStart ( const EXTDATA *  extdata )

inlinestatic

Gets start of data for initial component

Parameters

extdata

extension data

Definition at line 1370 of file extreduce_core.c.

References extInitialCompIsEdge(), extInitialCompIsGenStar(), extension_data::extstack_start, and extStackGetPosition().

Referenced by extStackTopProcessInitialEdges().

extStackTopProcessInitialEdges()

static void extStackTopProcessInitialEdges ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  initialRuleOut  )

inlinestatic

Computes ancestor SDs for leaves of initial component. Also checks for possible rule-out.

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
initialRuleOut	pointer to mark early rule-out

Definition at line 1393 of file extreduce_core.c.

References extensionHasImplicationConflict(), extInitialCompIsEdge(), extreduce_mstLevelVerticalAddLeafInitial(), extreduce_mstTopCompInSync(), extension_data::extstack_data, extension_data::extstack_start, extStackGetPosition(), extStackTopGetInitalDataStart(), extTreeRuleOutEdgeSimple(), FALSE, graph_knot_isInRange(), GRAPH::head, extension_data::reddata, SCIP_Bool, SCIPdebugMessage, STP_Vectype, GRAPH::tail, extension_data::tree_deg, extension_data::tree_root, extension_data::tree_starcenter, and TRUE.

Referenced by extStackTopExpandInitial().

extStackTopExpandSingletons()

static void extStackTopExpandSingletons ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  success  )

static

Expands top component of stack to singletons

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
success	success pointer

Definition at line 1461 of file extreduce_core.c.

References EXT_STATE_EXPANDED, EXT_STATE_NONE, extreduce_mstLevelVerticalAddEmpty(), extension_data::extstack_state, extStackAddCompsExpandedSing(), extStackGetPosition(), extStackTopCollectExtEdgesSing(), FALSE, ruledOut(), SCIP_Bool, SCIPdebugMessage, and STP_EXT_MAXGRAD.

Referenced by extStackTopExpand().

extStackTopExpandWrapped()

static void extStackTopExpandWrapped ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  success  )

static

Expands wrapped component of stack by adding all possible subsets of the component that cannot be ruled-out.

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
success	success pointer

Definition at line 1505 of file extreduce_core.c.

References EXT_STATE_EXPANDED, EXT_STATE_NONE, extBacktrack(), extension_data::extstack_state, extStackAddCompsExpanded(), extStackGetPosition(), extStackTopCollectExtEdges(), extStackTopIsWrapped(), FALSE, ruledOut(), SCIP_Bool, SCIPdebugMessage, STP_EXT_MAXGRAD, and TRUE.

Referenced by extStackTopExpand().

extStackTopExpand()

static void extStackTopExpand ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  success  )

static

Expands top component of stack. Note: This method can backtrack:

1. If stack is full (with success set to FALSE),
2. If all edges of the component can be ruled-out (with success set to TRUE).

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
success	success pointer

Definition at line 1573 of file extreduce_core.c.

References extStackTopExpandSingletons(), extStackTopExpandWrapped(), and extStackTopIsWrapped().

Referenced by extExtend(), and extProcessComponent().

extStackTopExpandInitial()

static void extStackTopExpandInitial ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  initialRuleOut  )

inlinestatic

same as 'extStackTopExpand', but for initial component only

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
initialRuleOut	pointer to mark early rule-out

Definition at line 1589 of file extreduce_core.c.

References EXT_STATE_NONE, extIsAtInitialComp(), extreduce_mstLevelInitialInit(), extreduce_mstLevelVerticalClose(), extreduce_mstLevelVerticalRemove(), extension_data::extstack_start, extension_data::extstack_state, extStackAddCompInitialExpanded(), extStackGetPosition(), extStackTopProcessInitialEdges(), and extension_data::reddata.

Referenced by extProcessInitialComponent().

extExtend()

static void extExtend ( SCIP *  scip, const GRAPH *  graph, EXTDATA *  extdata, SCIP_Bool *  success  )

static

Extends top component of stack. Backtracks if stack is full. Will not add anything in case of rule-out of at least one extension node.

Parameters

scip	SCIP data structure
graph	graph data structure
extdata	extension data
success	success pointer, FALSE iff no extension was possible

Definition at line 1634 of file extreduce_core.c.

References EXT_STATE_MARKED, extBacktrack(), extension_data::extstack_maxsize, extension_data::extstack_start, extension_data::extstack_state, extStackAddCompsNonExpanded(), extStackGetPosition(), extStackTopExpand(), extTreeFindExtensions(), FALSE, NULL, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, STP_EXT_MAXGRAD, and TRUE.

Referenced by extProcessComponent(), and extProcessInitialComponent().

extPreprocessInitialEdge()

static void extPreprocessInitialEdge ( SCIP *  scip, const GRAPH *  graph, const EXTCOMP *  extcomp, EXTDATA *  extdata  )

inlinestatic

adds initial single edge to stack

Parameters

scip	SCIP data structure
graph	graph data structure
extcomp	component to be checked
extdata	extension data

Definition at line 1705 of file extreduce_core.c.

References initial_extension_component::compedges, initial_extension_component::comproot, extension_data::extstack_data, GRAPH::head, initial_extension_component::ncompedges, SCIPdebugMessage, and GRAPH::tail.

Referenced by extPreprocessInitialComponent().

extPreprocessInitialStar()

static void extPreprocessInitialStar ( SCIP *  scip, const GRAPH *  graph, const EXTCOMP *  extcomp, EXTDATA *  extdata  )

inlinestatic

adds initial star component edges to stack

Parameters

scip	SCIP data structure
graph	graph data structure
extcomp	component to be checked
extdata	extension data

Definition at line 1730 of file extreduce_core.c.

References initial_extension_component::compedges, initial_extension_component::comproot, GRAPH::cost, extInnerNodeAdd(), extension_data::extstack_data, GRAPH::head, initial_extension_component::ncompedges, SCIPdebugMessage, GRAPH::tail, extension_data::tree_deg, extension_data::tree_parentEdgeCost, extension_data::tree_parentNode, and extension_data::tree_starcenter.

Referenced by extPreprocessInitialComponent().

extPreprocessInitialGenStar()

static void extPreprocessInitialGenStar ( SCIP *  scip, const GRAPH *  graph, const EXTCOMP *  extcomp, EXTDATA *  extdata  )

inlinestatic

adds initial general star component edges to stack

Parameters

scip	SCIP data structure
graph	graph data structure
extcomp	component to be checked
extdata	extension data

Definition at line 1778 of file extreduce_core.c.

References initial_extension_component::compedges, initial_extension_component::comproot, GRAPH::cost, extInitialCompIsGenStar(), extInnerNodeAdd(), extension_data::extstack_data, extension_data::genstar_centeredge, graph_edge_isInRange(), GRAPH::head, initial_extension_component::ncompedges, SCIPdebugMessage, GRAPH::tail, extension_data::tree_deg, extension_data::tree_parentEdgeCost, extension_data::tree_parentNode, and extension_data::tree_starcenter.

Referenced by extPreprocessInitialComponent().

extPreprocessInitialComponent()

static void extPreprocessInitialComponent ( SCIP *  scip, const GRAPH *  graph, const EXTCOMP *  extcomp, EXTDATA *  extdata  )

inlinestatic

Initial component preprocessing: The component root is added to the tree and the stack, and the remainder is added to the stack to allow for further expansion.

Parameters

scip	SCIP data structure
graph	graph data structure
extcomp	component to be checked
extdata	extension data

Definition at line 1843 of file extreduce_core.c.

References initial_extension_component::comproot, EXT_STATE_NONE, extInitialCompIsGenStar(), extLeafAdd(), extPreprocessInitialEdge(), extPreprocessInitialGenStar(), extPreprocessInitialStar(), extreduce_mstAddRootLevel(), extension_data::extstack_ncomponents, extension_data::extstack_start, extension_data::extstack_state, GRAPH::knots, initial_extension_component::ncompedges, nnodes, reduction_data::redcost_nlevels, reduction_data::redcost_treenodeswaps, extension_data::reddata, SCIP_Bool, SCIP_Real, STP_EXT_MAXGRAD, extension_data::tree_deg, extension_data::tree_leaves, extension_data::tree_nleaves, extension_data::tree_parentEdgeCost, extension_data::tree_parentNode, and extension_data::tree_root.

Referenced by extProcessInitialComponent().

extUnhashInitialComponent()

static void extUnhashInitialComponent ( const GRAPH *  graph, const EXTCOMP *  extcomp, EXTDATA *  extdata  )

inlinestatic

helper for rule-out during initial component processing

Parameters

graph	graph data structure
extcomp	component to be checked
extdata	extension data

Definition at line 1900 of file extreduce_core.c.

References initial_extension_component::compedges, extInitialCompIsGenStar(), initial_extension_component::genstar_centeredge, graph_edge_isInRange(), graph_pseudoAncestors_unhashEdge(), initial_extension_component::ncompedges, reduction_data::pseudoancestor_mark, GRAPH::pseudoancestors, and extension_data::reddata.

Referenced by extProcessInitialComponent().

extProcessInitialComponent()

static void extProcessInitialComponent ( SCIP *  scip, const GRAPH *  graph, const EXTCOMP *  extcomp, EXTDATA *  extdata, SCIP_Bool *  ruledOut, SCIP_Bool *  isExtendable  )

inlinestatic

Adds extensions initial component to stack (needs to be star component rooted in root). If no extensions are added, then the component has been ruled-out.

Parameters

scip	SCIP data structure
graph	graph data structure
extcomp	component to be checked
extdata	extension data
ruledOut	initial component ruled out?
isExtendable	extension possible?

Definition at line 1930 of file extreduce_core.c.

References EXT_STATE_EXPANDED, EXT_STATE_MARKED, extExtend(), extInitialCompIsGenStar(), extInitialCompIsStar(), extPreprocessInitialComponent(), extension_data::extstack_data, extension_data::extstack_state, extStackGetPosition(), extStackTopExpandInitial(), extTreeRuleOutPeriph(), extTreeStackTopAdd(), extUnhashInitialComponent(), FALSE, GRAPH::head, initial_extension_component::ncompedges, SCIP_Bool, extension_data::tree_deg, extension_data::tree_root, and TRUE.

Referenced by extProcessComponent().

extProcessComponent()

static void extProcessComponent ( SCIP *  scip, const GRAPH *  graph, const EXTCOMP *  extcomp, EXTDATA *  extdata, SCIP_Bool *  deletable  )

static

Checks whether component 'extcomp' (star or single edge) can be ruled out.

Parameters

scip	SCIP data structure
graph	graph data structure
extcomp	initial component to be checked
extdata	extension data
deletable	is component deletable?

Definition at line 1993 of file extreduce_core.c.

References EXT_STATE_EXPANDED, EXT_STATE_MARKED, EXT_STATE_NONE, extBacktrack(), extExtend(), extProcessInitialComponent(), extreduce_extCompClean(), extreduce_extdataIsClean(), extreduce_pcdataIsClean(), extreduce_reddataIsClean(), extension_data::extstack_ncomponents, extension_data::extstack_state, extStackGetPosition(), extStackTopExpand(), extStackTopIsWrapped(), extTreeRuleOutPeriph(), extTreeSyncWithStack(), extTruncate(), FALSE, extension_data::pcdata, extension_data::reddata, SCIP_Bool, and TRUE.

Referenced by extreduce_checkComponent().

extreduce_checkComponent()

SCIP_RETCODE extreduce_checkComponent	(	SCIP *	scip,
		const GRAPH *	graph,
		const REDCOST *	redcostdata,
		EXTCOMP *	extcomp,
		EXTPERMA *	extpermanent,
		SCIP_Bool *	compIsDeletable
	)

check component for possible elimination

Parameters

scip	SCIP data structure
graph	graph data structure
redcostdata	reduced cost data structures
extcomp	component to be checked (might be reverted)
extpermanent	extension data
compIsDeletable	is component deletable?

Definition at line 2081 of file extreduce_core.c.

References extension_data_permanent::bottleneckDistNode, extension_data_permanent::contration, reduction_data::contration, extension_data_permanent::dcmst, extension_data_permanent::distdata_biased, extension_data_permanent::distdata_default, extension_data_permanent::edgedeleted, GRAPH::edges, extProcessComponent(), extreduce_extCompFullIsPromising(), extreduce_extCompIsPromising(), extreduce_extCompRevert(), extreduce_extdataCleanArraysDbg(), extreduce_extPermaIsClean(), extreduce_getMaxStackNcomponents(), extreduce_getMaxStackSize(), extreduce_reddataClean(), extension_data::extstack_data, FALSE, initial_extension_component::genstar_centeredge, graph_pc_isPc(), graph_pseudoAncestorsGetHashArraySize(), extension_data_permanent::isterm, GRAPH::knots, extension_data_permanent::mode, extension_data_permanent::msts_comp, extension_data_permanent::msts_levelbase, initial_extension_component::ncompedges, nnodes, NULL, extension_data_permanent::pcSdToNode, pcmw_specific_data::pcSdToNode, GRAPH::pseudoancestors, extension_data_permanent::redcostEqualAllow, redcosts_getNlevels(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeCleanBufferArray, extension_data_permanent::sds_horizontal, extension_data_permanent::sds_vertical, extension_data_permanent::sdsbias_horizontal, extension_data_permanent::sdsbias_vertical, extension_data_permanent::tree_deg, extension_data_permanent::tree_maxdepth, extension_data_permanent::tree_maxnedges, extension_data_permanent::tree_maxnleaves, and extension_data_permanent::useSdBias.

Referenced by extreduce_checkArc(), extreduce_checkEdge(), extreduce_checkNode(), and generalStarCheck().