Scippy

SCIP

Solving Constraint Integer Programs

extreduce_mldists.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 extreduce_mldists.c
17  * @brief multi-level distance storage methods for Steiner tree extended reductions
18  * @author Daniel Rehfeldt
19  *
20  * This file implements utility methods for Steiner tree problem extended reduction techniques
21  * that allow use to store and retrieve (special) distances between vertices of the extension tree.
22  *
23  * A list of all interface methods can be found in extreduce.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
29 // #define SCIP_DEBUG
30 #include "extreduce.h"
31 #include "misc_stp.h"
32 #include "portab.h"
33 
34 
35 
36 #define MLDISTS_EMPTYSLOT_NONE -1
37 
38 
39 /** Structure for storing distances in the extension tree.
40  * Organized in slots that can be filled by the user.
41  * On each level there are a number of slots available (specified by the user).
42  * Each slots consists of a base (id) and a number of targets. Each target has a distance and an ID.
43  * Each slot on a level has the same number of targets, namely level_ntargets[level]. */
45 {
46  int* target_ids; /**< target ids only in DEBUG mode! */
47  SCIP_Real* target_dists; /**< target ids */
48  int* base_ids; /**< bases ids */
49  int* level_basestart; /**< start of bases for given level */
50  int* level_targetstart; /**< start of targets for given level */
51  int* level_ntargets; /**< number of targets per base on given level */
52  int level_maxntargets; /**< maximum number of targets per level */
53  int level_maxnslots; /**< maximum number of bases per level */
54  int nlevels; /**< number of levels */
55  int maxnlevels; /**< maximum number of levels */
56  int maxntargets; /**< total maximum number of targets */
57  int maxnslots; /**< total maximum number of bases */
58  int emptyslot_number; /**< number (0,...) of current empty slot, or EMPTYSLOT_NONE if none exists */
59  SCIP_Bool target_withids; /**< use ids? */
60 };
61 
62 
63 
64 /**@name Local methods
65  *
66  * @{
67  */
68 
69 
70 /** gets current level */
71 static inline
73  const MLDISTS* mldists /**< multi-level distances */
74 )
75 {
76  assert(mldists);
77  assert(mldists->nlevels > 0 && mldists->nlevels <= mldists->maxnlevels);
78 
79  return (mldists->nlevels - 1);
80 }
81 
82 
83 /** gets start of bases */
84 static inline
86  const MLDISTS* mldists, /**< multi-level distances */
87  int level /**< the level */
88 )
89 {
90  assert(level >= 0 && level <= mldistsGetTopLevel(mldists));
91  assert(mldists->level_basestart[level] >= 0 && mldists->level_basestart[level] < mldists->maxnslots);
92 
93  return mldists->level_basestart[level];
94 }
95 
96 
97 /** gets start of bases */
98 static inline
100  const MLDISTS* mldists, /**< multi-level distances */
101  int level /**< the level */
102 )
103 {
104  assert(level >= 0 && level <= mldistsGetTopLevel(mldists));
105  assert(mldists->level_basestart[level + 1] >= 0 && mldists->level_basestart[level] <= mldists->maxnslots);
106 
107  return mldists->level_basestart[level + 1];
108 }
109 
110 
111 /** Gets (internal) position of given base id,
112  * or -1 if it could not be found. */
113 static
115  const MLDISTS* mldists, /**< multi-level distances */
116  int level, /**< level */
117  int baseid /**< the base id */
118 )
119 {
120  const int start = mldistsGetPosBasesStart(mldists, level);
121  const int end = mldistsGetPosBasesEnd(mldists, level);
122  const int* const base_ids = mldists->base_ids;
123 
124  assert(baseid >= 0);
125 
126  /* top level and with empty slots? */
127  if( level == mldistsGetTopLevel(mldists) && extreduce_mldistsEmptySlotExists(mldists) )
128  {
129  const int emptyslotnumber = mldists->emptyslot_number;
130 
131  for( int i = start, j = 0; i < end && j < emptyslotnumber; ++i, ++j )
132  {
133  const int id = base_ids[i];
134 
135  assert(id >= 0);
136 
137  if( id == baseid )
138  return i;
139  }
140  }
141  else
142  {
143  for( int i = start; i < end; ++i )
144  {
145  const int id = base_ids[i];
146 
147  assert(id >= 0 || id == STP_MLDISTS_ID_EMPTY);
148 
149  if( id == baseid )
150  return i;
151  }
152  }
153 
154  return -1;
155 }
156 
157 
158 /** gets (internal) position of targets for given base id */
159 static inline
161  const MLDISTS* mldists, /**< multi-level distances */
162  int level, /**< level */
163  int baseid /**< the base id */
164 )
165 {
166  int targetpos;
167  int offset = 0;
168  const int ntargets = mldists->level_ntargets[level];
169 
170  assert(extreduce_mldistsLevelContainsBase(mldists, level, baseid));
171  assert(level >= 0 && level <= mldistsGetTopLevel(mldists));
172  assert(baseid >= 0);
173 
174  offset = mldistsGetPosBase(mldists, level, baseid) - mldists->level_basestart[level];
175 
176  assert(offset >= 0);
177  assert(ntargets >= 0);
178 
179  targetpos = mldists->level_targetstart[level] + offset * ntargets;
180 
181  assert(targetpos >= 0 && targetpos < mldists->maxntargets);
182 
183  return targetpos;
184 }
185 
186 
187 /** gets (internal) position of targets for given base id and target id */
188 static inline
190  const MLDISTS* mldists, /**< multi-level distances */
191  int level, /**< level */
192  int baseid, /**< the base id */
193  int targetid /**< the target id */
194 )
195 {
196  const int start = mldistsGetPosTargetsStart(mldists, level, baseid);
197  const int end = start + mldists->level_ntargets[level];
198  const int* const target_ids = mldists->target_ids;
199  int i;
200 
201  assert(mldists->target_withids);
202 
203  for( i = start; i != end; i++ )
204  {
205  if( target_ids[i] == targetid )
206  {
207  break;
208  }
209  }
210 
211  assert(i != end);
212 
213  return i;
214 }
215 
216 
217 /** gets targets start of current empty slot */
218 static inline
220  const MLDISTS* mldists /**< multi-level distances */
221 )
222 {
223  const int level = mldistsGetTopLevel(mldists);
224  const int ntargets = mldists->level_ntargets[level];
225  const int start = mldists->level_targetstart[level] + mldists->emptyslot_number * ntargets;
226 
227  assert(extreduce_mldistsEmptySlotExists(mldists));
228  assert(start >= 0 && start < mldists->maxntargets);
229  assert(mldists->emptyslot_number >= 0);
230  assert(ntargets >= 0 && ntargets <= mldists->level_maxntargets);
231 
232  return start;
233 }
234 
235 
236 /** only for debugging */
237 static inline
239  const MLDISTS* mldists /**< multi-level distances */
240 )
241 {
242 #ifndef NDEBUG
243  const int nlevels = mldists->nlevels;
244  const int start_base = mldists->level_basestart[nlevels - 1];
245  const int end_base = mldists->level_basestart[nlevels];
246  const int start_target = mldists->level_targetstart[nlevels - 1];
247  const int end_target = mldists->level_targetstart[nlevels];
248 
249  assert(start_base >= 0);
250  assert(start_base <= end_base);
251  assert(end_base <= mldists->maxnslots);
252 
253  for( int i = start_base; i < end_base; ++i )
254  {
255  mldists->base_ids[i] = STP_MLDISTS_ID_UNSET;
256  }
257 
258  assert(start_target >= 0);
259  assert(start_target <= end_target);
260  assert(end_target <= mldists->maxntargets);
261 
262  for( int i = start_target; i < end_target; ++i )
263  {
264  mldists->target_dists[i] = STP_MLDISTS_DIST_UNSET;
265  }
266 
267  if( mldists->target_withids )
268  {
269  assert(mldists->target_ids);
270 
271  for( int i = start_target; i < end_target; ++i )
272  {
273  mldists->target_ids[i] = STP_MLDISTS_ID_UNSET;
274  }
275  }
276 #endif
277 }
278 
279 
280 
281 /**@} */
282 
283 /**@name Interface methods
284  *
285  * @{
286  */
287 
288 
289 
290 /** initializes multi-level distances structure */
292  SCIP* scip, /**< SCIP */
293  int maxnlevels, /**< maximum number of levels that can be handled */
294  int maxnslots, /**< maximum number of of slots (per level) that can be handled */
295  int maxntargets, /**< maximum number of of targets (per slot) that can be handled */
296  int emptyslot_nbuffers, /**< buffer entries for empty slot (dists and IDs array is that much longer) */
297  SCIP_Bool use_targetids, /**< use target IDs? */
298  MLDISTS** mldistances /**< to be initialized */
299 )
300 {
301  MLDISTS* mldists;
302  /* NOTE: was also need to consider dummy/empty entry! */
303  const int maxnslots_internal = maxnslots + 1;
304 
305  assert(scip && mldistances);
306  assert(maxnlevels >= 1 && maxnslots >= 1 && maxntargets >= 1);
307  assert(emptyslot_nbuffers >= 0);
308 
309  SCIP_CALL( SCIPallocMemory(scip, mldistances) );
310 
311  mldists = *mldistances;
312  mldists->nlevels = 0;
313  mldists->maxnlevels = maxnlevels;
314  mldists->level_maxntargets = maxntargets;
315  mldists->level_maxnslots = maxnslots_internal;
316  mldists->target_withids = use_targetids;
317  mldists->maxnslots = maxnlevels * maxnslots_internal;
318  mldists->maxntargets = maxnlevels * maxnslots_internal * maxntargets + emptyslot_nbuffers;
320 
321  if( use_targetids )
322  {
323  SCIP_CALL( SCIPallocMemoryArray(scip, &(mldists->target_ids), mldists->maxntargets) );
324  }
325  else
326  {
327  mldists->target_ids = NULL;
328  }
329 
330  SCIP_CALL( SCIPallocMemoryArray(scip, &(mldists->target_dists), mldists->maxntargets) );
331  SCIP_CALL( SCIPallocMemoryArray(scip, &(mldists->base_ids), mldists->maxnslots) );
332  SCIP_CALL( SCIPallocMemoryArray(scip, &(mldists->level_basestart), maxnlevels + 1) );
333  SCIP_CALL( SCIPallocMemoryArray(scip, &(mldists->level_targetstart), maxnlevels + 1) );
334  SCIP_CALL( SCIPallocMemoryArray(scip, &(mldists->level_ntargets), maxnlevels) );
335 
336  mldists->level_basestart[0] = 0;
337  mldists->level_targetstart[0] = 0;
338 
339  return SCIP_OKAY;
340 }
341 
342 
343 /** frees multi-level distances structure */
345  SCIP* scip, /**< SCIP */
346  MLDISTS** mldistances /**< to be freed */
347 )
348 {
349  MLDISTS* mldists;
350 
351  assert(scip && mldistances);
352 
353  mldists = *mldistances;
354 
355  SCIPfreeMemoryArray(scip, &(mldists->level_ntargets));
356  SCIPfreeMemoryArray(scip, &(mldists->level_targetstart));
357  SCIPfreeMemoryArray(scip, &(mldists->level_basestart));
358  SCIPfreeMemoryArray(scip, &(mldists->base_ids));
359  SCIPfreeMemoryArray(scip, &(mldists->target_dists));
360 
361  if( mldists->target_withids )
362  {
363  assert(mldists->target_ids);
364 
365  SCIPfreeMemoryArray(scip, &(mldists->target_ids));
366  }
367 
368  SCIPfreeMemory(scip, mldistances);
369 }
370 
371 /** empty? */
373  const MLDISTS* mldists /**< multi-level distances */
374 )
375 {
376  assert(mldists);
377 
378  return (mldists->nlevels == 0);
379 }
380 
381 
382 /** does an empty slot exits? (on current level) */
384  const MLDISTS* mldists /**< multi-level distances */
385 )
386 {
387  assert(mldists);
388  assert(MLDISTS_EMPTYSLOT_NONE == mldists->emptyslot_number || mldists->emptyslot_number >= 0);
389 
390  return (mldists->emptyslot_number != MLDISTS_EMPTYSLOT_NONE);
391 }
392 
393 
394 /** gets targets IDs memory from clean slot (to be filled in) */
396  const MLDISTS* mldists /**< multi-level distances */
397 )
398 {
399  const int start = mldistsGetPosEmptyTargetsStart(mldists);
400 
401 #ifndef NDEBUG
402  const int level = mldistsGetTopLevel(mldists);
403  const int end = start + mldists->level_ntargets[level];
404 
405  assert(mldists->target_withids);
406  assert(mldists->target_ids);
407 
408  for( int i = start; i < end; ++i )
409  {
410  assert(mldists->target_ids[i] == STP_MLDISTS_ID_UNSET);
411  }
412 #endif
413 
414  return &(mldists->target_ids[start]);
415 }
416 
417 /** gets targets IDs memory from clean slot (to be filled in) */
419  const MLDISTS* mldists /**< multi-level distances */
420 )
421 {
422  const int start = mldistsGetPosEmptyTargetsStart(mldists);
423 
424  assert(mldists->target_ids);
425 
426  return &(mldists->target_ids[start]);
427 }
428 
429 
430 /** Gets targets distances memory from clean slot (to be filled in).
431  * NOTE: Can only be called as long as this empty slots' distances have not not modified! */
433  const MLDISTS* mldists /**< multi-level distances */
434 )
435 {
436  const int start = mldistsGetPosEmptyTargetsStart(mldists);
437 
438 #ifndef NDEBUG
439  const int level = mldistsGetTopLevel(mldists);
440  const int end = start + mldists->level_ntargets[level];
441 
442  for( int i = start; i < end; ++i )
443  {
444  assert(EQ(mldists->target_dists[i], STP_MLDISTS_DIST_UNSET));
445  }
446 #endif
447 
448  return &(mldists->target_dists[start]);
449 }
450 
451 
452 /** Gets targets distances memory from empty slot.
453  * NOTE: This method does not make sure that the distances are clean! (i.e. not already set) */
455  const MLDISTS* mldists /**< multi-level distances */
456 )
457 {
458  const int start = mldistsGetPosEmptyTargetsStart(mldists);
459 
460  return &(mldists->target_dists[start]);
461 }
462 
463 
464 
465 /** gets level of current empty slot */
467  const MLDISTS* mldists /**< multi-level distances */
468 )
469 {
470  assert(extreduce_mldistsEmptySlotExists(mldists));
471 
472  return mldistsGetTopLevel(mldists);
473 }
474 
475 
476 /** sets base of empty slot */
478  int baseid, /**< base */
479  MLDISTS* mldists /**< multi-level distances */
480 )
481 {
482  const int level = mldistsGetTopLevel(mldists);
483  const int position = mldists->level_basestart[level] + mldists->emptyslot_number;
484 
485  assert(extreduce_mldistsEmptySlotExists(mldists));
486  assert(position >= 0 && position < mldists->maxnslots);
487  assert(baseid >= 0 || baseid == STP_MLDISTS_ID_EMPTY);
488  assert(mldists->base_ids[position] == STP_MLDISTS_ID_UNSET);
489 
490  mldists->base_ids[position] = baseid;
491 }
492 
493 
494 /** Resets all changes (especially bases) of empty slot.
495  * NOTE: Assumes that at least the basis of the slot has been set */
497  MLDISTS* mldists /**< multi-level distances */
498 )
499 {
500  const int level = mldistsGetTopLevel(mldists);
501  const int position = mldists->level_basestart[level] + mldists->emptyslot_number;
502 
503  assert(extreduce_mldistsEmptySlotExists(mldists));
504  assert(position >= 0 && position < mldists->maxnslots);
505  assert(mldists->base_ids[position] != STP_MLDISTS_ID_UNSET);
506 
507  mldists->base_ids[position] = STP_MLDISTS_ID_UNSET;
508 
509 #ifndef NDEBUG
510  {
511  const int target_start = mldistsGetPosEmptyTargetsStart(mldists);
512  const int target_end = target_start + mldists->level_ntargets[level];
513 
514  for( int i = target_start; i != target_end; i++ )
515  {
516  mldists->target_dists[i] = STP_MLDISTS_DIST_UNSET;
517  }
518 
519  if( mldists->target_withids )
520  {
521  assert(mldists->target_ids);
522 
523  for( int i = target_start; i != target_end; i++ )
524  {
525  mldists->target_ids[i] = STP_MLDISTS_ID_UNSET;
526  }
527  }
528  }
529 #endif
530 }
531 
532 
533 /** marks current empty slot as filled */
535  MLDISTS* mldists /**< multi-level distances */
536 )
537 {
538  const int level = mldistsGetTopLevel(mldists);
539 
540  assert(extreduce_mldistsEmptySlotExists(mldists));
541  assert(mldists->emptyslot_number < extreduce_mldistsLevelNSlots(mldists, level));
542 
543 #ifndef NDEBUG
544  {
545  const int position = mldists->level_basestart[level] + mldists->emptyslot_number;
546 
547  assert(mldists->base_ids[position] != STP_MLDISTS_ID_UNSET);
548  }
549 #endif
550 
551  mldists->emptyslot_number++;
552 
553  /* all slots of current level used? */
554  if( mldists->emptyslot_number >= extreduce_mldistsLevelNSlots(mldists, level) )
555  {
557  }
558 }
559 
560 
561 /** adds another level of slots at top */
563  int nslots, /**< number of slots per this level */
564  int nslottargets, /**< number of targets per slot */
565  MLDISTS* mldists /**< multi-level distances */
566 )
567 {
568  int nlevels;
569 
570  assert(!extreduce_mldistsEmptySlotExists(mldists));
571  assert(nslots > 0 && nslots <= mldists->level_maxnslots);
572  assert(nslottargets >= 0 && nslottargets <= mldists->level_maxntargets);
573  assert(mldists->nlevels < mldists->maxnlevels);
574 
575  mldists->emptyslot_number = 0;
576  mldists->nlevels++;
577 
578  nlevels = mldists->nlevels;
579 
580  assert(nlevels > 0);
581 
582  mldists->level_basestart[nlevels] = mldists->level_basestart[nlevels - 1] + nslots;
583  mldists->level_targetstart[nlevels] = mldists->level_targetstart[nlevels - 1] + nslots * nslottargets;
584 
585  mldists->level_ntargets[nlevels - 1] = nslottargets;
586 
587  assert(extreduce_mldistsEmptySlotExists(mldists));
588 
589  mldistsTopLevelUnset(mldists);
590 }
591 
592 
593 /** adds dummy level */
595  int nslottargets, /**< number of targets per slot */
596  MLDISTS* mldists /**< multi-level distances */
597 )
598 {
599  assert(mldists);
600 
601  extreduce_mldistsLevelAddTop(1, nslottargets, mldists);
605 }
606 
607 
608 /** adds root level of slots */
610  int base, /**< the base */
611  MLDISTS* mldists /**< multi-level distances */
612 )
613 {
614  assert(mldists);
615  assert(base >= 0);
616 
617  extreduce_mldistsLevelAddTop(1, 0, mldists);
618  extreduce_mldistsEmptySlotSetBase(base, mldists);
621 }
622 
623 
624 /** closes the top level for further extensions */
626  MLDISTS* mldists /**< multi-level distances */
627 )
628 {
629  assert(!extreduce_mldistsIsEmpty(mldists));
630 
631  if( extreduce_mldistsEmptySlotExists(mldists) )
632  {
633  const int nlevels = mldists->nlevels;
634  const int emptyslot = mldists->emptyslot_number;
635  int nslottargets;
636 
637  assert(nlevels >= 1);
638  assert(emptyslot >= 0);
639 
640  nslottargets = mldists->level_ntargets[nlevels - 1];
641 
642  assert(nslottargets >= 1);
643 
644  mldists->level_basestart[nlevels] = mldists->level_basestart[nlevels - 1] + emptyslot;
645  mldists->level_targetstart[nlevels] = mldists->level_targetstart[nlevels - 1] + emptyslot * nslottargets;
646 
648  }
649 
650  assert(!extreduce_mldistsEmptySlotExists(mldists));
651 }
652 
653 
654 
655 /** reopens top level for one further extensions */
657  MLDISTS* mldists /**< multi-level distances */
658 )
659 {
660  const int nlevels = mldists->nlevels;
661  const int nslottargets = mldists->level_ntargets[nlevels - 1];
662 
663  assert(nlevels > 0);
664  assert(!extreduce_mldistsIsEmpty(mldists));
665  assert(!extreduce_mldistsEmptySlotExists(mldists));
666  assert(mldists->nlevels <= mldists->maxnlevels);
667 
668  mldists->emptyslot_number = mldists->level_basestart[nlevels] - mldists->level_basestart[nlevels - 1];
669  mldists->level_basestart[nlevels]++;
670  mldists->level_targetstart[nlevels] += nslottargets;
671 
672  assert(extreduce_mldistsEmptySlotExists(mldists));
673 
674 #ifndef NDEBUG
675  {
676  const int targetend = mldists->level_targetstart[nlevels];
677  mldists->base_ids[mldists->level_basestart[nlevels] - 1] = STP_MLDISTS_ID_UNSET;
678 
679  for( int i = targetend - nslottargets; i < targetend; ++i )
680  mldists->target_dists[i] = STP_MLDISTS_DIST_UNSET;
681 
682  if( mldists->target_withids )
683  {
684  assert(mldists->target_ids);
685 
686  for( int i = targetend - nslottargets; i < targetend; ++i )
687  mldists->target_ids[i] = STP_MLDISTS_ID_UNSET;
688  }
689  }
690 #endif
691 }
692 
693 
694 /** removes top level of slots */
696  MLDISTS* mldists /**< multi-level distances */
697 )
698 {
699  assert(mldists);
700  assert(!extreduce_mldistsEmptySlotExists(mldists));
701  assert(mldists->nlevels > 0);
702 
703  mldistsTopLevelUnset(mldists);
704 
705  mldists->nlevels--;
706 
707  assert(!extreduce_mldistsEmptySlotExists(mldists));
708 }
709 
710 
711 /** removes top level of slots, which is not yet closed */
713  MLDISTS* mldists /**< multi-level distances */
714 )
715 {
716  assert(mldists);
717  assert(extreduce_mldistsEmptySlotExists(mldists));
718  assert(mldists->nlevels > 0);
719 
720  mldistsTopLevelUnset(mldists);
721 
722  mldists->nlevels--;
724 
725  assert(!extreduce_mldistsEmptySlotExists(mldists));
726 }
727 
728 
729 /** gets number of targets (per slots) for given level */
731  const MLDISTS* mldists, /**< multi-level distances */
732  int level /**< level */
733 )
734 {
735  assert(mldists);
736  assert(level >= 0 && level <= mldistsGetTopLevel(mldists));
737  assert(mldists->level_ntargets[level] >= 0 && mldists->level_ntargets[level] <= mldists->level_maxntargets);
738 
739  return mldists->level_ntargets[level];
740 }
741 
742 /** gets number of targets (per slots) for top level */
744  const MLDISTS* mldists /**< multi-level distances */
745 )
746 {
747  assert(mldists);
748 
749  return extreduce_mldistsLevelNTargets(mldists, mldistsGetTopLevel(mldists));
750 }
751 
752 
753 /** gets number of slots for given level */
755  const MLDISTS* mldists, /**< multi-level distances */
756  int level /**< level */
757 )
758 {
759  assert(mldists);
760  assert(level >= 0 && level <= mldistsGetTopLevel(mldists));
761  assert(mldists->level_basestart[level + 1] - mldists->level_basestart[level] >= 0);
762  assert(mldists->level_basestart[level + 1] - mldists->level_basestart[level] <= mldists->level_maxnslots);
763 
764  return (mldists->level_basestart[level + 1] - mldists->level_basestart[level]);
765 }
766 
767 
768 /** gets number of slots for top level */
770  const MLDISTS* mldists /**< multi-level distances */
771 )
772 {
773  return (extreduce_mldistsLevelNSlots(mldists, extreduce_mldistsTopLevel(mldists)));
774 }
775 
776 
777 /** gets number of levels */
779  const MLDISTS* mldists /**< multi-level distances */
780 )
781 {
782  assert(mldists);
783  assert(mldists->nlevels >= 0);
784 
785  return (mldists->nlevels);
786 }
787 
788 
789 /** gets top level */
791  const MLDISTS* mldists /**< multi-level distances */
792 )
793 {
794  assert(mldists);
795  assert(mldists->nlevels >= 1);
796 
797  return (mldists->nlevels - 1);
798 }
799 
800 
801 /** gets top level bases*/
803  const MLDISTS* mldists /**< multi-level distances */
804 )
805 {
806  const int toplevel = mldistsGetTopLevel(mldists);
807  const int basestart_pos = mldistsGetPosBasesStart(mldists, toplevel);
808 
809  return &(mldists->base_ids[basestart_pos]);
810 }
811 
812 
813 /** is the base contained in a slot of the given level? */
815  const MLDISTS* mldists, /**< multi-level distances */
816  int level, /**< level */
817  int baseid /**< the base id */
818 )
819 {
820  assert(mldists);
821  assert(level >= 0 && level <= mldistsGetTopLevel(mldists));
822  assert(baseid >= 0);
823 
824  return (mldistsGetPosBase(mldists, level, baseid) != -1);
825 }
826 
827 
828 /** gets targets ids */
830  const MLDISTS* mldists, /**< multi-level distances */
831  int level, /**< level */
832  int baseid /**< the base */
833 )
834 {
835  const int targetpos = mldistsGetPosTargetsStart(mldists, level, baseid);
836 
837  assert(mldists->target_withids);
838  assert(mldists->target_ids);
839 
840  return &(mldists->target_ids[targetpos]);
841 }
842 
843 
844 /** gets targets distances */
846  const MLDISTS* mldists, /**< multi-level distances */
847  int level, /**< level */
848  int baseid /**< the base */
849 )
850 {
851  int targetpos;
852 
853  assert(mldists);
854  assert(level >= 0 && baseid >= 0);
855 
856  targetpos = mldistsGetPosTargetsStart(mldists, level, baseid);
857 
858  return &(mldists->target_dists[targetpos]);
859 }
860 
861 
862 /** Gets targets ids */
864  const MLDISTS* mldists, /**< multi-level distances */
865  int baseid /**< the base */
866 )
867 {
868  return extreduce_mldistsTargetIds(mldists, mldistsGetTopLevel(mldists), baseid);
869 }
870 
871 
872 /** gets targets distances */
874  const MLDISTS* mldists, /**< multi-level distances */
875  int baseid /**< the base */
876 )
877 {
878  const int targetpos = mldistsGetPosTargetsStart(mldists, mldistsGetTopLevel(mldists), baseid);
879 
880  return &(mldists->target_dists[targetpos]);
881 }
882 
883 
884 /** gets (one!) target distance for given target ID and base ID */
886  const MLDISTS* mldists, /**< multi-level distances */
887  int baseid, /**< the base */
888  int targetid /**< the identifier */
889 )
890 {
891  int targetpos;
892 
893  assert(mldists);
894  assert(baseid >= 0 && targetid >= 0);
895 
896  targetpos = mldistsGetPosTargets(mldists, mldistsGetTopLevel(mldists), baseid, targetid);
897 
898  assert(GE(mldists->target_dists[targetpos], 0.0));
899 
900  return (mldists->target_dists[targetpos]);
901 }
902 
903 /** gets (one!) target distance for given level, target ID and base ID */
905  const MLDISTS* mldists, /**< multi-level distances */
906  int level, /**< level */
907  int baseid, /**< the base */
908  int targetid /**< the identifier */
909 )
910 {
911  int targetpos;
912 
913  assert(mldists);
914  assert(baseid >= 0 && targetid >= 0);
915  assert(level >= 0 && level <= mldistsGetTopLevel(mldists));
916 
917  targetpos = mldistsGetPosTargets(mldists, level, baseid, targetid);
918 
919  assert(GE(mldists->target_dists[targetpos], 0.0));
920 
921  return (mldists->target_dists[targetpos]);
922 }
923 
924 /**@} */
void extreduce_mldistsLevelAddAndCloseRoot(int base, MLDISTS *mldists)
const int * extreduce_mldistsTopTargetIds(const MLDISTS *mldists, int baseid)
void extreduce_mldistsEmptySlotSetFilled(MLDISTS *mldists)
int extreduce_mldistsLevelNSlots(const MLDISTS *mldists, int level)
static int mldistsGetPosBasesEnd(const MLDISTS *mldists, int level)
SCIP_Real * extreduce_mldistsEmptySlotTargetDistsDirty(const MLDISTS *mldists)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_Real extreduce_mldistsTargetDist(const MLDISTS *mldists, int level, int baseid, int targetid)
SCIP_Bool extreduce_mldistsIsEmpty(const MLDISTS *mldists)
SCIP_RETCODE extreduce_mldistsInit(SCIP *scip, int maxnlevels, int maxnslots, int maxntargets, int emptyslot_nbuffers, SCIP_Bool use_targetids, MLDISTS **mldistances)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_Bool extreduce_mldistsLevelContainsBase(const MLDISTS *mldists, int level, int baseid)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int extreduce_mldistsTopLevelNSlots(const MLDISTS *mldists)
SCIP_Real extreduce_mldistsTopTargetDist(const MLDISTS *mldists, int baseid, int targetid)
static int mldistsGetPosBase(const MLDISTS *mldists, int level, int baseid)
const SCIP_Real * extreduce_mldistsTopTargetDists(const MLDISTS *mldists, int baseid)
This file implements extended reduction techniques for several Steiner problems.
#define GE(a, b)
Definition: portab.h:85
void extreduce_mldistsLevelAddTop(int nslots, int nslottargets, MLDISTS *mldists)
miscellaneous methods used for solving Steiner problems
static int mldistsGetPosTargets(const MLDISTS *mldists, int level, int baseid, int targetid)
void extreduce_mldistsEmptySlotSetBase(int baseid, MLDISTS *mldists)
SCIP_Bool extreduce_mldistsEmptySlotExists(const MLDISTS *mldists)
#define NULL
Definition: lpi_spx1.cpp:155
#define EQ(a, b)
Definition: portab.h:79
static int mldistsGetPosTargetsStart(const MLDISTS *mldists, int level, int baseid)
#define SCIP_CALL(x)
Definition: def.h:384
int extreduce_mldistsNlevels(const MLDISTS *mldists)
#define STP_MLDISTS_ID_UNSET
Definition: extreducedefs.h:57
void extreduce_mldistsLevelRemoveTop(MLDISTS *mldists)
#define STP_MLDISTS_ID_EMPTY
Definition: extreducedefs.h:56
#define SCIP_Bool
Definition: def.h:84
void extreduce_mldistsLevelAddAndCloseEmpty(int nslottargets, MLDISTS *mldists)
int * extreduce_mldistsEmptySlotTargetIdsDirty(const MLDISTS *mldists)
static void mldistsTopLevelUnset(const MLDISTS *mldists)
int extreduce_mldistsLevelNTargets(const MLDISTS *mldists, int level)
#define STP_MLDISTS_DIST_UNSET
Definition: extreducedefs.h:58
const int * extreduce_mldistsTargetIds(const MLDISTS *mldists, int level, int baseid)
static int mldistsGetPosEmptyTargetsStart(const MLDISTS *mldists)
int * extreduce_mldistsEmptySlotTargetIds(const MLDISTS *mldists)
static int mldistsGetPosBasesStart(const MLDISTS *mldists, int level)
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
void extreduce_mldistsEmptySlotReset(MLDISTS *mldists)
int extreduce_mldistsEmptySlotLevel(const MLDISTS *mldists)
static int mldistsGetTopLevel(const MLDISTS *mldists)
void extreduce_mldistsFree(SCIP *scip, MLDISTS **mldistances)
const int * extreduce_mldistsTopLevelBases(const MLDISTS *mldists)
void extreduce_mldistsLevelRemoveTopNonClosed(MLDISTS *mldists)
#define SCIP_Real
Definition: def.h:177
#define MLDISTS_EMPTYSLOT_NONE
const SCIP_Real * extreduce_mldistsTargetDists(const MLDISTS *mldists, int level, int baseid)
void extreduce_mldistsLevelReopenTop(MLDISTS *mldists)
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
int extreduce_mldistsTopLevel(const MLDISTS *mldists)
int extreduce_mldistsLevelNTopTargets(const MLDISTS *mldists)
void extreduce_mldistsLevelCloseTop(MLDISTS *mldists)
SCIP_Real * extreduce_mldistsEmptySlotTargetDists(const MLDISTS *mldists)