Detailed Description

Miscellaneous methods used for solving Steiner problems.

Author: Daniel Rehfeldt

This file includes miscellaneous methods used for solving Steiner problems. For more details see Miscellaneous methods used for Steiner tree problems page.

Definition in file misc_stp.c.

#include <assert.h>
#include <string.h>
#include "probdata_stp.h"
#include "portab.h"
#include "misc_stp.h"

Go to the source code of this file.

Functions
static SCIP_RETCODE	pairheapCombineSiblings (SCIP scip, PHNODE *p, int size)

static PHNODE *	pairheapAddtoHeap (SCIP scip, PHNODE root1, PHNODE *root2)

SCIP_Real	miscstp_maxReal (const SCIP_Real *realarr, unsigned nreals)

	SCIP_DECL_SORTPTRCOMP (GNODECmpByDist)

SCIP_RETCODE	SCIPintListNodeInsert (SCIP scip, IDX *node, int nodeval)

SCIP_RETCODE	SCIPintListNodeAppendCopy (SCIP scip, IDX node1, IDX node2, SCIP_Bool *conflict)

void	SCIPintListNodeAppend (IDX node1, IDX node2)

void	SCIPintListNodeFree (SCIP scip, IDX *node)

void	SCIPlinkcuttreeInitNode (LCNODE *v)

void	SCIPlinkcuttreeLink (LCNODE *tree, int v, int w, int edge)

void	SCIPlinkcuttreeCutNode (LCNODE *v)

SCIP_Real	SCIPlinkcuttreeFindMinChainMw (SCIP scip, const LCNODE tree, const SCIP_Real nodeweight, const int heads, const int stdeg, const SCIP_Bool nodeIsBlocked, int start, int first, int last)

SCIP_Real	SCIPlinkcuttreeFindMaxChain (SCIP scip, const LCNODE tree, const SCIP_Real edgecosts, const SCIP_Real prizes, const int heads, const int nonTermDeg, const SCIP_Bool nodeIsBlocked, int start, int first, int *last)

int	SCIPlinkcuttreeFindMax (const LCNODE tree, const SCIP_Real cost, int v)

void	SCIPlinkcuttreeEvert (LCNODE *RESTRICT tree, int root_new)

PHNODE *	SCIPpairheapMergeheaps (SCIP scip, PHNODE root1, PHNODE *root2)

SCIP_RETCODE	SCIPpairheapInsert (SCIP scip, PHNODE root, PHNODE pheapelems, int element, SCIP_Real key, int *size)

SCIP_RETCODE	SCIPpairheapDeletemin (SCIP scip, int element, SCIP_Real key, PHNODE root, int size)

void	SCIPpairheapMeldheaps (SCIP scip, PHNODE root1, PHNODE root2, int sizeroot1, int *sizeroot2)

void	SCIPpairheapFree (SCIP scip, PHNODE *root)

SCIP_RETCODE	SCIPpairheapBuffarr (SCIP scip, const PHNODE root, int size, int **elements)

SCIP_RETCODE	SCIPStpunionfindInit (SCIP scip, UF uf, int length)

void	SCIPStpunionfindClear (SCIP scip, UF uf)

SCIP_Bool	SCIPStpunionfindIsClear (SCIP scip, const UF uf)

int	SCIPStpunionfindFind (UF *uf, int element)

void	SCIPStpunionfindUnion (UF *uf, int p, int q, SCIP_Bool compress)

void	SCIPStpunionfindFreeMembers (SCIP scip, UF uf)

Function Documentation

◆ pairheapCombineSiblings()

static SCIP_RETCODE pairheapCombineSiblings	(	SCIP *	scip,
		PHNODE **	p,
		int	size
	)

static

internal method for combining the siblings after the root has been deleted

Parameters

scip	SCIP data structure
p	the first sibling
size	the size of the heap

Definition at line 41 of file misc_stp.c.

References NULL, PHeap_Node::prev, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPpairheapMergeheaps(), and PHeap_Node::sibling.

Referenced by SCIPpairheapDeletemin().

◆ pairheapAddtoHeap()

static PHNODE* pairheapAddtoHeap	(	SCIP *	scip,
		PHNODE *	root1,
		PHNODE *	root2
	)

static

add heap to heap

Parameters

