Line data Source code
1 : /* Template class for Dijkstra's algorithm on directed graphs.
2 : Copyright (C) 2019-2026 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 6391 : 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 6391 : shortest_paths<GraphTraits, Path_t>::
90 : shortest_paths (const graph_t &graph,
91 : const node_t *given_node,
92 : enum shortest_path_sense sense)
93 6391 : : m_graph (graph),
94 6391 : m_sense (sense),
95 12782 : m_dist (graph.m_nodes.length ()),
96 12782 : m_best_edge (graph.m_nodes.length ())
97 : {
98 6391 : auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS);
99 :
100 12782 : auto_vec<int> queue (graph.m_nodes.length ());
101 :
102 1776252 : for (unsigned i = 0; i < graph.m_nodes.length (); i++)
103 : {
104 1769861 : m_dist.quick_push (INT_MAX);
105 1769861 : m_best_edge.quick_push (NULL);
106 1769861 : queue.quick_push (i);
107 : }
108 6391 : m_dist[given_node->m_index] = 0;
109 :
110 169221 : 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 214464043 : for (unsigned i = 0; i < queue.length (); i++)
118 : {
119 214301213 : int idx = queue[i];
120 214301213 : if (m_dist[queue[i]] < min_dist)
121 : {
122 205258 : min_dist = m_dist[idx];
123 205258 : idx_with_min_dist = idx;
124 205258 : idx_in_queue_with_min_dist = i;
125 : }
126 : }
127 162830 : if (idx_with_min_dist == -1)
128 : break;
129 156597 : gcc_assert (idx_in_queue_with_min_dist != -1);
130 :
131 : // FIXME: this is confusing: there are two indices here
132 :
133 156597 : queue.unordered_remove (idx_in_queue_with_min_dist);
134 :
135 156597 : node_t *n
136 156597 : = static_cast <node_t *> (m_graph.m_nodes[idx_with_min_dist]);
137 :
138 156597 : if (m_sense == SPS_FROM_GIVEN_ORIGIN)
139 : {
140 : int i;
141 : edge_t *succ;
142 250 : FOR_EACH_VEC_ELT (n->m_succs, i, succ)
143 : {
144 : // TODO: only for dest still in queue
145 125 : node_t *dest = succ->m_dest;
146 125 : int alt = m_dist[n->m_index] + 1;
147 125 : if (alt < m_dist[dest->m_index])
148 : {
149 109 : m_dist[dest->m_index] = alt;
150 109 : m_best_edge[dest->m_index] = succ;
151 : }
152 : }
153 : }
154 : else
155 : {
156 : int i;
157 : edge_t *pred;
158 475690 : FOR_EACH_VEC_ELT (n->m_preds, i, pred)
159 : {
160 : // TODO: only for dest still in queue
161 156230 : node_t *src = pred->m_src;
162 156230 : int alt = m_dist[n->m_index] + 1;
163 156230 : if (alt < m_dist[src->m_index])
164 : {
165 150097 : m_dist[src->m_index] = alt;
166 150097 : m_best_edge[src->m_index] = pred;
167 : }
168 : }
169 : }
170 : }
171 6391 : }
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 174 : shortest_paths<GraphTraits, Path_t>::
184 : get_shortest_path (const node_t *other_node) const
185 : {
186 174 : Path_t result;
187 :
188 932 : while (m_best_edge[other_node->m_index])
189 : {
190 758 : result.m_edges.safe_push (m_best_edge[other_node->m_index]);
191 758 : if (m_sense == SPS_FROM_GIVEN_ORIGIN)
192 85 : other_node = m_best_edge[other_node->m_index]->m_src;
193 : else
194 673 : other_node = m_best_edge[other_node->m_index]->m_dest;
195 : }
196 :
197 174 : if (m_sense == SPS_FROM_GIVEN_ORIGIN)
198 76 : result.m_edges.reverse ();
199 :
200 174 : 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 385904 : shortest_paths<GraphTraits, Path_t>::
210 : get_shortest_distance (const node_t *other_node) const
211 : {
212 385904 : return m_dist[other_node->m_index];
213 : }
214 :
215 : #endif /* GCC_SHORTEST_PATHS_H */
|
