graph_sdpath.c File Reference

Detailed Description

Special distance path and walk algorithms for Steiner problems.

Author

Daniel Rehfeldt

This file encompasses various special distance path (and walk) algorithms for Steiner tree and related problems.

Definition in file graph_sdpath.c.

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

Go to the source code of this file.

Data Structures
struct	special_distance_clique_paths

Typedefs
typedef struct special_distance_clique_paths	CLIQUEPATHS

Functions
static SCIP_RETCODE	cliquePathsInitData (SCIP *scip, const GRAPH *g, CLIQUEPATHS *cliquepaths)
static void	cliquePathsFreeData (SCIP *scip, CLIQUEPATHS *cliquepaths)
static SCIP_Real	sdwalkGetdistnewEdge (const int *prevedges, const int *nprevedges, const SCIP_Real *cost, const SCIP_Real *dist, int k, int e, int maxnprevs)
static SCIP_Real	sdwalkGetdistnewPrize (const int *prevNPterms, const int *nprevNPterms, const int *termmark, const STP_Bool *visited, const SCIP_Real *prize, int k, int m, SCIP_Real distnew, int maxnprevs)
static SCIP_Bool	sdwalkHasConflict (const GRAPH *g, int node, int prednode, int maxnprevs, const int *prevterms, const int *nprevterms, const SCIP_Bool nodevisited)
static void	sdwalkUpdate (const GRAPH *g, int node, int prednode, int maxnprevs, int *prevterms, int *nprevterms)
static void	sdwalkUpdateCopy (int node, int prednode, int maxnprevs, int *prev, int *nprev)
static void	sdwalkUpdate2 (const int *termmark, int node, int prednode, int edge, int maxnprevs, SCIP_Bool clear, int *prevterms, int *nprevterms, int *prevNPterms, int *nprevNPterms, int *prevedges, int *nprevedges)
static void	sdwalkReset (int nvisits, const int *visitlist, SCIP_Real *dist, int *state, STP_Bool *visited)
static void	sdwalkCorrectHeap (int *RESTRICT heap, int *RESTRICT state, int *RESTRICT count, SCIP_Real *RESTRICT pathdist, int node, SCIP_Real newcost)
static int	sdCliqueStarGetSdPosition (int ncliquenodes, int newnode, int prednode, const SCIP_Real *nodes_dist, const int *nodes_base, const int *baseToClique)
static void	sdCliqueStarUpdateNodeMaxDist (int newnode, int prednode, const SCIP_Real *nodes_dist, SCIP_Real newprofit, SCIP_Real newedgecost, SCIP_Real *RESTRICT nodes_distBaseToMax, SCIP_Real *RESTRICT nodes_distFromMax, SCIP_Real *RESTRICT nodes_maxpathprofit)
static void	sdCliqueStarUpdateNodeDist (int newnode, int prednode, SCIP_Real newdist, DHEAP *RESTRICT dheap, SCIP_Real *RESTRICT nodes_dist, int *RESTRICT nodes_base, int *RESTRICT nodes_pred)
static SCIP_Real	sdGet2ProfitsDist (SCIP_Real distBaseToBase, SCIP_Real distBaseToProfit1, SCIP_Real distBaseToProfit2, SCIP_Real profit1, SCIP_Real profit2)
static SCIP_Real	sdGet1ProfitDist (SCIP_Real distBaseToBase, SCIP_Real distBaseToProfit, SCIP_Real profit)
static SCIP_Real	sdCliqueStarGetNodeBias (const SDPROFIT *sdprofit, int node, int nextnode, int prevnode, SCIP_Real edgecost, SCIP_Real dist)
static void	sdCliqueStarGetFinalProfitData (const SDPROFIT *sdprofit, int centernode, int node, int neighbor, const SCIP_Real *nodes_dist, const int *nodes_pred, const SCIP_Real *nodes_distBaseToMax, const SCIP_Real *nodes_distFromMax, const SCIP_Real *nodes_maxpathprofit, SCIP_Real *distToMax, SCIP_Real *distFromMax, SCIP_Real *maxprofit_node, SCIP_Bool *nodeHasMaxProfit)
static void	sdCliqueStarUpdateSd (const SDPROFIT *sdprofit, const int *nodes_pred, const SCIP_Real *nodes_baseToMaxDist, const SCIP_Real *nodes_distFromMax, const SCIP_Real *nodes_maxpathprofit, int ncliquenodes, int centernode, int newnode, int prednode, SCIP_Real newdist, SCIP_Real edgecost, const SCIP_Real *nodes_dist, const int *nodes_base, const int *baseToClique, SCIP_Real *RESTRICT sds)
static void	sdCliqueStarInit (const GRAPH *g, SDCLIQUE *cliquedata, CLIQUEPATHS *cliquepaths)
static SCIP_Real	sdCliqueStarGetDistLimit (const SDCLIQUE *cliquedata, const SCIP_Real *sds)
static void	sdCliqueStarComputeSds (const GRAPH *g, const SDPROFIT *sdprofit, SDCLIQUE *cliquedata, CLIQUEPATHS *cliquepaths, SCIP_Real *RESTRICT sds)
void	graph_sdStar (SCIP *scip, const GRAPH *g, SCIP_Bool with_zero_edges, int star_root, int edgelimit, int *star_base, SCIP_Real *dist, int *visitlist, int *nvisits, DHEAP *dheap, STP_Bool *visited, SCIP_Bool *success)
SCIP_RETCODE	graph_sdStarBiased (SCIP *scip, const GRAPH *g, const SDPROFIT *sdprofit, int star_root, int *star_base, DIJK *dijkdata, SCIP_Bool *success)
SCIP_RETCODE	graph_sdCloseNodesBiased (SCIP *scip, const GRAPH *g, const SDPROFIT *sdprofit, int sourcenode, DIJK *dijkdata)
SCIP_Bool	graph_sdWalks (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const int *termmark, SCIP_Real distlimit, int start, int end, int edgelimit, SCIP_Real *dist, int *heap, int *state, int *visitlist, int *nvisits, STP_Bool *visited)
SCIP_Bool	graph_sdWalks_csr (SCIP *scip, const GRAPH *g, const int *termmark, SCIP_Real distlimit, int start, int end, int edgelimit, SCIP_Real *dist, int *visitlist, int *nvisits, DHEAP *dheap, STP_Bool *visited)
SCIP_Bool	graph_sdWalksTriangle (SCIP *scip, const GRAPH *g, const int *termmark, const int *stateprev, SCIP_Real distlimit, int start, int end, int edgelimit, SCIP_Real *prizeoffset, SCIP_Real *dist, int *visitlist, int *nvisits, DHEAP *dheap, STP_Bool *visited)
SCIP_Bool	graph_sdWalksExt (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real distlimit, int start, int end, int edgelimit, int maxnprevs, SCIP_Real *dist, int *prevterms, int *nprevterms, int *heap, int *state, int *visitlist, int *nvisits, STP_Bool *visited)
SCIP_Bool	graph_sdWalksExt2 (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const int *termmark, SCIP_Real distlimit, int start, int end, int edgelimit, int maxnprevs, SCIP_Real *dist, int *prevterms, int *nprevterms, int *prevNPterms, int *nprevNPterms, int *prevedges, int *nprevedges, int *heap, int *state, int *visitlist, int *nvisits, STP_Bool *visited)
SCIP_Bool	graph_sdWalksConnected (SCIP *scip, const GRAPH *g, const int *termmark, const SCIP_Real *cost, const STP_Bool *endpoint, int start, int edgelimit, SCIP_Real *dist, int *visitlist, int *nvisits, STP_Bool *visited, SCIP_Bool resetarrays)
SCIP_RETCODE	graph_sdComputeCliqueStar (SCIP *scip, const GRAPH *g, const SDPROFIT *sdprofit, SDCLIQUE *cliquedata)