scip	SCIP data structure
root1	pointer to root of first heap
root2	pointer to root of second heap

Definition at line 96 of file misc_stp.c.

References PHeap_Node::child, PHeap_Node::key, NULL, PHeap_Node::prev, and PHeap_Node::sibling.

Referenced by SCIPpairheapInsert().

◆ miscstp_maxReal()

SCIP_Real miscstp_maxReal	(	const SCIP_Real *	realarr,
		unsigned	nreals
	)

returns maximum of given SCIP_Real values todo check whether this is really more efficient than a variadic function

Parameters

realarr	array of reals
nreals	size of array of reals

Definition at line 142 of file misc_stp.c.

References SCIP_Real.

Referenced by distgraphGetBoundaryEdgeDist(), distgraphGetBoundaryEdgeDist2(), sdGet2ProfitsDist(), and sdGetSdPcMw().

◆ SCIP_DECL_SORTPTRCOMP()

SCIP_DECL_SORTPTRCOMP ( GNODECmpByDist )

compares distances of two GNODE structures

Definition at line 161 of file misc_stp.c.

References EQ, LT, and SCIP_Real.

◆ SCIPintListNodeInsert()

SCIP_RETCODE SCIPintListNodeInsert	(	SCIP *	scip,
		IDX **	node,
		int	nodeval
	)

insert a new node

Parameters

scip	SCIP data structure
node	pointer to the last list node
nodeval	data of the new node

Definition at line 180 of file misc_stp.c.

References SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory().

◆ SCIPintListNodeAppendCopy()

SCIP_RETCODE SCIPintListNodeAppendCopy	(	SCIP *	scip,
		IDX **	node1,
		IDX *	node2,
		SCIP_Bool *	conflict
	)

append copy of list pertaining to node2 to node1

Parameters

scip	SCIP data structure
node1	pointer to the last node of list to be enlarged
node2	pointer to the last node of source list
conflict	pointer to store whether a conflict has been detected by the method

Definition at line 197 of file misc_stp.c.

References FALSE, Int_List_Node::index, NULL, Int_List_Node::parent, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory(), SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPprobdataGetNorgEdges(), SCIPprobdataGetType(), STP_SPG, and TRUE.

Referenced by delPseudoPath(), extractSubgraphAddEdge(), graph_edge_reinsert(), graph_fixed_add(), graph_knot_contract(), graph_knot_replaceDeg2(), graph_pc_contractNodeAncestors(), graph_singletonAncestors_init(), mwTraverseChain(), reduce_contract0Edges(), and reduce_simple_sap().

◆ SCIPintListNodeAppend()

void SCIPintListNodeAppend	(	IDX *	node1,
		IDX *	node2
	)

append list pertaining to node2 to (non-empty!) node1

Parameters

node1	pointer to the last node of non-empty list to be enlarged
node2	pointer to the last node of source list

Definition at line 309 of file misc_stp.c.

References Int_List_Node::parent.

Referenced by graph_knot_replaceDeg2().

◆ SCIPintListNodeFree()

void SCIPintListNodeFree	(	SCIP *	scip,
		IDX **	node
	)

free list

Parameters

scip	SCIP data structure
node	pointer to the last list node

Definition at line 325 of file misc_stp.c.

References NULL, Int_List_Node::parent, and SCIPfreeBlockMemory.

Referenced by graph_edge_delHistory(), graph_fixed_moveNodePc(), graph_knot_contract(), graph_knot_replaceDeg2(), graph_singletonAncestors_freeMembers(), and mwTraverseChain().

◆ SCIPlinkcuttreeInitNode()

void SCIPlinkcuttreeInitNode ( LCNODE * v )

inits a node, setting 'parent' and 'edge' to its default values

Parameters

v	pointer to node

Definition at line 347 of file misc_stp.c.

References link_cut_node::edge, and link_cut_node::parent.

Referenced by insertionFinalizeReplacement(), localKeyVertexHeuristics(), localVertexInsertion(), and markSolTreeNodes().

◆ SCIPlinkcuttreeLink()

void SCIPlinkcuttreeLink	(	LCNODE *	tree,
		int	v,
		int	w,
		int	edge
	)

renders v a child of w; v has to be the root index of its tree

Parameters

tree	the tree
v	pointer to node representing the tree
w	pointer to node of another tree
edge	link edge

