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.h.

#include "scip/scip.h"

Go to the source code of this file.

Data Structures
struct	Graph_Node

struct	Vnoi_List_Node

struct	ST_Node

struct	UnionFind_Structure

struct	Int_List_Node

struct	PHeap_Node

Typedefs
typedef struct Graph_Node	GNODE

typedef struct Vnoi_List_Node	VLIST

typedef struct ST_Node	NODE

typedef struct UnionFind_Structure	UF

typedef struct Int_List_Node	IDX

typedef struct PHeap_Node	PHNODE

Functions
SCIP_Real	misc_stp_maxReal (SCIP_Real *realarr, unsigned nreals)

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

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

void	SCIPintListNodeFree (SCIP scip, IDX *node)

int	GNODECmpByDist (void first_arg, void second_arg)

void	SCIPlinkcuttreeInit (NODE *v)

void	SCIPlinkcuttreeLink (NODE v, NODE w, int edge)

void	SCIPlinkcuttreeCut (NODE *v)

SCIP_Real	SCIPlinkcuttreeFindMinChain (SCIP scip, const SCIP_Real nodeweight, const int head, const int stdeg, const NODE start, NODE first, NODE *last)

NODE *	SCIPlinkcuttreeFindMax (SCIP scip, const SCIP_Real cost, NODE *v)

void	SCIPlinkcuttreeEvert (NODE *v)

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

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

SCIP_RETCODE	SCIPpairheapInsert (SCIP scip, PHNODE root, 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, PHNODE root, int size, int **elements)

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

void	SCIPStpunionfindClear (SCIP scip, UF uf, int length)

int	SCIPStpunionfindFind (UF *uf, int element)

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

void	SCIPStpunionfindFree (SCIP scip, UF uf)

Typedef Documentation

◆ GNODE

typedef struct Graph_Node GNODE

graph node structure storing number and distance

◆ VLIST

typedef struct Vnoi_List_Node VLIST

voronoi list node structure storing distance, incoming edge,base and pointer to next list node

◆ NODE

typedef struct ST_Node NODE

node

◆ UF

typedef struct UnionFind_Structure UF

a weighted-quick-union-path-compression union find structure

◆ IDX

typedef struct Int_List_Node IDX

integer list node

◆ PHNODE

typedef struct PHeap_Node PHNODE

Pairing heap node

Function Documentation

◆ misc_stp_maxReal()

SCIP_Real misc_stp_maxReal	(	SCIP_Real *	realarr,
		unsigned	nreals
	)

returns maximum of given SCIP_Real values

Parameters

realarr	array of reals
nreals	size of array of reals

Definition at line 41 of file misc_stp.c.

References SCIP_Real.

Referenced by reduce_getSdPcMw().

◆ SCIPintListNodeAppendCopy()

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

Int Listappend copy of list pertaining to node2 to node1

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 94 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 getlecloseterms(), graph_edge_reinsert(), graph_knot_contract(), graph_knot_delPseudo(), graph_pack(), graph_pc_contractEdgeAncestors(), reduce_contractZeroEdges(), reduce_nv(), reduce_nvAdv(), reduce_rpt(), reduce_simple(), reduce_simple_pc(), reduce_simple_sap(), reduce_sl(), traverseChain(), and trydg1edgepc().

◆ 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 77 of file misc_stp.c.

References SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.

◆ SCIPintListNodeFree()

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

free list

Parameters

scip	SCIP data structure
node	pointer to the last list node

Definition at line 205 of file misc_stp.c.

References NULL, Int_List_Node::parent, and SCIPfreeBlockMemory.

