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.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.
Function Documentation
◆ misc_stp_maxReal()
returns maximum of given SCIP_Real values
- Parameters
-
realarr array of reals nreals size 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.
◆ 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 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
-
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 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()
free list
- Parameters
-
scip SCIP data structure node pointer 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
-
v pointer 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()
renders v a child of w; 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 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
-
v node 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
-
scip SCIP data structure nodeweight node weight array head head of an arc stdeg degree in Steiner tree start the node to start at first first node of chain last last 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()
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 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
-
v the 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()
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 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()
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 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 |
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 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
-
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 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
-
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 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
-
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 599 of file misc_stp.c.
References NULL, and SCIPpairheapMergeheaps().
Referenced by SCIPStpHeurLocalRun().
◆ SCIPpairheapFree()
frees the paring heap with root 'p'
- Parameters
-
scip SCIP data structure root root 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 |
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
-
scip SCIP data structure root root of the heap size size of the array elements pointer 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
-
scip SCIP data structure uf union find data structure length number 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()
clears the union-find structure 'uf'
- Parameters
-
scip SCIP data structure uf union find data structure length number 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
-
uf union find data structure element element 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()
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 752 of file misc_stp.c.
References UnionFind_Structure::count, UnionFind_Structure::parent, SCIPStpunionfindFind(), and UnionFind_Structure::size.
Referenced by lca(), and SCIPStpHeurLocalRun().
◆ SCIPStpunionfindFree()
frees the data fields of the union-find structure
- Parameters
-
scip SCIP data structure uf union find data structure
Definition at line 795 of file misc_stp.c.
References UnionFind_Structure::parent, SCIPfreeMemoryArray, and UnionFind_Structure::size.
Referenced by SCIPStpHeurLocalRun().