Scippy

SCIP

Solving Constraint Integer Programs

graph_grid.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 /* */
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 graph_grid.c
17  * @brief includes graph grid methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * Graph grid methods for Steiner problems
21  * !!!OBSTACLE GRID METHODS ARE DEPRECATED!!!
22  *
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 /*lint -esym(766,stdlib.h) -esym(766,malloc.h) */
28 /*lint -esym(766,string.h) */
29 
30 #include "graph.h"
31 #include "portab.h"
32 
33 
34 
35 /** used by graph_grid_create */
36 static
38  int grid_dim,
39  int shiftcoord,
40  int* ncoords,
41  int* currcoord
42  )
43 {
44  int number = 0;
45  int tmp;
46  int i;
47  int j;
48  for( i = 0; i < grid_dim; i++ )
49  {
50  tmp = 1;
51  for( j = i + 1; j < grid_dim; j++ )
52  {
53  tmp = tmp * ncoords[j];
54  }
55  if( shiftcoord == i )
56  number += (currcoord[i] + 1) * tmp;
57  else
58  number += currcoord[i] * tmp;
59  }
60  number++;
61  return number;
62 }
63 
64 
65 /** used by graph_obstgrid_create */
66 static
68  int coord,
69  int grid_dim,
70  int nobstacles,
71  int* ncoords,
72  int* currcoord,
73  int* edgecosts,
74  int* gridedgecount,
75  int** coords,
76  int** gridedges,
77  int** obst_coords,
78  char* inobstacle
79  )
80 {
81  char inobst;
82  int i;
83  int j;
84  int z;
85  int x;
86  int y;
87  int node;
88  i = 0;
89  while( i < ncoords[coord] )
90  {
91  currcoord[coord] = i;
92  if( coord < grid_dim - 1 )
93  compEdgesObst(coord + 1, grid_dim, nobstacles, ncoords, currcoord, edgecosts, gridedgecount, coords, gridedges, obst_coords, inobstacle);
94  else
95  {
96  x = coords[0][currcoord[0]];
97  y = coords[1][currcoord[1]];
98  inobst = FALSE;
99  node = getNodeNumber(grid_dim, -1, ncoords, currcoord);
100  for( z = 0; z < nobstacles; z++ )
101  {
102  assert(obst_coords[0][z] < obst_coords[2][z]);
103  assert(obst_coords[1][z] < obst_coords[3][z]);
104  if( x > obst_coords[0][z] && x < obst_coords[2][z] &&
105  y > obst_coords[1][z] && y < obst_coords[3][z] )
106  {
107  inobst = TRUE;
108  inobstacle[node-1] = TRUE;
109  break;
110  }
111  }
112  for( j = 0; j < grid_dim; j++ )
113  {
114  if( currcoord[j] + 1 < ncoords[j] )
115  {
116  if( inobst == FALSE )
117  {
118  gridedges[0][*gridedgecount] = node;
119  gridedges[1][*gridedgecount] = getNodeNumber(grid_dim, j, ncoords, currcoord);
120  edgecosts[*gridedgecount] = coords[j][currcoord[j] + 1] - coords[j][currcoord[j]];
121  (*gridedgecount)++;
122  }
123  }
124  }
125  }
126  i++;
127  }
128 }
129 
130 /** used by graph_grid_create */
131 static
133  int coord,
134  int grid_dim,
135  int* ncoords,
136  int* currcoord,
137  int* edgecosts,
138  int* gridedgecount,
139  int** coords,
140  int** gridedges
141  )
142 {
143  int j;
144  int i = 0;
145  while( i < ncoords[coord] )
146  {
147  currcoord[coord] = i;
148  if( coord < grid_dim - 1 )
149  compEdges(coord + 1, grid_dim, ncoords, currcoord, edgecosts, gridedgecount, coords, gridedges);
150  else
151  {
152  for( j = 0; j < grid_dim; j++ )
153  {
154  if( currcoord[j] + 1 < ncoords[j] )
155  {
156  gridedges[0][*gridedgecount] = getNodeNumber(grid_dim, -1, ncoords, currcoord);
157  gridedges[1][*gridedgecount] = getNodeNumber(grid_dim, j, ncoords, currcoord);
158  edgecosts[*gridedgecount] = coords[j][currcoord[j] + 1] - coords[j][currcoord[j]];
159  (*gridedgecount)++;
160  }
161  }
162  }
163  i++;
164  }
165 }
166 
167 /*
168  * Interface methods
169  */
170 
171 
172 
173 
174 /** creates a graph out of a given grid */
176  SCIP* scip, /**< SCIP data structure */
177  GRAPH** gridgraph, /**< the (obstacle) grid graph to be constructed */
178  int** coords, /**< coordinates of all points */
179  int** obst_coords, /**< coordinates of obstacles */
180  int nterms, /**< number of terminals */
181  int grid_dim, /**< dimension of the problem */
182  int nobstacles, /**< number of obstacles*/
183  int scale_order /**< scale factor */
184  )
185 {
186  GRAPH* g;
187  GRAPH* gp;
188  double cost;
189  int i;
190  int j;
191  int k;
192  int tmp;
193  int shift;
194  int nnodes;
195  int nedges;
196  double scale_factor;
197  int gridedgecount;
198  int* ncoords;
199  int* currcoord;
200  int* edgecosts;
201  int** termcoords;
202  int** gridedges;
203  char* inobstacle;
204  assert(coords != NULL);
205  assert(grid_dim > 1);
206  assert(nterms > 0);
207  assert(grid_dim == 2);
208  scale_factor = pow(10.0, (double) scale_order);
209 
210  /* initialize the terminal-coordinates array */
211  SCIP_CALL( SCIPallocBufferArray(scip, &termcoords, grid_dim) );
212 
213  for( i = 0; i < grid_dim; i++ )
214  {
215  SCIP_CALL( SCIPallocBufferArray(scip, &(termcoords[i]), nterms) ); /*lint !e866*/
216  for( j = 0; j < nterms; j++ )
217  termcoords[i][j] = coords[i][j];
218  }
219 
220  SCIP_CALL( SCIPallocBufferArray(scip, &ncoords, grid_dim) );
221  SCIP_CALL( SCIPallocBufferArray(scip, &currcoord, grid_dim) );
222 
223  /* sort the coordinates and delete multiples */
224  for( i = 0; i < grid_dim; i++ )
225  {
226  ncoords[i] = 1;
227  SCIPsortInt(coords[i], nterms);
228  shift = 0;
229  for( j = 0; j < nterms - 1; j++ )
230  {
231  if( coords[i][j] == coords[i][j + 1] )
232  {
233  shift++;
234  }
235  else
236  {
237  coords[i][j + 1 - shift] = coords[i][j + 1];
238  ncoords[i]++;
239  }
240  }
241  }
242 
243  nnodes = 1;
244 
245  for( i = 0; i < grid_dim; i++ )
246  nnodes = nnodes * ncoords[i];
247 
248  tmp = 0;
249 
250  for( i = 0; i < grid_dim; i++ )
251  tmp = tmp + nnodes / ncoords[i];
252 
253  nedges = grid_dim * nnodes - tmp;
254  SCIP_CALL( SCIPallocBufferArray(scip, &gridedges, 2) );
255  SCIP_CALL( SCIPallocBufferArray(scip, &edgecosts, nedges) );
256  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[0]), nedges) );
257  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[1]), nedges) );
258  SCIP_CALL( SCIPallocBufferArray(scip, &(inobstacle), nnodes) );
259  gridedgecount = 0;
260  for( i = 0; i < nnodes; i++ )
261  inobstacle[i] = FALSE;
262  compEdgesObst(0, grid_dim, nobstacles, ncoords, currcoord, edgecosts, &gridedgecount, coords, gridedges, obst_coords, inobstacle);
263  nedges = gridedgecount;
264  /* initialize empty g with allocated slots for nodes and edges */
265  SCIP_CALL( graph_init(scip, gridgraph, nnodes, 2 * nedges, 1) );
266 
267  g = *gridgraph;
268  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->grid_ncoords), grid_dim) );
269  for( i = 0; i < grid_dim; i++ )
270  g->grid_ncoords[i] = ncoords[i];
271 
272  g->grid_dim = grid_dim;
273  g->grid_coordinates = coords;
274 
275  /* add nodes */
276  for( i = 0; i < nnodes; i++ )
277  graph_knot_add(g, -1);
278 
279  /* add edges */
280  for( i = 0; i < nedges; i++ )
281  {
282  /* (re) scale edge costs */
283  if( inobstacle[gridedges[1][i] - 1] == FALSE )
284  {
285  cost = ((double) edgecosts[i]) / scale_factor;
286  graph_edge_add(scip, g, gridedges[0][i] - 1, gridedges[1][i] - 1, cost, cost);
287  }
288  }
289 
290  /* add terminals */
291  for( i = 0; i < nterms; i++ )
292  {
293  for( j = 0; j < grid_dim; j++ )
294  {
295  for( k = 0; k <= ncoords[j]; k++ )
296  {
297  assert(k != ncoords[j]);
298  if( coords[j][k] == termcoords[j][i] )
299  {
300  currcoord[j] = k;
301  break;
302  }
303  }
304  }
305  /* the position of the (future) terminal */
306  k = getNodeNumber(grid_dim, -1, ncoords, currcoord) - 1;
307 
308  if( i == 0 )
309  g->source = k;
310 
311  /* make a terminal out of the node */
312  graph_knot_chg(g, k, 0);
313  }
314 
315  SCIP_CALL( graph_pack(scip, g, &gp, NULL, TRUE) );
316  g = gp;
317  g->stp_type = STP_OARSMT;
318 
319  SCIPfreeBufferArray(scip, &inobstacle);
320  SCIPfreeBufferArray(scip, &(gridedges[1]));
321  SCIPfreeBufferArray(scip, &(gridedges[0]));
322  SCIPfreeBufferArray(scip, &edgecosts);
323  SCIPfreeBufferArray(scip, &gridedges);
324  SCIPfreeBufferArray(scip, &currcoord);
325  SCIPfreeBufferArray(scip, &ncoords);
326 
327  for( i = grid_dim - 1; i >= 0 ; --i )
328  SCIPfreeBufferArray(scip, &(termcoords[i]));
329 
330  SCIPfreeBufferArray(scip, &termcoords);
331 
332  return SCIP_OKAY;
333 }
334 
335 
336 
337 /** creates a graph out of a given grid */
339  SCIP* scip, /**< SCIP data structure */
340  GRAPH** gridgraph, /**< the grid graph to be constructed */
341  int** coords, /**< coordinates */
342  int nterms, /**< number of terminals*/
343  int grid_dim, /**< problem dimension */
344  int scale_order /**< scale order */
345  )
346 {
347  GRAPH* g;
348  double cost;
349  int i;
350  int j;
351  int k;
352  int tmp;
353  int shift;
354  int nnodes;
355  int nedges;
356  double scale_factor;
357  int gridedgecount;
358  int* ncoords;
359  int* currcoord;
360  int* edgecosts;
361  int** termcoords;
362  int** gridedges;
363  assert(coords != NULL);
364  assert(grid_dim > 1);
365  assert(nterms > 0);
366 
367  scale_factor = pow(10.0, (double) scale_order);
368 
369  /* initialize the terminal-coordinates array */
370  SCIP_CALL( SCIPallocBufferArray(scip, &termcoords, grid_dim) );
371  for( i = 0; i < grid_dim; i++ )
372  {
373  SCIP_CALL( SCIPallocBufferArray(scip, &(termcoords[i]), nterms) ); /*lint !e866*/
374  for( j = 0; j < nterms; j++ )
375  termcoords[i][j] = coords[i][j];
376  }
377  SCIP_CALL( SCIPallocBufferArray(scip, &ncoords, grid_dim) );
378  SCIP_CALL( SCIPallocBufferArray(scip, &currcoord, grid_dim) );
379 
380  /* sort the coordinates and delete multiples */
381  for( i = 0; i < grid_dim; i++ )
382  {
383  ncoords[i] = 1;
384  SCIPsortInt(coords[i], nterms);
385  shift = 0;
386  for( j = 0; j < nterms - 1; j++ )
387  {
388  if( coords[i][j] == coords[i][j + 1] )
389  {
390  shift++;
391  }
392  else
393  {
394  coords[i][j + 1 - shift] = coords[i][j + 1];
395  ncoords[i]++;
396  }
397  }
398  }
399 
400  nnodes = 1;
401  for( i = 0; i < grid_dim; i++ )
402  nnodes = nnodes * ncoords[i];
403 
404  tmp = 0;
405  for( i = 0; i < grid_dim; i++ )
406  {
407  tmp = tmp + nnodes / ncoords[i];
408  }
409 
410  nedges = grid_dim * nnodes - tmp;
411 
412  SCIP_CALL( SCIPallocBufferArray(scip, &gridedges, 2) );
413  SCIP_CALL( SCIPallocBufferArray(scip, &edgecosts, nedges) );
414  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[0]), nedges) );
415  SCIP_CALL( SCIPallocBufferArray(scip, &(gridedges[1]), nedges) );
416 
417  gridedgecount = 0;
418 
419  compEdges(0, grid_dim, ncoords, currcoord, edgecosts, &gridedgecount, coords, gridedges);
420 
421  /* initialize empty graph with allocated slots for nodes and edges */
422  SCIP_CALL( graph_init(scip, gridgraph, nnodes, 2 * nedges, 1) );
423 
424  g = *gridgraph;
425 
426  SCIP_CALL( SCIPallocMemoryArray(scip, &(g->grid_ncoords), grid_dim) );
427  for( i = 0; i < grid_dim; i++ )
428  g->grid_ncoords[i] = ncoords[i];
429 
430  g->grid_dim = grid_dim;
431  g->grid_coordinates = coords;
432 
433  /* add nodes */
434  for( i = 0; i < nnodes; i++ )
435  graph_knot_add(g, -1);
436 
437  /* add edges */
438  for( i = 0; i < nedges; i++ )
439  {
440  /* (re) scale edge costs */
441  cost = (double) edgecosts[i] / scale_factor;
442  graph_edge_add(scip, g, gridedges[0][i] - 1, gridedges[1][i] - 1, cost, cost);
443  }
444 
445  /* add terminals */
446  for( i = 0; i < nterms; i++ )
447  {
448  for( j = 0; j < grid_dim; j++ )
449  {
450  for( k = 0; k <= ncoords[j]; k++ )
451  {
452  assert(k != ncoords[j]);
453  if( coords[j][k] == termcoords[j][i] )
454  {
455  currcoord[j] = k;
456  break;
457  }
458  }
459  }
460  /* the position of the (future) terminal */
461  k = getNodeNumber(grid_dim, -1, ncoords, currcoord) - 1;
462 
463  /* make a terminal out of the node */
464  graph_knot_chg(g, k, 0);
465  }
466 
467  g->stp_type = STP_RSMT;
468 
469  SCIPfreeBufferArray(scip, &(gridedges[1]));
470  SCIPfreeBufferArray(scip, &(gridedges[0]));
471  SCIPfreeBufferArray(scip, &edgecosts);
472  SCIPfreeBufferArray(scip, &gridedges);
473  SCIPfreeBufferArray(scip, &currcoord);
474  SCIPfreeBufferArray(scip, &ncoords);
475 
476  for( i = grid_dim - 1; i >= 0 ; i-- )
477  SCIPfreeBufferArray(scip, &(termcoords[i]));
478 
479  SCIPfreeBufferArray(scip, &termcoords);
480 
481  return SCIP_OKAY;
482 }
483 
484 
485 /** computes coordinates of node 'node' */
487  SCIP* scip, /**< SCIP data structure */
488  int** coords, /**< coordinates */
489  int** nodecoords, /**< coordinates of the node (to be computed) */
490  int* ncoords, /**< array with number of coordinate */
491  int node, /**< the node */
492  int grid_dim /**< problem dimension */
493  )
494 {
495  int i;
496  int j;
497  int tmp;
498  int coord;
499  assert(grid_dim > 1);
500  assert(node >= 0);
501  assert(coords != NULL);
502  assert(ncoords != NULL);
503  if( *nodecoords == NULL )
504  SCIP_CALL( SCIPallocMemoryArray(scip, nodecoords, grid_dim) );
505 
506  for( i = 0; i < grid_dim; i++ )
507  {
508  tmp = 1;
509  for( j = i; j < grid_dim; j++ )
510  tmp = tmp * ncoords[j];
511 
512  coord = node % tmp;
513  tmp = tmp / ncoords[i];
514  coord = coord / tmp;
515  (*nodecoords)[i] = coords[i][coord];
516  }
517  return SCIP_OKAY;
518 }
void graph_knot_chg(GRAPH *, int, int)
Definition: graph_node.c:86
static volatile int nterms
Definition: interrupt.c:38
int source
Definition: graphdefs.h:195
static void compEdgesObst(int coord, int grid_dim, int nobstacles, int *ncoords, int *currcoord, int *edgecosts, int *gridedgecount, int **coords, int **gridedges, int **obst_coords, char *inobstacle)
Definition: graph_grid.c:67
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
#define FALSE
Definition: def.h:87
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
SCIP_RETCODE graph_pack(SCIP *, GRAPH *, GRAPH **, REDSOL *, SCIP_Bool)
Definition: graph_base.c:1324
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_VAR ** x
Definition: circlepacking.c:54
#define STP_RSMT
Definition: graphdefs.h:49
int stp_type
Definition: graphdefs.h:264
void graph_edge_add(SCIP *, GRAPH *, int, int, double, double)
void graph_knot_add(GRAPH *, int)
Definition: graph_node.c:64
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE graph_obstgrid_create(SCIP *scip, GRAPH **gridgraph, int **coords, int **obst_coords, int nterms, int grid_dim, int nobstacles, int scale_order)
Definition: graph_grid.c:175
#define STP_OARSMT
Definition: graphdefs.h:50
static void compEdges(int coord, int grid_dim, int *ncoords, int *currcoord, int *edgecosts, int *gridedgecount, int **coords, int **gridedges)
Definition: graph_grid.c:132
static int getNodeNumber(int grid_dim, int shiftcoord, int *ncoords, int *currcoord)
Definition: graph_grid.c:37
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
static long * number
int grid_dim
Definition: graphdefs.h:259
int ** grid_coordinates
Definition: graphdefs.h:261
SCIP_RETCODE graph_grid_create(SCIP *scip, GRAPH **gridgraph, int **coords, int nterms, int grid_dim, int scale_order)
Definition: graph_grid.c:338
Portable definitions.
SCIP_VAR ** y
Definition: circlepacking.c:55
void SCIPsortInt(int *intarray, int len)
int * grid_ncoords
Definition: graphdefs.h:260
#define nnodes
Definition: gastrans.c:65
SCIP_RETCODE graph_init(SCIP *, GRAPH **, int, int, int)
Definition: graph_base.c:607
SCIP_RETCODE graph_grid_coordinates(SCIP *scip, int **coords, int **nodecoords, int *ncoords, int node, int grid_dim)
Definition: graph_grid.c:486