Referenced by graph_edge_del(), graph_edge_reinsert(), graph_knot_contract(), graph_knot_delPseudo(), graph_pack(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_simple_pc(), traverseChain(), and trydg1edgepc().

◆ GNODECmpByDist()

int GNODECmpByDist	(	void *	first_arg,
		void *	second_arg
	)

compares distances of two GNODE structures

Parameters

first_arg	first argument
second_arg	second argument

Referenced by SCIPStpDualAscent(), SCIPStpDualAscentPcMw(), SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurTMRun().

◆ SCIPlinkcuttreeInit()

void SCIPlinkcuttreeInit ( NODE * v )

Linear Link Cut Treeinits a node, setting 'parent' and 'edge' to its default values

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

Parameters

v	pointer to node representing the tree

Definition at line 227 of file misc_stp.c.

References ST_Node::edge, NULL, and ST_Node::parent.

Referenced by SCIPStpHeurLocalRun().

◆ SCIPlinkcuttreeLink()

void SCIPlinkcuttreeLink	(	NODE *	v,
		NODE *	w,
		int	edge
	)

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

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

Parameters

v	pointer to node representing the tree
w	pointer to the child
edge	link edge

Definition at line 236 of file misc_stp.c.

References ST_Node::edge, NULL, ST_Node::parent, and w.

Referenced by SCIPStpHeurLocalRun().

◆ SCIPlinkcuttreeCut()

void SCIPlinkcuttreeCut ( NODE * v )

cut tree at given node

Parameters

v	node to cut at

Definition at line 249 of file misc_stp.c.

References ST_Node::edge, NULL, and ST_Node::parent.

Referenced by SCIPStpHeurLocalRun().

◆ SCIPlinkcuttreeFindMinChain()

SCIP_Real SCIPlinkcuttreeFindMinChain	(	SCIP *	scip,
		const SCIP_Real *	nodeweight,
		const int *	head,
		const int *	stdeg,
		const NODE *	start,
		NODE **	first,
		NODE **	last
	)

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

Parameters

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

Definition at line 258 of file misc_stp.c.

References ST_Node::edge, FALSE, NULL, ST_Node::parent, SCIP_Bool, SCIP_Real, SCIPisLT(), SCIPisPositive(), and TRUE.

Referenced by SCIPStpHeurLocalRun().

◆ SCIPlinkcuttreeFindMax()

NODE* SCIPlinkcuttreeFindMax	(	SCIP *	scip,
		const SCIP_Real *	cost,
		NODE *	v
	)

finds the max value between node 'v' and the root of the tree

finds the max edge value between node 'v' and the root of the tree

Parameters

scip	SCIP data structure
cost	edge cost array
v	the node

Definition at line 327 of file misc_stp.c.

References ST_Node::edge, NULL, ST_Node::parent, SCIP_Real, and SCIPisGE().

Referenced by SCIPStpHeurLocalRun().

◆ SCIPlinkcuttreeEvert()

void SCIPlinkcuttreeEvert ( NODE * v )

makes vertex v the root of the link cut tree

Parameters

v	the vertex to become the root

Definition at line 352 of file misc_stp.c.

References ST_Node::edge, flipedge, NULL, ST_Node::parent, and r.

Referenced by SCIPStpHeurLocalRun().

◆ 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 386 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().

◆ SCIPpairheapAddtoheap()

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

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 429 of file misc_stp.c.

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

Referenced by SCIPpairheapInsert().

◆ SCIPpairheapInsert()

SCIP_RETCODE SCIPpairheapInsert	(	SCIP *	scip,
		PHNODE **	root,
		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
element	data of new node
key	key of new node
size	pointer to size of the heap

Definition at line 528 of file misc_stp.c.

References PHeap_Node::child, PHeap_Node::element, PHeap_Node::key, NULL, PHeap_Node::prev, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPpairheapAddtoheap(), and PHeap_Node::sibling.

Referenced by SCIPStpHeurLocalRun().

◆ 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 562 of file misc_stp.c.

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

Referenced by SCIPStpHeurLocalRun().

◆ 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 599 of file misc_stp.c.

References NULL, and SCIPpairheapMergeheaps().

Referenced by SCIPStpHeurLocalRun().

◆ 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 627 of file misc_stp.c.

References NULL, SCIPfreeBlockMemory, and SCIPpairheapFree().

Referenced by SCIPpairheapFree(), and SCIPStpHeurLocalRun().

◆ SCIPpairheapBuffarr()

SCIP_RETCODE SCIPpairheapBuffarr	(	SCIP *	scip,
		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

Definition at line 670 of file misc_stp.c.

References pairheapRec(), SCIP_CALL, SCIP_OKAY, and SCIPallocBufferArray.

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 components

Definition at line 689 of file misc_stp.c.

References UnionFind_Structure::count, UnionFind_Structure::parent, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and UnionFind_Structure::size.

Referenced by SCIPStpHeurLocalRun().

◆ SCIPStpunionfindClear()

void SCIPStpunionfindClear	(	SCIP *	scip,
		UF *	uf,
		int	length
	)

clears the union-find structure 'uf'

Parameters

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

Definition at line 708 of file misc_stp.c.

References UnionFind_Structure::count, UnionFind_Structure::parent, and UnionFind_Structure::size.

Referenced by SCIPStpHeurLocalRun().

◆ 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 728 of file misc_stp.c.

References UnionFind_Structure::parent.

Referenced by graph_voronoiRepair(), graph_voronoiRepairMult(), lca(), SCIPStpHeurLocalRun(), and SCIPStpunionfindUnion().

◆ SCIPStpunionfindUnion()

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

merges the components containing p and q respectively

Parameters

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

Definition at line 752 of file misc_stp.c.

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

Referenced by lca(), and SCIPStpHeurLocalRun().

◆ SCIPStpunionfindFree()

void SCIPStpunionfindFree	(	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 795 of file misc_stp.c.

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

Referenced by SCIPStpHeurLocalRun().

SCIP

Detailed Description

Data Structures

Typedefs

Functions

Typedef Documentation

◆ GNODE

◆ VLIST

◆ NODE

◆ UF

◆ IDX

◆ PHNODE

Function Documentation

◆ misc_stp_maxReal()

◆ SCIPintListNodeAppendCopy()

◆ SCIPintListNodeInsert()

◆ SCIPintListNodeFree()

◆ GNODECmpByDist()

◆ SCIPlinkcuttreeInit()

◆ SCIPlinkcuttreeLink()

◆ SCIPlinkcuttreeCut()

◆ SCIPlinkcuttreeFindMinChain()

◆ SCIPlinkcuttreeFindMax()

◆ SCIPlinkcuttreeEvert()

◆ SCIPpairheapMergeheaps()

◆ SCIPpairheapAddtoheap()

◆ SCIPpairheapInsert()

◆ SCIPpairheapDeletemin()

◆ SCIPpairheapMeldheaps()

◆ SCIPpairheapFree()

◆ SCIPpairheapBuffarr()

◆ SCIPStpunionfindInit()

◆ SCIPStpunionfindClear()

◆ SCIPStpunionfindFind()

◆ SCIPStpunionfindUnion()

◆ SCIPStpunionfindFree()