Scippy

SCIP

Solving Constraint Integer Programs

misc_stp.c File Reference

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_Real misc_stp_maxReal (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 SCIPintListNodeFree (SCIP *scip, IDX **node)
 
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)
 
NODESCIPlinkcuttreeFindMax (SCIP *scip, const SCIP_Real *cost, NODE *v)
 
void SCIPlinkcuttreeEvert (NODE *v)
 
PHNODESCIPpairheapMergeheaps (SCIP *scip, PHNODE *root1, PHNODE *root2)
 
PHNODESCIPpairheapAddtoheap (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 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)
 

Function Documentation

◆ misc_stp_maxReal()

SCIP_Real misc_stp_maxReal ( SCIP_Real realarr,
unsigned  nreals 
)

returns maximum of given SCIP_Real values

Parameters
realarrarray of reals
nrealssize of array of reals

Definition at line 41 of file misc_stp.c.

References SCIP_Real.

Referenced by reduce_getSdPcMw().

◆ SCIP_DECL_SORTPTRCOMP()

SCIP_DECL_SORTPTRCOMP ( GNODECmpByDist  )

compares distances of two GNODE structures

Definition at line 58 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
scipSCIP data structure
nodepointer to the last list node
nodevaldata of the new node

Definition at line 77 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
scipSCIP data structure
node1pointer to the last node of list to be enlarged
node2pointer to the last node of source list
conflictpointer 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().

◆ SCIPintListNodeFree()

void SCIPintListNodeFree ( SCIP scip,
IDX **  node 
)

free list

Parameters
scipSCIP data structure
nodepointer 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().

◆ SCIPlinkcuttreeInit()

void SCIPlinkcuttreeInit ( NODE v)

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

Parameters
vpointer 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 v a child of w; v has to be the root of its tree

Parameters
vpointer to node representing the tree
wpointer to the child
edgelink 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
vnode 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
scipSCIP data structure
nodeweightnode weight array
headhead of an arc
stdegdegree in Steiner tree
startthe node to start at
firstfirst node of chain
lastlast 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 edge value between node 'v' and the root of the tree

Parameters
scipSCIP data structure
costedge cost array
vthe 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
vthe 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
scipSCIP data structure
root1pointer to root of first heap
root2pointer 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
scipSCIP data structure
root1pointer to root of first heap
root2pointer 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().

◆ 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
scipSCIP data structure
pthe first sibling
sizethe size of the heap

Definition at line 474 of file misc_stp.c.

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

Referenced by SCIPpairheapDeletemin().

◆ SCIPpairheapInsert()

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

inserts a new node into the pairing heap

Parameters
scipSCIP data structure
rootpointer to root of the heap
elementdata of new node
keykey of new node
sizepointer 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
scipSCIP data structure
elementdata of the root
keykey of the root
rootpointer to root of the heap
sizepointer 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
scipSCIP data structure
root1pointer to root of first heap
root2pointer to root of second heap
sizeroot1pointer to size of first heap
sizeroot2pointer 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
scipSCIP data structure
rootroot of heap to be freed

Definition at line 627 of file misc_stp.c.

References NULL, SCIPfreeBlockMemory, and SCIPpairheapFree().

Referenced by SCIPpairheapFree(), and SCIPStpHeurLocalRun().

◆ pairheapRec()

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

internal method used by 'pairheap_buffarr'

Definition at line 653 of file misc_stp.c.

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

Referenced by SCIPpairheapBuffarr().

◆ SCIPpairheapBuffarr()

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

stores all elements of the pairing heap in an array

Parameters
scipSCIP data structure
rootroot of the heap
sizesize of the array
elementspointer 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
scipSCIP data structure
ufunion find data structure
lengthnumber 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
scipSCIP data structure
ufunion find data structure
lengthnumber 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
ufunion find data structure
elementelement 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
ufunion find data structure
pfirst component
qsecond component
compresscompress 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
scipSCIP data structure
ufunion find data structure

Definition at line 795 of file misc_stp.c.

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

Referenced by SCIPStpHeurLocalRun().