Typedef Documentation

CLIQUEPATHS

typedef struct special_distance_clique_paths CLIQUEPATHS

internal data for clique-paths computations

Function Documentation

cliquePathsInitData()

static SCIP_RETCODE cliquePathsInitData ( SCIP *  scip, const GRAPH *  g, CLIQUEPATHS *  cliquepaths  )

static

initializes clique paths

Parameters

scip	SCIP data structure
g	graph data structure
cliquepaths	data

Definition at line 51 of file graph_sdpath.c.

References graph_get_nNodes(), nnodes, special_distance_clique_paths::nodes_base, special_distance_clique_paths::nodes_baseToClique, special_distance_clique_paths::nodes_distBaseToMax, special_distance_clique_paths::nodes_distFromMax, special_distance_clique_paths::nodes_maxprofit, special_distance_clique_paths::nodes_pred, SCIP_CALL, SCIP_OKAY, and SCIPallocBufferArray.

Referenced by graph_sdComputeCliqueStar().

cliquePathsFreeData()

static void cliquePathsFreeData ( SCIP *  scip, CLIQUEPATHS *  cliquepaths  )

static

frees clique paths

Parameters

scip	SCIP data structure
cliquepaths	data

Definition at line 74 of file graph_sdpath.c.

References special_distance_clique_paths::nodes_base, special_distance_clique_paths::nodes_baseToClique, special_distance_clique_paths::nodes_distBaseToMax, special_distance_clique_paths::nodes_distFromMax, special_distance_clique_paths::nodes_maxprofit, special_distance_clique_paths::nodes_pred, and SCIPfreeBufferArray.

