Detailed Description

Graph algorithms for Steiner problems related to shortest paths to terminals.

Author: Thorsten Koch; Daniel Rehfeldt

This file encompasses various algorithms that are used to compute shortest paths from non-terminals to terminals.

Definition in file graph_tpath.c.

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <assert.h>
#include "graph.h"
#include "graphdefs.h"
#include "stpvector.h"
#include "reduce.h"

Go to the source code of this file.

Data Structures
struct	nodes_to_terminal_paths

struct	tpaths_repair

Macros
#define	STP_TPATHS_NTERMBASES 4

#define	STP_TPATHS_RESERVESIZE 16

#define	pathResetSingle(entry)

#define	tpathsRepairResetNode(scip, node, resetnodes, stack, nodes_isvisited)

Typedefs
typedef struct tpaths_repair	TREPAIR

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

static void	pathheapCorrectDist (int RESTRICT heap, int RESTRICT state, int RESTRICT count, PATH RESTRICT path, int l, int k, int edge, SCIP_Real newdist)

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)

static void	tpathsPrintPath (const GRAPH g, const SDPROFIT sdprofit, const TPATHS *tpaths, int node, int level)

static SCIP_RETCODE	tpathsAlloc (SCIP scip, const GRAPH g, TPATHS **tpaths)

static void	tpathsResetMembers (const GRAPH g, int level, TPATHS tpaths)

static void	tpathsGetKCloseTerms (const GRAPH g, const TPATHS tpaths, int maxnumber, int node, SCIP_Real maxdist, SCIP_Bool distIsStrict, int RESTRICT closeterms, int RESTRICT firstedges, SCIP_Real RESTRICT closeterms_dist, int RESTRICT ncloseterms)

static SCIP_Real	tpathsGetDistNew (const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const int vbase, int node, int nextnode, int edge, const SDPROFIT sdprofit, const PATH path)

static void	tpathsBuild (SCIP scip, GRAPH g, TPATHS *tpaths)

static void	tpathsBuildBiased (const SDPROFIT sdprofit, GRAPH g, TPATHS *tpaths)

static void	tpathsScan1st (SCIP scip, const GRAPH g, const SCIP_Real cost, const SDPROFIT sdprofit, int heapsize, TPATHS tpaths, TREPAIR repair)

static void	tpathsScan2nd (SCIP scip, const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, int heapsize, TPATHS tpaths, TREPAIR *repair)

static void	tpathsScan3rd (SCIP scip, const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, int heapsize, TPATHS tpaths, TREPAIR *repair)

static void	tpathsScan4th (SCIP scip, const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, int heapsize, TPATHS tpaths, TREPAIR *repair)

static SCIP_RETCODE	tpathsRepairInitLevel (SCIP scip, int level, const GRAPH g, TREPAIR *repair)

static void	tpathsRepairExitLevel (SCIP scip, int level, const GRAPH g, TREPAIR *repair)

static SCIP_RETCODE	tpathsRepairTraverse1st (SCIP scip, int start, int pred, const GRAPH g, TREPAIR *repair)

static void	tpathsRepairTraverseLevelWithStack (SCIP scip, const GRAPH g, int level, TREPAIR *repair)

static void	tpathsRepairTraverseStackAddEdge (SCIP scip, const GRAPH g, int level, TREPAIR *repair)

static void	tpathsRepairTraverseStackAddBelow (SCIP scip, const GRAPH g, int level, TREPAIR *repair)

static void	tpathsRepairTraverseLevel (SCIP scip, const GRAPH g, int level, TREPAIR *repair)

static void	tpathsRepairUpdate1st (SCIP scip, const GRAPH g, TREPAIR *repair)

static void	tpathsRepairUpdateLevel (SCIP scip, const GRAPH g, int level, TREPAIR *repair)

static SCIP_RETCODE	tpathsRepair1st (SCIP scip, const GRAPH g, TREPAIR *repair)

static SCIP_RETCODE	tpathsRepair2nd (SCIP scip, const GRAPH g, TREPAIR *repair)

static SCIP_RETCODE	tpathsRepair3rd (SCIP scip, const GRAPH g, TREPAIR *repair)

static SCIP_RETCODE	tpathsRepair4th (SCIP scip, const GRAPH g, TREPAIR *repair)

static void	tpathsRepairInit (SCIP scip, const GRAPH g, TREPAIR *repair)

static void	tpathsRepairExit (SCIP scip, const GRAPH g, TREPAIR *repair)

void	graph_add1stTermPaths (const GRAPH g, const SCIP_Real cost, PATH path, int vbase, int *state)

void	graph_add2ndTermPaths (const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, PATH path2, int vbase2, int state2)

void	graph_add3rdTermPaths (const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, PATH path3, int vbase3, int state3)

void	graph_add4thTermPaths (const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, PATH path4, int vbase4, int state4)

void	graph_get2nextTermPaths (GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, PATH path2, int vbase2, int state2)

void	graph_get3nextTermPaths (GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, PATH path3, int vbase3, int state3)

void	graph_get4nextTermPaths (GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, PATH path4, int vbase4, int state4)

SCIP_RETCODE	graph_get4nextTTerms (SCIP scip, GRAPH g, const SCIP_Real cost, PATH path, int vbase, int heap, int *state)

SCIP_RETCODE	graph_tpathsInit (SCIP scip, GRAPH g, TPATHS **tpaths)

SCIP_RETCODE	graph_tpathsInitBiased (SCIP scip, const SDPROFIT sdprofit, GRAPH g, TPATHS *tpaths)

SCIP_RETCODE	graph_tpathsRepairSetUp (const GRAPH g, TPATHS tpaths)

SCIP_RETCODE	graph_tpathsRepair (SCIP scip, int edge, SCIP_Bool withEdgeReplacement, const GRAPH g, TPATHS *tpaths)

SCIP_RETCODE	graph_tpathsRecomputeBiased (const SDPROFIT sdprofit, GRAPH g, TPATHS *tpaths)

void	graph_tpathsPrintForNode (const GRAPH g, const SDPROFIT sdprofit, const TPATHS *tpaths, int node)

void	graph_tpathsGetProfitNodes (SCIP scip, const GRAPH g, const TPATHS tpaths, const SDPROFIT sdprofit, int start, int base, STP_Vectype(int) profitnodes)

