Scippy

SCIP

Solving Constraint Integer Programs

shortestpath.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file shortestpath.h
17  * @brief Shortest path based algorithms for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file encompasses various shortest path based algorithms.
21  * Note: This file is supposed to replace graph_path.c in the long run, as it includes faster implementations.
22  *
23  */
24 
25 
26 #ifndef APPLICATIONS_STP_SRC_SHORTESTPATH_H_
27 #define APPLICATIONS_STP_SRC_SHORTESTPATH_H_
28 
29 #include "graph.h"
30 
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34 
35 /** information needed for prize-collecting problems */
36 typedef
38 {
39  SCIP_Real* orderedprizes; /**< ordered prizes for (pseudo) terminals */
40  int* orderedprizes_id; /**< ordered prizes IDs */
41  SCIP_Real maxoutprize; /**< maximum prize of not yet connected vertex */
42  int maxoutprize_idx; /**< index */
43 } SPATHSPC;
44 
45 
46 /** information for shortest paths */
47 typedef
48 struct stortest_paths
49 {
50  const CSR* csr; /**< CSR with possibly biased edge costs
51  NOTE: all pointers except for cost alias with csr_orgcosts */
52  const CSR* csr_orgcosts; /**< CSR with original edge costs
53  NOTE: all pointers except for cost alias with csr */
54  DHEAP* dheap; /**< Dijkstra heap */
55  SCIP_Real* RESTRICT nodes_dist; /**< distance array (on vertices) */
56  int* RESTRICT nodes_pred; /**< predecessor node array (on vertices)
57  NOTE: might contain uninitialized values in opt mode! */
58  STP_Bool* RESTRICT nodes_isConnected; /**< array to mark whether a vertex is part of computed Steiner tree */
59  const SCIP_Real edgecost_zeroOffset;/**< zero offset for edge costs (used instead of actual 0 value) */
60 } SPATHS;
61 
62 
66 void shortestpath_pcConnectNode(const GRAPH*, const STP_Bool*, int, SPATHSPC*);
67 
68 void shortestpath_computeSteinerTree(const GRAPH*, int, SPATHS*);
74 
75 #ifdef __cplusplus
76 }
77 #endif
78 
79 #endif /* APPLICATIONS_STP_SRC_SHORTESTPATH_H_ */
const SCIP_Real edgecost_zeroOffset
Definition: shortestpath.h:59
const CSR * csr
Definition: shortestpath.h:50
void shortestpath_computeSteinerTree(const GRAPH *, int, SPATHS *)
void shortestpath_computeSteinerTreeDirected(SCIP *, const GRAPH *, int, SPATHS *)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_Real *RESTRICT nodes_dist
Definition: shortestpath.h:55
STP_Bool *RESTRICT nodes_isConnected
Definition: shortestpath.h:58
void shortestpath_computeSteinerTreeBiased(const GRAPH *, const SDPROFIT *, int, SPATHS *)
struct stortest_paths SPATHS
void shortestpath_computeSteinerTreePcMwFull(const GRAPH *, int, SPATHS *)
unsigned char STP_Bool
Definition: portab.h:34
const CSR * csr_orgcosts
Definition: shortestpath.h:52
void shortestpath_pcReset(SPATHSPC *)
Definition: shortestpath.c:977
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE shortestpath_pcInit(SCIP *, const GRAPH *, const SCIP_Real *, const SCIP_Real *, SPATHSPC **)
Definition: shortestpath.c:893
void shortestpath_pcFree(SCIP *, SPATHSPC **)
Definition: shortestpath.c:964
int *RESTRICT nodes_pred
Definition: shortestpath.h:56
#define SCIP_Real
Definition: def.h:177
struct stortest_path_prizecollecting SPATHSPC
void shortestpath_computeSteinerTreeRpcMw(const GRAPH *, int, const SCIP_Real *, SPATHSPC *, SPATHS *)
void shortestpath_computeSteinerTreePcMw(const GRAPH *, int, const SCIP_Real *, SCIP_Bool, SPATHSPC *, SPATHS *)
void shortestpath_pcConnectNode(const GRAPH *, const STP_Bool *, int, SPATHSPC *)
Definition: shortestpath.c:991