  # SCIP

Solving Constraint Integer Programs

grphpath.c File Reference

## Detailed Description

Shortest path based graph algorithms for Steiner problems.

This file encompasses various (heap-based) shortest path based algorithms including Dijkstra's algorithm and Voronoi diagram algorithms

The underlying heap routines can be found in Jon Bentley, Programming Pearls, Addison-Wesley 1989

The heap array is initialized with n elements (nodes), but only at most n-1 nodes can be included in the array, since element 0 is not used for storing.

Definition in file grphpath.c.

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <assert.h>
#include "portab.h"
#include "grph.h"

Go to the source code of this file.

## Functions

static int nearest (int *heap, int *state, int *count, const PATH *path)

static int nearestX (int *heap, int *state, int *count, const SCIP_Real *pathdist)

static void correct (SCIP *scip, int *heap, int *state, int *count, PATH *path, int l, int k, int e, SCIP_Real cost, int mode)

static void correctX (SCIP *scip, int *heap, int *state, int *count, SCIP_Real *pathdist, int *pathedge, int l, int k, int e, SCIP_Real cost)

void heap_add (int *heap, int *state, int *count, int node, PATH *path)

static void resetX (SCIP *scip, SCIP_Real *pathdist, int *heap, int *state, int *count, int node)

static void reset (SCIP *scip, PATH *path, int *heap, int *state, int *count, int node)

static void utdist (SCIP *scip, const GRAPH *g, PATH *path, SCIP_Real ecost, int *vbase, int k, int l, int k2, int shift, int nnodes)

SCIP_RETCODE graph_path_init (SCIP *scip, GRAPH *g)

void graph_path_exit (SCIP *scip, GRAPH *g)

void graph_path_exec (SCIP *scip, const GRAPH *p, const int mode, int start, const SCIP_Real *cost, PATH *path)

void graph_sdPaths (SCIP *scip, const GRAPH *g, PATH *path, SCIP_Real *cost, SCIP_Real distlimit, int *heap, int *state, int *memlbl, int *nlbl, int tail, int head, int limit)

void graph_path_PcMwSd (SCIP *scip, const GRAPH *g, PATH *path, SCIP_Real *cost, SCIP_Real distlimit, int *pathmaxnode, int *heap, int *state, int *stateblock, int *memlbl, int *nlbl, int tail, int head, int limit)

void graph_path_execX (SCIP *scip, const GRAPH *g, int start, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge)

void graph_path_invroot (SCIP *scip, const GRAPH *g, int start, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge)

void graph_path_st (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, SCIP_RANDNUMGEN *randnumgen, STP_Bool *connected)

void graph_path_st_rpc (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)

void graph_path_st_pcmw (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)

void graph_path_st_pcmw_reduce (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *tmpnodeweight, int *result, int start, STP_Bool *connected)

void graph_path_st_pcmw_full (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)

void graph_path_st_pcmw_extend (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, PATH *path, STP_Bool *connected, SCIP_Bool *extensions)

void graph_path_st_rmw (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)

SCIP_RETCODE graph_voronoiExtend (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, SCIP_Real **distarr, int **basearr, int **edgearr, STP_Bool *termsmark, int *reachednodes, int *nreachednodes, int *nodenterms, int nneighbterms, int base, int countex)

void graph_voronoi (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, STP_Bool *base, int *vbase, PATH *path)

void graph_get2next (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)

void graph_get3next (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)

void graph_get4next (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)

void graph_get3nextTerms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path3, int *vbase, int *heap, int *state)

void graph_get4nextTerms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)

SCIP_RETCODE graph_get4nextTTerms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, int *vbase, int *heap, int *state)

void graph_voronoiTerms (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, PATH *path, int *vbase, int *heap, int *state)

void graph_voronoiMw (SCIP *scip, const GRAPH *g, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)

SCIP_RETCODE graph_voronoiWithDist (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *distance, int *minedgepred, int *vbase, int *minarc, int *heap, int *state, int *distnode, PATH *path)

