]>
Commit | Line | Data |
---|---|---|
757bf1df | 1 | /* Template class for Dijkstra's algorithm on directed graphs. |
a945c346 | 2 | Copyright (C) 2019-2024 Free Software Foundation, Inc. |
757bf1df DM |
3 | Contributed by David Malcolm <dmalcolm@redhat.com>. |
4 | ||
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU General Public License as published by | |
9 | the Free Software Foundation; either version 3, or (at your option) | |
10 | any later version. | |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
18 | along with GCC; see the file COPYING3. If not see | |
19 | <http://www.gnu.org/licenses/>. */ | |
20 | ||
21 | #ifndef GCC_SHORTEST_PATHS_H | |
22 | #define GCC_SHORTEST_PATHS_H | |
23 | ||
24 | #include "timevar.h" | |
25 | ||
5e33e5b0 DM |
26 | enum shortest_path_sense |
27 | { | |
28 | /* Find the shortest path from the given origin node to each | |
29 | node in the graph. */ | |
30 | SPS_FROM_GIVEN_ORIGIN, | |
31 | ||
32 | /* Find the shortest path from each node in the graph to the | |
33 | given target node. */ | |
34 | SPS_TO_GIVEN_TARGET | |
35 | }; | |
36 | ||
37 | /* A record of the shortest path for each node relative to a special | |
38 | "given node", either: | |
39 | SPS_FROM_GIVEN_ORIGIN: | |
40 | from the given origin node to each node in a graph, or | |
41 | SPS_TO_GIVEN_TARGET: | |
42 | from each node in a graph to the given target node. | |
43 | ||
757bf1df DM |
44 | The constructor runs Dijkstra's algorithm, and the results are |
45 | stored in this class. */ | |
46 | ||
47 | template <typename GraphTraits, typename Path_t> | |
48 | class shortest_paths | |
49 | { | |
50 | public: | |
51 | typedef typename GraphTraits::graph_t graph_t; | |
52 | typedef typename GraphTraits::node_t node_t; | |
53 | typedef typename GraphTraits::edge_t edge_t; | |
54 | typedef Path_t path_t; | |
55 | ||
5e33e5b0 DM |
56 | shortest_paths (const graph_t &graph, const node_t *given_node, |
57 | enum shortest_path_sense sense); | |
757bf1df | 58 | |
5e33e5b0 | 59 | path_t get_shortest_path (const node_t *other_node) const; |
3857edb5 | 60 | int get_shortest_distance (const node_t *other_node) const; |
757bf1df DM |
61 | |
62 | private: | |
63 | const graph_t &m_graph; | |
64 | ||
5e33e5b0 DM |
65 | enum shortest_path_sense m_sense; |
66 | ||
67 | /* For each node (by index), the minimal distance between that node | |
68 | and the given node (with direction depending on m_sense). */ | |
757bf1df DM |
69 | auto_vec<int> m_dist; |
70 | ||
5e33e5b0 DM |
71 | /* For each node (by index): |
72 | SPS_FROM_GIVEN_ORIGIN: | |
73 | the previous edge in the shortest path from the origin, | |
74 | SPS_TO_GIVEN_TARGET: | |
75 | the next edge in the shortest path to the target. */ | |
76 | auto_vec<const edge_t *> m_best_edge; | |
757bf1df DM |
77 | }; |
78 | ||
79 | /* shortest_paths's constructor. | |
80 | ||
5e33e5b0 DM |
81 | Use Dijkstra's algorithm relative to GIVEN_NODE to populate m_dist and |
82 | m_best_edge with enough information to be able to generate Path_t instances | |
83 | to give the shortest path... | |
84 | SPS_FROM_GIVEN_ORIGIN: to each node in a graph from the origin node, or | |
85 | SPS_TO_GIVEN_TARGET: from each node in a graph to the target node. */ | |
757bf1df DM |
86 | |
87 | template <typename GraphTraits, typename Path_t> | |
88 | inline | |
5e33e5b0 DM |
89 | shortest_paths<GraphTraits, Path_t>:: |
90 | shortest_paths (const graph_t &graph, | |
91 | const node_t *given_node, | |
92 | enum shortest_path_sense sense) | |
757bf1df | 93 | : m_graph (graph), |
5e33e5b0 | 94 | m_sense (sense), |
757bf1df | 95 | m_dist (graph.m_nodes.length ()), |
5e33e5b0 | 96 | m_best_edge (graph.m_nodes.length ()) |
757bf1df DM |
97 | { |
98 | auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS); | |
99 | ||
100 | auto_vec<int> queue (graph.m_nodes.length ()); | |
101 | ||
102 | for (unsigned i = 0; i < graph.m_nodes.length (); i++) | |
103 | { | |
104 | m_dist.quick_push (INT_MAX); | |
5e33e5b0 | 105 | m_best_edge.quick_push (NULL); |
757bf1df DM |
106 | queue.quick_push (i); |
107 | } | |
5e33e5b0 | 108 | m_dist[given_node->m_index] = 0; |
757bf1df DM |
109 | |
110 | while (queue.length () > 0) | |
111 | { | |
112 | /* Get minimal distance in queue. | |
113 | FIXME: this is O(N^2); replace with a priority queue. */ | |
114 | int idx_with_min_dist = -1; | |
115 | int idx_in_queue_with_min_dist = -1; | |
116 | int min_dist = INT_MAX; | |
117 | for (unsigned i = 0; i < queue.length (); i++) | |
118 | { | |
119 | int idx = queue[i]; | |
120 | if (m_dist[queue[i]] < min_dist) | |
121 | { | |
122 | min_dist = m_dist[idx]; | |
123 | idx_with_min_dist = idx; | |
124 | idx_in_queue_with_min_dist = i; | |
125 | } | |
126 | } | |
3f958348 DM |
127 | if (idx_with_min_dist == -1) |
128 | break; | |
757bf1df DM |
129 | gcc_assert (idx_in_queue_with_min_dist != -1); |
130 | ||
131 | // FIXME: this is confusing: there are two indices here | |
132 | ||
133 | queue.unordered_remove (idx_in_queue_with_min_dist); | |
134 | ||
135 | node_t *n | |
136 | = static_cast <node_t *> (m_graph.m_nodes[idx_with_min_dist]); | |
137 | ||
5e33e5b0 | 138 | if (m_sense == SPS_FROM_GIVEN_ORIGIN) |
757bf1df | 139 | { |
5e33e5b0 DM |
140 | int i; |
141 | edge_t *succ; | |
142 | FOR_EACH_VEC_ELT (n->m_succs, i, succ) | |
757bf1df | 143 | { |
5e33e5b0 DM |
144 | // TODO: only for dest still in queue |
145 | node_t *dest = succ->m_dest; | |
146 | int alt = m_dist[n->m_index] + 1; | |
147 | if (alt < m_dist[dest->m_index]) | |
148 | { | |
149 | m_dist[dest->m_index] = alt; | |
150 | m_best_edge[dest->m_index] = succ; | |
151 | } | |
152 | } | |
153 | } | |
154 | else | |
155 | { | |
156 | int i; | |
157 | edge_t *pred; | |
158 | FOR_EACH_VEC_ELT (n->m_preds, i, pred) | |
159 | { | |
160 | // TODO: only for dest still in queue | |
161 | node_t *src = pred->m_src; | |
162 | int alt = m_dist[n->m_index] + 1; | |
163 | if (alt < m_dist[src->m_index]) | |
164 | { | |
165 | m_dist[src->m_index] = alt; | |
166 | m_best_edge[src->m_index] = pred; | |
167 | } | |
757bf1df DM |
168 | } |
169 | } | |
170 | } | |
171 | } | |
172 | ||
5e33e5b0 DM |
173 | /* Generate an Path_t instance giving the shortest path between OTHER_NODE |
174 | and the given node. | |
175 | ||
176 | SPS_FROM_GIVEN_ORIGIN: shortest path from given origin node to OTHER_NODE | |
177 | SPS_TO_GIVEN_TARGET: shortest path from OTHER_NODE to given target node. | |
178 | ||
3f958348 | 179 | If no such path exists, return an empty path. */ |
757bf1df DM |
180 | |
181 | template <typename GraphTraits, typename Path_t> | |
182 | inline Path_t | |
5e33e5b0 DM |
183 | shortest_paths<GraphTraits, Path_t>:: |
184 | get_shortest_path (const node_t *other_node) const | |
757bf1df DM |
185 | { |
186 | Path_t result; | |
187 | ||
5e33e5b0 | 188 | while (m_best_edge[other_node->m_index]) |
757bf1df | 189 | { |
5e33e5b0 DM |
190 | result.m_edges.safe_push (m_best_edge[other_node->m_index]); |
191 | if (m_sense == SPS_FROM_GIVEN_ORIGIN) | |
192 | other_node = m_best_edge[other_node->m_index]->m_src; | |
193 | else | |
194 | other_node = m_best_edge[other_node->m_index]->m_dest; | |
757bf1df DM |
195 | } |
196 | ||
5e33e5b0 DM |
197 | if (m_sense == SPS_FROM_GIVEN_ORIGIN) |
198 | result.m_edges.reverse (); | |
757bf1df DM |
199 | |
200 | return result; | |
201 | } | |
202 | ||
3857edb5 DM |
203 | /* Get the shortest distance... |
204 | SPS_FROM_GIVEN_ORIGIN: ...from given origin node to OTHER_NODE | |
205 | SPS_TO_GIVEN_TARGET: ...from OTHER_NODE to given target node. */ | |
206 | ||
207 | template <typename GraphTraits, typename Path_t> | |
208 | inline int | |
209 | shortest_paths<GraphTraits, Path_t>:: | |
210 | get_shortest_distance (const node_t *other_node) const | |
211 | { | |
212 | return m_dist[other_node->m_index]; | |
213 | } | |
214 | ||
757bf1df | 215 | #endif /* GCC_SHORTEST_PATHS_H */ |