Definition at line 357 of file misc_stp.c.

References link_cut_node::edge, link_cut_node::parent, and w.

Referenced by insertionInitInsert(), insertionReplaceChain(), insertionRestoreTree(), localKeyVertexHeuristics(), localVertexInsertion(), and markSolTreeNodes().

◆ SCIPlinkcuttreeCutNode()

void SCIPlinkcuttreeCutNode ( LCNODE * v )

cut tree at given node

Parameters

v	node to cut at

Definition at line 372 of file misc_stp.c.

References link_cut_node::edge, and link_cut_node::parent.

Referenced by insertionReplaceChain(), and insertionRestoreTree().

◆ SCIPlinkcuttreeFindMinChainMw()

SCIP_Real SCIPlinkcuttreeFindMinChainMw	(	SCIP *	scip,
		const LCNODE *	tree,
		const SCIP_Real *	nodeweight,
		const int *	heads,
		const int *	stdeg,
		const SCIP_Bool *	nodeIsBlocked,
		int	start,
		int *	first,
		int *	last
	)

finds minimum weight chain between node 'start' and distinct root node

Parameters

scip	SCIP data structure
tree	tree
nodeweight	node weight array
heads	head of an arc
stdeg	degree in Steiner tree
nodeIsBlocked	has node been blocked?
start	the node to start at
first	first node of chain
last	last node of chain

Definition at line 381 of file misc_stp.c.

References link_cut_node::edge, FALSE, link_cut_node::parent, SCIP_Bool, SCIP_Real, SCIPisLT(), and TRUE.

Referenced by localVertexInsertion().

◆ SCIPlinkcuttreeFindMaxChain()

SCIP_Real SCIPlinkcuttreeFindMaxChain	(	SCIP *	scip,
		const LCNODE *	tree,
		const SCIP_Real *	edgecosts,
		const SCIP_Real *	prizes,
		const int *	heads,
		const int *	nonTermDeg,
		const SCIP_Bool *	nodeIsBlocked,
		int	start,
		int *	first,
		int *	last
	)

Finds maximum weight chain between node 'start' and distinct root node and returns cost. Note: 'last' is the tail of the last edge of the chain. So if 'last' and 'first' coincide, the chain is an edge.

Parameters

scip	SCIP data structure
tree	tree
edgecosts	edge cost array
prizes	node weight array for PC/RPC
heads	head of an arc
nonTermDeg	degree in Steiner tree, or UNKNOWN if vertex is terminal
nodeIsBlocked	has node been blocked?
start	the node to start at (NOT the root!)
first	first node of chain
last	last node of chain

Definition at line 445 of file misc_stp.c.

References link_cut_node::edge, FALSE, NULL, link_cut_node::parent, SCIP_Bool, SCIP_Real, SCIPisGE(), and TRUE.

Referenced by localVertexInsertion().

◆ SCIPlinkcuttreeFindMax()

int SCIPlinkcuttreeFindMax	(	const LCNODE *	tree,
		const SCIP_Real *	cost,
		int	v
	)

finds the max edge value between node 'v' and the root of the tree Returns index of node that has this edge

Parameters

tree	tree
cost	edge cost array
v	the node

Definition at line 533 of file misc_stp.c.

References link_cut_node::edge, GE, link_cut_node::parent, and SCIP_Real.

◆ SCIPlinkcuttreeEvert()

void SCIPlinkcuttreeEvert	(	LCNODE *RESTRICT	tree,
		int	root_new
	)

makes vertex v the root of the link cut tree

Parameters

tree	tree
root_new	the vertex to become the root

Definition at line 559 of file misc_stp.c.

References flipedge, and r.

Referenced by insertionRestoreTree(), and localVertexInsertion().

◆ SCIPpairheapMergeheaps()

PHNODE* SCIPpairheapMergeheaps	(	SCIP *	scip,
		PHNODE *	root1,
		PHNODE *	root2
	)

links nodes 'root1' and 'root2' together

Parameters

scip	SCIP data structure
root1	pointer to root of first heap
root2	pointer to root of second heap

Definition at line 592 of file misc_stp.c.

References PHeap_Node::child, PHeap_Node::key, NULL, PHeap_Node::prev, and PHeap_Node::sibling.

