Detailed Description

Shortest path based graph algorithms for Steiner problems.

Author: Thorsten Koch; Henriette Franz; Daniel Rehfeldt

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

Definition in file graph_path.c.

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <assert.h>
#include "portab.h"
#include "graph.h"
#include "graphheaps.h"
#include "shortestpath.h"
#include "solstp.h"

Go to the source code of this file.

Functions
static void	pathheapCorrect (int RESTRICT heap, int RESTRICT state, int RESTRICT count, PATH RESTRICT path, int l, int k, int edge, SCIP_Real cost, int mode)

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

static void	pathheapReset (PATH RESTRICT path, int RESTRICT heap, int RESTRICT state, int RESTRICT count, int node)

static void	stPcmwConnectNode (int k, const GRAPH g, SPATHSPC spaths_pc, SCIP_Real pathdist, int pathedge, STP_Bool connected, int count, int *nterms)

static void	stPcmwInit (GRAPH g, SCIP_Real pathdist, int pathedge, STP_Bool connected, int *npseudoterms)

static void	stRpcmwInit (GRAPH g, SCIP_Real pathdist, int pathedge, STP_Bool connected, int *nrealterms)

static SCIP_Bool	stDcTermIsConnectable (const GRAPH g, int term, const int deg_free, const int pathedge, const STP_Bool connected)

static void	sdDcExtendTree (const GRAPH g, const SCIP_Real cost, int heapsize, int pathdeg_free, int nodedeg_free, SCIP_Real pathdist, int pathedge, STP_Bool connected, int result, int soldegfree, int *nsolterms)

void	graph_pathHeapAdd (const PATH path, int node, int RESTRICT heap, int RESTRICT state, int count)

SCIP_RETCODE	graph_path_init (SCIP scip, GRAPH g)

SCIP_Bool	graph_path_exists (const GRAPH *g)

void	graph_path_exit (SCIP scip, GRAPH g)

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

void	graph_pathInLimitedExec (const GRAPH g, const SCIP_Real edges_cost, const SCIP_Bool nodes_abort, int startnode, DIJK dijkdata, SCIP_Real *abortdistance)

