Scippy

SCIP

Solving Constraint Integer Programs

grphpath.c File Reference

Detailed Description

Shortest path based graph algorithms for Steiner problems.

Author
Thorsten Koch
Daniel Rehfeldt

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

The underlying heap routines can be found in Jon Bentley, Programming Pearls, Addison-Wesley 1989

The heap array is initialized with n elements (nodes), but only at most n-1 nodes can be included in the array, since element 0 is not used for storing.

Definition in file grphpath.c.

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>
#include <assert.h>
#include "portab.h"
#include "grph.h"

Go to the source code of this file.

Functions

static int nearest (int *heap, int *state, int *count, const PATH *path)
 
static int nearestX (int *heap, int *state, int *count, const SCIP_Real *pathdist)
 
static void correct (SCIP *scip, int *heap, int *state, int *count, PATH *path, int l, int k, int e, SCIP_Real cost, int mode)
 
static void correctX (SCIP *scip, int *heap, int *state, int *count, SCIP_Real *pathdist, int *pathedge, int l, int k, int e, SCIP_Real cost)
 
void heap_add (int *heap, int *state, int *count, int node, PATH *path)
 
static void resetX (SCIP *scip, SCIP_Real *pathdist, int *heap, int *state, int *count, int node)
 
static void reset (SCIP *scip, PATH *path, int *heap, int *state, int *count, int node)
 
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)
 
SCIP_RETCODE graph_path_init (SCIP *scip, GRAPH *g)
 
void graph_path_exit (SCIP *scip, GRAPH *g)
 
void graph_path_exec (SCIP *scip, const GRAPH *p, const int mode, int start, const SCIP_Real *cost, PATH *path)
 
void graph_sdPaths (SCIP *scip, const GRAPH *g, PATH *path, SCIP_Real *cost, SCIP_Real distlimit, int *heap, int *state, int *memlbl, int *nlbl, int tail, int head, int limit)
 
void graph_path_PcMwSd (SCIP *scip, const GRAPH *g, PATH *path, SCIP_Real *cost, SCIP_Real distlimit, int *pathmaxnode, int *heap, int *state, int *stateblock, int *memlbl, int *nlbl, int tail, int head, int limit)
 
void graph_path_execX (SCIP *scip, const GRAPH *g, int start, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge)
 
void graph_path_invroot (SCIP *scip, const GRAPH *g, int start, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge)
 
void graph_path_st (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, SCIP_RANDNUMGEN *randnumgen, STP_Bool *connected)
 
void graph_path_st_rpc (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)
 
void graph_path_st_pcmw (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)
 
void graph_path_st_pcmw_reduce (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *tmpnodeweight, int *result, int start, STP_Bool *connected)
 
void graph_path_st_pcmw_full (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)
 
void graph_path_st_pcmw_extend (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, PATH *path, STP_Bool *connected, SCIP_Bool *extensions)
 
void graph_path_st_rmw (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, SCIP_Real *pathdist, int *pathedge, int start, STP_Bool *connected)
 
SCIP_RETCODE graph_voronoiExtend (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, SCIP_Real **distarr, int **basearr, int **edgearr, STP_Bool *termsmark, int *reachednodes, int *nreachednodes, int *nodenterms, int nneighbterms, int base, int countex)
 
void graph_voronoi (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, STP_Bool *base, int *vbase, PATH *path)
 
void graph_get2next (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)
 
void graph_get3next (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)
 
void graph_get4next (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)
 
void graph_get3nextTerms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path3, int *vbase, int *heap, int *state)
 
void graph_get4nextTerms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)
 
SCIP_RETCODE graph_get4nextTTerms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, int *vbase, int *heap, int *state)
 
void graph_voronoiTerms (SCIP *scip, const GRAPH *g, const SCIP_Real *cost, PATH *path, int *vbase, int *heap, int *state)
 
