Detailed Description

Shortest path based algorithms for Steiner problems.

Author: Daniel Rehfeldt

This file encompasses various shortest path based algorithms. Note: This file is supposed to replace graph_path.c in the long run, as it includes the faster implementations.

Definition in file shortestpath.c.

#include "reduce.h"
#include "shortestpath.h"
#include "portab.h"
#include "stpvector.h"

Go to the source code of this file.

Functions
static SCIP_Bool	computeSteinerTree_allTermsAreReached (const GRAPH g, const STP_Bool connected)

static SCIP_Bool	computeSteinerTree_allPseudoTermsAreReached (const GRAPH g, const STP_Bool connected)

static SCIP_Bool	computeSteinerTree_allFixedTermsAreReached (const GRAPH g, const STP_Bool connected)

static void	computeSteinerTree_init (const GRAPH g, int startnode, SPATHS spaths)

static void	computeSteinerTree_connectTerminal (const GRAPH g, int k, const int nodes_pred, SCIP_Real RESTRICT nodes_dist, DHEAP dheap, STP_Bool *RESTRICT connected)

static void	computeSteinerTree_connectNode (const GRAPH g, int k, const int nodes_pred, SCIP_Real RESTRICT nodes_dist, DHEAP dheap, int termscount, STP_Bool RESTRICT connected)

static void	computeSteinerTree_exec (const GRAPH g, int startnode, SPATHS spaths)

static void	computeSteinerTree_execDirected (SCIP scip, const GRAPH g, int startnode, SPATHS *spaths)

static void	computeSteinerTree_execBiased (const GRAPH g, const SDPROFIT sdprofit, int startnode, SPATHS *spaths)

static void	computeSteinerTree_connectPseudoTerm (const GRAPH g, int k, const int nodes_pred, SCIP_Real RESTRICT nodes_dist, SPATHSPC spaths_pc, DHEAP dheap, STP_Bool RESTRICT connected, int *RESTRICT nPseudoTerms)

static void	computeSteinerTree_tryConnectNodePcMw (const GRAPH g, int k, const SCIP_Real prize, SCIP_Bool costIsBiased, const int nodes_pred, SCIP_Real RESTRICT nodes_dist, DHEAP dheap, STP_Bool RESTRICT connected, SPATHSPC spaths_pc, SCIP_Bool isConnected, int *RESTRICT nPseudoTerms)

static void	computeSteinerTree_execPcMw (const GRAPH g, int startnode, const SCIP_Real prize, SCIP_Bool costIsBiased, SPATHSPC spaths_pc, SPATHS spaths)

static void	computeSteinerTree_execRpcMw (const GRAPH g, int startnode, const SCIP_Real prize, SPATHSPC spaths_pc, SPATHS spaths)

static void	computeSteinerTree_execPcMwFull (const GRAPH g, int startnode, SPATHS spaths)

SCIP_RETCODE	shortestpath_pcInit (SCIP scip, const GRAPH graph, const SCIP_Real costs, const SCIP_Real prizes, SPATHSPC **sppc)

void	shortestpath_pcFree (SCIP scip, SPATHSPC *sppc)

void	shortestpath_pcReset (SPATHSPC *sppc)

void	shortestpath_pcConnectNode (const GRAPH g, const STP_Bool connected, int node_connected, SPATHSPC *sppc)

void	shortestpath_computeSteinerTree (const GRAPH g, int startnode, SPATHS spaths)

void	shortestpath_computeSteinerTreeDirected (SCIP scip, const GRAPH g, int startnode, SPATHS *spaths)

void	shortestpath_computeSteinerTreeBiased (const GRAPH g, const SDPROFIT sdprofit, int startnode, SPATHS *spaths)

void	shortestpath_computeSteinerTreePcMw (const GRAPH g, int startnode, const SCIP_Real prize, SCIP_Bool costIsBiased, SPATHSPC spaths_pc, SPATHS spaths)

void	shortestpath_computeSteinerTreeRpcMw (const GRAPH g, int startnode, const SCIP_Real prize, SPATHSPC spaths_pc, SPATHS spaths)

void	shortestpath_computeSteinerTreePcMwFull (const GRAPH g, int startnode, SPATHS spaths)

Function Documentation

