Detailed Description
miscellaneous methods used for solving Steiner problems
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) |
PHNODE * | SCIPpairheapMergeheaps (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 | |||
) |
Definition at line 34 of file misc_stp.h.
Referenced by computeOrderingFromNode(), mincutFree(), mincutGetNextSinkTerm(), mst3LeafTreeGetSds(), and termsepaTraverseSinkComp().
◆ SWAP_REALS
#define SWAP_REALS | ( | real1, | |
real2 | |||
) |
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()
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
-
realarr array of reals nreals size 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
-
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 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()
append list pertaining to node2 to (non-empty!) node1
- Parameters
-
node1 pointer to the last node of non-empty list to be enlarged node2 pointer 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
-
scip SCIP data structure node pointer to the last list node nodeval data of the new node
Definition at line 180 of file misc_stp.c.
References SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory().
◆ SCIPintListNodeFree()
free list
- Parameters
-
scip SCIP data structure node pointer 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_arg first argument second_arg second 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
-
v pointer 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
-
tree the tree v pointer to node representing the tree w pointer to node of another tree edge link 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
-
v node 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
-
scip SCIP data structure tree tree nodeweight node weight array heads head of an arc stdeg degree in Steiner tree nodeIsBlocked has node been blocked? start the node to start at first first node of chain last last 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
-
scip SCIP data structure tree tree edgecosts edge cost array prizes node weight array for PC/RPC heads head of an arc nonTermDeg degree in Steiner tree, or UNKNOWN if vertex is terminal nodeIsBlocked has node been blocked? start the node to start at (NOT the root!) first first node of chain last last 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()
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
-
tree tree cost edge cost array v the 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
-
tree tree root_new the vertex to become the root
Definition at line 559 of file misc_stp.c.
Referenced by insertionRestoreTree(), and localVertexInsertion().
◆ SCIPpairheapMergeheaps()
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 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
-
scip SCIP data structure root pointer to root of the heap pheapelems data array element data of new node key key of new node size pointer 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
-
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 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
-
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 708 of file misc_stp.c.
References NULL, and SCIPpairheapMergeheaps().
Referenced by getKeyPathUpper(), localKeyVertexHeuristics(), soltreeElimKeyPathsStar(), and soltreeExchangeKeyPath().
◆ SCIPpairheapFree()
frees the paring heap with root 'p'
- Parameters
-
scip SCIP data structure root root 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
-
scip SCIP data structure root root of the heap size size of the array elements pointer 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
-
scip SCIP data structure uf union find data structure length number 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()
clears the union-find structure 'uf'
- Parameters
-
scip SCIP data structure uf union 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()
is the union-find structure 'uf' clear?
- Parameters
-
scip SCIP data structure uf union 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 | ||
) |
finds and returns the component identifier
- Parameters
-
uf union find data structure element element to be found
Definition at line 885 of file misc_stp.c.
References UnionFind_Structure::parent, and terminal_separator_storage::root.
Referenced by connectivityDataKeyElimUpdate(), getKeyPathUpper(), graph_voronoiRepair(), graph_voronoiRepairMult(), lca(), localKeyVertexHeuristics(), SCIPStpunionfindUnion(), sdqueryAttachBinaryTreeNode(), sdqueryFullDfs(), soltreeElimKeyPathsStar(), soltreeExchangeKeyPath(), and supergraphComputeMst().
◆ SCIPStpunionfindUnion()
Merges the components containing p and q respectively. Identifier of 'p' will always be used if 'compress' is FALSE.
- Parameters
-
uf union find data structure p first component q second component compress compress 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()
frees the data fields of the union-find structure
- Parameters
-
scip SCIP data structure uf union 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().