Referenced by graph_sdComputeCliqueStar().

sdwalkGetdistnewEdge()

static SCIP_Real sdwalkGetdistnewEdge ( const int *  prevedges, const int *  nprevedges, const SCIP_Real *  cost, const SCIP_Real *  dist, int  k, int  e, int  maxnprevs  )

inlinestatic

gets distance for extension along edge e

Parameters

prevedges	previous edges per node
nprevedges	number of previous edges per node
cost	cost
dist	distance
k	previous node
e	current outgoing edge
maxnprevs	maximum number of previous

Definition at line 92 of file graph_sdpath.c.

References SCIP_Real.

Referenced by graph_sdWalksExt2().

sdwalkGetdistnewPrize()

static SCIP_Real sdwalkGetdistnewPrize ( const int *  prevNPterms, const int *  nprevNPterms, const int *  termmark, const STP_Bool *  visited, const SCIP_Real *  prize, int  k, int  m, SCIP_Real  distnew, int  maxnprevs  )

inlinestatic

Parameters

prevNPterms	previous np terminals per node
nprevNPterms	number of previous np terminals per node
termmark	terminal mark
visited	visited
prize	prize
k	current node
m	next node
distnew	distance of m
maxnprevs	maximum number of previous

Definition at line 140 of file graph_sdpath.c.

References MAX, and SCIP_Real.

Referenced by graph_sdWalksExt2().

sdwalkHasConflict()

static SCIP_Bool sdwalkHasConflict ( const GRAPH *  g, int  node, int  prednode, int  maxnprevs, const int *  prevterms, const int *  nprevterms, const SCIP_Bool  nodevisited  )

inlinestatic

Parameters

g	graph data structure
node	the node to be updated
prednode	the predecessor node
maxnprevs	maximum number of previous terminals to save
prevterms	previous terminals
nprevterms	number of previous terminals
nodevisited	visited node already?

Definition at line 191 of file graph_sdpath.c.

References FALSE, Is_term, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by graph_sdWalksExt(), and graph_sdWalksExt2().

sdwalkUpdate()

static void sdwalkUpdate ( const GRAPH *  g, int  node, int  prednode, int  maxnprevs, int *  prevterms, int *  nprevterms  )

inlinestatic

updates

Parameters

g	graph data structure
node	the node to be updated
prednode	the predecessor node
maxnprevs	maximum number of previous terminals to save
prevterms	previous terminals
nprevterms	number of previous terminals

Definition at line 232 of file graph_sdpath.c.

References Is_term, SCIP_Bool, and GRAPH::term.

Referenced by graph_sdWalksExt().

sdwalkUpdateCopy()

static void sdwalkUpdateCopy ( int  node, int  prednode, int  maxnprevs, int *  prev, int *  nprev  )

inlinestatic

copies from of predecessor

Parameters

node	the node to be updated
prednode	the predecessor node
maxnprevs	maximum number of previous terminals to save
prev	previous data elements
nprev	number of previous data elements

Definition at line 275 of file graph_sdpath.c.

Referenced by sdwalkUpdate2().

sdwalkUpdate2()

static void sdwalkUpdate2 ( const int *  termmark, int  node, int  prednode, int  edge, int  maxnprevs, SCIP_Bool  clear, int *  prevterms, int *  nprevterms, int *  prevNPterms, int *  nprevNPterms, int *  prevedges, int *  nprevedges  )

static

update method for second version of SD walks

Parameters

termmark	terminal mark
node	the node to be updated
prednode	the predecessor node
edge	the edge to be updated
maxnprevs	maximum number of previous terminals to save
clear	clear arrays
prevterms	previous terminals
nprevterms	number of previous terminals
prevNPterms	previous non-proper terminals
nprevNPterms	number of previous non-proper terminals
prevedges	previous edges
nprevedges	number of previous edges