◆ computeSteinerTree_allTermsAreReached()

static SCIP_Bool computeSteinerTree_allTermsAreReached	(	const GRAPH *	g,
		const STP_Bool *	connected
	)

static

all terminals reached?

Parameters

g	graph data structure
connected	array to mark whether a vertex is part of computed Steiner tree

Definition at line 35 of file shortestpath.c.

References FALSE, graph_get_nNodes(), Is_term, nnodes, SCIPdebugMessage, GRAPH::term, and TRUE.

Referenced by shortestpath_computeSteinerTree(), shortestpath_computeSteinerTreeBiased(), and shortestpath_computeSteinerTreeDirected().

◆ computeSteinerTree_allPseudoTermsAreReached()

static SCIP_Bool computeSteinerTree_allPseudoTermsAreReached	(	const GRAPH *	g,
		const STP_Bool *	connected
	)

static

all pseudo terminals reached?

Parameters

g	graph data structure
connected	array to mark whether a vertex is part of computed Steiner tree

Definition at line 57 of file shortestpath.c.

References FALSE, graph_get_nNodes(), graph_pc_isPcMw(), Is_pseudoTerm, nnodes, GRAPH::term, and TRUE.

Referenced by computeSteinerTree_execPcMw().

◆ computeSteinerTree_allFixedTermsAreReached()

static SCIP_Bool computeSteinerTree_allFixedTermsAreReached	(	const GRAPH *	g,
		const STP_Bool *	connected
	)

static

all fixed terminals reached?

Parameters

g	graph data structure
connected	array to mark whether a vertex is part of computed Steiner tree

Definition at line 80 of file shortestpath.c.

References FALSE, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), nnodes, and TRUE.

Referenced by computeSteinerTree_execPcMwFull(), and computeSteinerTree_execRpcMw().

◆ computeSteinerTree_init()

static void computeSteinerTree_init	(	const GRAPH *	g,
		int	startnode,
		SPATHS *	spaths
	)

inlinestatic

initializes

Parameters

g	graph data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 104 of file shortestpath.c.

References stortest_paths::csr, stortest_paths::dheap, GRAPH::edges, FALSE, FARAWAY, graph_get_nNodes(), graph_heap_clean(), graph_heap_correct(), nnodes, csr_storage::nnodes, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, dijkstra_heap::position, SCIP_Real, dijkstra_heap::size, csr_storage::start, TRUE, and UNKNOWN.

Referenced by shortestpath_computeSteinerTree(), shortestpath_computeSteinerTreeBiased(), shortestpath_computeSteinerTreeDirected(), shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreePcMwFull(), and shortestpath_computeSteinerTreeRpcMw().

◆ computeSteinerTree_connectTerminal()

static void computeSteinerTree_connectTerminal	(	const GRAPH *	g,
		int	k,
		const int *	nodes_pred,
		SCIP_Real *RESTRICT	nodes_dist,
		DHEAP *	dheap,
		STP_Bool *RESTRICT	connected
	)

inlinestatic

connects (also PC/MW potential) terminal to current tree

Parameters

g	graph data structure
k	vertex to connect
nodes_pred	predecessor array (on vertices)
nodes_dist	distance array (on vertices)
dheap	Dijkstra heap
connected	array to mark whether a vertex is part of computed Steiner tree

Definition at line 147 of file shortestpath.c.

References graph_heap_correct(), Is_pseudoTerm, Is_term, SCIPdebugMessage, GRAPH::term, and TRUE.

Referenced by computeSteinerTree_exec(), computeSteinerTree_execBiased(), and computeSteinerTree_execPcMwFull().

◆ computeSteinerTree_connectNode()

static void computeSteinerTree_connectNode	(	const GRAPH *	g,
		int	k,
		const int *	nodes_pred,
		SCIP_Real *RESTRICT	nodes_dist,
		DHEAP *	dheap,
		int *	termscount,
		STP_Bool *RESTRICT	connected
	)

inlinestatic

connects node to current tree

Parameters

g	graph data structure
k	vertex to connect
nodes_pred	predecessor array (on vertices)
nodes_dist	distance array (on vertices)
dheap	Dijkstra heap
termscount	pointer for terminal count
connected	array to mark whether a vertex is part of computed Steiner tree

