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