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-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.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 */
43 struct DIJKSTRA_Graph
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 */
56 typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH;
57 
58 
59 
60 /** Check whether the data structures of the graph are valid. */
61 extern
62 DIJKSTRA_Bool dijkstraGraphIsValid(
63  const DIJKSTRA_GRAPH* G /**< directed graph to be checked */
64  );
65 
66 /** Dijkstra's algorithm using binary heaps */
67 extern
68 unsigned int dijkstra(
69  const DIJKSTRA_GRAPH* G, /**< directed graph */
70  unsigned int source, /**< source node */
71  unsigned long long* dist, /**< node distances (allocated by user) */
72  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
73  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
74  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
75  );
76 
77 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps */
78 extern
79 unsigned int dijkstraPair(
80  const DIJKSTRA_GRAPH* G, /**< directed graph */
81  unsigned int source, /**< source node */
82  unsigned int target, /**< target node */
83  unsigned long long* dist, /**< node distances (allocated by user) */
84  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
85  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
86  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
87  );
88 
89 /** Dijkstra's algorithm for shortest paths between a pair of nodes using binary heaps and truncated at cutoff */
90 extern
91 unsigned int dijkstraPairCutoff(
92  const DIJKSTRA_GRAPH* G, /**< directed graph */
93  unsigned int source, /**< source node */
94  unsigned int target, /**< target node */
95  unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
96  unsigned long long* dist, /**< node distances (allocated by user) */
97  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
98  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
99  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
100  );
101 
102 /** Dijkstra's algorithm for shortest paths between a pair of nodes ignoring nodes, using binary heaps, and truncated at cutoff */
103 extern
104 unsigned int dijkstraPairCutoffIgnore(
105  const DIJKSTRA_GRAPH* G, /**< directed graph */
106  unsigned int source, /**< source node */
107  unsigned int target, /**< target node */
108  unsigned int* ignore, /**< marking nodes to be ignored (if value is nonzero) */
109  unsigned long long cutoff, /**< if the distance of a node reached this value, we truncate the search */
110  unsigned long long* dist, /**< node distances (allocated by user) */
111  unsigned int* pred, /**< node predecessors in final shortest path tree (allocated by user) */
112  unsigned int* entry, /**< temporary storage (for each node - must be allocated by user) */
113  unsigned int* order /**< temporary storage (for each node - must be allocated by user) */
114  );
115 
116 #ifdef __cplusplus
117 }
118 #endif
119 
120 #endif
121