SCIP_RETCODE graph_voronoiWithRadius (SCIP *scip, const GRAPH *graph, GRAPH *adjgraph, PATH *path, SCIP_Real *rad, SCIP_Real *cost, SCIP_Real *costrev, int *vbase, int *heap, int *state)

void graph_voronoiWithRadiusMw (SCIP *scip, const GRAPH *g, PATH *path, const SCIP_Real *cost, SCIP_Real *radius, int *vbase, int *heap, int *state)

void graph_voronoiRepair (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int *count, int *vbase, PATH *path, int *newedge, int crucnode, UF *uf)

void graph_voronoiRepairMult (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int *count, int *vbase, int *boundedges, int *nboundedges, STP_Bool *nodesmark, UF *uf, PATH *path)

## ◆ nearest()

 static int nearest ( int * heap, int * state, int * count, const PATH * path )
inlinestatic

Definition at line 43 of file grphpath.c.

References GT, and LT.

## ◆ nearestX()

 static int nearestX ( int * heap, int * state, int * count, const SCIP_Real * pathdist )
inlinestatic

Definition at line 92 of file grphpath.c.

References GT, and LT.

## ◆ correct()

 static void correct ( SCIP * scip, int * heap, int * state, int * count, PATH * path, int l, int k, int e, SCIP_Real cost, int mode )
inlinestatic

Definition at line 147 of file grphpath.c.

References shortest_path::dist, shortest_path::edge, MST_MODE, SCIPisGT(), and UNKNOWN.

## ◆ correctX()

 static void correctX ( SCIP * scip, int * heap, int * state, int * count, SCIP_Real * pathdist, int * pathedge, int l, int k, int e, SCIP_Real cost )
inlinestatic

Definition at line 199 of file grphpath.c.

References SCIPisGT(), and UNKNOWN.

## ◆ heap_add()

 void heap_add ( int * heap, int * state, int * count, int node, PATH * path )

Definition at line 244 of file grphpath.c.

References GT.

Referenced by computeSteinerTreeVnoi(), and SCIPStpHeurLocalRun().

## ◆ resetX()

 static void resetX ( SCIP * scip, SCIP_Real * pathdist, int * heap, int * state, int * count, int node )
inlinestatic

Definition at line 275 of file grphpath.c.

References SCIPisGT().

## ◆ reset()

 static void reset ( SCIP * scip, PATH * path, int * heap, int * state, int * count, int node )
inlinestatic

Definition at line 309 of file grphpath.c.

References shortest_path::dist, and SCIPisGT().

Referenced by graph_path_st_pcmw_extend().

## ◆ utdist()

 static void utdist ( SCIP * scip, const GRAPH * g, PATH * path, SCIP_Real ecost, int * vbase, int k, int l, int k2, int shift, int nnodes )
inlinestatic

Definition at line 343 of file grphpath.c.

References shortest_path::dist, Is_term, nnodes, r, SCIP_Real, SCIPisLT(), and GRAPH::term.

Referenced by graph_get4nextTTerms().

## ◆ graph_path_init()

 SCIP_RETCODE graph_path_init ( SCIP * scip, GRAPH * g )
Parameters
 scip SCIP data structure g graph data structure

Definition at line 444 of file grphpath.c.

## ◆ graph_path_exit()

 void graph_path_exit ( SCIP * scip, GRAPH * g )
Parameters
 scip SCIP data structure g graph data structure

Definition at line 466 of file grphpath.c.

References NULL, GRAPH::path_heap, GRAPH::path_state, and SCIPfreeMemoryArray.

## ◆ graph_path_exec()

 void graph_path_exec ( SCIP * scip, const GRAPH * p, const int mode, int start, const SCIP_Real * cost, PATH * path )
Parameters
 scip SCIP data structure p graph data structure mode shortest path (FSP_MODE) or minimum spanning tree (MST_MODE)? start start vertex cost edge costs path shortest paths data structure

Definition at line 491 of file grphpath.c.