Definition at line 296 of file graph_sdpath.c.

References sdwalkUpdateCopy().

Referenced by graph_sdWalksExt2().

sdwalkReset()

static void sdwalkReset ( int  nvisits, const int *  visitlist, SCIP_Real *  dist, int *  state, STP_Bool *  visited  )

inlinestatic

resets temporary data

Parameters

nvisits	number of visited nodes
visitlist	stores all visited nodes
dist	distances array, initially set to FARAWAY
state	array to indicate whether a node has been scanned
visited	stores whether a node has been visited

Definition at line 394 of file graph_sdpath.c.

References FALSE, FARAWAY, and UNKNOWN.

Referenced by graph_sdWalksConnected().

sdwalkCorrectHeap()

static void sdwalkCorrectHeap ( int *RESTRICT  heap, int *RESTRICT  state, int *RESTRICT  count, SCIP_Real *RESTRICT  pathdist, int  node, SCIP_Real  newcost  )

inlinestatic

corrects heap entry

Definition at line 416 of file graph_sdpath.c.

References UNKNOWN.

Referenced by graph_sdWalks(), graph_sdWalksConnected(), graph_sdWalksExt(), and graph_sdWalksExt2().

sdCliqueStarGetSdPosition()

static int sdCliqueStarGetSdPosition ( int  ncliquenodes, int  newnode, int  prednode, const SCIP_Real *  nodes_dist, const int *  nodes_base, const int *  baseToClique  )

inlinestatic

gets position in Sd array todo: bad design, should be somewhere central...probably not too time expensive

Parameters

ncliquenodes	number of clique nodes
newnode	new node
prednode	predecessor node
nodes_dist	distance per node
nodes_base	base per node
baseToClique	mapping to clique ID

Definition at line 457 of file graph_sdpath.c.

References MAX.

Referenced by sdCliqueStarUpdateSd().

sdCliqueStarUpdateNodeMaxDist()

static void sdCliqueStarUpdateNodeMaxDist ( int  newnode, int  prednode, const SCIP_Real *  nodes_dist, SCIP_Real  newprofit, SCIP_Real  newedgecost, SCIP_Real *RESTRICT  nodes_distBaseToMax, SCIP_Real *RESTRICT  nodes_distFromMax, SCIP_Real *RESTRICT  nodes_maxpathprofit  )

inlinestatic

updates node data

Parameters

newnode	new node
prednode	predecessor node
nodes_dist	distance per node
newprofit	new profit
newedgecost	new edge cost
nodes_distBaseToMax	nodes to max
nodes_distFromMax	maximum bias
nodes_maxpathprofit	maximum profit

Definition at line 492 of file graph_sdpath.c.

References GE, and SCIP_Real.

Referenced by sdCliqueStarComputeSds().

sdCliqueStarUpdateNodeDist()

static void sdCliqueStarUpdateNodeDist ( int  newnode, int  prednode, SCIP_Real  newdist, DHEAP *RESTRICT  dheap, SCIP_Real *RESTRICT  nodes_dist, int *RESTRICT  nodes_base, int *RESTRICT  nodes_pred  )

inlinestatic

updates node data

Parameters

newnode	new node
prednode	predecessor node
newdist	new distance
dheap	heap
nodes_dist	distance per node
nodes_base	base per node
nodes_pred	predecessor per node

Definition at line 530 of file graph_sdpath.c.

References FARAWAY, GE, graph_heap_correct(), and LT.

Referenced by sdCliqueStarComputeSds().

sdGet2ProfitsDist()

static SCIP_Real sdGet2ProfitsDist ( SCIP_Real  distBaseToBase, SCIP_Real  distBaseToProfit1, SCIP_Real  distBaseToProfit2, SCIP_Real  profit1, SCIP_Real  profit2  )

inlinestatic

gets biased special distance for two profits

Definition at line 554 of file graph_sdpath.c.

References GE, LE, miscstp_maxReal(), and SCIP_Real.

Referenced by sdCliqueStarGetNodeBias(), and sdCliqueStarUpdateSd().

sdGet1ProfitDist()

static SCIP_Real sdGet1ProfitDist ( SCIP_Real  distBaseToBase, SCIP_Real  distBaseToProfit, SCIP_Real  profit  )

inlinestatic

gets biased special distance for one profit

Definition at line 585 of file graph_sdpath.c.

References GE, LE, MAX, and SCIP_Real.