void	graph_tpathsAdd1st (const GRAPH g, const SCIP_Real cost, const SDPROFIT sdprofit, TPATHS tpaths)

void	graph_tpathsAdd2nd (const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, TPATHS *tpaths)

void	graph_tpathsAdd3rd (const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, TPATHS *tpaths)

void	graph_tpathsAdd4th (const GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, TPATHS *tpaths)

void	graph_tpathsSetAll2 (GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, TPATHS *tpaths)

void	graph_tpathsSetAll3 (GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, TPATHS *tpaths)

void	graph_tpathsSetAll4 (GRAPH g, const SCIP_Real cost, const SCIP_Real costrev, const SDPROFIT sdprofit, TPATHS *tpaths)

void	graph_tpathsFree (SCIP scip, TPATHS *tpaths)

void	graph_tpathsGetClosestTerm (const GRAPH g, const TPATHS tpaths, int node, int RESTRICT closeterm, int RESTRICT firstedge, SCIP_Real *RESTRICT closeterm_dist)

void	graph_tpathsGet3CloseTerms (const GRAPH g, const TPATHS tpaths, int node, SCIP_Real maxdist_strict, int RESTRICT closeterms, int RESTRICT firstedges, SCIP_Real RESTRICT closeterms_dist, int RESTRICT ncloseterms)

void	graph_tpathsGet4CloseTerms (const GRAPH g, const TPATHS tpaths, int node, SCIP_Real maxdist_strict, int RESTRICT closeterms, int RESTRICT firstedges, SCIP_Real RESTRICT closeterms_dist, int RESTRICT ncloseterms)

void	graph_tpathsGet4CloseTermsLE (const GRAPH g, const TPATHS tpaths, int node, SCIP_Real maxdist_nonstrict, int RESTRICT closeterms, int RESTRICT firstedges, SCIP_Real RESTRICT closeterms_dist, int RESTRICT ncloseterms)

Macro Definition Documentation

◆ STP_TPATHS_NTERMBASES

#define STP_TPATHS_NTERMBASES 4

Definition at line 35 of file graph_tpath.c.

Referenced by graph_tpathsGetProfitNodes(), graph_tpathsInit(), graph_tpathsInitBiased(), graph_tpathsPrintForNode(), graph_tpathsRecomputeBiased(), graph_tpathsRepair(), graph_tpathsRepairSetUp(), tpathsAlloc(), tpathsBuild(), tpathsBuildBiased(), tpathsGetKCloseTerms(), tpathsPrintPath(), tpathsRepairExit(), tpathsRepairExitLevel(), and tpathsRepairInit().

◆ STP_TPATHS_RESERVESIZE

#define STP_TPATHS_RESERVESIZE 16

Definition at line 36 of file graph_tpath.c.

Referenced by tpathsRepairInit().

◆ pathResetSingle

#define pathResetSingle ( entry )

Value:

do                          \
   {                           \
      entry.dist = FARAWAY;    \
      entry.edge = UNKNOWN;    \
   } while( 0 )

reset single path struct

Definition at line 39 of file graph_tpath.c.

Referenced by tpathsRepairUpdate1st(), tpathsRepairUpdateLevel(), and tpathsResetMembers().

◆ tpathsRepairResetNode

#define tpathsRepairResetNode	(	scip,
		node,
		resetnodes,
		stack,
		nodes_isvisited
	)

Value:

do                                                                                 \
   {                                                                 \
      assert(scip && resetnodes && stack && nodes_isvisited); \
      assert(!nodes_isvisited[node]);                              \
      StpVecPushBack(scip, resetnodes, node);                        \
      StpVecPushBack(scip, stack, node);                             \
      nodes_isvisited[node] = TRUE;                                  \
   } while( 0 )

resets node

Definition at line 48 of file graph_tpath.c.

Referenced by tpathsRepairTraverse1st(), tpathsRepairTraverseLevelWithStack(), tpathsRepairTraverseStackAddBelow(), and tpathsRepairTraverseStackAddEdge().

Typedef Documentation

◆ TREPAIR

typedef struct tpaths_repair TREPAIR

data needed to repair node to terminal paths for edge-deletion

Function Documentation

◆ pathheapGetNearest()

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

inlinestatic

Definition at line 100 of file graph_tpath.c.

References GT, and LT.

Referenced by tpathsScan1st(), tpathsScan2nd(), tpathsScan3rd(), and tpathsScan4th().

◆ pathheapCorrectDist()

static void pathheapCorrectDist	(	int *RESTRICT	heap,
		int *RESTRICT	state,
		int *RESTRICT	count,
		PATH *RESTRICT	path,
		int	l,
		int	k,
		int	edge,
		SCIP_Real	newdist
	)

inlinestatic

set new distance and predeccesor

Definition at line 145 of file graph_tpath.c.

References UNKNOWN.

Referenced by graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), graph_tpathsAdd4th(), tpathsScan1st(), tpathsScan2nd(), tpathsScan3rd(), and tpathsScan4th().

◆ 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

terminal to terminal distance

Definition at line 188 of file graph_tpath.c.

References shortest_path::dist, Is_term, nodes_to_terminal_paths::nnodes, r, SCIP_Real, SCIPisLT(), and GRAPH::term.

Referenced by graph_get4nextTTerms().

◆ tpathsPrintPath()

static void tpathsPrintPath	(	const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		const TPATHS *	tpaths,
		int	node,
		int	level
	)

static

prints terminal path from given node

Parameters

g	graph data structure
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths
node	node to start from
level	between 1 and 4

Definition at line 285 of file graph_tpath.c.

References shortest_path::edge, graph_edge_isDeleted(), graph_edge_isInRange(), graph_edge_printInfo(), graph_get_nNodes(), graph_knot_isInRange(), nodes_to_terminal_paths::nnodes, reduce_sdprofitGetProfit(), SCIP_Real, STP_TPATHS_NTERMBASES, GRAPH::tail, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and UNKNOWN.

Referenced by graph_tpathsPrintForNode().

◆ tpathsAlloc()

static SCIP_RETCODE tpathsAlloc	(	SCIP *	scip,
		const GRAPH *	g,
		TPATHS **	tpaths
	)

static

allocates TPATHS data

Parameters

scip	SCIP
g	graph
tpaths	the terminal paths

Definition at line 344 of file graph_tpath.c.

