Scippy

SCIP

Solving Constraint Integer Programs

dijkstra.h
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.h
17  * @brief Definitions for Disjkstra's shortest path algorithm
18  * @author Thorsten Koch
19  * @author Marc Pfetsch
20  */
21 
22 #ifndef DIJSKSTRA_H
23 #define DIJSKSTRA_H
24 
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28 
29 /* declare own bools, if necessary */
30 #ifndef DIJKSTRA_Bool
31 #define DIJKSTRA_Bool unsigned int /**< type used for boolean values */
32 #endif
33 #ifndef TRUE
34 #define TRUE 1 /**< boolean value TRUE */
35 #define FALSE 0 /**< boolean value FALSE */
36 #endif
37 
38 #define DIJKSTRA_FARAWAY 0xffffffffu /**< node has distance 'infinity' */
39 #define DIJKSTRA_UNUSED 0xffffffffu /**< node is unused */
40 
41 
42 /** graph structure - use consecutive storage for arcs */
44 {
45  unsigned int nodes; /**< number of nodes */
46  unsigned int* outbeg; /**< indices of out-arcs for each node in arcs array */
47  unsigned int* outcnt; /**< number of out-arcs for each node */
48  unsigned int arcs; /**< consecutive storage for all arcs */
49  unsigned int* weight; /**< corresponding weights for all arcs */
50  unsigned int* head; /**< target nodes for all arcs */
51  unsigned int minweight; /**< total minimal weight */
52  unsigned int maxweight; /**< total maximal weight */
53 };
54 
55 /** graph structure - use consecutive storage for arcs */
57 
58 
59 
60 /** Check whether the data structures of the graph are valid. */
62  const DIJKSTRA_GRAPH* G /**< directed graph to be checked */
63  );
64 
65 /** Dijkstra's algorithm using binary heaps */
66 unsigned int dijkstra(
67  const DIJKSTRA_GRAPH* G, /**< directed graph */
68  unsigned int source, /**< source node */
69  unsigned long long* dist, /**< node distances (allocated by user) */
70  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
71  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
72  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
73  );
74 
75 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps */
76 unsigned int dijkstraPair(
77  const DIJKSTRA_GRAPH* G, /**< directed graph */
78  unsigned int source, /**< source node */
79  unsigned int target, /**< target node */
80  unsigned long long* dist, /**< node distances (allocated by user) */
81  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
82  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
83  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
84  );
85 
86 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff */
87 unsigned int dijkstraPairCutoff(
88  const DIJKSTRA_GRAPH* G, /**< directed graph */
89  unsigned int source, /**< source node */
90  unsigned int target, /**< target node */
91  unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
92  unsigned long long* dist, /**< node distances (allocated by user) */
93  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
94  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
95  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
96  );
97 
98 /** Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff */
99 unsigned int dijkstraPairCutoffIgnore(
100  const DIJKSTRA_GRAPH* G, /**< directed graph */
101  unsigned int source, /**< source node */
102  unsigned int target, /**< target node */
103  unsigned int* ignore, /**< marking nodes to be ignored (if value is nonzero) */
104  unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
105  unsigned long long* dist, /**< node distances (allocated by user) */
106  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
107  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
108  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
109  );
110 
111 #ifdef __cplusplus
112 }
113 #endif
114 
115 #endif
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 * outcnt
Definition: dijkstra.h:47
unsigned int maxweight
Definition: dijkstra.h:52
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
unsigned int nodes
Definition: dijkstra.h:45
#define DIJKSTRA_Bool
Definition: dijkstra.h:31
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 minweight
Definition: dijkstra.h:51
unsigned int * head
Definition: dijkstra.h:50
unsigned int * weight
Definition: dijkstra.h:49
DIJKSTRA_Bool dijkstraGraphIsValid(const DIJKSTRA_GRAPH *G)
Definition: dijkstra.c:33
unsigned int arcs
Definition: dijkstra.h:48
unsigned int * outbeg
Definition: dijkstra.h:46
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