Definition at line 182 of file shortestpath.c.

References graph_heap_correct(), Is_term, SCIPdebugMessage, GRAPH::term, and TRUE.

Referenced by computeSteinerTree_execDirected().

◆ computeSteinerTree_exec()

static void computeSteinerTree_exec	(	const GRAPH *	g,
		int	startnode,
		SPATHS *	spaths
	)

inlinestatic

executes

Parameters

g	graph data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 224 of file shortestpath.c.

References computeSteinerTree_connectTerminal(), CONNECT, csr_storage::cost, stortest_paths::csr, stortest_paths::dheap, graph_heap_correct(), graph_heap_deleteMinReturnNode(), csr_storage::head, Is_term, LT, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, dijkstra_heap::position, SCIP_Real, SCIPdebugMessage, dijkstra_heap::size, csr_storage::start, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by shortestpath_computeSteinerTree().

◆ computeSteinerTree_execDirected()

static void computeSteinerTree_execDirected	(	SCIP *	scip,
		const GRAPH *	g,
		int	startnode,
		SPATHS *	spaths
	)

inlinestatic

Executes directed Steiner tree computation. Here we always start from the root, but connect the 'startnode' vertex first

Parameters

scip	SCIP data structure
g	graph data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 304 of file shortestpath.c.

References computeSteinerTree_connectNode(), CONNECT, csr_storage::cost, stortest_paths::csr, stortest_paths::dheap, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_typeIsDirected(), csr_storage::head, Is_term, LT, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, NULL, dijkstra_heap::position, SCIP_Real, SCIPdebugMessage, dijkstra_heap::size, GRAPH::source, csr_storage::start, STP_Vectype, StpVecFree, StpVecGetSize, StpVecPushBack, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by shortestpath_computeSteinerTreeDirected().

◆ computeSteinerTree_execBiased()

static void computeSteinerTree_execBiased	(	const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		int	startnode,
		SPATHS *	spaths
	)

inlinestatic

executes

Parameters

g	graph data structure
sdprofit	implied profit data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 408 of file shortestpath.c.

References computeSteinerTree_connectTerminal(), CONNECT, csr_storage::cost, stortest_paths::csr, stortest_paths::dheap, stortest_paths::edgecost_zeroOffset, EQ, FARAWAY, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_knot_isInRange(), graph_typeIsSpgLike(), GT, csr_storage::head, Is_term, LT_HARD, special_distance_implied_profit::nodes_bias, special_distance_implied_profit::nodes_biassource, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, dijkstra_heap::position, SCIP_Real, SCIPdebugMessage, dijkstra_heap::size, csr_storage::start, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by shortestpath_computeSteinerTreeBiased().

◆ computeSteinerTree_connectPseudoTerm()

static void computeSteinerTree_connectPseudoTerm	(	const GRAPH *	g,
		int	k,
		const int *	nodes_pred,
		SCIP_Real *RESTRICT	nodes_dist,
		SPATHSPC *	spaths_pc,
		DHEAP *	dheap,
		STP_Bool *RESTRICT	connected,
		int *RESTRICT	nPseudoTerms
	)

inlinestatic

connects node to current tree

Parameters

g	graph data structure
k	vertex to connect
nodes_pred	predecessor array (on vertices)
nodes_dist	distance array (on vertices)
spaths_pc	PC/MW shortest paths data
dheap	Dijkstra heap
connected	array to mark whether a vertex is part of computed Steiner tree
nPseudoTerms	pointer

Definition at line 511 of file shortestpath.c.

References graph_heap_correct(), Is_pseudoTerm, Is_term, SCIPdebugMessage, shortestpath_pcConnectNode(), GRAPH::term, and TRUE.

Referenced by computeSteinerTree_tryConnectNodePcMw().

◆ computeSteinerTree_tryConnectNodePcMw()

static void computeSteinerTree_tryConnectNodePcMw	(	const GRAPH *	g,
		int	k,
		const SCIP_Real *	prize,
		SCIP_Bool	costIsBiased,
		const int *	nodes_pred,
		SCIP_Real *RESTRICT	nodes_dist,
		DHEAP *	dheap,
		STP_Bool *RESTRICT	connected,
		SPATHSPC *	spaths_pc,
		SCIP_Bool *	isConnected,
		int *RESTRICT	nPseudoTerms
	)