References graph_get_nNodes(), nodes_to_terminal_paths::nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, nodes_to_terminal_paths::state, STP_TPATHS_NTERMBASES, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termbases_org, and nodes_to_terminal_paths::termpaths.

Referenced by graph_tpathsInit(), and graph_tpathsInitBiased().

◆ tpathsResetMembers()

static void tpathsResetMembers	(	const GRAPH *	g,
		int	level,
		TPATHS *	tpaths
	)

static

resets TPATHS members

Parameters

g	graph
level	level between 2 and 4
tpaths	the terminal paths

Definition at line 371 of file graph_tpath.c.

References CONNECT, graph_get_nNodes(), nodes_to_terminal_paths::nnodes, pathResetSingle, nodes_to_terminal_paths::state, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and UNKNOWN.

Referenced by graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), and graph_tpathsAdd4th().

◆ tpathsGetKCloseTerms()

static void tpathsGetKCloseTerms	(	const GRAPH *	g,
		const TPATHS *	tpaths,
		int	maxnumber,
		int	node,
		SCIP_Real	maxdist,
		SCIP_Bool	distIsStrict,
		int *RESTRICT	closeterms,
		int *RESTRICT	firstedges,
		SCIP_Real *RESTRICT	closeterms_dist,
		int *RESTRICT	ncloseterms
	)

inlinestatic

gets (up to) four close terminals to given node i

Parameters

g	graph
tpaths	the terminal paths
maxnumber	number of close terms
node	node
maxdist	maximum valid distance
distIsStrict	is 'maxdist' strict?
closeterms	four close terminals
firstedges	corresponding first edge (can be NULL)
closeterms_dist	four close terminal distance
ncloseterms	number of close terminals found

Definition at line 405 of file graph_tpath.c.

References shortest_path::dist, shortest_path::edge, GE, GRAPH::grad, graph_knot_isInRange(), Is_term, GRAPH::knots, LE, LT, nodes_to_terminal_paths::nnodes, NULL, SCIP_Bool, STP_TPATHS_NTERMBASES, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and UNKNOWN.

Referenced by graph_tpathsGet3CloseTerms(), graph_tpathsGet4CloseTerms(), and graph_tpathsGet4CloseTermsLE().

◆ tpathsGetDistNew()

static SCIP_Real tpathsGetDistNew	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const int *	vbase,
		int	node,
		int	nextnode,
		int	edge,
		const SDPROFIT *	sdprofit,
		const PATH *	path
	)

inlinestatic

gets new distance for extension

Parameters

g	graph
cost	edge costs
costrev	reversed edge costs
vbase	bases
node	node to extend from
nextnode	node to extend to
edge	the edge
sdprofit	SD bias for nodes or NULL
path	the actual terminal paths

Definition at line 484 of file graph_tpath.c.

References shortest_path::dist, shortest_path::edge, GE, graph_get_nNodes(), graph_pc_isMw(), GRAPH::head, Is_term, GRAPH::knots, LE, nodes_to_terminal_paths::nnodes, reduce_sdprofitGetBiasedDist(), SCIP_Real, GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), graph_tpathsAdd4th(), tpathsScan2nd(), tpathsScan3rd(), and tpathsScan4th().

◆ tpathsBuild()

static void tpathsBuild	(	SCIP *	scip,
		GRAPH *	g,
		TPATHS *	tpaths
	)

inlinestatic

allocates TPATHS data

Parameters

scip	SCIP
g	graph
tpaths	the terminal paths

Definition at line 535 of file graph_tpath.c.

References GRAPH::cost, graph_tpathsSetAll4(), NULL, and STP_TPATHS_NTERMBASES.

Referenced by graph_tpathsInit().

◆ tpathsBuildBiased()

static void tpathsBuildBiased	(	const SDPROFIT *	sdprofit,
		GRAPH *	g,
		TPATHS *	tpaths
	)

inlinestatic

allocates TPATHS data

Parameters

sdprofit	SD profit
g	graph
tpaths	the terminal paths

Definition at line 548 of file graph_tpath.c.

References GRAPH::cost, graph_tpathsSetAll4(), and STP_TPATHS_NTERMBASES.

Referenced by graph_tpathsInitBiased(), and graph_tpathsRecomputeBiased().

◆ tpathsScan1st()

static void tpathsScan1st	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const SDPROFIT *	sdprofit,
		int	heapsize,
		TPATHS *	tpaths,
		TREPAIR *	repair
	)

static

sub-method to find closest terminal to each non terminal (Voronoi diagram)

Parameters

scip	SCIP or NULL
g	graph data structure
cost	edge costs
sdprofit	SD bias for nodes or NULL
heapsize	size of heap
tpaths	storage for terminal paths
repair	data for repairing or NULL

Definition at line 562 of file graph_tpath.c.

References CONNECT, EAT_LAST, GE, GT, GRAPH::head, Is_term, LE, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), pathheapGetNearest(), reduce_sdprofitGetBiasedDist(), SCIP_Bool, SCIP_Real, nodes_to_terminal_paths::state, StpVecPushBack, GRAPH::tail, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and TRUE.

Referenced by graph_tpathsAdd1st(), and tpathsRepair1st().

◆ tpathsScan2nd()

static void tpathsScan2nd	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		int	heapsize,
		TPATHS *	tpaths,
		TREPAIR *	repair
	)

static

sub-method to find 2nd closest terminal to each non terminal

Parameters

scip	SCIP or NULL
g	graph data structure
cost	edge costs
costrev	reverse edge costs
sdprofit	SD bias for nodes or NULL
heapsize	size of heap
tpaths	storage for terminal paths
repair	data for repairing or NULL

Definition at line 637 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), graph_knot_isInRange(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), pathheapGetNearest(), SCIP_Bool, SCIP_Real, nodes_to_terminal_paths::state, StpVecPushBack, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), TRUE, and UNKNOWN.

Referenced by graph_tpathsAdd2nd(), and tpathsRepair2nd().

◆ tpathsScan3rd()

static void tpathsScan3rd	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		int	heapsize,
		TPATHS *	tpaths,
		TREPAIR *	repair
	)

static

sub-method to find 3rd closest terminal to each non terminal

Parameters

scip	SCIP or NULL
g	graph data structure
cost	edge costs
costrev	reverse edge costs
sdprofit	SD bias for nodes or NULL
heapsize	size of heap
tpaths	storage for terminal paths
repair	data for repairing or NULL

