1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
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 */
52   	struct DIJKSTRA_Graph
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 */
65   	typedef struct DIJKSTRA_Graph DIJKSTRA_GRAPH;
66   	
67   	
68   	
69   	/** Check whether the data structures of the graph are valid. */
70   	DIJKSTRA_Bool dijkstraGraphIsValid(
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
125