1 /* Template class for Dijkstra's algorithm on directed graphs.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
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
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
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
56 shortest_paths (const graph_t &graph, const node_t *given_node,
57 enum shortest_path_sense sense);
58
59 path_t get_shortest_path (const node_t *other_node) const;
60 int get_shortest_distance (const node_t *other_node) const;
61
62 private:
63 const graph_t &m_graph;
64
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). */
69 auto_vec<int> m_dist;
70
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;
77 };
78
79 /* shortest_paths's constructor.
80
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. */
86
87 template <typename GraphTraits, typename Path_t>
88 inline
89 shortest_paths<GraphTraits, Path_t>::
shortest_paths(const graph_t & graph,const node_t * given_node,enum shortest_path_sense sense)90 shortest_paths (const graph_t &graph,
91 const node_t *given_node,
92 enum shortest_path_sense sense)
93 : m_graph (graph),
94 m_sense (sense),
95 m_dist (graph.m_nodes.length ()),
96 m_best_edge (graph.m_nodes.length ())
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);
105 m_best_edge.quick_push (NULL);
106 queue.quick_push (i);
107 }
108 m_dist[given_node->m_index] = 0;
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 }
127 if (idx_with_min_dist == -1)
128 break;
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
138 if (m_sense == SPS_FROM_GIVEN_ORIGIN)
139 {
140 int i;
141 edge_t *succ;
142 FOR_EACH_VEC_ELT (n->m_succs, i, succ)
143 {
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 }
168 }
169 }
170 }
171 }
172
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
179 If no such path exists, return an empty path. */
180
181 template <typename GraphTraits, typename Path_t>
182 inline Path_t
183 shortest_paths<GraphTraits, Path_t>::
get_shortest_path(const node_t * other_node)184 get_shortest_path (const node_t *other_node) const
185 {
186 Path_t result;
187
188 while (m_best_edge[other_node->m_index])
189 {
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;
195 }
196
197 if (m_sense == SPS_FROM_GIVEN_ORIGIN)
198 result.m_edges.reverse ();
199
200 return result;
201 }
202
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>::
get_shortest_distance(const node_t * other_node)210 get_shortest_distance (const node_t *other_node) const
211 {
212 return m_dist[other_node->m_index];
213 }
214
215 #endif /* GCC_SHORTEST_PATHS_H */
216