void graph_voronoiMw (SCIP *scip, const GRAPH *g, const SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state)
 
SCIP_RETCODE graph_voronoiWithDist (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *distance, int *minedgepred, int *vbase, int *minarc, int *heap, int *state, int *distnode, PATH *path)
 
SCIP_RETCODE graph_voronoiWithRadius (SCIP *scip, const GRAPH *graph, GRAPH *adjgraph, PATH *path, SCIP_Real *rad, SCIP_Real *cost, SCIP_Real *costrev, int *vbase, int *heap, int *state)
 
void graph_voronoiWithRadiusMw (SCIP *scip, const GRAPH *g, PATH *path, const SCIP_Real *cost, SCIP_Real *radius, int *vbase, int *heap, int *state)
 
void graph_voronoiRepair (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int *count, int *vbase, PATH *path, int *newedge, int crucnode, UF *uf)
 
void graph_voronoiRepairMult (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int *count, int *vbase, int *boundedges, int *nboundedges, STP_Bool *nodesmark, UF *uf, PATH *path)
 

Function Documentation

◆ nearest()

◆ nearestX()

static int nearestX ( int *  heap,
int *  state,
int *  count,
const SCIP_Real pathdist 
)
inlinestatic

◆ correct()

◆ correctX()

static void correctX ( SCIP scip,
int *  heap,
int *  state,
int *  count,
SCIP_Real pathdist,
int *  pathedge,
int  l,
int  k,
int  e,
SCIP_Real  cost 
)
inlinestatic

◆ heap_add()

void heap_add ( int *  heap,
int *  state,
int *  count,
int  node,
PATH path 
)

Definition at line 244 of file grphpath.c.

References GT.

Referenced by computeSteinerTreeVnoi(), and SCIPStpHeurLocalRun().

◆ resetX()

static void resetX ( SCIP scip,
SCIP_Real pathdist,
int *  heap,
int *  state,
int *  count,
int  node 
)
inlinestatic

◆ reset()

static void reset ( SCIP scip,
PATH path,
int *  heap,
int *  state,
int *  count,
int  node 
)
inlinestatic

Definition at line 309 of file grphpath.c.

References shortest_path::dist, and SCIPisGT().

Referenced by graph_path_st_pcmw_extend().

◆ 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

Definition at line 343 of file grphpath.c.

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

Referenced by graph_get4nextTTerms().

◆ graph_path_init()

◆ graph_path_exit()

◆ graph_path_exec()

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

◆ graph_sdPaths()

void graph_sdPaths ( SCIP scip,
const GRAPH g,
PATH path,
SCIP_Real cost,
SCIP_Real  distlimit,
int *  heap,
int *  state,
int *  memlbl,
int *  nlbl,
int  tail,
int  head,
int  limit 
)

limited Dijkstra, stopping at terminals

Parameters
scipSCIP data structure
ggraph data structure
pathshortest paths data structure
costedge costs
distlimitdistance limit of the search
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
memlblarray to save labelled nodes
nlblnumber of labelled nodes
tailtail of the edge
headhead of the edge
limitmaximum number of edges to consider during execution

Definition at line 567 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by findDaRoots(), reduce_getSd(), reduce_sdsp(), and reduce_sdspSap().

◆ graph_path_PcMwSd()

void graph_path_PcMwSd ( SCIP scip,
const GRAPH g,
PATH path,
SCIP_Real cost,
SCIP_Real  distlimit,
int *  pathmaxnode,
int *  heap,
int *  state,
int *  stateblock,
int *  memlbl,
int *  nlbl,
int  tail,
int  head,
int  limit 
)

limited Dijkstra for PCSTP, taking terminals into account

Parameters
scipSCIP data structure
ggraph data structure
pathshortest paths data structure
costedge costs
distlimitdistance limit of the search
pathmaxnodemaximum weight node on path
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
stateblockarray to indicate whether a node has been scanned during previous SP calculation
memlblarray to save labelled nodes
nlblnumber of labelled nodes
tailtail of the edge
headhead of the edge
limitmaximum number of edges to consider during execution