## ◆ graph_sdPaths()

 void graph_sdPaths ( SCIP * scip, const GRAPH * g, PATH * path, SCIP_Real * cost, SCIP_Real distlimit, int * heap, int * state, int * memlbl, int * nlbl, int tail, int head, int limit )

limited Dijkstra, stopping at terminals

Parameters
 scip SCIP data structure g graph data structure path shortest paths data structure cost edge costs distlimit distance limit of the search heap array representing a heap state array to indicate whether a node has been scanned during SP calculation memlbl array to save labelled nodes nlbl number of labelled nodes tail tail of the edge head head of the edge limit maximum number of edges to consider during execution

Definition at line 567 of file grphpath.c.

Referenced by findDaRoots(), reduce_getSd(), reduce_sdsp(), and reduce_sdspSap().

## ◆ graph_path_PcMwSd()

 void graph_path_PcMwSd ( SCIP * scip, const GRAPH * g, PATH * path, SCIP_Real * cost, SCIP_Real distlimit, int * pathmaxnode, int * heap, int * state, int * stateblock, int * memlbl, int * nlbl, int tail, int head, int limit )

limited Dijkstra for PCSTP, taking terminals into account

Parameters
 scip SCIP data structure g graph data structure path shortest paths data structure cost edge costs distlimit distance limit of the search pathmaxnode maximum weight node on path heap array representing a heap state array to indicate whether a node has been scanned during SP calculation stateblock array to indicate whether a node has been scanned during previous SP calculation memlbl array to save labelled nodes nlbl number of labelled nodes tail tail of the edge head head of the edge limit maximum number of edges to consider during execution

Definition at line 664 of file grphpath.c.

Referenced by reduce_getSdPcMw(), and reduce_sdsp().

## ◆ graph_path_execX()

 void graph_path_execX ( SCIP * scip, const GRAPH * g, int start, const SCIP_Real * cost, SCIP_Real * pathdist, int * pathedge )

Dijkstra's algorithm starting from node 'start'

Parameters
 scip SCIP data structure g graph data structure start start vertex cost edge costs pathdist distance array (on vertices) pathedge predecessor edge array (on vertices)

Definition at line 781 of file grphpath.c.

## ◆ graph_path_invroot()

 void graph_path_invroot ( SCIP * scip, const GRAPH * g, int start, const SCIP_Real * cost, SCIP_Real * pathdist, int * pathedge )

Dijkstra on incoming edges until root is reached

Parameters
 scip SCIP data structure g graph data structure start start vertex cost edge costs pathdist distance array (on vertices) pathedge predecessor edge array (on vertices)

Definition at line 849 of file grphpath.c.

## ◆ graph_path_st()

 void graph_path_st ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, SCIP_Real * pathdist, int * pathedge, int start, SCIP_RANDNUMGEN * randnumgen, STP_Bool * connected )

Find a directed tree rooted in node 'start' and spanning all terminals

Parameters
 scip SCIP data structure g graph data structure cost edgecosts pathdist distance array (on vertices) pathedge predecessor edge array (on vertices) start start vertex randnumgen random number generator connected array to mark whether a vertex is part of computed Steiner tree

Definition at line 926 of file grphpath.c.

Referenced by computeSteinerTreeDijk().

## ◆ graph_path_st_rpc()

 void graph_path_st_rpc ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, SCIP_Real * pathdist, int * pathedge, int start, STP_Bool * connected )

For rooted prize-collecting problem find a tree rooted in node 'start' and connecting positive vertices as long as this is profitable. Note that this function overwrites g->mark.

Parameters
 scip SCIP data structure g graph data structure cost edge costs pathdist distance array (on vertices) pathedge predecessor edge array (on vertices) start start vertex connected array to mark whether a vertex is part of computed Steiner tree

Definition at line 1033 of file grphpath.c.

Referenced by computeSteinerTreeDijkPcMw().

## ◆ graph_path_st_pcmw()

 void graph_path_st_pcmw ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, SCIP_Real * pathdist, int * pathedge, int start, STP_Bool * connected )

