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 "heur_tm.h"
#include "probdata_stp.h"
#include "portab.h"
#include "scip/misc.h"

Go to the source code of this file.

Functions
	SCIP_DECL_SORTPTRCOMP (GNODECmpByDist)

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

SCIP_RETCODE	SCIPintListNodeAppendCopy (SCIP scip, IDX node1, IDX node2)

void	SCIPintListNodeFree (SCIP scip, IDX *node)

void	SCIPlinkcuttreeInit (NODE *v)

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

void	SCIPlinkcuttreeCut (NODE *v)

NODE *	SCIPlinkcuttreeFindMinMW (SCIP scip, SCIP_Real nodeweight, int tail, int stdeg, NODE *v)

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)

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

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)

static void	pairheapRec (PHNODE p, int arr, int n)

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

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

int	SCIPunionfindFind (UF *uf, int element)

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

void	SCIPunionfindFree (SCIP scip, UF uf)

Function Documentation

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

References PHeap_Node::prev, SCIPpairheapMergeheaps(), and PHeap_Node::sibling.

Referenced by SCIPpairheapDeletemin().

static void pairheapRec	(	PHNODE *	p,
		int **	arr,
		int *	n
	)

static

internal method used by 'pairheap_buffarr'

Definition at line 564 of file misc_stp.c.

References PHeap_Node::child, PHeap_Node::element, and PHeap_Node::sibling.

Referenced by SCIPpairheapBuffarr().

SCIP_DECL_SORTPTRCOMP ( GNODECmpByDist )

compares distances of two GNODE structures

Definition at line 40 of file misc_stp.c.

References EQ, and LT.

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

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

Definition at line 76 of file misc_stp.c.

References Int_List_Node::index, and Int_List_Node::parent.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), da_reduce(), degree_test(), degree_test_pc(), degree_test_sap(), graph_edge_reinsert(), graph_knot_contract(), graph_knot_contractpc(), graph_pack(), nv_reduction(), nv_reductionAdv(), pcgraphtrans(), rptReduction(), sl_reduction(), traverseChain(), and trydg1edgepc().

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

free list

Parameters

scip	SCIP data structure
node	pointer to the last list node

Definition at line 140 of file misc_stp.c.

References Int_List_Node::parent.

Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), da_reduce(), daPc_reduce(), degree_test_pc(), graph_edge_del(), graph_edge_reinsert(), graph_knot_contract(), graph_knot_contractpc(), graph_pack(), pcgraphtrans(), traverseChain(), and trydg1edgepc().

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

void SCIPlinkcuttreeCut ( NODE * v )

cut tree at given node

Parameters

v	node to cut at

Definition at line 184 of file misc_stp.c.

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

Referenced by SCIPheurImproveSteinerTree().

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

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

Referenced by SCIPheurImproveSteinerTree().

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

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

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

Referenced by SCIPheurImproveSteinerTree().

NODE* SCIPlinkcuttreeFindMinMW	(	SCIP *	scip,
		SCIP_Real *	nodeweight,
		int *	tail,
		int *	stdeg,
		NODE *	v
	)

finds minimal non-key-node value between node 'v' and the root of the tree

Parameters

scip	SCIP data structure
nodeweight	node weight array
tail	tail of an arc
stdeg	degree in Steiner tree
v	the node

Definition at line 193 of file misc_stp.c.

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

Referenced by SCIPheurImproveSteinerTree().

void SCIPlinkcuttreeInit ( NODE * v )

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

Parameters

v	pointer to node representing the tree

Definition at line 162 of file misc_stp.c.

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

Referenced by SCIPheurImproveSteinerTree().

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

renders w a child of v; 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 171 of file misc_stp.c.

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

Referenced by SCIPheurImproveSteinerTree().

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

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

Referenced by SCIPpairheapInsert().

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

References pairheapRec().

Referenced by lca().

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

References PHeap_Node::child, and pairheapCombineSiblings().

Referenced by SCIPheurImproveSteinerTree().

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

References SCIPpairheapFree().

Referenced by SCIPheurImproveSteinerTree(), and SCIPpairheapFree().

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

References PHeap_Node::child, PHeap_Node::element, PHeap_Node::key, PHeap_Node::prev, SCIPpairheapAddtoheap(), and PHeap_Node::sibling.

Referenced by SCIPheurImproveSteinerTree().

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

References SCIPpairheapMergeheaps().

Referenced by SCIPheurImproveSteinerTree().

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

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

Referenced by pairheapCombineSiblings(), and SCIPpairheapMeldheaps().

int SCIPunionfindFind	(	UF *	uf,
		int	element
	)

finds and returns the component identifier

Parameters

uf	union find data structure
element	element to be found

Definition at line 620 of file misc_stp.c.

References UnionFind_Structure::parent.

Referenced by lca(), SCIPheurImproveSteinerTree(), SCIPunionfindUnion(), voronoi_repair(), and voronoi_repair_mult().

void SCIPunionfindFree	(	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 687 of file misc_stp.c.

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

Referenced by SCIPheurImproveSteinerTree().

SCIP_RETCODE SCIPunionfindInit	(	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 600 of file misc_stp.c.

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

Referenced by SCIPheurImproveSteinerTree().

void SCIPunionfindUnion	(	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 644 of file misc_stp.c.

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

Referenced by lca(), and SCIPheurImproveSteinerTree().

SCIP

Detailed Description

Functions

Function Documentation