Branch data Line data Source code
1 : : /* Template class for Dijkstra's algorithm on directed graphs.
2 : : Copyright (C) 2019-2024 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 : 7789 : 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 : 7789 : 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 : 7789 : : m_graph (graph),
94 : 7789 : m_sense (sense),
95 : 15578 : m_dist (graph.m_nodes.length ()),
96 : 15578 : m_best_edge (graph.m_nodes.length ())
97 : : {
98 : 7789 : auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS);
99 : :
100 : 15578 : auto_vec<int> queue (graph.m_nodes.length ());
101 : :
102 : 3881896 : for (unsigned i = 0; i < graph.m_nodes.length (); i++)
103 : : {
104 : 1933159 : m_dist.quick_push (INT_MAX);
105 : 1933159 : m_best_edge.quick_push (NULL);
106 : 1933159 : queue.quick_push (i);
107 : : }
108 : 7789 : m_dist[given_node->m_index] = 0;
109 : :
110 : 222060 : 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 : 214556182 : for (unsigned i = 0; i < queue.length (); i++)
118 : : {
119 : 214341911 : int idx = queue[i];
120 : 214341911 : if (m_dist[queue[i]] < min_dist)
121 : : {
122 : 267726 : min_dist = m_dist[idx];
123 : 267726 : idx_with_min_dist = idx;
124 : 267726 : idx_in_queue_with_min_dist = i;
125 : : }
126 : : }
127 : 214271 : if (idx_with_min_dist == -1)
128 : : break;
129 : 206662 : gcc_assert (idx_in_queue_with_min_dist != -1);
130 : :
131 : : // FIXME: this is confusing: there are two indices here
132 : :
133 : 206662 : queue.unordered_remove (idx_in_queue_with_min_dist);
134 : :
135 : 206662 : node_t *n
136 : 206662 : = static_cast <node_t *> (m_graph.m_nodes[idx_with_min_dist]);
137 : :
138 : 206662 : if (m_sense == SPS_FROM_GIVEN_ORIGIN)
139 : : {
140 : : int i;
141 : : edge_t *succ;
142 : 388 : FOR_EACH_VEC_ELT (n->m_succs, i, succ)
143 : : {
144 : : // TODO: only for dest still in queue
145 : 195 : node_t *dest = succ->m_dest;
146 : 195 : int alt = m_dist[n->m_index] + 1;
147 : 195 : if (alt < m_dist[dest->m_index])
148 : : {
149 : 176 : m_dist[dest->m_index] = alt;
150 : 176 : m_best_edge[dest->m_index] = succ;
151 : : }
152 : : }
153 : : }
154 : : else
155 : : {
156 : : int i;
157 : : edge_t *pred;
158 : 627182 : FOR_EACH_VEC_ELT (n->m_preds, i, pred)
159 : : {
160 : : // TODO: only for dest still in queue
161 : 206262 : node_t *src = pred->m_src;
162 : 206262 : int alt = m_dist[n->m_index] + 1;
163 : 206262 : if (alt < m_dist[src->m_index])
164 : : {
165 : 198697 : m_dist[src->m_index] = alt;
166 : 198697 : m_best_edge[src->m_index] = pred;
167 : : }
168 : : }
169 : : }
170 : : }
171 : 7789 : }
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 : 256 : shortest_paths<GraphTraits, Path_t>::
184 : : get_shortest_path (const node_t *other_node) const
185 : : {
186 : 256 : Path_t result;
187 : :
188 : 1537 : while (m_best_edge[other_node->m_index])
189 : : {
190 : 1281 : result.m_edges.safe_push (m_best_edge[other_node->m_index]);
191 : 1281 : if (m_sense == SPS_FROM_GIVEN_ORIGIN)
192 : 132 : other_node = m_best_edge[other_node->m_index]->m_src;
193 : : else
194 : 1149 : other_node = m_best_edge[other_node->m_index]->m_dest;
195 : : }
196 : :
197 : 256 : if (m_sense == SPS_FROM_GIVEN_ORIGIN)
198 : 77 : result.m_edges.reverse ();
199 : :
200 : 256 : 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 : 476660 : shortest_paths<GraphTraits, Path_t>::
210 : : get_shortest_distance (const node_t *other_node) const
211 : : {
212 : 476660 : return m_dist[other_node->m_index];
213 : : }
214 : :
215 : : #endif /* GCC_SHORTEST_PATHS_H */
|