Find a tree rooted in node 'start' and connecting positive vertices as long as this is profitable. Note that this function overwrites g->mark.

Parameters
 scip SCIP data structure g graph data structure cost edge costs pathdist distance array (on vertices) pathedge predecessor edge array (on vertices) start start vertex connected array to mark whether a vertex is part of computed Steiner tree

Definition at line 1154 of file grphpath.c.

Referenced by computeSteinerTreeDijkPcMw().

## ◆ graph_path_st_pcmw_reduce()

 void graph_path_st_pcmw_reduce ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, SCIP_Real * tmpnodeweight, int * result, int start, STP_Bool * connected )

Reduce given solution Note that this function overwrites g->mark.

Parameters
 scip SCIP data structure g graph data structure cost edge costs tmpnodeweight node weight array result incoming arc array start start vertex connected array to mark whether a vertex is part of computed Steiner tree

Definition at line 1264 of file grphpath.c.

## ◆ graph_path_st_pcmw_full()

 void graph_path_st_pcmw_full ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, SCIP_Real * pathdist, int * pathedge, int start, STP_Bool * connected )

Find a tree rooted in node 'start' and connecting all positive vertices. Note that this function overwrites g->mark.

Parameters
 scip SCIP data structure g graph data structure cost edge costs pathdist distance array (on vertices) pathedge predecessor edge array (on vertices) start start vertex connected array to mark whether a vertex is part of computed Steiner tree

Definition at line 1316 of file grphpath.c.

Referenced by computeSteinerTreeDijkPcMwFull().

## ◆ graph_path_st_pcmw_extend()

 void graph_path_st_pcmw_extend ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, PATH * path, STP_Bool * connected, SCIP_Bool * extensions )

greedy extension of a given tree for PC or MW problems

Parameters
 scip SCIP data structure g graph data structure cost edge costs path shortest paths data structure connected array to mark whether a vertex is part of computed Steiner tree extensions extensions performed?

Definition at line 1410 of file grphpath.c.

Referenced by SCIPStpHeurLocalExtendPcMw().

## ◆ graph_path_st_rmw()

 void graph_path_st_rmw ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, SCIP_Real * pathdist, int * pathedge, int start, STP_Bool * connected )

Shortest path heuristic for the RMWCSP Find a directed tree rooted in node 'start' and connecting all terminals as well as all positive vertices (as long as this is profitable).

Parameters
 scip SCIP data structure g graph data structure cost edge costs pathdist distance array (on vertices) pathedge predecessor edge array (on vertices) start start vertex connected array to mark whether a vertex is part of computed Steiner tree

Definition at line 1536 of file grphpath.c.

Referenced by computeSteinerTreeDijkPcMw().

## ◆ graph_voronoiExtend()

 SCIP_RETCODE graph_voronoiExtend ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, PATH * path, SCIP_Real ** distarr, int ** basearr, int ** edgearr, STP_Bool * termsmark, int * reachednodes, int * nreachednodes, int * nodenterms, int nneighbterms, int base, int countex )

extend a voronoi region until all neighbouring terminals are spanned

Parameters
 scip SCIP data structure g graph data structure cost edgecosts path shortest paths data structure distarr array to store distance from each node to its base basearr array to store the bases edgearr array to store the ancestor edge termsmark array to mark terminal reachednodes array to mark reached nodes nreachednodes pointer to number of reached nodes nodenterms array to store number of terimals to each node nneighbterms number of neighbouring terminals base voronoi base countex count of heap elements

Definition at line 1671 of file grphpath.c.

Referenced by computeSteinerTreeVnoi().

## ◆ graph_voronoi()

 void graph_voronoi ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, SCIP_Real * costrev, STP_Bool * base, int * vbase, PATH * path )

build a voronoi region, w.r.t. shortest paths, for a given set of bases

Parameters
 scip SCIP data structure g graph data structure cost edge costs costrev reversed edge costs base array to indicate whether a vertex is a Voronoi base vbase voronoi base to each vertex path path data struture (leading to respective Voronoi base)