Referenced by pairheapCombineSiblings(), and SCIPpairheapMeldheaps().

◆ SCIPpairheapInsert()

SCIP_RETCODE SCIPpairheapInsert	(	SCIP *	scip,
		PHNODE **	root,
		PHNODE *	pheapelems,
		int	element,
		SCIP_Real	key,
		int *	size
	)

inserts a new node into the pairing heap

Parameters

scip	SCIP data structure
root	pointer to root of the heap
pheapelems	data array
element	data of new node
key	key of new node
size	pointer to size of the heap

Definition at line 636 of file misc_stp.c.

References PHeap_Node::child, PHeap_Node::element, PHeap_Node::key, NULL, pairheapAddtoHeap(), PHeap_Node::prev, SCIP_OKAY, and PHeap_Node::sibling.

Referenced by connectivityDataInit(), connectivityDataKeyElimUpdate(), and localKeyVertexHeuristics().

◆ SCIPpairheapDeletemin()

SCIP_RETCODE SCIPpairheapDeletemin	(	SCIP *	scip,
		int *	element,
		SCIP_Real *	key,
		PHNODE **	root,
		int *	size
	)

deletes the root of the paring heap, concomitantly storing its data and key in '*element' and '*key' respectively

Parameters

scip	SCIP data structure
element	data of the root
key	key of the root
root	pointer to root of the heap
size	pointer to size of the heap

Definition at line 671 of file misc_stp.c.

References PHeap_Node::child, NULL, pairheapCombineSiblings(), SCIP_CALL, and SCIP_OKAY.

Referenced by connectivityDataKeyElimUpdate(), and localKeyVertexHeuristics().

◆ SCIPpairheapMeldheaps()

void SCIPpairheapMeldheaps	(	SCIP *	scip,
		PHNODE **	root1,
		PHNODE **	root2,
		int *	sizeroot1,
		int *	sizeroot2
	)

links nodes 'root1' and 'root2' together, roots the resulting tree at root1 and sets root2 to NULL

Parameters

scip	SCIP data structure
root1	pointer to root of first heap
root2	pointer to root of second heap
sizeroot1	pointer to size of first heap
sizeroot2	pointer to size of second heap

Definition at line 708 of file misc_stp.c.

References NULL, and SCIPpairheapMergeheaps().

Referenced by getKeyPathUpper(), localKeyVertexHeuristics(), soltreeElimKeyPathsStar(), and soltreeExchangeKeyPath().

◆ SCIPpairheapFree()

void SCIPpairheapFree	(	SCIP *	scip,
		PHNODE **	root
	)

frees the paring heap with root 'p'

Parameters

scip	SCIP data structure
root	root of heap to be freed

Definition at line 736 of file misc_stp.c.

References NULL, and SCIPpairheapFree().

Referenced by localKeyVertexHeuristics(), and SCIPpairheapFree().

◆ SCIPpairheapBuffarr()

SCIP_RETCODE SCIPpairheapBuffarr	(	SCIP *	scip,
		const PHNODE *	root,
		int	size,
		int **	elements
	)

stores all elements of the pairing heap in an array

Parameters

scip	SCIP data structure
root	root of the heap
size	size of the array
elements	pointer to array (will be allocated)

Definition at line 761 of file misc_stp.c.

References PHeap_Node::child, PHeap_Node::element, NULL, terminal_separator_storage::root, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and PHeap_Node::sibling.

Referenced by lca().

◆ SCIPStpunionfindInit()

SCIP_RETCODE SCIPStpunionfindInit	(	SCIP *	scip,
		UF *	uf,
		int	length
	)

initializes the union-find structure 'uf' with 'length' many components (of size one)

Parameters

scip	SCIP data structure
uf	union find data structure
length	number of elements

Definition at line 817 of file misc_stp.c.

References UnionFind_Structure::nComponents, UnionFind_Structure::nElements, UnionFind_Structure::parent, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and UnionFind_Structure::size.

Referenced by localKeyVertexHeuristics(), sdqueryBuildBinaryTree(), and sdqueryFullBuild().

◆ SCIPStpunionfindClear()

void SCIPStpunionfindClear	(	SCIP *	scip,
		UF *	uf
	)

clears the union-find structure 'uf'

Parameters

scip	SCIP data structure
uf	union find data structure

