Detailed Description

Shortest path based graph algorithms for Steiner problems.

Author: Thorsten Koch; Daniel Rehfeldt

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)

Function Documentation

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

Referenced by getlecloseterms(), graph_get2next(), graph_get3next(), graph_get4next(), graph_path_exec(), graph_path_PcMwSd(), graph_path_st_pcmw_extend(), graph_sdPaths(), graph_voronoi(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiRepairMult(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), and graph_voronoiWithRadiusMw().

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

Referenced by graph_path_execX(), graph_path_invroot(), graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_full(), graph_path_st_rmw(), and graph_path_st_rpc().

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

Referenced by getlecloseterms(), graph_get2next(), graph_get3next(), graph_get4next(), graph_path_exec(), graph_path_PcMwSd(), graph_path_st_pcmw_extend(), graph_sdPaths(), graph_voronoi(), graph_voronoiExtend(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiRepairMult(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), and graph_voronoiWithRadiusMw().

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

Referenced by graph_path_execX(), graph_path_invroot(), graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_full(), graph_path_st_rmw(), and graph_path_st_rpc().

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

Referenced by graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_full(), graph_path_st_rmw(), and graph_path_st_rpc().

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

References GRAPH::knots, NULL, GRAPH::path_heap, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by initReceivedSubproblem(), redbasedVarfixing(), reduce(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), SCIP_DECL_PROBCOPY(), SCIPprobdataCreate(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

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

Referenced by graph_pack(), initReceivedSubproblem(), redbasedVarfixing(), reduce(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), SCIP_DECL_PROBDELORIG(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), and SCIPStpHeurSlackPruneRunPcMw().

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

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, MST_MODE, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and UNKNOWN.

Referenced by central_terminal(), createVariables(), getlecloseterms(), pricing(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHop(), reduce_boundPrune(), reduce_daSlackPrune(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_sd(), SCIPprobdataAddNewSol(), SCIPStpHeurLocalRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrune(), and SCIPStpHeurTMPrunePc().

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

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

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.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::head, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), and UNKNOWN.

Referenced by computeTransVoronoi(), reduce_boundHopR(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_rpt(), SCIPStpHeurTMRun(), and setVnoiDistances().

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

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::path_heap, GRAPH::path_state, SCIP_Real, SCIPisGT(), GRAPH::source, GRAPH::tail, and UNKNOWN.

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

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGT(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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.

References CONNECT, EAT_LAST, FALSE, GRAPH::head, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPfreeBufferArray, SCIPisGE(), GRAPH::term, and UNKNOWN.

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

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIPisGT(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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.

References correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, FSP_MODE, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, reset(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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.

References correctX(), GRAPH::cost, EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FSP_MODE, 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	(	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.

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

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.

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

Referenced by graph_get3nextTerms(), graph_get4nextTerms(), reduce_bound(), reduce_boundHop(), reduce_boundMw(), reduce_boundPrune(), and reduce_daPcMw().

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

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

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.

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

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.

References GRAPH::grad, graph_get2next(), graph_get3next(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

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

References GRAPH::grad, graph_get2next(), graph_get3next(), graph_get4next(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

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.

References shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, UNKNOWN, and utdist().

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.

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

Referenced by computeTransVoronoi(), graph_get3nextTerms(), graph_get4nextTerms(), reduce_boundHopR(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_sl(), and setVnoiDistances().

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

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

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.

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisLT(), GRAPH::tail, GRAPH::term, 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 2614 of file grphpath.c.

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, FARAWAY, FSP_MODE, graph_edge_add(), graph_knot_add(), 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(), SCIPisLT(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, 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,
		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.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), SCIPStpunionfindFind(), GRAPH::tail, and UNKNOWN.

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.

References CONNECT, correct(), EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), and SCIPStpunionfindFind().

Referenced by SCIPStpHeurLocalRun().

SCIP

Detailed Description

Functions

Function Documentation

◆ nearest()

◆ nearestX()

◆ correct()

◆ correctX()

◆ heap_add()

◆ resetX()

◆ reset()

◆ utdist()

◆ graph_path_init()

◆ graph_path_exit()

◆ graph_path_exec()

◆ graph_sdPaths()

◆ graph_path_PcMwSd()

◆ graph_path_execX()

◆ graph_path_invroot()

◆ graph_path_st()

◆ graph_path_st_rpc()

◆ graph_path_st_pcmw()

◆ graph_path_st_pcmw_reduce()

◆ graph_path_st_pcmw_full()

◆ graph_path_st_pcmw_extend()

◆ graph_path_st_rmw()

◆ graph_voronoiExtend()

◆ graph_voronoi()

◆ graph_get2next()

◆ graph_get3next()

◆ graph_get4next()

◆ graph_get3nextTerms()

◆ graph_get4nextTerms()

◆ graph_get4nextTTerms()

◆ graph_voronoiTerms()

◆ graph_voronoiMw()

◆ graph_voronoiWithDist()

◆ graph_voronoiWithRadius()

◆ graph_voronoiWithRadiusMw()

◆ graph_voronoiRepair()

◆ graph_voronoiRepairMult()