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