Definition at line 700 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), pathheapGetNearest(), SCIP_Bool, SCIP_Real, nodes_to_terminal_paths::state, StpVecPushBack, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), TRUE, and UNKNOWN.

Referenced by graph_tpathsAdd3rd(), and tpathsRepair3rd().

◆ tpathsScan4th()

static void tpathsScan4th	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		int	heapsize,
		TPATHS *	tpaths,
		TREPAIR *	repair
	)

static

sub-method to find 4th closest terminal to each non terminal

Parameters

scip	SCIP or NULL
g	graph data structure
cost	edge costs
costrev	reverse edge costs
sdprofit	SD bias for nodes or NULL
heapsize	size of heap
tpaths	storage for terminal paths
repair	data for repairing or NULL

Definition at line 764 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), pathheapGetNearest(), SCIP_Bool, SCIP_Real, nodes_to_terminal_paths::state, StpVecPushBack, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), TRUE, and UNKNOWN.

Referenced by graph_tpathsAdd4th(), and tpathsRepair4th().

◆ tpathsRepairInitLevel()

static SCIP_RETCODE tpathsRepairInitLevel	(	SCIP *	scip,
		int	level,
		const GRAPH *	g,
		TREPAIR *	repair
	)

inlinestatic

initializes

Parameters

scip	SCIP
level	0 - 3
g	graph
repair	data for repairing

Definition at line 831 of file graph_tpath.c.

References graph_get_nNodes(), nodes_to_terminal_paths::nnodes, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, nodes_to_terminal_paths::state, and UNKNOWN.

Referenced by tpathsRepair1st(), tpathsRepair2nd(), tpathsRepair3rd(), and tpathsRepair4th().

◆ tpathsRepairExitLevel()

static void tpathsRepairExitLevel	(	SCIP *	scip,
		int	level,
		const GRAPH *	g,
		TREPAIR *	repair
	)

inlinestatic

cleans and frees

Parameters

scip	SCIP
level	0 - 3
g	graph
repair	data for repairing

Definition at line 859 of file graph_tpath.c.

References FALSE, graph_knot_isInRange(), GRAPH::knots, SCIP_Bool, SCIPfreeCleanBufferArray, nodes_to_terminal_paths::state, STP_TPATHS_NTERMBASES, STP_Vectype, StpVecGetSize, and UNKNOWN.

Referenced by tpathsRepair1st(), tpathsRepair2nd(), tpathsRepair3rd(), and tpathsRepair4th().

◆ tpathsRepairTraverse1st()

