Scippy

SCIP

Solving Constraint Integer Programs

dijkstra.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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file dijkstra.c
26  * @ingroup OTHER_CFILES
27  * @brief C implementation of Dijkstra's algorithm
28  * @author Thorsten Koch
29  * @author Marc Pfetsch
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <assert.h>
37 
38 #include "dijkstra.h"
39 
40 
41 /** Check whether the data structures of the graph are valid. */
43  const DIJKSTRA_GRAPH* G /**< directed graph to be checked */
44  )
45 {
46  unsigned int count = 0;
47  unsigned int i;
48  unsigned int k;
49 
50  if ( G == NULL || G->outbeg == NULL || G->outcnt == NULL || G->weight == NULL || G->head == NULL )
51  abort();
52 
53  for (i = 0; i < G->nodes; ++i)
54  {
55  for (k = G->outbeg[i]; k < G->outbeg[i] + G->outcnt[i]; ++k)
56  {
57  if ( G->head[k] >= G->nodes )
58  abort();
59 
60  if ( G->weight[k] > G->maxweight || G->weight[k] < G->minweight )
61  abort();
62 
63  ++count;
64  }
65  if ( G->head[k] != DIJKSTRA_UNUSED )
66  abort();
67 
68  ++count;
69  }
70  if ( count > G->arcs )
71  abort();
72 
73  return TRUE;
74 }
75 
76 
77 #ifndef NDEBUG
78 /** Check whether heap is valid.
79  *
80  * @note Sift up/down do not use order, only for the last the changed one is entered.
81  */
82 static
84  const unsigned int* entry, /**< entries of heap */
85  const unsigned long long* value, /**< values in heap */
86  const unsigned int* order, /**< order of entries */
87  const unsigned int used, /**< number of used entries */
88  const unsigned int size /**< size of entry array */
89  )
90 {
91  unsigned int i;
92 
93  if ( entry == NULL || value == NULL || order == NULL || used > size )
94  return FALSE;
95 
96  /* check heap property */
97  for (i = 0; i < used / 2; ++i)
98  {
99  if ( value[entry[i]] > value[entry[i + i]] )
100  return FALSE;
101  if ( i + i + 1 < used && value[entry[i]] > value[entry[i + i + 1]] )
102  return FALSE;
103  }
104 
105  return TRUE;
106 }
107 #endif
108 
109 
110 /** Moves an entry down in the vector until the sorting is valid again. */
111 static
113  unsigned int* entry, /**< entries of heap */
114  const unsigned long long* value, /**< values in heap */
115  unsigned int* order, /**< order of entries */
116  unsigned int used, /**< number of used entries */
117  unsigned int current /**< current entry to be sifted */
118  )
119 {
120  unsigned long long val;
121  unsigned int child;
122  unsigned int ent;
123  unsigned int e;
124 
125  child = current + current;
126  ent = entry[current];
127  val = value[ent];
128 
129  while ( child < used )
130  {
131  e = entry[child];
132 
133  if ( child + 1 < used )
134  {
135  if ( value[entry[child + 1]] < value[e] )
136  {
137  ++child;
138  e = entry[child];
139  }
140  }
141  if ( value[e] >= val )
142  break;
143 
144  entry[current] = e;
145  order[e] = current;
146 
147  current = child;
148  child += child;
149  }
150  entry[current] = ent;
151  order[ent] = current;
152 }
153 
154 
155 /** Moves an entry up in the vector until the sorting is valid again. */
156 static
158  unsigned int* entry, /**< entries of heap */
159  const unsigned long long* value, /**< values in heap */
160  unsigned int* order, /**< order of entries */
161  unsigned int current /**< current entry to be sifted */
162  )
163 {
164  unsigned long long val;
165  unsigned int parent;
166  unsigned int ent;
167  unsigned int e;
168 
169  ent = entry[current];
170  val = value[ent];
171 
172  while ( current > 0 )
173  {
174  parent = current / 2;
175  e = entry[parent];
176 
177  if ( value[e] <= val )
178  break;
179 
180  entry[current] = e;
181  order[e] = current;
182  current = parent;
183  }
184  entry[current] = ent;
185  order[ent] = current;
186 }
187 
188 
189 /** Dijkstra's algorithm for shortest paths from a single source using binary heaps */
190 unsigned int dijkstra(
191  const DIJKSTRA_GRAPH* G, /**< directed graph */
192  unsigned int source, /**< source node */
193  unsigned long long* dist, /**< node distances (allocated by user) */
194  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
195  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
196  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
197  )
198 {
199  unsigned long long weight;
200  unsigned int iters = 0;
201  unsigned int used = 0;
202  unsigned int head;
203  unsigned int tail;
204  unsigned int i;
205  unsigned int e;
206 
207  assert( dijkstraGraphIsValid(G) );
208  assert( source < G->nodes );
209  assert( dist != NULL );
210  assert( pred != NULL );
211 
212  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
213 
214  /* initialize nodes */
215  for (i = 0; i < G->nodes; ++i)
216  {
217  dist[i] = DIJKSTRA_FARAWAY;
218  order[i] = DIJKSTRA_UNUSED;
219  pred[i] = DIJKSTRA_UNUSED;
220  }
221 
222  /* enter source node into heap */
223  entry[0] = source;
224  order[source] = 0;
225  pred[source] = DIJKSTRA_UNUSED;
226  dist[source] = 0;
227 
228  ++used;
229 
230  /* loop while heap is not empty */
231  while ( used > 0 )
232  {
233  /* get next node */
234  tail = entry[0];
235 
236  /* remove node from heap */
237  --used;
238  entry[0] = entry[used];
239  order[entry[0]] = 0;
240  order[tail] = DIJKSTRA_UNUSED;
241 
242  dijkstraSiftDown(entry, dist, order, used, 0);
243 
244  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
245  assert( entry[used] < G->nodes );
246 
247  /* check adjacent nodes */
248  for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
249  {
250  head = G->head[e];
251  weight = G->weight[e] + dist[tail];
252 
253  /* Can we improve the current shortest path? */
254  if ( dist[head] > weight )
255  {
256  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
257  assert( used < G->nodes );
258  assert( head <= G->nodes );
259 
260  pred[head] = tail;
261  dist[head] = weight;
262 
263  if ( order[head] == DIJKSTRA_UNUSED )
264  {
265  assert( head < G->nodes );
266 
267  entry[used] = head;
268  order[head] = used;
269 
270  dijkstraSiftUp(entry, dist, order, used);
271  ++used;
272  }
273  else
274  {
275  dijkstraSiftUp(entry, dist, order, order[head]);
276  }
277  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
278 
279  ++iters;
280  }
281  }
282  }
283  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
284 
285  return iters;
286 }
287 
288 
289 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps */
290 unsigned int dijkstraPair(
291  const DIJKSTRA_GRAPH* G, /**< directed graph */
292  unsigned int source, /**< source node */
293  unsigned int target, /**< target node */
294  unsigned long long* dist, /**< node distances (allocated by user) */
295  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
296  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
297  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
298  )
299 {
300  unsigned long long weight;
301  unsigned int iters = 0;
302  unsigned int used = 0;
303  unsigned int head;
304  unsigned int tail;
305  unsigned int i;
306  unsigned int e;
307 
308  assert( dijkstraGraphIsValid(G) );
309  assert( source < G->nodes );
310  assert( target < G->nodes );
311  assert( dist != NULL );
312  assert( pred != NULL );
313 
314  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
315 
316  /* initialize nodes */
317  for (i = 0; i < G->nodes; ++i)
318  {
319  dist[i] = DIJKSTRA_FARAWAY;
320  order[i] = DIJKSTRA_UNUSED;
321  pred[i] = DIJKSTRA_UNUSED;
322  }
323 
324  /* enter source node into heap */
325  entry[0] = source;
326  order[source] = 0;
327  pred[source] = DIJKSTRA_UNUSED;
328  dist[source] = 0;
329 
330  ++used;
331 
332  /* loop while heap is not empty */
333  while ( used > 0 )
334  {
335  /* get next node */
336  tail = entry[0];
337 
338  /* stop if we have found the target node */
339  if ( tail == target )
340  break;
341 
342  /* remove node from heap */
343  --used;
344  entry[0] = entry[used];
345  order[entry[0]] = 0;
346  order[tail] = DIJKSTRA_UNUSED;
347 
348  dijkstraSiftDown(entry, dist, order, used, 0);
349 
350  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
351  assert( entry[used] < G->nodes );
352 
353  /* check adjacent nodes */
354  for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
355  {
356  head = G->head[e];
357  weight = G->weight[e] + dist[tail];
358 
359  /* Can we improve the current shortest path? */
360  if ( dist[head] > weight )
361  {
362  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
363  assert( used < G->nodes );
364  assert( head <= G->nodes );
365 
366  pred[head] = tail;
367  dist[head] = weight;
368 
369  if ( order[head] == DIJKSTRA_UNUSED )
370  {
371  assert( head < G->nodes );
372 
373  entry[used] = head;
374  order[head] = used;
375 
376  dijkstraSiftUp(entry, dist, order, used);
377  ++used;
378  }
379  else
380  {
381  dijkstraSiftUp(entry, dist, order, order[head]);
382  }
383  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
384 
385  ++iters;
386  }
387  }
388  }
389  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
390 
391  return iters;
392 }
393 
394 
395 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff */
396 unsigned int dijkstraPairCutoff(
397  const DIJKSTRA_GRAPH* G, /**< directed graph */
398  unsigned int source, /**< source node */
399  unsigned int target, /**< target node */
400  unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
401  unsigned long long* dist, /**< node distances (allocated by user) */
402  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
403  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
404  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
405  )
406 {
407  unsigned long long weight;
408  unsigned int iters = 0;
409  unsigned int used = 0;
410  unsigned int head;
411  unsigned int tail;
412  unsigned int i;
413  unsigned int e;
414 
415  assert( dijkstraGraphIsValid(G) );
416  assert( source < G->nodes );
417  assert( target < G->nodes );
418  assert( dist != NULL );
419  assert( pred != NULL );
420 
421  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
422 
423  /* initialize nodes */
424  for (i = 0; i < G->nodes; ++i)
425  {
426  dist[i] = DIJKSTRA_FARAWAY;
427  order[i] = DIJKSTRA_UNUSED;
428  pred[i] = DIJKSTRA_UNUSED;
429  }
430 
431  /* enter source node into heap */
432  entry[0] = source;
433  order[source] = 0;
434  pred[source] = DIJKSTRA_UNUSED;
435  dist[source] = 0;
436 
437  ++used;
438 
439  /* loop while heap is not empty */
440  while ( used > 0 )
441  {
442  /* get next node */
443  tail = entry[0];
444 
445  /* stop if we have found the target node */
446  if ( tail == target )
447  break;
448 
449  /* remove node from heap */
450  --used;
451  entry[0] = entry[used];
452  order[entry[0]] = 0;
453  order[tail] = DIJKSTRA_UNUSED;
454 
455  dijkstraSiftDown(entry, dist, order, used, 0);
456 
457  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
458  assert( entry[used] < G->nodes );
459 
460  /* only work on nodes if their distance is less than the cutoff */
461  if ( dist[tail] >= cutoff )
462  continue;
463 
464  /* check adjacent nodes */
465  for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
466  {
467  head = G->head[e];
468  weight = G->weight[e] + dist[tail];
469 
470  /* Can we improve the current shortest path? */
471  if ( dist[head] > weight )
472  {
473  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
474  assert( used < G->nodes );
475  assert( head <= G->nodes );
476 
477  pred[head] = tail;
478  dist[head] = weight;
479 
480  if ( order[head] == DIJKSTRA_UNUSED )
481  {
482  assert( head < G->nodes );
483 
484  entry[used] = head;
485  order[head] = used;
486 
487  dijkstraSiftUp(entry, dist, order, used);
488  ++used;
489  }
490  else
491  {
492  dijkstraSiftUp(entry, dist, order, order[head]);
493  }
494  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
495 
496  ++iters;
497  }
498  }
499  }
500  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
501 
502  return iters;
503 }
504 
505 
506 /** Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff */
508  const DIJKSTRA_GRAPH* G, /**< directed graph */
509  unsigned int source, /**< source node */
510  unsigned int target, /**< target node */
511  unsigned int* ignore, /**< marking nodes to be ignored (if value is nonzero) */
512  unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
513  unsigned long long* dist, /**< node distances (allocated by user) */
514  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
515  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
516  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
517  )
518 {
519  unsigned long long weight;
520  unsigned int iters = 0;
521  unsigned int used = 0;
522  unsigned int head;
523  unsigned int tail;
524  unsigned int i;
525  unsigned int e;
526 
527  assert( dijkstraGraphIsValid(G) );
528  assert( source < G->nodes );
529  assert( target < G->nodes );
530  assert( dist != NULL );
531  assert( pred != NULL );
532  assert( ignore[source] == 0 );
533  assert( ignore[target] == 0 );
534 
535  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
536 
537  /* initialize nodes */
538  for (i = 0; i < G->nodes; ++i)
539  {
540  dist[i] = DIJKSTRA_FARAWAY;
541  order[i] = DIJKSTRA_UNUSED;
542  pred[i] = DIJKSTRA_UNUSED;
543  }
544 
545  /* enter source node into heap */
546  entry[0] = source;
547  order[source] = 0;
548  pred[source] = DIJKSTRA_UNUSED;
549  dist[source] = 0;
550 
551  ++used;
552 
553  /* loop while heap is not empty */
554  while ( used > 0 )
555  {
556  /* get next node */
557  tail = entry[0];
558 
559  /* stop if we have found the target node */
560  if ( tail == target )
561  break;
562 
563  /* remove node from heap */
564  --used;
565  entry[0] = entry[used];
566  order[entry[0]] = 0;
567  order[tail] = DIJKSTRA_UNUSED;
568 
569  dijkstraSiftDown(entry, dist, order, used, 0);
570 
571  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
572  assert( entry[used] < G->nodes );
573 
574  /* only work on nodes if their distance is less than the cutoff */
575  if ( dist[tail] >= cutoff )
576  continue;
577 
578  /* check adjacent nodes */
579  for (e = G->outbeg[tail]; G->head[e] != DIJKSTRA_UNUSED; ++e)
580  {
581  head = G->head[e];
582 
583  /* skip ignored nodes */
584  if ( ignore[head] != 0 )
585  continue;
586 
587  weight = G->weight[e] + dist[tail];
588 
589  /* Can we improve the current shortest path? */
590  if ( dist[head] > weight )
591  {
592  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
593  assert( used < G->nodes );
594  assert( head <= G->nodes );
595 
596  pred[head] = tail;
597  dist[head] = weight;
598 
599  if ( order[head] == DIJKSTRA_UNUSED )
600  {
601  assert( head < G->nodes );
602 
603  entry[used] = head;
604  order[head] = used;
605 
606  dijkstraSiftUp(entry, dist, order, used);
607  ++used;
608  }
609  else
610  {
611  dijkstraSiftUp(entry, dist, order, order[head]);
612  }
613  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
614 
615  ++iters;
616  }
617  }
618  }
619  assert( dijkstraHeapIsValid(entry, dist, order, used, G->nodes) );
620 
621  return iters;
622 }
unsigned int dijkstraPair(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
Definition: dijkstra.c:290
static void dijkstraSiftUp(unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int current)
Definition: dijkstra.c:157
Definitions for Disjkstra&#39;s shortest path algorithm.
#define DIJKSTRA_FARAWAY
Definition: dijkstra.h:47
static DIJKSTRA_Bool dijkstraHeapIsValid(const unsigned int *entry, const unsigned long long *value, const unsigned int *order, const unsigned int used, const unsigned int size)
Definition: dijkstra.c:83
size_t * size
Definition: memory.c:2499
#define FALSE
Definition: def.h:96
unsigned int * outcnt
Definition: dijkstra.h:56
unsigned int maxweight
Definition: dijkstra.h:61
#define TRUE
Definition: def.h:95
unsigned int * used
Definition: memory.c:2500
unsigned int dijkstraPairCutoff(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
Definition: dijkstra.c:396
unsigned int nodes
Definition: dijkstra.h:54
#define DIJKSTRA_Bool
Definition: dijkstra.h:40
unsigned int minweight
Definition: dijkstra.h:60
unsigned int * head
Definition: dijkstra.h:59
#define NULL
Definition: lpi_spx1.cpp:164
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
Definition: dijkstra.c:42
#define DIJKSTRA_UNUSED
Definition: dijkstra.h:48
unsigned int dijkstraPairCutoffIgnore(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned int target, unsigned int *ignore, unsigned long long cutoff, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
Definition: dijkstra.c:507
static void dijkstraSiftDown(unsigned int *entry, const unsigned long long *value, unsigned int *order, unsigned int used, unsigned int current)
Definition: dijkstra.c:112
unsigned int * weight
Definition: dijkstra.h:58
unsigned int dijkstra(const DIJKSTRA_GRAPH *G, unsigned int source, unsigned long long *dist, unsigned int *pred, unsigned int *entry, unsigned int *order)
Definition: dijkstra.c:190
unsigned int arcs
Definition: dijkstra.h:57
unsigned int * outbeg
Definition: dijkstra.h:55