Definition at line 664 of file grphpath.c.

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

Referenced by reduce_getSdPcMw(), and reduce_sdsp().

◆ graph_path_execX()

void graph_path_execX ( SCIP scip,
const GRAPH g,
int  start,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge 
)

Dijkstra's algorithm starting from node 'start'

Parameters
scipSCIP data structure
ggraph data structure
startstart vertex
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)

Definition at line 781 of file grphpath.c.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::head, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), and UNKNOWN.

Referenced by computeTransVoronoi(), reduce_boundHopR(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_rpt(), SCIPStpHeurTMRun(), and setVnoiDistances().

◆ graph_path_invroot()

void graph_path_invroot ( SCIP scip,
const GRAPH g,
int  start,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge 
)

Dijkstra on incoming edges until root is reached

Parameters
scipSCIP data structure
ggraph data structure
startstart vertex
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)

Definition at line 849 of file grphpath.c.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::path_heap, GRAPH::path_state, SCIP_Real, SCIPisGT(), GRAPH::source, GRAPH::tail, and UNKNOWN.

◆ graph_path_st()

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

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

Parameters
scipSCIP data structure
ggraph data structure
costedgecosts
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
randnumgenrandom number generator
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 926 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijk().

◆ graph_path_st_rpc()

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

For rooted prize-collecting problem find a tree rooted in node 'start' and connecting positive vertices as long as this is profitable. Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1033 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_path_st_pcmw()

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

Find a tree rooted in node 'start' and connecting positive vertices as long as this is profitable. Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1154 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGT(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_path_st_pcmw_reduce()

void graph_path_st_pcmw_reduce ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real tmpnodeweight,
int *  result,
int  start,
STP_Bool connected 
)

Reduce given solution Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
tmpnodeweightnode weight array
resultincoming arc array
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1264 of file grphpath.c.

References CONNECT, EAT_LAST, FALSE, GRAPH::head, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPfreeBufferArray, SCIPisGE(), GRAPH::term, and UNKNOWN.

◆ graph_path_st_pcmw_full()

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

Find a tree rooted in node 'start' and connecting all positive vertices. Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1316 of file grphpath.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIPisGT(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMwFull().

◆ graph_path_st_pcmw_extend()

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

greedy extension of a given tree for PC or MW problems

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathshortest paths data structure
connectedarray to mark whether a vertex is part of computed Steiner tree
extensionsextensions performed?

Definition at line 1410 of file grphpath.c.

References correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FARAWAY, FSP_MODE, GRAPH::grad, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, reset(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ graph_path_st_rmw()

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

Shortest path heuristic for the RMWCSP Find a directed tree rooted in node 'start' and connecting all terminals as well as all positive vertices (as long as this is profitable).

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1536 of file grphpath.c.

References correctX(), GRAPH::cost, EAT_LAST, FALSE, FARAWAY, GRAPH::grad, GRAPH::head, Is_gterm, Is_pterm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, resetX(), SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_voronoiExtend()

SCIP_RETCODE graph_voronoiExtend ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
PATH path,
SCIP_Real **  distarr,
int **  basearr,
int **  edgearr,
STP_Bool termsmark,
int *  reachednodes,
int *  nreachednodes,
int *  nodenterms,
int  nneighbterms,
int  base,
int  countex 
)

extend a voronoi region until all neighbouring terminals are spanned

Parameters
scipSCIP data structure
ggraph data structure
costedgecosts
pathshortest paths data structure
distarrarray to store distance from each node to its base
basearrarray to store the bases
edgearrarray to store the ancestor edge
termsmarkarray to mark terminal
reachednodesarray to mark reached nodes
nreachednodespointer to number of reached nodes
nodentermsarray to store number of terimals to each node
nneighbtermsnumber of neighbouring terminals
basevoronoi base
countexcount of heap elements

Definition at line 1671 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, FSP_MODE, GT, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_OKAY, GRAPH::term, and TRUE.

Referenced by computeSteinerTreeVnoi().

◆ graph_voronoi()

void graph_voronoi ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real costrev,
STP_Bool base,
int *  vbase,
PATH path 
)

