# SCIP

Solving Constraint Integer Programs

graph_vnoi.c File Reference

## Detailed Description

Voronoi graph algorithms for Steiner problems.

This file encompasses various Voronoi diagram algorithms.

Definition in file graph_vnoi.c.

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

Go to the source code of this file.

## Functions

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

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

static void vnoiInit (const GRAPH *g, DHEAP *dheap, VNOI *vnoi)

static void vnoiCompute (SCIP *scip, const GRAPH *g, DHEAP *dheap, VNOI *vnoi)

static void vnoiComputeImplied (const GRAPH *g, const SDPROFIT *sdprofit, DHEAP *dheap, VNOI *vnoi)

SCIP_RETCODE graph_voronoiExtend (SCIP *scip, const GRAPH *g, const 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 (const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, const STP_Bool *basemark, int *vbase, PATH *path)

void graph_voronoiTerms (const GRAPH *g, const SCIP_Bool *nodes_isTerm, int *RESTRICT vbase, PATH *RESTRICT path)

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, const SCIP_Bool *nodes_isTerm, const SCIP_Real *cost, SCIP_Real *distance, int *edges_isMinedgePred, int *vbase, int *minarc, 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, const SCIP_Real *cost, const SCIP_Real *cost_org, int *nheapelems, int *vbase, PATH *path, int *newedge, int crucnode, UF *uf)

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

SCIP_RETCODE graph_vnoiInit (SCIP *scip, const GRAPH *graph, SCIP_Bool useBufferArrays, VNOI **vnoi)

SCIP_RETCODE graph_vnoiCompute (SCIP *scip, const GRAPH *graph, VNOI *vnoi)

SCIP_RETCODE graph_vnoiComputeImplied (SCIP *scip, const GRAPH *graph, const SDPROFIT *sdprofit, VNOI *vnoi)

void graph_vnoiFree (SCIP *scip, VNOI **vnoi)

## ◆ correct()

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

Definition at line 35 of file graph_vnoi.c.

References UNKNOWN.

## ◆ nearest()

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

Definition at line 76 of file graph_vnoi.c.

References GT, and LT.

## ◆ vnoiInit()

 static void vnoiInit ( const GRAPH * g, DHEAP * dheap, VNOI * vnoi )
static

initializes

Parameters
 g graph data structure dheap heap vnoi vnoi data structure

Definition at line 116 of file graph_vnoi.c.

Referenced by graph_vnoiCompute(), and graph_vnoiComputeImplied().

## ◆ vnoiCompute()

 static void vnoiCompute ( SCIP * scip, const GRAPH * g, DHEAP * dheap, VNOI * vnoi )
static

builds a Voronoi region w.r.t. shortest paths for all terminals

Parameters
 scip SCIP data structure g graph data structure dheap heap vnoi Voronoi data structure

Definition at line 153 of file graph_vnoi.c.

Referenced by graph_vnoiCompute().

## ◆ vnoiComputeImplied()

 static void vnoiComputeImplied ( const GRAPH * g, const SDPROFIT * sdprofit, DHEAP * dheap, VNOI * vnoi )
static

build a Voronoi region w.r.t. implied shortest paths for all terminals

Parameters
 g graph data structure sdprofit SD profit dheap heap vnoi Voronoi data structure

Definition at line 201 of file graph_vnoi.c.

Referenced by graph_vnoiComputeImplied().

## ◆ graph_voronoiExtend()

 SCIP_RETCODE graph_voronoiExtend ( SCIP * scip, const GRAPH * g, const 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 253 of file graph_vnoi.c.

Referenced by computeSteinerTreeVnoi().

## ◆ graph_voronoi()

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

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

Parameters
 g graph data structure cost edge costs costrev reversed edge costs (or NULL if symmetric) basemark 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 333 of file graph_vnoi.c.

Referenced by computeSteinerTreeVnoi(), and localKeyVertexHeuristics().

## ◆ graph_voronoiTerms()

 void graph_voronoiTerms ( const GRAPH * g, const SCIP_Bool * nodes_isTerm, int *RESTRICT vbase, PATH *RESTRICT path )

build a voronoi region, w.r.t. shortest paths, for all terminal NOTE: uses bias for PC!

Parameters
 g graph data structure nodes_isTerm for each node: is terminal? vbase array containing Voronoi base to each node path array containing Voronoi paths data

Definition at line 438 of file graph_vnoi.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 517 of file graph_vnoi.c.

Referenced by boundPruneHeurMw(), and reduce_boundMw().

## ◆ graph_voronoiWithDist()

 SCIP_RETCODE graph_voronoiWithDist ( SCIP * scip, const GRAPH * g, const SCIP_Bool * nodes_isTerm, const SCIP_Real * cost, SCIP_Real * distance, int * edges_isMinedgePred, int * vbase, int * minarc, 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 nodes_isTerm for each node: is terminal? cost edge costs distance array storing path from a terminal over shortest incident edge to nearest terminal edges_isMinedgePred 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' distnode array to store terminal corresponding to distance stored in distance array path array containing Voronoi paths data

Definition at line 597 of file graph_vnoi.c.

 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 774 of file graph_vnoi.c.

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

 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 973 of file graph_vnoi.c.

Referenced by reduce_boundMw().

## ◆ graph_voronoiRepair()

 void graph_voronoiRepair ( SCIP * scip, const GRAPH * g, const SCIP_Real * cost, const SCIP_Real * cost_org, int * nheapelems, 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 (possibly biased) cost_org original edge costs (only needed for PC) nheapelems 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 1100 of file graph_vnoi.c.

Referenced by localKeyVertexHeuristics().

## ◆ graph_voronoiRepairMult()

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

repair the Voronoi diagram for a given set nodes

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

Definition at line 1206 of file graph_vnoi.c.

## ◆ graph_vnoiInit()

 SCIP_RETCODE graph_vnoiInit ( SCIP * scip, const GRAPH * graph, SCIP_Bool useBufferArrays, VNOI ** vnoi )

initializes VNOI structure

Parameters
 scip SCIP graph graph data structure to work on useBufferArrays should buffer arrays be used? vnoi the VNOI

Definition at line 1265 of file graph_vnoi.c.

Referenced by sdgraphBuildDistgraph().

## ◆ graph_vnoiCompute()

 SCIP_RETCODE graph_vnoiCompute ( SCIP * scip, const GRAPH * graph, VNOI * vnoi )

computes Voronoi region on given graph

Parameters
 scip SCIP graph graph data structure to work on vnoi the VNOI

Definition at line 1302 of file graph_vnoi.c.

Referenced by sdgraphBuildDistgraph().

## ◆ graph_vnoiComputeImplied()

 SCIP_RETCODE graph_vnoiComputeImplied ( SCIP * scip, const GRAPH * graph, const SDPROFIT * sdprofit, VNOI * vnoi )

computes implied Voronoi region on given graph

Parameters
 scip SCIP graph graph data structure to work on sdprofit SD profit vnoi the VNOI

Definition at line 1323 of file graph_vnoi.c.

Referenced by sdgraphBuildDistgraph().

## ◆ graph_vnoiFree()

 void graph_vnoiFree ( SCIP * scip, VNOI ** vnoi )

frees VNOI structure

Parameters
 scip SCIP vnoi the VNOI

Definition at line 1348 of file graph_vnoi.c.

Referenced by sdgraphFinalize().