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 faster implementations.

Definition in file shortestpath.h.

#include "graph.h"

Go to the source code of this file.

Data Structures
struct	stortest_path_prizecollecting

struct	stortest_paths

Typedefs
typedef struct stortest_path_prizecollecting	SPATHSPC

typedef struct stortest_paths	SPATHS

Functions
SCIP_RETCODE	shortestpath_pcInit (SCIP , const GRAPH , const SCIP_Real , const SCIP_Real , SPATHSPC **)

void	shortestpath_pcFree (SCIP , SPATHSPC *)

void	shortestpath_pcReset (SPATHSPC *)

void	shortestpath_pcConnectNode (const GRAPH , const STP_Bool , int, SPATHSPC *)

void	shortestpath_computeSteinerTree (const GRAPH , int, SPATHS )

void	shortestpath_computeSteinerTreeBiased (const GRAPH , const SDPROFIT , int, SPATHS *)

void	shortestpath_computeSteinerTreeDirected (SCIP , const GRAPH , int, SPATHS *)

void	shortestpath_computeSteinerTreePcMw (const GRAPH , int, const SCIP_Real , SCIP_Bool, SPATHSPC , SPATHS )

void	shortestpath_computeSteinerTreeRpcMw (const GRAPH , int, const SCIP_Real , SPATHSPC , SPATHS )

void	shortestpath_computeSteinerTreePcMwFull (const GRAPH , int, SPATHS )

Typedef Documentation

◆ SPATHSPC

typedef struct stortest_path_prizecollecting SPATHSPC

information needed for prize-collecting problems

◆ SPATHS

typedef struct stortest_paths SPATHS

information for shortest paths

Function Documentation

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