build a voronoi region, w.r.t. shortest paths, for a given set of bases

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
basearray to indicate whether a vertex is a Voronoi base
vbasevoronoi base to each vertex
pathpath data struture (leading to respective Voronoi base)

Definition at line 1751 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, GRAPH::knots, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), GRAPH::source, and UNKNOWN.

Referenced by computeSteinerTreeVnoi(), and SCIPStpHeurLocalRun().

◆ graph_get2next()

void graph_get2next ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

2th next terminal to all non terminal nodes

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
pathpath data structure (leading to first and second nearest terminal)
vbasefirst and second nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 1838 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by graph_get3nextTerms(), graph_get4nextTerms(), reduce_bound(), reduce_boundHop(), reduce_boundMw(), reduce_boundPrune(), and reduce_daPcMw().

◆ graph_get3next()

void graph_get3next ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)
Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
pathpath data structure (leading to first, second and third nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 1934 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by graph_get3nextTerms(), graph_get4nextTerms(), reduce_bound(), and reduce_boundPrune().

◆ graph_get4next()

void graph_get4next ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)
Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
pathpath data struture (leading to first, second and third nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2041 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by graph_get4nextTerms(), and reduce_bound().

◆ graph_get3nextTerms()

void graph_get3nextTerms ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real costrev,
PATH path3,
int *  vbase,
int *  heap,
int *  state 
)

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
path3path data struture (leading to first, second and third nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2150 of file grphpath.c.

References GRAPH::grad, graph_get2next(), graph_get3next(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

◆ graph_get4nextTerms()

void graph_get4nextTerms ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

build a voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
costrevreversed edge costs
pathpath data struture (leading to first, second, third and fouth nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2186 of file grphpath.c.

References GRAPH::grad, graph_get2next(), graph_get3next(), graph_get4next(), graph_voronoiTerms(), GRAPH::knots, GRAPH::mark, NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

Referenced by reduce_da(), reduce_daSlackPrune(), reduce_sd(), and reduce_sdPc().

◆ graph_get4nextTTerms()

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

get 4 close terminals to each terminal

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathpath data structure (leading to first, second, third and fourth nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2227 of file grphpath.c.

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

Referenced by reduce_bound(), and reduce_sdPc().

◆ graph_voronoiTerms()

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

build a Voronoi region in presolving, w.r.t. shortest paths, for all terminals

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathpath data structure (leading to respective Voronoi base)
vbaseVoronoi base to each vertex
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2307 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGT(), GRAPH::term, and UNKNOWN.

Referenced by computeTransVoronoi(), graph_get3nextTerms(), graph_get4nextTerms(), reduce_boundHopR(), reduce_boundHopRc(), reduce_da(), reduce_daPcMw(), reduce_daSlackPruneMw(), reduce_ledge(), reduce_sl(), and setVnoiDistances().

◆ graph_voronoiMw()

void graph_voronoiMw ( SCIP scip,
const GRAPH g,
const SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

build a Voronoi region, w.r.t. shortest paths, for all positive vertices

Parameters
scipSCIP data structure
ggraph data structure
costrevreversed edge costs
pathpath data structure (leading to respective Voronoi base)
vbaseVoronoi base to each vertex
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 2383 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), GRAPH::term, and UNKNOWN.

Referenced by reduce_boundMw(), and reduce_boundPrune().

◆ graph_voronoiWithDist()

SCIP_RETCODE graph_voronoiWithDist ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
SCIP_Real distance,
int *  minedgepred,
int *  vbase,
int *  minarc,
int *  heap,
int *  state,
int *  distnode,
PATH path 
)

build a voronoi region, w.r.t. shortest paths, for all terminal and the distance

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
distancearray storing path from a terminal over shortest incident edge to nearest terminal
minedgepredshortest edge predecessor array
vbasearray containing Voronoi base to each node
minarcarray to mark whether an edge is one a path corresponding to 'distance'
heaparray representing a heap
statearray indicating state of each vertex during calculation of Voronoi regions
distnodearray to store terminal corresponding to distance stored in distance array
patharray containing Voronoi paths data

Definition at line 2463 of file grphpath.c.

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::edges, FALSE, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_OKAY, SCIP_Real, SCIPisEQ(), SCIPisGT(), SCIPisLT(), GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

◆ graph_voronoiWithRadius()

SCIP_RETCODE graph_voronoiWithRadius ( SCIP scip,
const GRAPH graph,
GRAPH adjgraph,
PATH path,
SCIP_Real rad,
SCIP_Real cost,
SCIP_Real costrev,
int *  vbase,
int *  heap,
int *  state 
)

build voronoi regions, w.r.t. shortest paths, for all terminals and compute the radii

Parameters
scipSCIP data structure
graphgraph data structure
adjgraphgraph data structure
patharray containing Voronoi paths data
radarray storing shortest way from a terminal out of its Voronoi region
costedge costs
costrevreversed edge costs
vbasearray containing Voronoi base of each node
heaparray representing a heap
statearray to mark state of each node during calculation

Definition at line 2614 of file grphpath.c.

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, FARAWAY, FSP_MODE, graph_edge_add(), graph_knot_add(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by reduce_bound(), reduce_boundHop(), and reduce_boundPrune().

◆ graph_voronoiWithRadiusMw()

void graph_voronoiWithRadiusMw ( SCIP scip,
const GRAPH g,
PATH path,
const SCIP_Real cost,
SCIP_Real radius,
int *  vbase,
int *  heap,
int *  state 
)

Build partition of graph for MWCSP into regions around the positive vertices. Store the weight of a minimum weight center-boundary path for each region in the radius array (has to be reverted to obtain the final r() value).

Parameters
scipSCIP data structure
ggraph data structure
patharray containing graph decomposition data
costedge costs
radiusarray storing shortest way from a positive vertex out of its region
vbasearray containing base of each node
heaparray representing a heap
statearray to mark state of each node during calculation

Definition at line 2852 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by reduce_boundMw().

◆ graph_voronoiRepair()

void graph_voronoiRepair ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
int *  count,
int *  vbase,
PATH path,
int *  newedge,
int  crucnode,
UF uf 
)

repair a Voronoi diagram for a given set of base nodes

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
countpointer to number of heap elements
vbasearray containing Voronoi base of each node
pathVoronoi paths data struture
newedgethe new edge
crucnodethe current crucial node
ufunion find data structure

Definition at line 2979 of file grphpath.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), SCIPStpunionfindFind(), GRAPH::tail, and UNKNOWN.

Referenced by SCIPStpHeurLocalRun().

◆ graph_voronoiRepairMult()

void graph_voronoiRepairMult ( SCIP scip,
const GRAPH g,
SCIP_Real cost,
int *  count,
int *  vbase,
int *  boundedges,
int *  nboundedges,
STP_Bool nodesmark,
UF uf,
PATH path 
)

repair the Voronoi diagram for a given set nodes

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
countpointer to number of heap elements
vbasearray containing Voronoi base of each node
boundedgesboundary edges
nboundedgesnumber of boundary edges
nodesmarkarray to mark temporarily discarded nodes
ufunion find data structure
pathVoronoi paths data structure

Definition at line 3057 of file grphpath.c.

References CONNECT, correct(), EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), and SCIPStpunionfindFind().

Referenced by SCIPStpHeurLocalRun().