inlinestatic

connects node to current tree

Parameters

g	graph data structure
k	vertex to connect
prize	(possibly biased) prize
costIsBiased	is cost biased?
nodes_pred	predecessor array (on vertices)
nodes_dist	distance array (on vertices)
dheap	Dijkstra heap
connected	array to mark whether a vertex is part of computed Steiner tree
spaths_pc	PC/MW shortest paths data
isConnected	node connected to tree?
nPseudoTerms	pointer

Definition at line 556 of file shortestpath.c.

References computeSteinerTree_connectPseudoTerm(), FALSE, FARAWAY, GE, graph_pc_isPc(), graph_pc_knotIsNonLeafTerm(), Is_pseudoTerm, LT, SCIP_Bool, SCIP_Real, and GRAPH::term.

Referenced by computeSteinerTree_execPcMw().

◆ computeSteinerTree_execPcMw()

static void computeSteinerTree_execPcMw	(	const GRAPH *	g,
		int	startnode,
		const SCIP_Real *	prize,
		SCIP_Bool	costIsBiased,
		SPATHSPC *	spaths_pc,
		SPATHS *	spaths
	)

inlinestatic

executes

Parameters

g	graph data structure
startnode	start vertex
prize	(possibly biased) prize
costIsBiased	is cost biased?
spaths_pc	PC/MW shortest paths data
spaths	shortest paths data

Definition at line 607 of file shortestpath.c.

References computeSteinerTree_allPseudoTermsAreReached(), computeSteinerTree_tryConnectNodePcMw(), CONNECT, csr_storage::cost, stortest_paths::csr, stortest_paths::dheap, GRAPH::extended, FALSE, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_nNonFixedTerms(), csr_storage::head, Is_pseudoTerm, LT, stortest_path_prizecollecting::maxoutprize, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, dijkstra_heap::position, SCIP_Bool, SCIP_Real, SCIPdebugMessage, shortestpath_pcConnectNode(), shortestpath_pcReset(), dijkstra_heap::size, csr_storage::start, GRAPH::term, and UNKNOWN.

Referenced by shortestpath_computeSteinerTreePcMw().

◆ computeSteinerTree_execRpcMw()

static void computeSteinerTree_execRpcMw	(	const GRAPH *	g,
		int	startnode,
		const SCIP_Real *	prize,
		SPATHSPC *	spaths_pc,
		SPATHS *	spaths
	)

inlinestatic

executes

Parameters

g	graph data structure
startnode	start vertex
prize	(possibly biased) prize
spaths_pc	PC/MW shortest paths data
spaths	shortest paths data

Definition at line 699 of file shortestpath.c.

References computeSteinerTree_allFixedTermsAreReached(), CONNECT, csr_storage::cost, stortest_paths::csr, stortest_paths::dheap, EQ, GRAPH::extended, GE, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_nFixedTerms(), csr_storage::head, Is_anyTerm, Is_pseudoTerm, Is_term, stortest_path_prizecollecting::maxoutprize, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, dijkstra_heap::position, SCIP_Real, SCIPdebugMessage, shortestpath_pcConnectNode(), shortestpath_pcReset(), dijkstra_heap::size, csr_storage::start, GRAPH::term, TRUE, and UNKNOWN.

Referenced by shortestpath_computeSteinerTreeRpcMw().

◆ computeSteinerTree_execPcMwFull()

static void computeSteinerTree_execPcMwFull	(	const GRAPH *	g,
		int	startnode,
		SPATHS *	spaths
	)

inlinestatic

executes

Parameters

g	graph data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 809 of file shortestpath.c.

References computeSteinerTree_allFixedTermsAreReached(), computeSteinerTree_connectTerminal(), CONNECT, csr_storage::cost, stortest_paths::csr, stortest_paths::dheap, GRAPH::extended, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), csr_storage::head, Is_pseudoTerm, Is_term, LT, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, nterms, dijkstra_heap::position, SCIP_Real, SCIPdebugMessage, dijkstra_heap::size, csr_storage::start, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by shortestpath_computeSteinerTreePcMwFull().