Definition at line 841 of file misc_stp.c.

References UnionFind_Structure::nComponents, UnionFind_Structure::nElements, UnionFind_Structure::parent, and UnionFind_Structure::size.

Referenced by localKeyVertexHeuristics().

◆ SCIPStpunionfindIsClear()

SCIP_Bool SCIPStpunionfindIsClear	(	SCIP *	scip,
		const UF *	uf
	)

is the union-find structure 'uf' clear?

Parameters

scip	SCIP data structure
uf	union find data structure

Definition at line 861 of file misc_stp.c.

References FALSE, UnionFind_Structure::nComponents, UnionFind_Structure::nElements, UnionFind_Structure::parent, UnionFind_Structure::size, and TRUE.

Referenced by getLowestCommonAncestors().

◆ SCIPStpunionfindFind()

int SCIPStpunionfindFind	(	UF *	uf,
		int	element
	)

finds and returns the component identifier

Parameters

uf	union find data structure
element	element to be found

Definition at line 885 of file misc_stp.c.

References UnionFind_Structure::parent, and terminal_separator_storage::root.

Referenced by connectivityDataKeyElimUpdate(), getKeyPathUpper(), graph_voronoiRepair(), graph_voronoiRepairMult(), lca(), localKeyVertexHeuristics(), SCIPStpunionfindUnion(), sdqueryAttachBinaryTreeNode(), sdqueryFullDfs(), soltreeElimKeyPathsStar(), soltreeExchangeKeyPath(), and supergraphComputeMst().

◆ SCIPStpunionfindUnion()

void SCIPStpunionfindUnion	(	UF *	uf,
		int	p,
		int	q,
		SCIP_Bool	compress
	)

Merges the components containing p and q respectively. Identifier of 'p' will always be used if 'compress' is FALSE.

Parameters

uf	union find data structure
p	first component
q	second component
compress	compress union find structure?

Definition at line 912 of file misc_stp.c.

References UnionFind_Structure::nComponents, UnionFind_Structure::parent, SCIPStpunionfindFind(), and UnionFind_Structure::size.

Referenced by getKeyPathsStar(), getKeyPathUpper(), lca(), localKeyVertexHeuristics(), sdqueryAttachBinaryTreeNode(), sdqueryFullDfs(), soltreeElimKeyPathsStar(), and soltreeExchangeKeyPath().

◆ SCIPStpunionfindFreeMembers()

void SCIPStpunionfindFreeMembers	(	SCIP *	scip,
		UF *	uf
	)

frees the data fields of the union-find structure

Parameters

scip	SCIP data structure
uf	union find data structure

Definition at line 955 of file misc_stp.c.

References UnionFind_Structure::nComponents, UnionFind_Structure::nElements, UnionFind_Structure::parent, SCIPfreeMemoryArray, and UnionFind_Structure::size.

Referenced by localKeyVertexHeuristics(), sdqueryBuildBinaryTree(), and sdqueryFullBuild().

SCIP

Detailed Description

Functions

Function Documentation

◆ pairheapCombineSiblings()

◆ pairheapAddtoHeap()

◆ miscstp_maxReal()

◆ SCIP_DECL_SORTPTRCOMP()

◆ SCIPintListNodeInsert()

◆ SCIPintListNodeAppendCopy()

◆ SCIPintListNodeAppend()

◆ SCIPintListNodeFree()

◆ SCIPlinkcuttreeInitNode()

◆ SCIPlinkcuttreeLink()

◆ SCIPlinkcuttreeCutNode()

◆ SCIPlinkcuttreeFindMinChainMw()

◆ SCIPlinkcuttreeFindMaxChain()

◆ SCIPlinkcuttreeFindMax()

◆ SCIPlinkcuttreeEvert()

◆ SCIPpairheapMergeheaps()

◆ SCIPpairheapInsert()

◆ SCIPpairheapDeletemin()

◆ SCIPpairheapMeldheaps()

◆ SCIPpairheapFree()

◆ SCIPpairheapBuffarr()

◆ SCIPStpunionfindInit()

◆ SCIPStpunionfindClear()

◆ SCIPStpunionfindIsClear()

◆ SCIPStpunionfindFind()

◆ SCIPStpunionfindUnion()

◆ SCIPStpunionfindFreeMembers()