static SCIP_RETCODE tpathsRepairTraverse1st	(	SCIP *	scip,
		int	start,
		int	pred,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

traverses graph to find nodes that need to be reseted

Parameters

scip	SCIP
start	node to start from
pred	predecessor node
g	graph
repair	data for repairing

Definition at line 902 of file graph_tpath.c.

References a, EAT_LAST, shortest_path::edge, graph_knot_isInRange(), GRAPH::head, Is_term, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, STP_Vectype, StpVecGetSize, StpVecIsEmpty, StpVecPopBack, GRAPH::tail, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and tpathsRepairResetNode.

Referenced by tpathsRepair1st().

◆ tpathsRepairTraverseLevelWithStack()

static void tpathsRepairTraverseLevelWithStack	(	SCIP *	scip,
		const GRAPH *	g,
		int	level,
		TREPAIR *	repair
	)

static

DFS on level

Parameters

scip	SCIP
g	graph
level	level from 1-3
repair	data for repairing

Definition at line 963 of file graph_tpath.c.

References a, EAT_LAST, shortest_path::edge, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, nodes_to_terminal_paths::nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, STP_Vectype, StpVecGetSize, StpVecIsEmpty, StpVecPopBack, GRAPH::tail, nodes_to_terminal_paths::termbases_org, nodes_to_terminal_paths::termpaths, and tpathsRepairResetNode.

Referenced by tpathsRepairTraverseLevel().

◆ tpathsRepairTraverseStackAddEdge()

static void tpathsRepairTraverseStackAddEdge	(	SCIP *	scip,
		const GRAPH *	g,
		int	level,
		TREPAIR *	repair
	)

static

adds outdated nodes whose predecessor points along edge to be deleted

Parameters

scip	SCIP
g	graph
level	level (1-3, level 0 is handled separately)
repair	data for repairing

Definition at line 1021 of file graph_tpath.c.

References shortest_path::edge, graph_get_nNodes(), GRAPH::head, nodes_to_terminal_paths::nnodes, GRAPH::tail, nodes_to_terminal_paths::termpaths, and tpathsRepairResetNode.

Referenced by tpathsRepairTraverseLevel().

◆ tpathsRepairTraverseStackAddBelow()

static void tpathsRepairTraverseStackAddBelow	(	SCIP *	scip,
		const GRAPH *	g,
		int	level,
		TREPAIR *	repair
	)

static

adds outdated nodes whose predecessor point to lower level

Parameters

scip	SCIP
g	graph
level	level (1-3, level 0 is handled separately)
repair	data for repairing

Definition at line 1050 of file graph_tpath.c.

References a, EAT_LAST, shortest_path::edge, graph_get_nNodes(), graph_knot_isInRange(), GRAPH::head, Is_term, nodes_to_terminal_paths::nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIPdebugMessage, STP_Vectype, StpVecGetSize, GRAPH::tail, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termbases_org, nodes_to_terminal_paths::termpaths, and tpathsRepairResetNode.

Referenced by tpathsRepairTraverseLevel().

◆ tpathsRepairTraverseLevel()

static void tpathsRepairTraverseLevel	(	SCIP *	scip,
		const GRAPH *	g,
		int	level,
		TREPAIR *	repair
	)

static

Traverses graph to find nodes on given level that need to be reseted, by updating from previous levels. Also considers duplicates.

Parameters

scip	SCIP
g	graph
level	level (1-3, level 0 is handled separately)
repair	data for repairing

Definition at line 1117 of file graph_tpath.c.

References tpathsRepairTraverseLevelWithStack(), tpathsRepairTraverseStackAddBelow(), and tpathsRepairTraverseStackAddEdge().

Referenced by tpathsRepair2nd(), tpathsRepair3rd(), and tpathsRepair4th().

◆ tpathsRepairUpdate1st()

static void tpathsRepairUpdate1st	(	SCIP *	scip,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

updates reset nodes from non-reset nodes

Parameters

scip	SCIP
g	graph
repair	data for repairing

Definition at line 1135 of file graph_tpath.c.

References GRAPH::cost, EAT_LAST, flipedge, graph_knot_isInRange(), graph_pathHeapAdd(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::path_heap, pathResetSingle, SCIP_Bool, SCIP_Real, SCIPdebugMessage, nodes_to_terminal_paths::state, STP_Vectype, StpVecGetSize, GRAPH::tail, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and UNKNOWN.

Referenced by tpathsRepair1st().

◆ tpathsRepairUpdateLevel()

static void tpathsRepairUpdateLevel	(	SCIP *	scip,
		const GRAPH *	g,
		int	level,
		TREPAIR *	repair
	)

static

updates reset nodes from non-reset nodes of given level

Parameters

scip	SCIP
g	graph
level	level (1-3, 0 is handled separately)
repair	data for repairing

Definition at line 1199 of file graph_tpath.c.

References GRAPH::cost, EAT_LAST, flipedge, graph_get_nNodes(), graph_knot_isInRange(), graph_pathHeapAdd(), h, GRAPH::ieat, GRAPH::inpbeg, Is_term, nodes_to_terminal_paths::nnodes, GRAPH::path_heap, pathResetSingle, SCIP_Bool, SCIP_Real, SCIPdebugMessage, nodes_to_terminal_paths::state, STP_Vectype, StpVecGetSize, GRAPH::tail, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and UNKNOWN.

Referenced by tpathsRepair2nd(), tpathsRepair3rd(), and tpathsRepair4th().

◆ tpathsRepair1st()

static SCIP_RETCODE tpathsRepair1st	(	SCIP *	scip,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

repairs TPATHS structure for imminent edge deletion (1st level)

Parameters

scip	SCIP
g	graph
repair	data for repairing

Definition at line 1287 of file graph_tpath.c.

References GRAPH::cost, GRAPH::head, NULL, SCIP_CALL, SCIP_OKAY, GRAPH::tail, tpathsRepairExitLevel(), tpathsRepairInitLevel(), tpathsRepairTraverse1st(), tpathsRepairUpdate1st(), and tpathsScan1st().

Referenced by graph_tpathsRepair().

◆ tpathsRepair2nd()

static SCIP_RETCODE tpathsRepair2nd	(	SCIP *	scip,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

repairs TPATHS structure for imminent edge deletion (2nd level)

Parameters

scip	SCIP
g	graph
repair	data for repairing

Definition at line 1318 of file graph_tpath.c.

References GRAPH::cost, NULL, SCIP_CALL, SCIP_OKAY, tpathsRepairExitLevel(), tpathsRepairInitLevel(), tpathsRepairTraverseLevel(), tpathsRepairUpdateLevel(), and tpathsScan2nd().

Referenced by graph_tpathsRepair().

◆ tpathsRepair3rd()

static SCIP_RETCODE tpathsRepair3rd	(	SCIP *	scip,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

repairs TPATHS structure for imminent edge deletion (3rd level)

Parameters

scip	SCIP
g	graph
repair	data for repairing

Definition at line 1340 of file graph_tpath.c.

References GRAPH::cost, NULL, SCIP_CALL, SCIP_OKAY, tpathsRepairExitLevel(), tpathsRepairInitLevel(), tpathsRepairTraverseLevel(), tpathsRepairUpdateLevel(), and tpathsScan3rd().

Referenced by graph_tpathsRepair().

◆ tpathsRepair4th()

static SCIP_RETCODE tpathsRepair4th	(	SCIP *	scip,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

repairs TPATHS structure for imminent edge deletion (4th level)

Parameters

scip	SCIP
g	graph
repair	data for repairing

Definition at line 1363 of file graph_tpath.c.

References GRAPH::cost, NULL, SCIP_CALL, SCIP_OKAY, tpathsRepairExitLevel(), tpathsRepairInitLevel(), tpathsRepairTraverseLevel(), tpathsRepairUpdateLevel(), and tpathsScan4th().

Referenced by graph_tpathsRepair().

◆ tpathsRepairInit()

static void tpathsRepairInit	(	SCIP *	scip,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

initializes

Parameters

scip	SCIP
g	graph
repair	data for repairing

Definition at line 1386 of file graph_tpath.c.

References GRAPH::knots, STP_TPATHS_NTERMBASES, STP_TPATHS_RESERVESIZE, StpVecReserve, nodes_to_terminal_paths::termbases, and nodes_to_terminal_paths::termbases_org.

Referenced by graph_tpathsRepair().

◆ tpathsRepairExit()

static void tpathsRepairExit	(	SCIP *	scip,
		const GRAPH *	g,
		TREPAIR *	repair
	)

static

frees and resets

Parameters

scip	SCIP
g	graph
repair	data for repairing

Definition at line 1414 of file graph_tpath.c.

References graph_get_nNodes(), graph_knot_isInRange(), nodes_to_terminal_paths::nnodes, STP_TPATHS_NTERMBASES, STP_Vectype, StpVecFree, StpVecGetSize, nodes_to_terminal_paths::termbases, and nodes_to_terminal_paths::termbases_org.

Referenced by graph_tpathsRepair().

◆ graph_add1stTermPaths()

void graph_add1stTermPaths	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		PATH *	path,
		int *	vbase,
		int *	state
	)

builds a Voronoi region w.r.t. shortest paths, for all terminals NOTE: serves as a wrapper

Parameters

g	graph data structure
cost	edge costs
path	path data structure (leading to respective Voronoi base)
vbase	Voronoi base to each vertex
state	array to mark the state of each node during calculation

Definition at line 1464 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsAdd1st(), nodes_to_terminal_paths::nnodes, NULL, nodes_to_terminal_paths::state, and nodes_to_terminal_paths::termpaths.

Referenced by computeTransVoronoi(), redcosts_initializeDistances(), reduce_boundHopR(), reduce_boundHopRc(), and reduce_daPcMw().

◆ graph_add2ndTermPaths()

void graph_add2ndTermPaths	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		PATH *	path2,
		int *	vbase2,
		int *	state2
	)

2nd next terminal to all non terminal nodes NOTE: legacy wrapper

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
path2	path data structure (leading to first and second nearest terminal)
vbase2	first and second nearest terminal to each non terminal
state2	array to mark the state of each node during calculation

Definition at line 1482 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsAdd2nd(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by boundPruneHeur(), boundPruneHeurMw(), reduce_bound(), reduce_boundHop(), reduce_boundMw(), and reduce_daPcMw().

◆ graph_add3rdTermPaths()

void graph_add3rdTermPaths	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		PATH *	path3,
		int *	vbase3,
		int *	state3
	)

3rd next terminal to all non terminal nodes NOTE: legacy wrapper

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
path3	path data structure (leading to first, second and third nearest terminal)
vbase3	first, second and third nearest terminal to each non terminal
state3	array to mark the state of each node during calculation

Definition at line 1501 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsAdd3rd(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by boundPruneHeur(), and reduce_bound().

◆ graph_add4thTermPaths()

void graph_add4thTermPaths	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		PATH *	path4,
		int *	vbase4,
		int *	state4
	)

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
path4	path data structure (leading to first, second, third and fourth nearest terminal)
vbase4	first, second, third, and fourth nearest terminal to each non terminal
state4	array to mark the state of each node during calculation

Definition at line 1521 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsAdd4th(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by reduce_bound().

◆ graph_get2nextTermPaths()

void graph_get2nextTermPaths	(	GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		PATH *	path2,
		int *	vbase2,
		int *	state2
	)

gets non-terminal shortest paths to 2 closest terminal for each non-terminal NOTE: legacy wrapper

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
path2	path data structure (leading to first, second terminal)
vbase2	first, second and third nearest terminal to each non terminal
state2	array to mark the state of each node during calculation

Definition at line 1542 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsSetAll2(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by getRedCost2ndNextDistances(), redcosts_initializeDistances(), and reduce_daSlackPrune().

◆ graph_get3nextTermPaths()

void graph_get3nextTermPaths	(	GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		PATH *	path3,
		int *	vbase3,
		int *	state3
	)

gets non-terminal shortest paths to 3 closest terminal for each non-terminal NOTE: legacy wrapper

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
path3	path data structure (leading to first, second and third nearest terminal)
vbase3	first, second and third nearest terminal to each non terminal
state3	array to mark the state of each node during calculation

Definition at line 1562 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsSetAll3(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by redcosts_initializeDistances().

◆ graph_get4nextTermPaths()

void graph_get4nextTermPaths	(	GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		PATH *	path4,
		int *	vbase4,
		int *	state4
	)

gets non-terminal shortest paths to 4 closest terminal for each non-terminal NOTE: legacy wrapper

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
path4	path data struture (leading to first, second, third and fouth nearest terminal)
vbase4	first, second and third nearest terminal to each non terminal
state4	array to mark the state of each node during calculation

Definition at line 1582 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsSetAll4(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by reduce_sd(), and reduce_sdPc().

◆ graph_get4nextTTerms()

SCIP_RETCODE graph_get4nextTTerms	(	SCIP *	scip,
		GRAPH *	g,
		const 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 1601 of file graph_tpath.c.

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

Referenced by reduce_bound(), and reduce_sdPc().

◆ graph_tpathsInit()

SCIP_RETCODE graph_tpathsInit	(	SCIP *	scip,
		GRAPH *	g,
		TPATHS **	tpaths
	)

initializes TPATHS structure

Parameters

scip	SCIP
g	graph NOTE: will mark the graph, thus not const :( terrible design
tpaths	the terminal paths

Definition at line 1682 of file graph_tpath.c.

References SCIP_CALL, SCIP_OKAY, STP_TPATHS_NTERMBASES, tpathsAlloc(), and tpathsBuild().

Referenced by reduce_sdInit(), testBiasedTerminalPathsTo4NextFound(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), and testTerminalPathsTo3NextFound().

◆ graph_tpathsInitBiased()

SCIP_RETCODE graph_tpathsInitBiased	(	SCIP *	scip,
		const SDPROFIT *	sdprofit,
		GRAPH *	g,
		TPATHS **	tpaths
	)

initializes biased TPATHS structure

Parameters

scip	SCIP
sdprofit	SD profit
g	graph NOTE: will mark the graph, thus not const :( terrible design
tpaths	the terminal paths

Definition at line 1700 of file graph_tpath.c.

References SCIP_CALL, SCIP_OKAY, STP_TPATHS_NTERMBASES, tpathsAlloc(), and tpathsBuildBiased().

Referenced by reduce_sdInitBiased(), reduce_sdInitBiasedBottleneck(), and testSdGraphStrongBiasedDistsAreValid().

◆ graph_tpathsRepairSetUp()

SCIP_RETCODE graph_tpathsRepairSetUp	(	const GRAPH *	g,
		TPATHS *	tpaths
	)

sets up TPATHS for subsequent edge deletions

Parameters

g	graph
tpaths	the terminal paths

Definition at line 1719 of file graph_tpath.c.

References BMScopyMemoryArray, graph_get_nNodes(), nodes_to_terminal_paths::nnodes, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, nodes_to_terminal_paths::state, STP_TPATHS_NTERMBASES, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termbases_org, and UNKNOWN.

Referenced by reduce_sdRepairSetUp(), testTerminalPathsRepair(), testTerminalPathsRepair2(), and testTerminalPathsRepair3().

◆ graph_tpathsRepair()

SCIP_RETCODE graph_tpathsRepair	(	SCIP *	scip,
		int	edge,
		SCIP_Bool	withEdgeReplacement,
		const GRAPH *	g,
		TPATHS *	tpaths
	)

repairs TPATHS structure for imminent edge deletion

Parameters

scip	SCIP
edge	edge about to be eliminated
withEdgeReplacement	with edge replacement?
g	graph
tpaths	the terminal paths

Definition at line 1744 of file graph_tpath.c.

References graph_edge_isInRange(), graph_isMarked(), NULL, SCIP_CALL, SCIP_OKAY, STP_TPATHS_NTERMBASES, STP_Vectype, nodes_to_terminal_paths::termbases_org, tpathsRepair1st(), tpathsRepair2nd(), tpathsRepair3rd(), tpathsRepair4th(), tpathsRepairExit(), and tpathsRepairInit().

Referenced by reduce_sdRepair(), testTerminalPathsRepair(), testTerminalPathsRepair2(), and testTerminalPathsRepair3().

◆ graph_tpathsRecomputeBiased()

SCIP_RETCODE graph_tpathsRecomputeBiased	(	const SDPROFIT *	sdprofit,
		GRAPH *	g,
		TPATHS *	tpaths
	)

recomputes biased TPATHS structure

Parameters

sdprofit	SD profit
g	graph NOTE: will mark the graph, thus not const :( terrible design
tpaths	the terminal paths

Definition at line 1776 of file graph_tpath.c.

References SCIP_OKAY, STP_TPATHS_NTERMBASES, and tpathsBuildBiased().

Referenced by reduce_impliedProfitBased(), and reduce_impliedProfitBasedRpc().

◆ graph_tpathsPrintForNode()

void graph_tpathsPrintForNode	(	const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		const TPATHS *	tpaths,
		int	node
	)

prints terminal paths from given node

Parameters

g	graph data structure
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths
node	node to start from

Definition at line 1793 of file graph_tpath.c.

References shortest_path::dist, graph_get_nNodes(), graph_knot_isInRange(), graph_knot_printInfo(), Is_term, nodes_to_terminal_paths::nnodes, STP_TPATHS_NTERMBASES, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsPrintPath(), and UNKNOWN.

◆ graph_tpathsGetProfitNodes()

void graph_tpathsGetProfitNodes	(	SCIP *	scip,
		const GRAPH *	g,
		const TPATHS *	tpaths,
		const SDPROFIT *	sdprofit,
		int	start,
		int	base,
		STP_Vectype(int)	profitnodes
	)

gets nodes with positive profit on path

Parameters

scip	SCIP
g	graph data structure
tpaths	storage for terminal paths
sdprofit	SD bias for nodes
start	start vertex
base	base vertex (terminal)
profitnodes	NOTE: needs to be of capacity at least g->knots!

Definition at line 1842 of file graph_tpath.c.

References shortest_path::edge, graph_edge_isInRange(), graph_get_nNodes(), graph_knot_isInRange(), GT, Is_term, GRAPH::knots, nodes_to_terminal_paths::nnodes, reduce_sdprofitGetProfit(), SCIP_Real, STP_TPATHS_NTERMBASES, StpVecClear, StpVecGetcapacity, StpVecGetSize, StpVecPushBack, GRAPH::tail, GRAPH::term, nodes_to_terminal_paths::termbases, and nodes_to_terminal_paths::termpaths.

Referenced by sdgraphUpdateDistgraphFromTpaths().

◆ graph_tpathsAdd1st()

void graph_tpathsAdd1st	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SDPROFIT *	sdprofit,
		TPATHS *	tpaths
	)

Computes next terminal to all non-terminal nodes. Essentially a Voronoi diagram

Parameters

g	graph data structure
cost	edge costs
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths

Definition at line 1932 of file graph_tpath.c.

References FARAWAY, graph_get_nNodes(), Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::path_heap, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsScan1st(), and UNKNOWN.

Referenced by graph_add1stTermPaths(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), and graph_tpathsSetAll4().

◆ graph_tpathsAdd2nd()

void graph_tpathsAdd2nd	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		TPATHS *	tpaths
	)

computes 2nd next terminal to all non-terminal nodes

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths

Definition at line 1987 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), SCIP_Real, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), tpathsResetMembers(), and tpathsScan2nd().

Referenced by graph_add2ndTermPaths(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), and graph_tpathsSetAll4().

◆ graph_tpathsAdd3rd()

void graph_tpathsAdd3rd	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		TPATHS *	tpaths
	)

computes 3rd next terminal to all non-terminal nodes

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths

Definition at line 2044 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), SCIP_Real, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), tpathsResetMembers(), and tpathsScan3rd().

Referenced by graph_add3rdTermPaths(), graph_tpathsSetAll3(), and graph_tpathsSetAll4().

◆ graph_tpathsAdd4th()

void graph_tpathsAdd4th	(	const GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		TPATHS *	tpaths
	)

computes 4th next terminal to all non-terminal nodes

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths

Definition at line 2112 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), SCIP_Real, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), tpathsResetMembers(), and tpathsScan4th().

Referenced by graph_add4thTermPaths(), and graph_tpathsSetAll4().

◆ graph_tpathsSetAll2()

void graph_tpathsSetAll2	(	GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		TPATHS *	tpaths
	)

computes 2 next terminal to all non-terminal nodes

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths

Definition at line 2180 of file graph_tpath.c.

References EPSILON, graph_get_nNodes(), graph_mark(), graph_pc_isPcMw(), graph_tpathsAdd1st(), graph_tpathsAdd2nd(), LE_FEAS_EPS, nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by graph_get2nextTermPaths().

◆ graph_tpathsSetAll3()

void graph_tpathsSetAll3	(	GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		TPATHS *	tpaths
	)

computes 3 next terminal to all non-terminal nodes

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths

Definition at line 2219 of file graph_tpath.c.

References EPSILON, graph_get_nNodes(), graph_mark(), graph_pc_isPcMw(), graph_tpathsAdd1st(), graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), LE_FEAS_EPS, nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by graph_get3nextTermPaths().

◆ graph_tpathsSetAll4()

void graph_tpathsSetAll4	(	GRAPH *	g,
		const SCIP_Real *	cost,
		const SCIP_Real *	costrev,
		const SDPROFIT *	sdprofit,
		TPATHS *	tpaths
	)

computes 4 next terminal to all non-terminal nodes

Parameters

g	graph data structure
cost	edge costs
costrev	reversed edge costs
sdprofit	SD bias for nodes or NULL
tpaths	storage for terminal paths

Definition at line 2260 of file graph_tpath.c.

References graph_get_nNodes(), graph_mark(), graph_tpathsAdd1st(), graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), graph_tpathsAdd4th(), LE, nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by graph_get4nextTermPaths(), testBiasedTerminalPathsTo4NextFound(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), tpathsBuild(), and tpathsBuildBiased().

◆ graph_tpathsFree()

void graph_tpathsFree	(	SCIP *	scip,
		TPATHS **	tpaths
	)

frees TPATHS structure

Parameters

scip	SCIP
tpaths	the terminal paths

Definition at line 2300 of file graph_tpath.c.

References SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, nodes_to_terminal_paths::state, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termbases_org, and nodes_to_terminal_paths::termpaths.

Referenced by reduce_sdFree(), testBiasedTerminalPathsTo4NextFound(), testSdGraphStrongBiasedDistsAreValid(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), and testTerminalPathsTo3NextFound().

◆ graph_tpathsGetClosestTerm()

void graph_tpathsGetClosestTerm	(	const GRAPH *	g,
		const TPATHS *	tpaths,
		int	node,
		int *RESTRICT	closeterm,
		int *RESTRICT	firstedge,
		SCIP_Real *RESTRICT	closeterm_dist
	)

gets (up to) four close terminals to given node i; with strict upper bound on allowed distances

Parameters

g	graph
tpaths	the terminal paths
node	node
closeterm	terminal
firstedge	corresponding first edge (can be NULL)
closeterm_dist	terminal distance

Definition at line 2322 of file graph_tpath.c.

References shortest_path::dist, shortest_path::edge, graph_knot_isInRange(), Is_term, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, and UNKNOWN.

◆ graph_tpathsGet3CloseTerms()

void graph_tpathsGet3CloseTerms	(	const GRAPH *	g,
		const TPATHS *	tpaths,
		int	node,
		SCIP_Real	maxdist_strict,
		int *RESTRICT	closeterms,
		int *RESTRICT	firstedges,
		SCIP_Real *RESTRICT	closeterms_dist,
		int *RESTRICT	ncloseterms
	)

gets (up to) three close terminals to given node i; with strict upper bound on allowed distances

Parameters

g	graph
tpaths	the terminal paths
node	node
maxdist_strict	maximum valid distance (strict)
closeterms	three close terminals
firstedges	corresponding first edge (can be NULL)
closeterms_dist	three close terminal distance
ncloseterms	number of close terminals found

Definition at line 2356 of file graph_tpath.c.

References SCIP_Bool, tpathsGetKCloseTerms(), and TRUE.

◆ graph_tpathsGet4CloseTerms()

void graph_tpathsGet4CloseTerms	(	const GRAPH *	g,
		const TPATHS *	tpaths,
		int	node,
		SCIP_Real	maxdist_strict,
		int *RESTRICT	closeterms,
		int *RESTRICT	firstedges,
		SCIP_Real *RESTRICT	closeterms_dist,
		int *RESTRICT	ncloseterms
	)

gets (up to) four close terminals to given node i; with strict upper bound on allowed distances

Parameters

g	graph
tpaths	the terminal paths
node	node
maxdist_strict	maximum valid distance (strict)
closeterms	four close terminals
firstedges	corresponding first edge (can be NULL)
closeterms_dist	four close terminal distance
ncloseterms	number of close terminals found

Definition at line 2374 of file graph_tpath.c.

References SCIP_Bool, tpathsGetKCloseTerms(), and TRUE.

◆ graph_tpathsGet4CloseTermsLE()

void graph_tpathsGet4CloseTermsLE	(	const GRAPH *	g,
		const TPATHS *	tpaths,
		int	node,
		SCIP_Real	maxdist_nonstrict,
		int *RESTRICT	closeterms,
		int *RESTRICT	firstedges,
		SCIP_Real *RESTRICT	closeterms_dist,
		int *RESTRICT	ncloseterms
	)

gets (up to) four close terminals to given node i with non-strict upper bound on allowed distances

Parameters

g	graph
tpaths	the terminal paths
node	node
maxdist_nonstrict	maximum valid distance (not strict)
closeterms	four close terminals
firstedges	corresponding first edge (can be NULL)
closeterms_dist	four close terminal distance
ncloseterms	number of close terminals found

Definition at line 2392 of file graph_tpath.c.

References FALSE, SCIP_Bool, and tpathsGetKCloseTerms().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ STP_TPATHS_NTERMBASES

◆ STP_TPATHS_RESERVESIZE

◆ pathResetSingle

◆ tpathsRepairResetNode

Typedef Documentation

◆ TREPAIR

Function Documentation

◆ pathheapGetNearest()

◆ pathheapCorrectDist()

◆ utdist()

◆ tpathsPrintPath()

◆ tpathsAlloc()

◆ tpathsResetMembers()

◆ tpathsGetKCloseTerms()

◆ tpathsGetDistNew()

◆ tpathsBuild()

◆ tpathsBuildBiased()

◆ tpathsScan1st()

◆ tpathsScan2nd()

◆ tpathsScan3rd()

◆ tpathsScan4th()

◆ tpathsRepairInitLevel()

◆ tpathsRepairExitLevel()

◆ tpathsRepairTraverse1st()

◆ tpathsRepairTraverseLevelWithStack()

◆ tpathsRepairTraverseStackAddEdge()

◆ tpathsRepairTraverseStackAddBelow()

◆ tpathsRepairTraverseLevel()

◆ tpathsRepairUpdate1st()

◆ tpathsRepairUpdateLevel()

◆ tpathsRepair1st()

◆ tpathsRepair2nd()

◆ tpathsRepair3rd()

◆ tpathsRepair4th()

◆ tpathsRepairInit()

◆ tpathsRepairExit()

◆ graph_add1stTermPaths()

◆ graph_add2ndTermPaths()

◆ graph_add3rdTermPaths()

◆ graph_add4thTermPaths()

◆ graph_get2nextTermPaths()

◆ graph_get3nextTermPaths()

◆ graph_get4nextTermPaths()

◆ graph_get4nextTTerms()

◆ graph_tpathsInit()

◆ graph_tpathsInitBiased()

◆ graph_tpathsRepairSetUp()

◆ graph_tpathsRepair()

◆ graph_tpathsRecomputeBiased()

◆ graph_tpathsPrintForNode()

◆ graph_tpathsGetProfitNodes()

◆ graph_tpathsAdd1st()

◆ graph_tpathsAdd2nd()

◆ graph_tpathsAdd3rd()

◆ graph_tpathsAdd4th()

◆ graph_tpathsSetAll2()

◆ graph_tpathsSetAll3()

◆ graph_tpathsSetAll4()

◆ graph_tpathsFree()

◆ graph_tpathsGetClosestTerm()

◆ graph_tpathsGet3CloseTerms()

◆ graph_tpathsGet4CloseTerms()

◆ graph_tpathsGet4CloseTermsLE()