# SCIP

Solving Constraint Integer Programs

mst.c
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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file mst.c
17  * @brief minimum spanning tree based algorithms for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file encompasses various minimum spanning tree based algorithms.
21  * Note: This file is supposed to (partly) replace graph_path.c in the long run, as it includes the faster implementations.
22  *
23  */
24
25
26 #include "mst.h"
27 #include "portab.h"
28
29
30 /** initializes */
31 static inline
33  const GRAPH* g, /**< graph data structure */
34  const STP_Bool* nodes_isMarked, /**< should the node be considered? */
35  int startnode, /**< start vertex */
36  MST* mst /**< MST data */
37 )
38 {
39  const int nnodes = graph_get_nNodes(g);
40  DHEAP* dheap = mst->dheap;
41  SCIP_Real* RESTRICT nodes_dist = mst->nodes_dist;
42  int* RESTRICT nodes_pred = mst->nodes_predEdge;
43
44  assert(startnode >= 0 && startnode < g->knots);
45  assert(nodes_isMarked[startnode]);
46  assert(nnodes >= 1);
47  assert(mst->csr->nnodes == nnodes);
48  assert(mst->csr->start[nnodes] <= g->edges);
49
50  graph_heap_clean(TRUE, dheap);
51
52  for( int k = 0; k < nnodes; k++ )
53  {
54  nodes_pred[k] = UNKNOWN;
55  nodes_dist[k] = FARAWAY;
56  }
57
58  nodes_dist[startnode] = 0.0;
59  graph_heap_correct(startnode, 0.0, dheap);
60 }
61
62
63 /** executes */
64 static inline
66  const GRAPH* g, /**< graph data structure */
67  const STP_Bool* nodes_isMarked, /**< should the node be considered? */
68  int startnode, /**< start vertex */
69  MST* mst /**< MST data */
70 )
71 {
72  const CSR* const csr = mst->csr;
73  DHEAP* const dheap = mst->dheap;
74  SCIP_Real* RESTRICT nodes_dist = mst->nodes_dist;
75  int* RESTRICT nodes_pred = mst->nodes_predEdge;
76  int* const state = dheap->position;
77  const SCIP_Real* const cost_csr = csr->cost;
79  const int* const start_csr = csr->start;
80
81  assert(dheap->size == 1);
82
83  /* main loop */
84  while( dheap->size > 0 )
85  {
86  /* get nearest labelled node */
87  const int k = graph_heap_deleteMinReturnNode(dheap);
88  const int k_start = start_csr[k];
89  const int k_end = start_csr[k + 1];
90
91  SCIPdebugMessage("take node %d from queue \n", k);
92  assert(state[k] == CONNECT);
93
94  for( int e = k_start; e != k_end; e++ )
95  {
96  const int m = head_csr[e];
97
98  if( state[m] != CONNECT && nodes_isMarked[m] && LT(cost_csr[e], nodes_dist[m]) )
99  {
100  nodes_pred[m] = e;
101  nodes_dist[m] = cost_csr[e];
102  graph_heap_correct(m, cost_csr[e], dheap);
103  }
104  }
105  }
106
107  assert(nodes_pred[startnode] == UNKNOWN);
108 }
109
110
111
112 /*
113  * Interface methods
114  */
115
116
117 /** initializes */
119  SCIP* scip, /**< SCIP data structure */
120  const GRAPH* g, /**< graph data structure */
121  MST** minspantree /**< MST data */
122 )
123 {
124  MST* mst;
125  CSR* csr;
126  const int nnodes = graph_get_nNodes(g);
127  const int nedges = graph_get_nEdges(g);
128
129  SCIP_CALL( SCIPallocMemory(scip, minspantree) );
130  mst = *minspantree;
131
132  SCIP_CALL( SCIPallocMemoryArray(scip, &mst->nodes_dist, nnodes) );
133  SCIP_CALL( SCIPallocMemoryArray(scip, &mst->nodes_predEdge, nnodes) );
134
135  SCIP_CALL( graph_heap_create(scip, nnodes, NULL, NULL, &mst->dheap) );
136  SCIP_CALL( graph_csr_allocWithEdgeId(scip, nnodes, nedges, &csr) );
137  graph_csr_build(g, g->cost, csr);
138  mst->csr = csr;
139
140  return SCIP_OKAY;
141 }
142
143
144 /** frees */
145 void mst_free(
146  SCIP* scip, /**< SCIP data structure */
147  MST** minspantree /**< MST data */
148 )
149 {
150  MST* mst;
151  CSR* csr;
152  assert(scip && minspantree);
153
154  mst = *minspantree;
155  /* :/ */
156  csr = (CSR*) mst->csr;
157
158  graph_csr_free(scip, &csr);
159  graph_heap_free(scip, TRUE, TRUE, &mst->dheap);
160  SCIPfreeMemoryArray(scip, &mst->nodes_predEdge);
161  SCIPfreeMemoryArray(scip, &mst->nodes_dist);
162
163  SCIPfreeMemory(scip, minspantree);
164 }
165
166
167 /** gets objective value of MST */
169  const GRAPH* g, /**< graph data structure */
170  const MST* mst /**< MST data */
171 )
172 {
173  SCIP_Real obj = 0.0;
174  const int nnodes = graph_get_nNodes(g);
175  const int* const nodes_pred = mst->nodes_predEdge;
176  const CSR* const csr = mst->csr;
177
178  assert(nodes_pred && csr);
179
180  for( int i = 0; i < nnodes; i++ )
181  {
182  if( nodes_pred[i] != UNKNOWN )
183  {
184  assert(nodes_pred[i] >= 0);
185  assert(GE(csr->cost[nodes_pred[i]], 0.0) && LE(csr->cost[nodes_pred[i]], FARAWAY));
186
187  obj += csr->cost[nodes_pred[i]];
188  }
189  }
190
191  return obj;
192 }
193
194
195 /** gets solution edges */
197  const GRAPH* g, /**< graph data structure */
198  const MST* mst, /**< MST data */
199  int* RESTRICT soledges /**< to be filled (CONNECT/UNKNOWN) */
200 )
201 {
202  const int* const nodes_pred = mst->nodes_predEdge;
203  const int* const edgeid_csr = mst->csr->edge_id;
204  const int nnodes = graph_get_nNodes(g);
205  const int nedges = graph_get_nEdges(g);
206
207  for( int e = 0; e < nedges; e++ )
208  soledges[e] = UNKNOWN;
209
210  for( int i = 0; i < nnodes; i++ )
211  {
212  const int edge_csr = nodes_pred[i];
213  if( edge_csr != UNKNOWN )
214  {
215  assert(soledges[edgeid_csr[edge_csr]] == UNKNOWN);
216  soledges[edgeid_csr[edge_csr]] = CONNECT;
217  }
218  }
219 }
220
221
222 /** computes MST on marked vertices */
224  const GRAPH* g, /**< graph data structure */
225  const STP_Bool* nodes_isMarked, /**< should the node be considered? */
226  int startnode, /**< start vertex */
227  MST* mst /**< MST data */
228 )
229 {
230  assert(g && mst);
231  assert(mst->csr && mst->dheap && mst->nodes_dist && mst->nodes_predEdge);
232  assert(g->stp_type == STP_MWCSP || g->stp_type == STP_PCSPG || startnode == g->source);
233
234  computeOnMarked_init(g, nodes_isMarked, startnode, mst);
235
236  if( g->knots == 1 )
237  return;
238
239  computeOnMarked_exec(g, nodes_isMarked, startnode, mst);
240  // computeOnMarked_computePredecessors(g, mst);
241 }
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
SCIP_Real mst_getObj(const GRAPH *g, const MST *mst)
Definition: mst.c:168
Definition: graphdefs.h:141
int source
Definition: graphdefs.h:195
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void graph_csr_build(const GRAPH *, const SCIP_Real *, CSR *)
Definition: graph_util.c:1351
static void computeOnMarked_init(const GRAPH *g, const STP_Bool *nodes_isMarked, int startnode, MST *mst)
Definition: mst.c:32
SCIP_Real *RESTRICT nodes_dist
Definition: mst.h:45
SCIP_Real * cost
Definition: graphdefs.h:142
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void graph_heap_clean(SCIP_Bool, DHEAP *)
Definition: graph_util.c:938
int *RESTRICT nodes_predEdge
Definition: mst.h:46
minimum spanning tree based algorithms for Steiner problems
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
int * start
Definition: graphdefs.h:140
void mst_computeOnMarked(const GRAPH *g, const STP_Bool *nodes_isMarked, int startnode, MST *mst)
Definition: mst.c:223
void mst_getSoledges(const GRAPH *g, const MST *mst, int *RESTRICT soledges)
Definition: mst.c:196
int * position
Definition: graphdefs.h:305
#define LE(a, b)
Definition: portab.h:83
#define GE(a, b)
Definition: portab.h:85
int stp_type
Definition: graphdefs.h:264
SCIP_RETCODE graph_csr_allocWithEdgeId(SCIP *, int, int, CSR **)
Definition: graph_util.c:1270
#define NULL
Definition: lpi_spx1.cpp:155
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
#define STP_PCSPG
Definition: graphdefs.h:44
#define LT(a, b)
Definition: portab.h:81
unsigned char STP_Bool
Definition: portab.h:34
void graph_heap_free(SCIP *, SCIP_Bool, SCIP_Bool, DHEAP **)
Definition: graph_util.c:1034
static void computeOnMarked_exec(const GRAPH *g, const STP_Bool *nodes_isMarked, int startnode, MST *mst)
Definition: mst.c:65
const CSR * csr
Definition: mst.h:43
void mst_free(SCIP *scip, MST **minspantree)
Definition: mst.c:145
#define CONNECT
Definition: graphdefs.h:87
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
int * edge_id
Definition: graphdefs.h:143
SCIP_Real * cost
Definition: graphdefs.h:221
void graph_csr_free(SCIP *, CSR **)
Definition: graph_util.c:1554
SCIP_RETCODE graph_heap_create(SCIP *, int, int *, DENTRY *, DHEAP **)
Definition: graph_util.c:992
DHEAP * dheap
Definition: mst.h:44
#define SCIP_Real
Definition: def.h:177
int graph_heap_deleteMinReturnNode(DHEAP *)
Definition: graph_util.c:1076
SCIP_RETCODE mst_init(SCIP *scip, const GRAPH *g, MST **minspantree)
Definition: mst.c:118
int edges
Definition: graphdefs.h:219
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define UNKNOWN
Definition: sepa_mcf.c:4095
#define nnodes
Definition: gastrans.c:65
#define STP_MWCSP
Definition: graphdefs.h:51
void graph_heap_correct(int, SCIP_Real, DHEAP *)
Definition: graph_util.c:1166