Referenced by sdCliqueStarGetNodeBias(), and sdCliqueStarUpdateSd().

sdCliqueStarGetNodeBias()

static SCIP_Real sdCliqueStarGetNodeBias ( const SDPROFIT *  sdprofit, int  node, int  nextnode, int  prevnode, SCIP_Real  edgecost, SCIP_Real  dist  )

inlinestatic

gets node biased

Parameters

sdprofit	profit or NULL
node	node to get bias for
nextnode	next node
prevnode	previous node
edgecost	edge cost
dist	distance

Definition at line 608 of file graph_sdpath.c.

References GRAPH::cost, EAT_LAST, GE, GT, GRAPH::head, Is_term, LE, special_distance_clique_paths::nodes_base, special_distance_clique_paths::nodes_pred, GRAPH::oeat, GRAPH::outbeg, reduce_sdprofitGetProfit(), SCIP_Real, sdGet1ProfitDist(), sdGet2ProfitsDist(), GRAPH::tail, and GRAPH::term.

Referenced by sdCliqueStarUpdateSd().

sdCliqueStarGetFinalProfitData()

static void sdCliqueStarGetFinalProfitData ( const SDPROFIT *  sdprofit, int  centernode, int  node, int  neighbor, const SCIP_Real *  nodes_dist, const int *  nodes_pred, const SCIP_Real *  nodes_distBaseToMax, const SCIP_Real *  nodes_distFromMax, const SCIP_Real *  nodes_maxpathprofit, SCIP_Real *  distToMax, SCIP_Real *  distFromMax, SCIP_Real *  maxprofit_node, SCIP_Bool *  nodeHasMaxProfit  )

inlinestatic

helper

Parameters

sdprofit	profit or NULL
centernode	center node
node	node
neighbor	neighbor node
nodes_dist	distance
nodes_pred	predecessors
nodes_distBaseToMax	distance
nodes_distFromMax	distance
nodes_maxpathprofit	maximum profit
distToMax	pointer
distFromMax	pointer
maxprofit_node	pointer
nodeHasMaxProfit	pointer

Definition at line 793 of file graph_sdpath.c.

References EQ, FALSE, reduce_sdprofitGetProfit(), and TRUE.

Referenced by sdCliqueStarUpdateSd().

sdCliqueStarUpdateSd()

static void sdCliqueStarUpdateSd ( const SDPROFIT *  sdprofit, const int *  nodes_pred, const SCIP_Real *  nodes_baseToMaxDist, const SCIP_Real *  nodes_distFromMax, const SCIP_Real *  nodes_maxpathprofit, int  ncliquenodes, int  centernode, int  newnode, int  prednode, SCIP_Real  newdist, SCIP_Real  edgecost, const SCIP_Real *  nodes_dist, const int *  nodes_base, const int *  baseToClique, SCIP_Real *RESTRICT  sds  )

inlinestatic

updates SD between nodes

Parameters

sdprofit	profit or NULL
nodes_pred	predecessors
nodes_baseToMaxDist	distance to max
nodes_distFromMax	distance from max
nodes_maxpathprofit	maximum profit
ncliquenodes	number of clique nodes
centernode	center node
newnode	new node
prednode	predecessor node
newdist	the new distance to 'newnode' (along prednode)
edgecost	the edgecost from 'pred' to 'new'
nodes_dist	distance per node
nodes_base	base per node
baseToClique	mapping to clique ID
sds	to be filled

Definition at line 840 of file graph_sdpath.c.

References FARAWAY, GE, GT, LE, LT, NULL, SCIP_Bool, SCIP_Real, sdCliqueStarGetFinalProfitData(), sdCliqueStarGetNodeBias(), sdCliqueStarGetSdPosition(), sdGet1ProfitDist(), and sdGet2ProfitsDist().

Referenced by sdCliqueStarComputeSds().

sdCliqueStarInit()

static void sdCliqueStarInit ( const GRAPH *  g, SDCLIQUE *  cliquedata, CLIQUEPATHS *  cliquepaths  )

static

initializes

Parameters

g	graph data structure
cliquedata	data
cliquepaths	paths data

Definition at line 929 of file graph_sdpath.c.

