Scippy

SCIP

Solving Constraint Integer Programs

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

#include "scip/scip.h"

Go to the source code of this file.

Data Structures

struct  Graph_Node
 
struct  Vnoi_List_Node
 
struct  link_cut_node
 
struct  UnionFind_Structure
 
struct  Int_List_Node
 
struct  PHeap_Node
 

Macros

#define SWAP_INTS(int1, int2)
 
#define SWAP_REALS(real1, real2)
 

Typedefs

typedef struct Graph_Node GNODE
 
typedef struct Vnoi_List_Node VLIST
 
typedef struct link_cut_node LCNODE
 
typedef struct UnionFind_Structure UF
 
typedef struct Int_List_Node IDX
 
typedef struct PHeap_Node PHNODE
 

Functions

SCIP_Real miscstp_maxReal (const SCIP_Real *realarr, unsigned nreals)
 
SCIP_RETCODE SCIPintListNodeAppendCopy (SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
 
void SCIPintListNodeAppend (IDX *node1, IDX *node2)
 
SCIP_RETCODE SCIPintListNodeInsert (SCIP *scip, IDX **node, int nodeval)
 
void SCIPintListNodeFree (SCIP *scip, IDX **node)
 
int GNODECmpByDist (void *first_arg, void *second_arg)
 
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)
 
PHNODESCIPpairheapMergeheaps (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)
 

Macro Definition Documentation

◆ SWAP_INTS

#define SWAP_INTS (   int1,
  int2 
)
Value:
do \
{ \
const int _tmp_ = int1; \
int1 = int2; \
int2 = _tmp_; \
} while(0)

Definition at line 34 of file misc_stp.h.

Referenced by computeOrderingFromNode(), mincutFree(), mincutGetNextSinkTerm(), mst3LeafTreeGetSds(), and termsepaTraverseSinkComp().

◆ SWAP_REALS

#define SWAP_REALS (   real1,
  real2 
)
Value:
do \
{ \
const SCIP_Real _tmp_ = real1; \
real1 = real2; \
real2 = _tmp_; \
} while(0)
#define SCIP_Real
Definition: def.h:177

Definition at line 43 of file misc_stp.h.

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

◆ LCNODE

typedef struct link_cut_node LCNODE

link-cut_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

◆ miscstp_maxReal()

SCIP_Real miscstp_maxReal ( const SCIP_Real realarr,
unsigned  nreals 
)

returns maximum of given SCIP_Real values

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

Parameters
realarrarray of reals
nrealssize of array of reals

Definition at line 142 of file misc_stp.c.

References SCIP_Real.

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

◆ 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
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 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
node1pointer to the last node of non-empty list to be enlarged
node2pointer 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().

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

References SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory().

◆ SCIPintListNodeFree()

void SCIPintListNodeFree ( SCIP scip,
IDX **  node 
)

free list

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

◆ GNODECmpByDist()

int GNODECmpByDist ( void *  first_arg,
void *  second_arg 
)

compares distances of two GNODE structures

Parameters
first_argfirst argument
second_argsecond argument

Referenced by daExec(), dualascent_execPcMw(), SCIPStpHeurLocalExtendPcMw(), and tmVnoiInit().

◆ SCIPlinkcuttreeInitNode()

void SCIPlinkcuttreeInitNode ( LCNODE 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
vpointer 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 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 index of its tree

Parameters
treethe tree
vpointer to node representing the tree
wpointer to node of another tree
edgelink 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
vnode 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 (for maximum-weight connected subgraph)

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

Parameters
scipSCIP data structure
treetree
nodeweightnode weight array
headshead of an arc
stdegdegree in Steiner tree
nodeIsBlockedhas node been blocked?
startthe node to start at
firstfirst node of chain
lastlast 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 cost chain between node 'start' and distinct root node

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
scipSCIP data structure
treetree
edgecostsedge cost array
prizesnode weight array for PC/RPC
headshead of an arc
nonTermDegdegree in Steiner tree, or UNKNOWN if vertex is terminal
nodeIsBlockedhas node been blocked?
startthe node to start at (NOT the root!)
firstfirst node of chain
lastlast 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 value between node 'v' and the root of the tree

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

Parameters
treetree
costedge cost array
vthe 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
treetree
root_newthe 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
scipSCIP data structure
root1pointer to root of first heap
root2pointer 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
scipSCIP data structure
rootpointer to root of the heap
pheapelemsdata array
elementdata of new node
keykey of new node
sizepointer 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
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 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
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 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
scipSCIP data structure
rootroot 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
scipSCIP data structure
rootroot of the heap
sizesize of the array
elementspointer 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
scipSCIP data structure
ufunion find data structure
lengthnumber 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
scipSCIP data structure
ufunion 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
scipSCIP data structure
ufunion 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 
)

◆ 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
ufunion find data structure
pfirst component
qsecond component
compresscompress 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
scipSCIP data structure
ufunion 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().