◆ shortestpath_pcInit()

SCIP_RETCODE shortestpath_pcInit	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	costs,
		const SCIP_Real *	prizes,
		SPATHSPC **	sppc
	)

initializes

Parameters

scip	SCIP data structure
graph	graph data structure
costs	cost for edges (might be negative for MWCS or RMWCS)
prizes	prizes for all nodes
sppc	PC/MW shortest path data

Definition at line 893 of file shortestpath.c.

References EAT_LAST, GRAPH::extended, FARAWAY, graph_get_nNodes(), graph_pc_isPcMw(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, nnodes, nterms, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, SCIPsortDownRealInt(), STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by runTmPcMW_mode().

◆ shortestpath_pcFree()

void shortestpath_pcFree	(	SCIP *	scip,
		SPATHSPC **	sppc
	)

frees

Parameters

scip	SCIP data structure
sppc	PC/MW shortest path data

Definition at line 964 of file shortestpath.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by runTmPcMW_mode().

◆ shortestpath_pcReset()

void shortestpath_pcReset ( SPATHSPC * sppc )

start computation

Parameters

sppc	PC/MW shortest path data

Definition at line 977 of file shortestpath.c.

References stortest_path_prizecollecting::maxoutprize, stortest_path_prizecollecting::maxoutprize_idx, stortest_path_prizecollecting::orderedprizes, and SCIP_Real.

Referenced by computeSteinerTree_execPcMw(), computeSteinerTree_execRpcMw(), graph_path_st_pcmw(), and graph_path_st_rpcmw().

◆ shortestpath_pcConnectNode()

void shortestpath_pcConnectNode	(	const GRAPH *	g,
		const STP_Bool *	connected,
		int	node_connected,
		SPATHSPC *	sppc
	)

update maximum prize

Parameters

g	graph data structure
connected	array to mark whether a vertex is part of computed Steiner tree
node_connected	node that is removed
sppc	PC data

Definition at line 991 of file shortestpath.c.

References EQ, stortest_path_prizecollecting::maxoutprize, stortest_path_prizecollecting::maxoutprize_idx, stortest_path_prizecollecting::orderedprizes, stortest_path_prizecollecting::orderedprizes_id, and SCIP_Real.

Referenced by computeSteinerTree_connectPseudoTerm(), computeSteinerTree_execPcMw(), computeSteinerTree_execRpcMw(), graph_path_st_pcmw(), graph_path_st_rpcmw(), and stPcmwConnectNode().

◆ shortestpath_computeSteinerTree()

void shortestpath_computeSteinerTree	(	const GRAPH *	g,
		int	startnode,
		SPATHS *	spaths
	)

shortest path based heuristic for computing a Steiner tree

Parameters

g	graph data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 1033 of file shortestpath.c.

References computeSteinerTree_allTermsAreReached(), computeSteinerTree_exec(), computeSteinerTree_init(), stortest_paths::csr, stortest_paths::dheap, graph_typeIsSpgLike(), GRAPH::knots, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, and stortest_paths::nodes_pred.

Referenced by computeSteinerTreeCsr(), and computeSteinerTreeKeyNodesCsr().

◆ shortestpath_computeSteinerTreeDirected()

void shortestpath_computeSteinerTreeDirected	(	SCIP *	scip,
		const GRAPH *	g,
		int	startnode,
		SPATHS *	spaths
	)

shortest path based heuristic for computing a Steiner tree

Parameters

scip	SCIP data structure
g	graph data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 1055 of file shortestpath.c.

References computeSteinerTree_allTermsAreReached(), computeSteinerTree_execDirected(), computeSteinerTree_init(), stortest_paths::csr, stortest_paths::dheap, graph_typeIsDirected(), GRAPH::knots, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, stortest_paths::nodes_pred, SCIPdebugMessage, and GRAPH::source.

Referenced by computeSteinerTreeCsr().

◆ shortestpath_computeSteinerTreeBiased()

void shortestpath_computeSteinerTreeBiased	(	const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		int	startnode,
		SPATHS *	spaths
	)

shortest path based heuristic for computing a Steiner tree

Parameters

g	graph data structure
sdprofit	implied profit data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 1081 of file shortestpath.c.

References computeSteinerTree_allTermsAreReached(), computeSteinerTree_execBiased(), computeSteinerTree_init(), stortest_paths::csr, stortest_paths::dheap, graph_typeIsSpgLike(), GRAPH::knots, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, and stortest_paths::nodes_pred.

Referenced by computeSteinerTreeCsr(), and computeSteinerTreeKeyNodesCsr().

◆ shortestpath_computeSteinerTreePcMw()

void shortestpath_computeSteinerTreePcMw	(	const GRAPH *	g,
		int	startnode,
		const SCIP_Real *	prize,
		SCIP_Bool	costIsBiased,
		SPATHSPC *	spaths_pc,
		SPATHS *	spaths
	)

shortest path based heuristic for computing a Steiner tree in PC/MW case

Parameters

g	graph data structure
startnode	start vertex
prize	(possibly biased) prize
costIsBiased	is cost biased?
spaths_pc	PC/MW shortest paths data
spaths	shortest paths data

Definition at line 1104 of file shortestpath.c.

References computeSteinerTree_execPcMw(), computeSteinerTree_init(), stortest_paths::csr, stortest_paths::dheap, GRAPH::extended, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::knots, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, and stortest_paths::nodes_pred.

Referenced by computeSteinerTreeDijkPcMw().

◆ shortestpath_computeSteinerTreeRpcMw()

void shortestpath_computeSteinerTreeRpcMw	(	const GRAPH *	g,
		int	startnode,
		const SCIP_Real *	prize,
		SPATHSPC *	spaths_pc,
		SPATHS *	spaths
	)

shortest path based heuristic for computing a Steiner tree in rooted PC/MW case

Parameters

g	graph data structure
startnode	start vertex
prize	(possibly biased) prize
spaths_pc	PC/MW shortest paths data
spaths	shortest paths data

Definition at line 1129 of file shortestpath.c.

References computeSteinerTree_execRpcMw(), computeSteinerTree_init(), stortest_paths::csr, stortest_paths::dheap, GRAPH::extended, graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::knots, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, and stortest_paths::nodes_pred.

Referenced by computeSteinerTreeDijkPcMw().

◆ shortestpath_computeSteinerTreePcMwFull()

void shortestpath_computeSteinerTreePcMwFull	(	const GRAPH *	g,
		int	startnode,
		SPATHS *	spaths
	)

shortest path based heuristic for computing a Steiner tree in PC/MW case that contains all (potential and fixed) terminals

Parameters

g	graph data structure
startnode	start vertex
spaths	shortest paths data

Definition at line 1153 of file shortestpath.c.

References computeSteinerTree_execPcMwFull(), computeSteinerTree_init(), stortest_paths::csr, stortest_paths::dheap, GRAPH::extended, graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::knots, stortest_paths::nodes_dist, stortest_paths::nodes_isConnected, and stortest_paths::nodes_pred.

Referenced by computeSteinerTreeDijkPcMwFull().

SCIP

Detailed Description

Functions

Function Documentation

◆ computeSteinerTree_allTermsAreReached()

◆ computeSteinerTree_allPseudoTermsAreReached()

◆ computeSteinerTree_allFixedTermsAreReached()

◆ computeSteinerTree_init()

◆ computeSteinerTree_connectTerminal()

◆ computeSteinerTree_connectNode()

◆ computeSteinerTree_exec()

◆ computeSteinerTree_execDirected()

◆ computeSteinerTree_execBiased()

◆ computeSteinerTree_connectPseudoTerm()

◆ computeSteinerTree_tryConnectNodePcMw()

◆ computeSteinerTree_execPcMw()

◆ computeSteinerTree_execRpcMw()

◆ computeSteinerTree_execPcMwFull()

◆ shortestpath_pcInit()

◆ shortestpath_pcFree()

◆ shortestpath_pcReset()

◆ shortestpath_pcConnectNode()

◆ shortestpath_computeSteinerTree()

◆ shortestpath_computeSteinerTreeDirected()

◆ shortestpath_computeSteinerTreeBiased()

◆ shortestpath_computeSteinerTreePcMw()

◆ shortestpath_computeSteinerTreeRpcMw()

◆ shortestpath_computeSteinerTreePcMwFull()