References special_distance_clique::cliquenodes, special_distance_clique::dijkdata, EQ, FARAWAY, graph_heap_correct(), graph_heap_isClean(), GRAPH::knots, special_distance_clique::ncliquenodes, special_distance_clique_paths::nodes_base, special_distance_clique_paths::nodes_baseToClique, special_distance_clique_paths::nodes_distBaseToMax, special_distance_clique_paths::nodes_distFromMax, special_distance_clique_paths::nodes_maxprofit, special_distance_clique_paths::nodes_pred, SCIP_Real, TRUE, and UNKNOWN.

Referenced by graph_sdComputeCliqueStar().

sdCliqueStarGetDistLimit()

static SCIP_Real sdCliqueStarGetDistLimit ( const SDCLIQUE *  cliquedata, const SCIP_Real *  sds  )

inlinestatic

returns distance limit

Parameters

cliquedata	data
sds	to be filled

Definition at line 991 of file graph_sdpath.c.

References FARAWAY, GE, GT, LT, special_distance_clique::ncliquenodes, and SCIP_Real.

Referenced by sdCliqueStarComputeSds().

sdCliqueStarComputeSds()

static void sdCliqueStarComputeSds ( const GRAPH *  g, const SDPROFIT *  sdprofit, SDCLIQUE *  cliquedata, CLIQUEPATHS *  cliquepaths, SCIP_Real *RESTRICT  sds  )

static

computes SDs

Parameters

g	graph data structure
sdprofit	profit or NULL
cliquedata	data
cliquepaths	paths data
sds	to be filled

Definition at line 1018 of file graph_sdpath.c.

References special_distance_clique::centernode, CONNECT, GRAPH::cost, special_distance_clique::dijkdata, EQ, GE, graph_heap_deleteMinReturnNode(), GT, GRAPH::head, GRAPH::knots, special_distance_clique::ncliquenodes, special_distance_clique_paths::nodes_base, special_distance_clique_paths::nodes_baseToClique, special_distance_clique_paths::nodes_distBaseToMax, special_distance_clique_paths::nodes_distFromMax, special_distance_clique_paths::nodes_maxprofit, special_distance_clique_paths::nodes_pred, NULL, GRAPH::oeat, GRAPH::outbeg, dijkstra_heap::position, reduce_sdprofitGetProfit(), SCIP_Bool, SCIP_Real, sdCliqueStarGetDistLimit(), sdCliqueStarUpdateNodeDist(), sdCliqueStarUpdateNodeMaxDist(), sdCliqueStarUpdateSd(), TRUE, and UNKNOWN.

Referenced by graph_sdComputeCliqueStar().

graph_sdStar()

void graph_sdStar	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool	with_zero_edges,
		int	star_root,
		int	edgelimit,
		int *	star_base,
		SCIP_Real *	dist,
		int *	visitlist,
		int *	nvisits,
		DHEAP *	dheap,
		STP_Bool *	visited,
		SCIP_Bool *	success
	)

limited Dijkstra, stopping at terminals

Parameters

scip	SCIP data structure
g	graph data structure
with_zero_edges	telling name
star_root	root of the start
edgelimit	maximum number of edges to consider during execution
star_base	star base node, must be initially set to SDSTAR_BASE_UNSET
dist	distances array, initially set to FARAWAY
visitlist	stores all visited nodes
nvisits	number of visited nodes
dheap	Dijkstra heap
visited	stores whether a node has been visited
success	will be set to TRUE iff at least one edge can be deleted

Definition at line 1137 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, eps, EQ, GRAPH::extended, FALSE, FARAWAY, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), GT, dynamic_csr_storage::head, GRAPH::knots, LE, LT, GRAPH::mark, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Real, SCIPepsilon(), SDSTAR_BASE_UNSET, dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by reduce_sdStar(), reduce_sdStarPc(), and reduce_sdStarPc2().

graph_sdStarBiased()

SCIP_RETCODE graph_sdStarBiased	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		int	star_root,
		int *	star_base,
		DIJK *	dijkdata,
		SCIP_Bool *	success
	)

limited Dijkstra with node bias

Parameters

scip	SCIP data structure
g	graph data structure
sdprofit	SD profit
star_root	root of the start
star_base	star base node, must be initially set to SDSTAR_BASE_UNSET
dijkdata	Dijkstra data
success	will be set to TRUE iff at least one edge can be deleted

Definition at line 1289 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, dijkstra_data::dheap, dijkstra_data::edgelimit, eps, EQ, GRAPH::extended, FALSE, FARAWAY, graph_get_nNodes(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), GT, dynamic_csr_storage::head, LE, LT, GRAPH::mark, nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dijkstra_heap::position, dynamic_csr_storage::range, reduce_sdprofitGetProfit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPepsilon(), SCIPfreeBufferArray, SDSTAR_BASE_UNSET, dijkstra_heap::size, TRUE, UNKNOWN, and dijkstra_data::visitlist.