Definition at line 1751 of file grphpath.c.

Referenced by computeSteinerTreeVnoi(), and SCIPStpHeurLocalRun().

## ◆ graph_get2next()

 void graph_get2next ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, const SCIP_Real * costrev, PATH * path, int * vbase, int * heap, int * state )

2th next terminal to all non terminal nodes

Parameters
 scip SCIP data structure g graph data structure cost edge costs costrev reversed edge costs path path data structure (leading to first and second nearest terminal) vbase first and second nearest terminal to each non terminal heap array representing a heap state array to mark the state of each node during calculation

Definition at line 1838 of file grphpath.c.

## ◆ graph_get3next()

 void graph_get3next ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, const SCIP_Real * costrev, PATH * path, int * vbase, int * heap, int * state )
Parameters
 scip SCIP data structure g graph data structure cost edge costs costrev reversed edge costs path path data structure (leading to first, second and third nearest terminal) vbase first, second and third nearest terminal to each non terminal heap array representing a heap state array to mark the state of each node during calculation

Definition at line 1934 of file grphpath.c.

Referenced by graph_get3nextTerms(), graph_get4nextTerms(), reduce_bound(), and reduce_boundPrune().

## ◆ graph_get4next()

 void graph_get4next ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, const SCIP_Real * costrev, PATH * path, int * vbase, int * heap, int * state )
Parameters
 scip SCIP data structure g graph data structure cost edge costs costrev reversed edge costs path path data struture (leading to first, second and third nearest terminal) vbase first, second and third nearest terminal to each non terminal heap array representing a heap state array to mark the state of each node during calculation

Definition at line 2041 of file grphpath.c.

Referenced by graph_get4nextTerms(), and reduce_bound().

## ◆ graph_get3nextTerms()

 void graph_get3nextTerms ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, SCIP_Real * costrev, PATH * path3, int * vbase, int * heap, int * state )

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
 scip SCIP data structure g graph data structure cost edge costs costrev reversed edge costs path3 path data struture (leading to first, second and third nearest terminal) vbase first, second and third nearest terminal to each non terminal heap array representing a heap state array to mark the state of each node during calculation

Definition at line 2150 of file grphpath.c.

## ◆ graph_get4nextTerms()

 void graph_get4nextTerms ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, SCIP_Real * costrev, PATH * path, int * vbase, int * heap, int * state )

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
 scip SCIP data structure g graph data structure cost edge costs costrev reversed edge costs path path data struture (leading to first, second, third and fouth nearest terminal) vbase first, second and third nearest terminal to each non terminal heap array representing a heap state array to mark the state of each node during calculation

Definition at line 2186 of file grphpath.c.

Referenced by reduce_da(), reduce_daSlackPrune(), reduce_sd(), and reduce_sdPc().

## ◆ graph_get4nextTTerms()

 SCIP_RETCODE graph_get4nextTTerms ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, PATH * path, int * vbase, int * heap, int * state )

get 4 close terminals to each terminal

Parameters
 scip SCIP data structure g graph data structure cost edge costs path path data structure (leading to first, second, third and fourth nearest terminal) vbase first, second and third nearest terminal to each non terminal heap array representing a heap state array to mark the state of each node during calculation

Definition at line 2227 of file grphpath.c.

Referenced by reduce_bound(), and reduce_sdPc().

## ◆ graph_voronoiTerms()

 void graph_voronoiTerms ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, PATH * path, int * vbase, int * heap, int * state )

build a Voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
 scip SCIP data structure g graph data structure cost edge costs path path data structure (leading to respective Voronoi base) vbase Voronoi base to each vertex heap array representing a heap state array to mark the state of each node during calculation

Definition at line 2307 of file grphpath.c.

## ◆ graph_voronoiMw()

 void graph_voronoiMw ( SCIP * scip, const GRAPH * g, const SCIP_Real * costrev, PATH * path, int * vbase, int * heap, int * state )

build a Voronoi region, w.r.t. shortest paths, for all positive vertices