void	graph_sdPaths (const GRAPH g, PATH path, const 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_pcmw_extendOut (SCIP scip, const GRAPH g, int start, STP_Bool connected, SCIP_Real dist, int pred, STP_Bool connected_out, DHEAP dheap, SCIP_Bool success)

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

SCIP_RETCODE	graph_path_st_dc (SCIP scip, const GRAPH g, const SCIP_Real cost, SCIP_Real pathdist, int pathedge, int start, STP_Bool connected, int result, STP_Bool solFound)

void	graph_path_st_pcmw (GRAPH g, SCIP_Real orderedprizes, int orderedprizes_id, const SCIP_Real cost, const SCIP_Real prize, SCIP_Bool costIsBiased, 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 (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, SCIP_Bool breakearly, PATH path, STP_Bool connected, SCIP_Bool extensions)

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

void	graph_path_st_rpcmw (GRAPH g, SCIP_Real orderedprizes, int orderedprizes_id, const SCIP_Real cost, const SCIP_Real prize, SCIP_Real pathdist, int pathedge, int start, STP_Bool connected)

SCIP_RETCODE	graph_path_st_brmwcs (SCIP scip, GRAPH g, const SCIP_Real prize, SCIP_Real pathdist, int pathedge, int start, STP_Bool connected, SCIP_Bool *solfound)

Function Documentation

◆ pathheapCorrect()

static void pathheapCorrect	(	int *RESTRICT	heap,
		int *RESTRICT	state,
		int *RESTRICT	count,
		PATH *RESTRICT	path,
		int	l,
		int	k,
		int	edge,
		SCIP_Real	cost,
		int	mode
	)

inlinestatic

Definition at line 50 of file graph_path.c.

References MST_MODE, and UNKNOWN.

Referenced by graph_path_exec(), graph_path_PcMwSd(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_extendBiased(), and graph_sdPaths().

◆ pathheapGetNearest()

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

inlinestatic

Definition at line 91 of file graph_path.c.

References GT, and LT.

Referenced by graph_path_exec(), graph_path_PcMwSd(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_extendBiased(), and graph_sdPaths().

◆ pathheapReset()

static void pathheapReset	(	PATH *RESTRICT	path,
		int *RESTRICT	heap,
		int *RESTRICT	state,
		int *RESTRICT	count,
		int	node
	)

inlinestatic

resets node

Definition at line 134 of file graph_path.c.

References GT.

Referenced by graph_path_st_pcmw_extend(), and graph_path_st_pcmw_extendBiased().

◆ stPcmwConnectNode()

static void stPcmwConnectNode	(	int	k,
		const GRAPH *	g,
		SPATHSPC *	spaths_pc,
		SCIP_Real *	pathdist,
		int *	pathedge,
		STP_Bool *	connected,
		int *	count,
		int *	nterms
	)

inlinestatic

connect given node to tree

Parameters

k	the vertex
g	graph data structure
spaths_pc	shortest paths data
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
connected	array to mark whether a vertex is part of computed Steiner tree
count	for the heap
nterms	terminal count

Definition at line 170 of file graph_path.c.

References Is_pseudoTerm, GRAPH::path_heap, GRAPH::path_state, resetX(), shortestpath_pcConnectNode(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by graph_path_st_pcmw().

◆ stPcmwInit()

static void stPcmwInit	(	GRAPH *	g,
		SCIP_Real *	pathdist,
		int *	pathedge,
		STP_Bool *	connected,
		int *	npseudoterms
	)

inlinestatic

initialize

Parameters

g	graph data structure
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
connected	array to mark whether a vertex is part of computed Steiner tree
npseudoterms	number of pseudo terminals

Definition at line 209 of file graph_path.c.

References FALSE, FARAWAY, GRAPH::grad, graph_get_nNodes(), Is_pseudoTerm, Is_term, GRAPH::mark, nnodes, GRAPH::path_state, GRAPH::term, and UNKNOWN.

Referenced by graph_path_st_pcmw(), and graph_path_st_pcmw_full().

◆ stRpcmwInit()

static void stRpcmwInit	(	GRAPH *	g,
		SCIP_Real *	pathdist,
		int *	pathedge,
		STP_Bool *	connected,
		int *	nrealterms
	)

inlinestatic

initialize

Parameters

g	graph data structure
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
connected	array to mark whether a vertex is part of computed Steiner tree
nrealterms	number of real terminals

Definition at line 240 of file graph_path.c.

References FALSE, FARAWAY, graph_get_nNodes(), graph_pc_knotIsFixedTerm(), graph_pc_markOrgGraph(), Is_pseudoTerm, GRAPH::mark, nnodes, GRAPH::path_state, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by graph_path_st_pcmw_full(), and graph_path_st_rpcmw().

◆ stDcTermIsConnectable()

static SCIP_Bool stDcTermIsConnectable	(	const GRAPH *	g,
		int	term,
		const int *	deg_free,
		const int *	pathedge,
		const STP_Bool *	connected
	)

inlinestatic

For DCSTP can terminal be connected to current tree?

Parameters

g	graph data structure
term	terminal to be checked
deg_free	free degree of each node
pathedge	predecessor edge array (on vertices)
connected	array to mark whether a vertex is part of computed Steiner tree

Definition at line 278 of file graph_path.c.

References FALSE, Is_term, SCIPdebugMessage, STP_DCSTP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by sdDcExtendTree().

◆ sdDcExtendTree()

static void sdDcExtendTree	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		int *	heapsize,
		int *	pathdeg_free,
		int *	nodedeg_free,
		SCIP_Real *	pathdist,
		int *	pathedge,
		STP_Bool *	connected,
		int *	result,
		int *	soldegfree,
		int *	nsolterms
	)

static

For DCSTP: extends (implicitly) given tree

Parameters

g	graph data structure
cost	edgecosts
heapsize	heap size
pathdeg_free	currently available degree of path
nodedeg_free	currently available degree of node
pathdist	distance array (on vertices)
pathedge	predecessor edge array (on vertices)
connected	array to mark whether a vertex is part of computed Steiner tree
result	solution array
soldegfree	per node: solution degree
nsolterms	number of solution terminals

Definition at line 327 of file graph_path.c.

References CONNECT, correctX(), EAT_LAST, EQ, GT, GRAPH::head, Is_term, nearestX(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIPdebugMessage, stDcTermIsConnectable(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by graph_path_st_dc().

◆ graph_pathHeapAdd()

void graph_pathHeapAdd	(	const PATH *	path,
		int	node,
		int *RESTRICT	heap,
		int *RESTRICT	state,
		int *	count
	)

adds element 'node' to heap

Definition at line 442 of file graph_path.c.

References GT.

◆ graph_path_init()

SCIP_RETCODE graph_path_init	(	SCIP *	scip,
		GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 480 of file graph_path.c.

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

Referenced by bdkInit(), boundPruneHeur(), checkSdWalk(), computeReducedProbSolution(), createModel(), extractSubgraphBuild(), graphBuildV5E5(), initReceivedSubproblem(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), propgraphApplyBoundchanges(), prunegraphInit(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), reduce_bd34(), reduce_bd34WithSd(), reduce_bound(), reduce_boundHop(), reduce_daPcMw(), reduce_exec(), reduce_impliedProfitBasedRpc(), reduce_npv(), reduce_sd(), runDualAscent(), SCIP_DECL_PROBCOPY(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurSlackPruneRun(), sdgraphMstBuild(), stptest_graphSetUp(), subgraphBuild(), substpsolver_solve(), supergraphComputeMst(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), and testSdGetterReturnsCorrectSds().

◆ graph_path_exists()

SCIP_Bool graph_path_exists ( const GRAPH * g )

existing?

Parameters

g	graph data structure

Definition at line 497 of file graph_path.c.

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

Referenced by graph_free(), reduce_exec(), and substpsolver_solve().

◆ graph_path_exit()

void graph_path_exit	(	SCIP *	scip,
		GRAPH *	g
	)

Parameters

scip	SCIP data structure
g	graph data structure

Definition at line 515 of file graph_path.c.

References GRAPH::path_heap, GRAPH::path_state, and SCIPfreeMemoryArrayNull.

Referenced by bdkFree(), boundPruneHeur(), checkSdWalk(), computeReducedProbSolution(), fixVarsRedbased(), graph_free(), graph_pack(), graph_subgraphFree(), graph_subgraphReinsert(), initReceivedSubproblem(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), lurkpruneFinalize(), pseudoAncestorsCreation(), pseudoAncestorsHash(), pseudoAncestorsHashPc(), pseudoAncestorsMerge(), pseudoAncestorsMergePc(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), reduce_bd34(), reduce_bd34WithSd(), reduce_bound(), reduce_boundHop(), reduce_daPcMw(), reduce_exec(), reduce_impliedProfitBasedRpc(), reduce_npv(), reduce_sd(), runDualAscent(), SCIP_DECL_PROBDELORIG(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurSlackPruneRun(), SCIPStpPropGetGraph(), sdgraphMstBuild(), stptest_graphTearDown(), supergraphComputeMst(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), and testDistRootPathsAreValid().

◆ graph_path_exec()

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

Parameters

scip	SCIP data structure
g	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 541 of file graph_path.c.

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

Referenced by bdkStarIsSdMstReplacable(), blctreeBuildMst(), boundPruneHeur(), createVariables(), graph_findCentralTerminal(), isPseudoDeletable(), pcsolGetMstEdges(), pricing(), pruneSteinerTreeStp(), reduce_bound(), reduce_boundHop(), reduce_daSlackPrune(), reduce_npv(), reduce_sd(), reduce_termcompChangeSubgraphToBottleneck(), SCIPprobdataAddNewSol(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreePcMw(), sdgraphMstBuild(), supergraphComputeMst(), and tryPathPcMw().

◆ graph_pathInLimitedExec()

void graph_pathInLimitedExec	(	const GRAPH *	g,
		const SCIP_Real *	edges_cost,
		const SCIP_Bool *	nodes_abort,
		int	startnode,
		DIJK *	dijkdata,
		SCIP_Real *	abortdistance
	)

limited Dijkstra on incoming edges

Parameters

g	graph data structure
edges_cost	edge cost
nodes_abort	nodes to abort at
startnode	start
dijkdata	Dijkstra data
abortdistance	distance at which abort happened

Definition at line 610 of file graph_path.c.

References CONNECT, dijkstra_data::dheap, FARAWAY, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_knot_isInRange(), GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, LT, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dijkstra_heap::position, SCIP_Real, dijkstra_heap::size, GRAPH::tail, TRUE, UNKNOWN, and dijkstra_data::visitlist.

Referenced by dapathsRunShortestPaths().

◆ graph_sdPaths()

void graph_sdPaths	(	const GRAPH *	g,
		PATH *	path,
		const 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

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 684 of file graph_path.c.

References CONNECT, shortest_path::dist, FALSE, FARAWAY, FSP_MODE, GE, GRAPH::grad, graph_pc_isMw(), graph_typeIsUndirected(), GT, GRAPH::head, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, pathheapCorrect(), pathheapGetNearest(), SCIP_Bool, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_getSdByPaths(), 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 788 of file graph_path.c.

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

Referenced by reduce_sdsp(), and sdGetSdPcMw().

◆ 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 905 of file graph_path.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 buildTmAllSp(), computeStarts(), computeTransVoronoi(), getRedCost2ndNextDistances(), redcosts_initializeDistances(), reduce_boundHopR(), reduce_boundHopRc(), reduce_daPcMw(), reduce_daSlackPrune(), and reduce_rpt().

◆ 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 973 of file graph_path.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_pcmw_extendOut()

void graph_path_st_pcmw_extendOut	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		STP_Bool *	connected,
		SCIP_Real *	dist,
		int *	pred,
		STP_Bool *	connected_out,
		DHEAP *	dheap,
		SCIP_Bool *	success
	)

extension heuristic

Parameters

scip	SCIP data structure
g	graph data structure
start	start
connected	array to mark whether a vertex is part of computed Steiner tree
dist	distances array
pred	predecessor node
connected_out	array for internal stuff
dheap	Dijkstra heap
success	extension successful?

Definition at line 1051 of file graph_path.c.

References csr_storage::cost, GRAPH::csr_storage, GRAPH::extended, FALSE, FARAWAY, graph_heap_clean(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), csr_storage::head, Is_term, GRAPH::knots, nnodes, dijkstra_heap::position, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), dijkstra_heap::size, csr_storage::start, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurLocalExtendPcMwOut().

◆ graph_path_st()

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

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

Parameters

g	graph data structure
cost	edgecosts
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 1199 of file graph_path.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_dc()

SCIP_RETCODE graph_path_st_dc	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		SCIP_Real *	pathdist,
		int *	pathedge,
		int	start,
		STP_Bool *	connected,
		int *	result,
		STP_Bool *	solFound
	)

For DCSTP: Find a directed tree rooted in node 'start' and spanning all terminals, while respecting degree constraints

Parameters

scip	SCIP
g	graph data structure
cost	edgecosts
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
result	solution
solFound	pointer to store whether solution was found

Definition at line 1299 of file graph_path.c.

References BMScopyMemoryArray, FALSE, FARAWAY, graph_get_nEdges(), graph_get_nNodes(), graph_knot_isInRange(), graph_knot_printInfo(), Is_term, GRAPH::maxdeg, nnodes, GRAPH::path_heap, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, sdDcExtendTree(), STP_DCSTP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

◆ graph_path_st_pcmw()

void graph_path_st_pcmw	(	GRAPH *	g,
		SCIP_Real *	orderedprizes,
		int *	orderedprizes_id,
		const SCIP_Real *	cost,
		const SCIP_Real *	prize,
		SCIP_Bool	costIsBiased,
		SCIP_Real *	pathdist,
		int *	pathedge,
		int	start,
		STP_Bool *	connected
	)

!!!LEGACY CODE!!! 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

g	graph data structure
orderedprizes	legacy code
orderedprizes_id	legacy code
cost	edge costs
prize	(possibly biased) prize
costIsBiased	is cost biased?
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 1430 of file graph_path.c.

References correctX(), EAT_LAST, GRAPH::extended, FALSE, FARAWAY, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsNonLeafTerm(), GRAPH::head, Is_pseudoTerm, GRAPH::knots, LT, GRAPH::mark, stortest_path_prizecollecting::maxoutprize, nearestX(), nnodes, nterms, GRAPH::oeat, stortest_path_prizecollecting::orderedprizes, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_Bool, SCIP_Real, SCIPdebugMessage, shortestpath_pcConnectNode(), shortestpath_pcReset(), stPcmwConnectNode(), stPcmwInit(), GRAPH::tail, GRAPH::term, 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 1556 of file graph_path.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	(	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

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 1608 of file graph_path.c.

References correctX(), GRAPH::extended, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GT, GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), stPcmwInit(), stRpcmwInit(), 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,
		SCIP_Bool	breakearly,
		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
breakearly	finish computation early if no profitable extension possible?
path	shortest paths data structure
connected	array to mark whether a vertex is part of computed Steiner tree
extensions	extensions performed?

Definition at line 1706 of file graph_path.c.

References shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, FSP_MODE, GRAPH::grad, GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, pathheapCorrect(), pathheapGetNearest(), pathheapReset(), GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ graph_path_st_pcmw_extendBiased()

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

greedy extension of a given tree for PC or MW problems; path[i].edge needs to be initialized

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
prize	(possibly biased) prize
path	shortest paths data structure with .edge initialized
connected	array to mark whether a vertex is part of computed Steiner tree
extensions	extensions performed?

Definition at line 1845 of file graph_path.c.

References shortest_path::dist, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, FSP_MODE, graph_pc_knotIsFixedTerm(), graph_pc_markOrgGraph(), GRAPH::head, Is_pseudoTerm, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, pathheapCorrect(), pathheapGetNearest(), pathheapReset(), SCIP_Real, SCIPisGE(), GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

◆ graph_path_st_rpcmw()

void graph_path_st_rpcmw	(	GRAPH *	g,
		SCIP_Real *	orderedprizes,
		int *	orderedprizes_id,
		const SCIP_Real *	cost,
		const SCIP_Real *	prize,
		SCIP_Real *	pathdist,
		int *	pathedge,
		int	start,
		STP_Bool *	connected
	)

!!!LEGACY CODE!!! Shortest path heuristic for the RMWCSP and RPCSPG 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

g	graph data structure
orderedprizes	legacy code
orderedprizes_id	legacy code
cost	edge costs
prize	(possibly biased) prize
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 1988 of file graph_path.c.

References correctX(), GRAPH::extended, FARAWAY, GE, graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), GRAPH::head, Is_anyTerm, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, stortest_path_prizecollecting::maxoutprize, nearestX(), nnodes, nterms, GRAPH::oeat, stortest_path_prizecollecting::orderedprizes, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIPdebugMessage, shortestpath_pcConnectNode(), shortestpath_pcReset(), stRpcmwInit(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_path_st_brmwcs()

SCIP_RETCODE graph_path_st_brmwcs	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	prize,
		SCIP_Real *	pathdist,
		int *	pathedge,
		int	start,
		STP_Bool *	connected,
		SCIP_Bool *	solfound
	)

todo refactor, was copied from Henriette's branch

Parameters

scip	SCIP data structure
g	graph data structure
prize	(possibly biased) prize
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
solfound	could a solution be found?

Definition at line 2146 of file graph_path.c.

References GRAPH::budget, correctX(), GRAPH::costbudget, EAT_LAST, FALSE, FARAWAY, graph_pc_markOrgGraph(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkBMw().

SCIP

Detailed Description

Functions

Function Documentation

◆ pathheapCorrect()

◆ pathheapGetNearest()

◆ pathheapReset()

◆ stPcmwConnectNode()

◆ stPcmwInit()

◆ stRpcmwInit()

◆ stDcTermIsConnectable()

◆ sdDcExtendTree()

◆ graph_pathHeapAdd()

◆ graph_path_init()

◆ graph_path_exists()

◆ graph_path_exit()

◆ graph_path_exec()

◆ graph_pathInLimitedExec()

◆ graph_sdPaths()

◆ graph_path_PcMwSd()

◆ graph_path_execX()

◆ graph_path_invroot()

◆ graph_path_st_pcmw_extendOut()

◆ graph_path_st()

◆ graph_path_st_dc()

◆ graph_path_st_pcmw()

◆ graph_path_st_pcmw_reduce()

◆ graph_path_st_pcmw_full()

◆ graph_path_st_pcmw_extend()

◆ graph_path_st_pcmw_extendBiased()

◆ graph_path_st_rpcmw()

◆ graph_path_st_brmwcs()