Referenced by sdStarBiasedProcessNode().

graph_sdCloseNodesBiased()

SCIP_RETCODE graph_sdCloseNodesBiased	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		int	sourcenode,
		DIJK *	dijkdata
	)

limited Dijkstra with node bias that stops at terminals

Parameters

scip	SCIP data structure
g	graph data structure
sdprofit	SD profit or NULL
sourcenode	node to start from
dijkdata	Dijkstra data

Definition at line 1461 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, dijkstra_data::dheap, dijkstra_data::edgelimit, EQ, GRAPH::extended, FARAWAY, graph_get_nNodes(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), dynamic_csr_storage::head, Is_term, LT, nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dijkstra_heap::position, dynamic_csr_storage::range, reduce_sdprofitGetProfit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, dijkstra_heap::size, GRAPH::term, TRUE, UNKNOWN, and dijkstra_data::visitlist.

Referenced by sdneighborMarkCloseNodes().

graph_sdWalks()

SCIP_Bool graph_sdWalks	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const int *	termmark,
		SCIP_Real	distlimit,
		int	start,
		int	end,
		int	edgelimit,
		SCIP_Real *	dist,
		int *	heap,
		int *	state,
		int *	visitlist,
		int *	nvisits,
		STP_Bool *	visited
	)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
termmark	terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
distlimit	distance limit of the search
start	start
end	end
edgelimit	maximum number of edges to consider during execution
dist	distances array, initially set to FARAWAY
heap	array representing a heap
state	array to indicate whether a node has been scanned
visitlist	stores all visited nodes
nvisits	number of visited nodes
visited	stores whether a node has been visited

Definition at line 1564 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, GRAPH::mark, MAX, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), sdwalkCorrectHeap(), TRUE, and UNKNOWN.

Referenced by reduce_sdWalk().

graph_sdWalks_csr()

SCIP_Bool graph_sdWalks_csr	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	termmark,
		SCIP_Real	distlimit,
		int	start,
		int	end,
		int	edgelimit,
		SCIP_Real *	dist,
		int *	visitlist,
		int *	nvisits,
		DHEAP *	dheap,
		STP_Bool *	visited
	)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters

scip	SCIP data structure
g	graph data structure
termmark	terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
distlimit	distance limit of the search
start	start
end	end
edgelimit	maximum number of edges to consider during execution
dist	distances array, initially set to FARAWAY
visitlist	stores all visited nodes
nvisits	number of visited nodes
dheap	Dijkstra heap
visited	stores whether a node has been visited

Definition at line 1696 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, GRAPH::extended, FALSE, GRAPH::grad, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), dynamic_csr_storage::head, GRAPH::knots, LT, GRAPH::mark, MAX, dijkstra_heap::position, GRAPH::prize, dynamic_csr_storage::range, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by reduce_sdWalk_csr().

graph_sdWalksTriangle()

SCIP_Bool graph_sdWalksTriangle	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	termmark,
		const int *	stateprev,
		SCIP_Real	distlimit,
		int	start,
		int	end,
		int	edgelimit,
		SCIP_Real *	prizeoffset,
		SCIP_Real *	dist,
		int *	visitlist,
		int *	nvisits,
		DHEAP *	dheap,
		STP_Bool *	visited
	)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters

scip	SCIP data structure
g	graph data structure
termmark	terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
stateprev	state of previous run or NULL
distlimit	distance limit of the search
start	start
end	end
edgelimit	maximum number of edges to consider during execution
prizeoffset	array for storing prize offset or NULL
dist	distances array, initially set to FARAWAY
visitlist	stores all visited nodes
nvisits	number of visited nodes
dheap	Dijkstra heap
visited	stores whether a node has been visited

Definition at line 1830 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, GRAPH::extended, FALSE, GRAPH::grad, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), dynamic_csr_storage::head, GRAPH::knots, LT, GRAPH::mark, MAX, dijkstra_heap::position, GRAPH::prize, dynamic_csr_storage::range, SCIP_Bool, SCIP_Real, SCIPisLE(), SCIPisZero(), dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by reduce_sdWalkTriangle().

graph_sdWalksExt()

