|
|
Shortest path based graph algorithms for Steiner problems.
- Author
- Thorsten Koch
-
Daniel Rehfeldt
This file encompasses various (heap-based) shortest path based algorithms inluding 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.
|
| 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 | 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, int mode, int start, SCIP_Real *cost, PATH *path) |
| |
| void | 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_execX (SCIP *scip, const GRAPH *g, int start, 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, unsigned int *randseed, char *connected) |
| |
| SCIP_RETCODE | voronoi_extend (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, VLIST **adjterms, char *termsmark, int *reachednodes, int *nreachednodes, int *nodenterms, int nneighbterms, int base, int countex) |
| |
| SCIP_RETCODE | voronoi_extend2 (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, SCIP_Real **distarr, int **basearr, int **edgearr, char *termsmark, int *reachednodes, int *nreachednodes, int *nodenterms, int nneighbterms, int base, int countex) |
| |
| void | voronoi (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, char *base, int *vbase, PATH *path) |
| |
| void | voronoiSteinerTreeExt (SCIP *scip, const GRAPH *g, SCIP_Real *costrev, int *vbase, char *stvertex, PATH *path) |
| |
| void | get2next (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state) |
| |
| void | get3next (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state) |
| |
| void | get4next (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state) |
| |
| void | getnext3terms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path3, int *vbase, int *heap, int *state) |
| |
| void | getnext4terms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *costrev, PATH *path, int *vbase, int *heap, int *state) |
| |
| void | getnext4tterms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, SCIP_Real *boundedges, PATH *path, int *vbase, int *heap, int *state) |
| |
| void | voronoi_terms (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, int *vbase, int *heap, int *state) |
| |
| SCIP_RETCODE | voronoi_dist (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 | voronoi_radius (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 | voronoi_slrepair (SCIP *scip, const GRAPH *g, SCIP_Real *cost, PATH *path, int *vbase, int *heap, int *state, int start, int adjnode) |
| |
| void | voronoi_repair (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int *count, int *vbase, PATH *path, int *newedge, int crucnode, UF *uf) |
| |
| void | voronoi_repair_mult (SCIP *scip, const GRAPH *g, SCIP_Real *cost, int *count, int *vbase, int *boundedges, int *nboundedges, char *nodesmark, UF *uf, PATH *path) |
| |
| void | graph_path_length (const GRAPH *g, const PATH *p) |
| |
| static void correct |
( |
SCIP * |
scip, |
|
|
int * |
heap, |
|
|
int * |
state, |
|
|
int * |
count, |
|
|
PATH * |
path, |
|
|
int |
l, |
|
|
int |
k, |
|
|
int |
e, |
|
|
SCIP_Real |
cost, |
|
|
int |
mode |
|
) |
| |
|
inlinestatic |
Definition at line 144 of file grphpath.c.
References shortest_path::dist, shortest_path::edge, MST_MODE, and UNKNOWN.
Referenced by get2next(), get3next(), get4next(), graph_path_exec(), sdpaths(), voronoi(), voronoi_dist(), voronoi_extend(), voronoi_extend2(), voronoi_radius(), voronoi_repair(), voronoi_repair_mult(), voronoi_slrepair(), voronoi_terms(), and voronoiSteinerTreeExt().
| 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 |
| void get2next |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
SCIP_Real * |
costrev, |
|
|
PATH * |
path, |
|
|
int * |
vbase, |
|
|
int * |
heap, |
|
|
int * |
state |
|
) |
| |
2th next terminal to all non terminal nodes
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| costrev | reversed edge costs |
| path | path data struture (leading to first and second nearest terminal) |
| vbase | first and second 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 1214 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(), GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, and UNKNOWN.
Referenced by bound_reduce(), getnext3terms(), getnext4terms(), and hopbound_reduce().
| void get3next |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
SCIP_Real * |
costrev, |
|
|
PATH * |
path, |
|
|
int * |
vbase, |
|
|
int * |
heap, |
|
|
int * |
state |
|
) |
| |
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| costrev | reversed edge costs |
| path | path data struture (leading to first, second and third 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 1310 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(), GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, and UNKNOWN.
Referenced by bound_reduce(), getnext3terms(), and getnext4terms().
| void get4next |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
SCIP_Real * |
costrev, |
|
|
PATH * |
path, |
|
|
int * |
vbase, |
|
|
int * |
heap, |
|
|
int * |
state |
|
) |
| |
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| costrev | reversed edge costs |
| path | path data struture (leading to first, second and third 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 1417 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(), GRAPH::oeat, GRAPH::outbeg, GRAPH::source, GRAPH::term, and UNKNOWN.
Referenced by bound_reduce(), and getnext4terms().
| void getnext3terms |
( |
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
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| costrev | reversed edge costs |
| path3 | path data struture (leading to first, second and third 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 1526 of file grphpath.c.
References get2next(), get3next(), GRAPH::grad, GRAPH::knots, GRAPH::mark, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, and voronoi_terms().
| void getnext4terms |
( |
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
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| costrev | reversed edge costs |
| path | path data struture (leading to first, second, third and fouth 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 1562 of file grphpath.c.
References get2next(), get3next(), get4next(), GRAPH::grad, GRAPH::knots, GRAPH::mark, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, and voronoi_terms().
Referenced by da_reduce(), sd_red(), and sdpc_reduction().
| void getnext4tterms |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
SCIP_Real * |
boundedges, |
|
|
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 |
| boundedges | array to store boundary edges |
| path | path data struture (leading to first, second, third and fouth 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 1603 of file grphpath.c.
References shortest_path::dist, EAT_LAST, FARAWAY, GRAPH::grad, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, GRAPH::oeat, GRAPH::outbeg, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, UNKNOWN, and utdist().
Referenced by bound_reduce(), and sdpc_reduction().
| void graph_path_exec |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
p, |
|
|
int |
mode, |
|
|
int |
start, |
|
|
SCIP_Real * |
cost, |
|
|
PATH * |
path |
|
) |
| |
- Parameters
-
| scip | SCIP data structure |
| p | graph data structure |
| mode | shortest path (FSP_MODE) or minimum spanning tree (MST_MODE)? |
| start | start vertex |
| cost | edge costs |
| path | shortest paths data structure |
Definition at line 453 of file grphpath.c.
References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, MST_MODE, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and UNKNOWN.
Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), central_terminal(), createVariables(), graph_path_st(), hopbound_reduce(), ledge_reduction(), npvReduction(), nvsl_reduction(), pricing(), SCIPheurImproveSteinerTree(), SCIPheurPrunePCSteinerTree(), SCIPheurPruneSteinerTree(), SCIPprobdataAddNewSol(), sd_red(), and sep_2cut().
| void graph_path_execX |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
int |
start, |
|
|
SCIP_Real * |
cost, |
|
|
SCIP_Real * |
pathdist, |
|
|
int * |
pathedge |
|
) |
| |
Dijkstra's algorithm starting from node 'start'
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| start | start vertex |
| cost | edgecosts |
| pathdist | distance array (on vertices) |
| pathedge | predecessor edge array (on vertices) |
Definition at line 639 of file grphpath.c.
References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::term, and UNKNOWN.
Referenced by da_reduce(), daPc_reduce(), hcrbound_reduce(), hcrcbound_reduce(), rptReduction(), SCIP_DECL_PROPEXEC(), SCIPheurComputeSteinerTree(), and sd_red().
| void graph_path_exit |
( |
SCIP * |
scip, |
|
|
GRAPH * |
g |
|
) |
| |
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
Definition at line 429 of file grphpath.c.
References GRAPH::path_heap, and GRAPH::path_state.
Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), daPc_reduce(), hopbound_reduce(), ledge_reduction(), npvReduction(), reduce(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBDELORIG(), SCIPheurImproveSteinerTree(), and sd_red().
| SCIP_RETCODE graph_path_init |
( |
SCIP * |
scip, |
|
|
GRAPH * |
g |
|
) |
| |
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
Definition at line 407 of file grphpath.c.
References GRAPH::knots, GRAPH::path_heap, and GRAPH::path_state.
Referenced by bd3_reduction(), bdr_reduction(), bound_reduce(), daPc_reduce(), hopbound_reduce(), ledge_reduction(), npvReduction(), reduce(), SCIP_DECL_HEUREXEC(), SCIP_DECL_PROBCOPY(), SCIPheurImproveSteinerTree(), SCIPprobdataCreate(), and sd_red().
| void graph_path_length |
( |
const GRAPH * |
g, |
|
|
const PATH * |
p |
|
) |
| |
| void graph_path_st |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
SCIP_Real * |
pathdist, |
|
|
int * |
pathedge, |
|
|
int |
start, |
|
|
unsigned int * |
randseed, |
|
|
char * |
connected |
|
) |
| |
Find a directed tree rooted in node 'start' and spanning all terminals
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edgecosts |
| pathdist | distance array (on vertices) |
| pathedge | predecessor edge array (on vertices) |
| start | start vertex |
| randseed | random seed |
| connected | array to mark whether a vertex is part of computed Steiner tree |
Definition at line 707 of file grphpath.c.
References BSP_MODE, correctX(), EAT_LAST, FALSE, FARAWAY, FSP_MODE, GRAPH::grad, graph_path_exec(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by computeSteinerTreeDijk().
| void heap_add |
( |
int * |
heap, |
|
|
int * |
state, |
|
|
int * |
count, |
|
|
int |
node, |
|
|
PATH * |
path |
|
) |
| |
| static int nearest |
( |
int * |
heap, |
|
|
int * |
state, |
|
|
int * |
count, |
|
|
const PATH * |
path |
|
) |
| |
|
inlinestatic |
Definition at line 43 of file grphpath.c.
References GT, and LT.
Referenced by get2next(), get3next(), get4next(), graph_path_exec(), sdpaths(), voronoi(), voronoi_dist(), voronoi_extend(), voronoi_extend2(), voronoi_radius(), voronoi_repair(), voronoi_repair_mult(), voronoi_slrepair(), voronoi_terms(), and voronoiSteinerTreeExt().
| static int nearestX |
( |
int * |
heap, |
|
|
int * |
state, |
|
|
int * |
count, |
|
|
const SCIP_Real * |
pathdist |
|
) |
| |
|
inlinestatic |
| static void resetX |
( |
SCIP * |
scip, |
|
|
SCIP_Real * |
pathdist, |
|
|
int * |
heap, |
|
|
int * |
state, |
|
|
int * |
count, |
|
|
int |
node |
|
) |
| |
|
inlinestatic |
| void 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
-
| scip | SCIP data structure |
| g | graph data structure |
| path | shortest paths data structure |
| cost | edge costs |
| distlimit | distance limit of the search |
| heap | array representing a heap |
| state | array to indicate whether a node has been scanned during SP calculation |
| memlbl | array to save labelled nodes |
| nlbl | number of labelled nodes |
| tail | tail of the edge |
| head | head of the edge |
| limit | maximum number of edges to consider during execution |
Definition at line 542 of file grphpath.c.
References CONNECT, correct(), shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, STP_MAX_NODE_WEIGHT, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.
Referenced by getSD(), sdsp_reduction(), and sdsp_sap_reduction().
| 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 |
| void voronoi |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
SCIP_Real * |
costrev, |
|
|
char * |
base, |
|
|
int * |
vbase, |
|
|
PATH * |
path |
|
) |
| |
build a voronoi region, w.r.t. shortest paths, for a given set of bases
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| costrev | reversed edge costs |
| base | array to indicate whether a vertex is a Voronoi base |
| vbase | voronoi base to each vertex |
| path | path data struture (leading to respective Voronoi base) |
Definition at line 1034 of file grphpath.c.
References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, GRAPH::knots, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::source, and UNKNOWN.
Referenced by computeSteinerTreeVnoi(), and SCIPheurImproveSteinerTree().
| SCIP_RETCODE voronoi_dist |
( |
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
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| distance | array storing path from a terminal over shortest incident edge to nearest terminal |
| minedgepred | shortest edge predecessor array |
| vbase | array containing Voronoi base to each node |
| minarc | array to mark whether an edge is one a path corresponding to 'distance' |
| heap | array representing a heap |
| state | array indicating state of each vertex during calculation of Voronoi regions |
| distnode | array to store terminal corresponding to distance stored in distance array |
| path | array containing Voronoi paths data |
Definition at line 1755 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(), GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.
| SCIP_RETCODE voronoi_extend |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
PATH * |
path, |
|
|
VLIST ** |
adjterms, |
|
|
char * |
termsmark, |
|
|
int * |
reachednodes, |
|
|
int * |
nreachednodes, |
|
|
int * |
nodenterms, |
|
|
int |
nneighbterms, |
|
|
int |
base, |
|
|
int |
countex |
|
) |
| |
extend a voronoi region until all neighbouring terminals are spanned
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edgecosts |
| path | shortest paths data structure |
| adjterms | structure for adjacent terminal data |
| termsmark | array to mark terminal |
| reachednodes | array to mark reached nodes |
| nreachednodes | pointer to number of reached nodes |
| nodenterms | array to store number of terimals to each node |
| nneighbterms | number of neighbouring terminals |
| base | voronoi base |
| countex | number of heap elements |
Definition at line 862 of file grphpath.c.
References Vnoi_List_Node::base, CONNECT, correct(), Vnoi_List_Node::dist, shortest_path::dist, EAT_LAST, Vnoi_List_Node::edge, shortest_path::edge, FALSE, FSP_MODE, GT, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), Vnoi_List_Node::next, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and TRUE.
| SCIP_RETCODE voronoi_extend2 |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
PATH * |
path, |
|
|
SCIP_Real ** |
distarr, |
|
|
int ** |
basearr, |
|
|
int ** |
edgearr, |
|
|
char * |
termsmark, |
|
|
int * |
reachednodes, |
|
|
int * |
nreachednodes, |
|
|
int * |
nodenterms, |
|
|
int |
nneighbterms, |
|
|
int |
base, |
|
|
int |
countex |
|
) |
| |
extend a voronoi region until all neighbouring terminals are spanned
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edgecosts |
| path | shortest paths data structure |
| distarr | array to store distance from each node to its base |
| basearr | array to store the bases |
| edgearr | array to store the ancestor edge |
| termsmark | array to mark terminal |
| reachednodes | array to mark reached nodes |
| nreachednodes | pointer to number of reached nodes |
| nodenterms | array to store number of terimals to each node |
| nneighbterms | number of neighbouring terminals |
| base | voronoi base |
| countex | count of heap elements |
Definition at line 954 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(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::term, and TRUE.
Referenced by computeSteinerTreeVnoi().
| SCIP_RETCODE voronoi_radius |
( |
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
-
| scip | SCIP data structure |
| graph | graph data structure |
| adjgraph | graph data structure |
| path | array containing Voronoi paths data |
| rad | array storing shortest way from a terminal out of its Voronoi region |
| cost | edge costs |
| costrev | reversed edge costs |
| vbase | array containing Voronoi base of each node |
| heap | array representing a heap |
| state | array to mark state of each node during calculation |
Definition at line 1912 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(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::source, STP_HOP_CONS, STP_MAX_NODE_WEIGHT, STP_PRIZE_COLLECTING, STP_ROOTED_PRIZE_COLLECTING, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.
Referenced by bound_reduce(), and hopbound_reduce().
| void voronoi_repair |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
int * |
count, |
|
|
int * |
vbase, |
|
|
PATH * |
path, |
|
|
int * |
newedge, |
|
|
int |
crucnode, |
|
|
UF * |
uf |
|
) |
| |
repair the voronoi diagram for a given set nodes
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| count | pointer to number of heap elements |
| vbase | array containing Voronoi base of each node |
| path | Voronoi paths data struture |
| newedge | the new edge |
| crucnode | the current crucial node |
| uf | union find data structure |
Definition at line 2211 of file grphpath.c.
References CONNECT, correct(), shortest_path::dist, EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPunionfindFind(), GRAPH::tail, and UNKNOWN.
Referenced by SCIPheurImproveSteinerTree().
| void voronoi_repair_mult |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
int * |
count, |
|
|
int * |
vbase, |
|
|
int * |
boundedges, |
|
|
int * |
nboundedges, |
|
|
char * |
nodesmark, |
|
|
UF * |
uf, |
|
|
PATH * |
path |
|
) |
| |
repair the voronoi diagram for a given set nodes
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| count | pointer to number of heap elements |
| vbase | array containing Voronoi base of each node |
| boundedges | boundary edges |
| nboundedges | number of boundary edges |
| nodesmark | array to mark temporarily discarded nodes |
| uf | union find data structure |
| path | Voronoi paths data struture |
Definition at line 2289 of file grphpath.c.
References CONNECT, correct(), EAT_LAST, FSP_MODE, GRAPH::head, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, and SCIPunionfindFind().
Referenced by SCIPheurImproveSteinerTree().
| void voronoi_slrepair |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
cost, |
|
|
PATH * |
path, |
|
|
int * |
vbase, |
|
|
int * |
heap, |
|
|
int * |
state, |
|
|
int |
start, |
|
|
int |
adjnode |
|
) |
| |
repair the voronoi diagram for SL reduction
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| path | array to store |
| vbase | array containing Voronoi base of each node |
| heap | array representing a heap |
| state | array indicating state of each vertex during calculation of Voronoi regions |
| start | node to start repair from |
| adjnode | adjacent node |
Definition at line 2136 of file grphpath.c.
References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FSP_MODE, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and UNKNOWN.
| void voronoi_terms |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
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
-
| scip | SCIP data structure |
| g | graph data structure |
| cost | edge costs |
| path | path data struture (leading to respective Voronoi base) |
| vbase | Voronoi base to each vertex |
| heap | array representing a heap |
| state | array to mark the state of each node during calculation |
Definition at line 1679 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(), GRAPH::oeat, GRAPH::outbeg, GRAPH::term, and UNKNOWN.
Referenced by daPc_reduce(), getnext3terms(), getnext4terms(), hcrbound_reduce(), hcrcbound_reduce(), ledge_reduction(), SCIP_DECL_PROPEXEC(), and sl_reduction().
| void voronoiSteinerTreeExt |
( |
SCIP * |
scip, |
|
|
const GRAPH * |
g, |
|
|
SCIP_Real * |
costrev, |
|
|
int * |
vbase, |
|
|
char * |
stvertex, |
|
|
PATH * |
path |
|
) |
| |
Voronoi Steiner tree extension for RPC, PC and MW
- Parameters
-
| scip | SCIP data structure |
| g | graph data structure |
| costrev | reversed edge costs |
| vbase | voronoi base to each vertex |
| stvertex | array to indicate whether a vertex is a Voronoi base |
| path | path data struture (leading to respective Voronoi base) |
Definition at line 1121 of file grphpath.c.
References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, FSP_MODE, GRAPH::head, Is_pterm, Is_term, GRAPH::knots, nearest(), GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, GRAPH::term, and UNKNOWN.
Referenced by extendSteinerTreePcMw().
|
