Detailed Description

Voronoi graph algorithms for Steiner problems.

Author: Daniel Rehfeldt

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)

Function Documentation

◆ 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.

Referenced by graph_voronoi(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiRepairMult(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), and graph_voronoiWithRadiusMw().

◆ 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.

Referenced by graph_voronoi(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiRepairMult(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), and graph_voronoiWithRadiusMw().

◆ 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.

References FARAWAY, graph_get_nNodes(), graph_heap_correct(), graph_heap_isClean(), Is_term, nnodes, voronoi_storage::nodes_base, voronoi_storage::nodes_dist, voronoi_storage::nodes_predEdge, dijkstra_heap::position, SCIP_Real, GRAPH::term, and UNKNOWN.

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.

References CONNECT, GRAPH::cost, graph_get_nNodes(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), GT, GRAPH::head, voronoi_storage::nodes_base, voronoi_storage::nodes_dist, voronoi_storage::nodes_predEdge, GRAPH::oeat, GRAPH::outbeg, dijkstra_heap::position, SCIP_Real, and dijkstra_heap::size.

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.

References CONNECT, GRAPH::cost, graph_get_nNodes(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), GT, GRAPH::head, voronoi_storage::nodes_base, voronoi_storage::nodes_dist, voronoi_storage::nodes_predEdge, GRAPH::oeat, GRAPH::outbeg, dijkstra_heap::position, reduce_sdprofitGetProfit(), SCIP_Real, dijkstra_heap::size, and GRAPH::tail.

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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, GT, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_OKAY, GRAPH::term, and TRUE.

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.

References CONNECT, correct(), shortest_path::dist, shortest_path::edge, FARAWAY, GT, GRAPH::head, GRAPH::knots, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::source, and UNKNOWN.

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.

References CONNECT, correct(), GRAPH::cost, EAT_LAST, FARAWAY, GE, graph_get_nNodes(), graph_pc_isPc(), GT, GRAPH::head, LE, GRAPH::mark, nearest(), nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_Real, and UNKNOWN.

◆ 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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), GRAPH::term, and UNKNOWN.

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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, EQ, FALSE, FARAWAY, GE, graph_edge_isInRange(), graph_get_nNodes(), graph_pc_isPc(), GRAPH::head, LE, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisLT(), GRAPH::tail, TRUE, and UNKNOWN.

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

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::extended, FARAWAY, graph_edge_add(), graph_knot_add(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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

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

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::term, GRAPH::terms, and UNKNOWN.

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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FARAWAY, graph_get_nNodes(), graph_pc_isPc(), graph_pc_isPcMw(), GRAPH::head, GRAPH::mark, nearest(), nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPStpunionfindFind(), and UNKNOWN.

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