SCIP_Bool graph_sdWalksExt	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		SCIP_Real	distlimit,
		int	start,
		int	end,
		int	edgelimit,
		int	maxnprevs,
		SCIP_Real *	dist,
		int *	prevterms,
		int *	nprevterms,
		int *	heap,
		int *	state,
		int *	visitlist,
		int *	nvisits,
		STP_Bool *	visited
	)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
distlimit	distance limit of the search
start	start
end	end
edgelimit	maximum number of edges to consider during execution
maxnprevs	maximum number of previous terminals to save
dist	distances array, initially set to FARAWAY
prevterms	previous terminals
nprevterms	number of previous terminals
heap	array representing a heap
state	array to indicate whether a node has been scanned
visitlist	stores all visited nodes
nvisits	number of visited nodes
visited	stores whether a node has been visited

Definition at line 1999 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, Is_term, GRAPH::mark, MAX, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), sdwalkCorrectHeap(), sdwalkHasConflict(), sdwalkUpdate(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_sdWalkExt().

graph_sdWalksExt2()

SCIP_Bool graph_sdWalksExt2	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cost,
		const int *	termmark,
		SCIP_Real	distlimit,
		int	start,
		int	end,
		int	edgelimit,
		int	maxnprevs,
		SCIP_Real *	dist,
		int *	prevterms,
		int *	nprevterms,
		int *	prevNPterms,
		int *	nprevNPterms,
		int *	prevedges,
		int *	nprevedges,
		int *	heap,
		int *	state,
		int *	visitlist,
		int *	nvisits,
		STP_Bool *	visited
	)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters

scip	SCIP data structure
g	graph data structure
cost	edge costs
termmark	terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
distlimit	distance limit of the search
start	start
end	end
edgelimit	maximum number of edges to consider during execution
maxnprevs	maximum number of previous terminals to save
dist	distances array, initially set to FARAWAY
prevterms	previous terminals
nprevterms	number of previous terminals
prevNPterms	previous non-proper terminals
nprevNPterms	number of previous non-proper terminals
prevedges	previous edges
nprevedges	number of previous edges
heap	array representing a heap
state	array to indicate whether a node has been scanned
visitlist	stores all visited nodes
nvisits	number of visited nodes
visited	stores whether a node has been visited

Definition at line 2140 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, GRAPH::mark, MAX, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisZero(), sdwalkCorrectHeap(), sdwalkGetdistnewEdge(), sdwalkGetdistnewPrize(), sdwalkHasConflict(), sdwalkUpdate2(), TRUE, and UNKNOWN.

Referenced by reduce_sdWalkExt2().

graph_sdWalksConnected()

SCIP_Bool graph_sdWalksConnected	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	termmark,
		const SCIP_Real *	cost,
		const STP_Bool *	endpoint,
		int	start,
		int	edgelimit,
		SCIP_Real *	dist,
		int *	visitlist,
		int *	nvisits,
		STP_Bool *	visited,
		SCIP_Bool	resetarrays
	)

modified Dijkstra along walks for PcMw

Parameters

scip	SCIP data structure
g	graph data structure
termmark	terminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
cost	edge costs
endpoint	stores whether search should be ended at vertex
start	start vertex
edgelimit	maximum number of edges to consider during execution
dist	distances array, initially set to FARAWAY
visitlist	stores all visited nodes
nvisits	number of visited nodes
visited	stores whether a node has been visited
resetarrays	should arrays be reset?

Definition at line 2285 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIP_Real, SCIPisGT(), SCIPisLE(), sdwalkCorrectHeap(), sdwalkReset(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by daPcFindRoots(), findRootsMark(), and sepaspecial_pcimplicationsInit().

graph_sdComputeCliqueStar()

SCIP_RETCODE graph_sdComputeCliqueStar	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		SDCLIQUE *	cliquedata
	)

computes (or rather updates) SDs between all

Parameters

scip	SCIP data structure
g	graph data structure
sdprofit	profit or NULL
cliquedata	data

Definition at line 2398 of file graph_sdpath.c.

References special_distance_clique::cliquenodes, cliquePathsFreeData(), cliquePathsInitData(), special_distance_clique::dijkdata, GRAPH::knots, special_distance_clique::ncliquenodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, sdCliqueStarComputeSds(), sdCliqueStarInit(), and special_distance_clique::sds.

Referenced by reduce_sdEdgeCliqueStar(), sdCliqueUpdateGraphWithStarWalks(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), and testSdCliqueStarDeg4IsCorrect().