Parameters
 scip SCIP data structure g graph data structure costrev reversed edge costs path path data structure (leading to respective Voronoi base) vbase Voronoi base to each vertex heap array representing a heap state array to mark the state of each node during calculation

Definition at line 2383 of file grphpath.c.

Referenced by reduce_boundMw(), and reduce_boundPrune().

## ◆ graph_voronoiWithDist()

 SCIP_RETCODE graph_voronoiWithDist ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, SCIP_Real * distance, int * minedgepred, int * vbase, int * minarc, int * heap, int * state, int * distnode, PATH * path )

build a voronoi region, w.r.t. shortest paths, for all terminal and the distance

Parameters
 scip SCIP data structure g graph data structure cost edge costs distance array storing path from a terminal over shortest incident edge to nearest terminal minedgepred shortest edge predecessor array vbase array containing Voronoi base to each node minarc array to mark whether an edge is one a path corresponding to 'distance' heap array representing a heap state array indicating state of each vertex during calculation of Voronoi regions distnode array to store terminal corresponding to distance stored in distance array path array containing Voronoi paths data

Definition at line 2463 of file grphpath.c.

## ◆ graph_voronoiWithRadius()

 SCIP_RETCODE graph_voronoiWithRadius ( SCIP * scip, const GRAPH * graph, GRAPH * adjgraph, PATH * path, SCIP_Real * rad, SCIP_Real * cost, SCIP_Real * costrev, int * vbase, int * heap, int * state )

build voronoi regions, w.r.t. shortest paths, for all terminals and compute the radii

Parameters
 scip SCIP data structure graph graph data structure adjgraph graph data structure path array containing Voronoi paths data rad array storing shortest way from a terminal out of its Voronoi region cost edge costs costrev reversed edge costs vbase array containing Voronoi base of each node heap array representing a heap state array to mark state of each node during calculation

Definition at line 2614 of file grphpath.c.

Referenced by reduce_bound(), reduce_boundHop(), and reduce_boundPrune().

## ◆ graph_voronoiWithRadiusMw()

 void graph_voronoiWithRadiusMw ( SCIP * scip, const GRAPH * g, PATH * path, const SCIP_Real * cost, SCIP_Real * radius, int * vbase, int * heap, int * state )

Build partition of graph for MWCSP into regions around the positive vertices. Store the weight of a minimum weight center-boundary path for each region in the radius array (has to be reverted to obtain the final r() value).

Parameters
 scip SCIP data structure g graph data structure path array containing graph decomposition data cost edge costs radius array storing shortest way from a positive vertex out of its region vbase array containing base of each node heap array representing a heap state array to mark state of each node during calculation

Definition at line 2852 of file grphpath.c.

Referenced by reduce_boundMw().

## ◆ graph_voronoiRepair()

 void graph_voronoiRepair ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, int * count, int * vbase, PATH * path, int * newedge, int crucnode, UF * uf )

repair a Voronoi diagram for a given set of base nodes

Parameters
 scip SCIP data structure g graph data structure cost edge costs count pointer to number of heap elements vbase array containing Voronoi base of each node path Voronoi paths data struture newedge the new edge crucnode the current crucial node uf union find data structure

Definition at line 2979 of file grphpath.c.

Referenced by SCIPStpHeurLocalRun().

## ◆ graph_voronoiRepairMult()

 void graph_voronoiRepairMult ( SCIP * scip, const GRAPH * g, SCIP_Real * cost, int * count, int * vbase, int * boundedges, int * nboundedges, STP_Bool * nodesmark, UF * uf, PATH * path )

repair the Voronoi diagram for a given set nodes

Parameters
 scip SCIP data structure g graph data structure cost edge costs count pointer to number of heap elements vbase array containing Voronoi base of each node boundedges boundary edges nboundedges number of boundary edges nodesmark array to mark temporarily discarded nodes uf union find data structure path Voronoi paths data structure

Definition at line 3057 of file grphpath.c.

Referenced by SCIPStpHeurLocalRun().