misc_stp.c
Go to the documentation of this file.
20 * This file includes miscellaneous methods used for solving Steiner problems. For more details see \ref STP_MISC page.
24 * This file implements an integer data linked list, a linear link-cut tree, a union-find data structure
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
444 ** Note: 'last' is the tail of the last edge of the chain. So if 'last' and 'first' coincide, the chain is an edge. */
670 /** deletes the root of the paring heap, concomitantly storing its data and key in '*element' and '*key' respectively */
707 /** links nodes 'root1' and 'root2' together, roots the resulting tree at root1 and sets root2 to NULL */
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)
Definition: misc_stp.c:381
Definition: misc_stp.h:88
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)
Definition: misc_stp.c:445
SCIP_RETCODE SCIPStpunionfindInit(SCIP *scip, UF *uf, int length)
Definition: misc_stp.c:817
Definition: struct_scip.h:59
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
void SCIPpairheapMeldheaps(SCIP *scip, PHNODE **root1, PHNODE **root2, int *sizeroot1, int *sizeroot2)
Definition: misc_stp.c:708
Definition: misc_stp.h:78
int SCIPlinkcuttreeFindMax(const LCNODE *tree, const SCIP_Real *cost, int v)
Definition: misc_stp.c:533
Problem data for stp problem.
Definition: misc_stp.h:70
SCIP_RETCODE SCIPpairheapDeletemin(SCIP *scip, int *element, SCIP_Real *key, PHNODE **root, int *size)
Definition: misc_stp.c:671
SCIP_Real miscstp_maxReal(const SCIP_Real *realarr, unsigned nreals)
Definition: misc_stp.c:142
void SCIPlinkcuttreeEvert(LCNODE *RESTRICT tree, int root_new)
Definition: misc_stp.c:559
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
static SCIP_RETCODE pairheapCombineSiblings(SCIP *scip, PHNODE **p, int size)
Definition: misc_stp.c:41
Definition: misc_stp.h:96
miscellaneous methods used for solving Steiner problems
SCIP_RETCODE SCIPintListNodeAppendCopy(SCIP *scip, IDX **node1, IDX *node2, SCIP_Bool *conflict)
Definition: misc_stp.c:197
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
SCIP_RETCODE SCIPpairheapInsert(SCIP *scip, PHNODE **root, PHNODE *pheapelems, int element, SCIP_Real key, int *size)
Definition: misc_stp.c:636
Definition: type_retcode.h:33
void SCIPStpunionfindUnion(UF *uf, int p, int q, SCIP_Bool compress)
Definition: misc_stp.c:912
Definition: graph_load.c:93
int GNODECmpByDist(void *first_arg, void *second_arg)
SCIP_RETCODE SCIPintListNodeInsert(SCIP *scip, IDX **node, int nodeval)
Definition: misc_stp.c:180
static PHNODE * pairheapAddtoHeap(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:96
void SCIPlinkcuttreeLink(LCNODE *tree, int v, int w, int edge)
Definition: misc_stp.c:357
Portable definitions.
PHNODE * SCIPpairheapMergeheaps(SCIP *scip, PHNODE *root1, PHNODE *root2)
Definition: misc_stp.c:592
Definition: misc_stp.h:53
SCIP_RETCODE SCIPpairheapBuffarr(SCIP *scip, const PHNODE *root, int size, int **elements)
Definition: misc_stp.c:761
SCIP_Bool SCIPStpunionfindIsClear(SCIP *scip, const UF *uf)
Definition: misc_stp.c:861
SCIPallocBlockMemory(scip, subsol))
Definition: objbenders.h:33
void SCIPStpunionfindFreeMembers(SCIP *scip, UF *uf)
Definition: misc_stp.c:955