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