]>
Commit | Line | Data |
---|---|---|
757bf1df DM |
1 | /* Template class for Dijkstra's algorithm on directed graphs. |
2 | Copyright (C) 2019-2020 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 | /* A record of the shortest path to each node in an graph | |
27 | from the origin node. | |
28 | The constructor runs Dijkstra's algorithm, and the results are | |
29 | stored in this class. */ | |
30 | ||
31 | template <typename GraphTraits, typename Path_t> | |
32 | class shortest_paths | |
33 | { | |
34 | public: | |
35 | typedef typename GraphTraits::graph_t graph_t; | |
36 | typedef typename GraphTraits::node_t node_t; | |
37 | typedef typename GraphTraits::edge_t edge_t; | |
38 | typedef Path_t path_t; | |
39 | ||
40 | shortest_paths (const graph_t &graph, const node_t *origin); | |
41 | ||
42 | path_t get_shortest_path (const node_t *to) const; | |
43 | ||
44 | private: | |
45 | const graph_t &m_graph; | |
46 | ||
47 | /* For each node (by index), the minimal distance to that node from the | |
48 | origin. */ | |
49 | auto_vec<int> m_dist; | |
50 | ||
51 | /* For each exploded_node (by index), the previous edge in the shortest | |
52 | path from the origin. */ | |
53 | auto_vec<const edge_t *> m_prev; | |
54 | }; | |
55 | ||
56 | /* shortest_paths's constructor. | |
57 | ||
58 | Use Dijkstra's algorithm relative to ORIGIN to populate m_dist and | |
59 | m_prev with enough information to be able to generate Path_t instances | |
60 | to give the shortest path to any node in GRAPH from ORIGIN. */ | |
61 | ||
62 | template <typename GraphTraits, typename Path_t> | |
63 | inline | |
64 | shortest_paths<GraphTraits, Path_t>::shortest_paths (const graph_t &graph, | |
65 | const node_t *origin) | |
66 | : m_graph (graph), | |
67 | m_dist (graph.m_nodes.length ()), | |
68 | m_prev (graph.m_nodes.length ()) | |
69 | { | |
70 | auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS); | |
71 | ||
72 | auto_vec<int> queue (graph.m_nodes.length ()); | |
73 | ||
74 | for (unsigned i = 0; i < graph.m_nodes.length (); i++) | |
75 | { | |
76 | m_dist.quick_push (INT_MAX); | |
77 | m_prev.quick_push (NULL); | |
78 | queue.quick_push (i); | |
79 | } | |
80 | m_dist[origin->m_index] = 0; | |
81 | ||
82 | while (queue.length () > 0) | |
83 | { | |
84 | /* Get minimal distance in queue. | |
85 | FIXME: this is O(N^2); replace with a priority queue. */ | |
86 | int idx_with_min_dist = -1; | |
87 | int idx_in_queue_with_min_dist = -1; | |
88 | int min_dist = INT_MAX; | |
89 | for (unsigned i = 0; i < queue.length (); i++) | |
90 | { | |
91 | int idx = queue[i]; | |
92 | if (m_dist[queue[i]] < min_dist) | |
93 | { | |
94 | min_dist = m_dist[idx]; | |
95 | idx_with_min_dist = idx; | |
96 | idx_in_queue_with_min_dist = i; | |
97 | } | |
98 | } | |
99 | gcc_assert (idx_with_min_dist != -1); | |
100 | gcc_assert (idx_in_queue_with_min_dist != -1); | |
101 | ||
102 | // FIXME: this is confusing: there are two indices here | |
103 | ||
104 | queue.unordered_remove (idx_in_queue_with_min_dist); | |
105 | ||
106 | node_t *n | |
107 | = static_cast <node_t *> (m_graph.m_nodes[idx_with_min_dist]); | |
108 | ||
109 | int i; | |
110 | edge_t *succ; | |
111 | FOR_EACH_VEC_ELT (n->m_succs, i, succ) | |
112 | { | |
113 | // TODO: only for dest still in queue | |
114 | node_t *dest = succ->m_dest; | |
115 | int alt = m_dist[n->m_index] + 1; | |
116 | if (alt < m_dist[dest->m_index]) | |
117 | { | |
118 | m_dist[dest->m_index] = alt; | |
119 | m_prev[dest->m_index] = succ; | |
120 | } | |
121 | } | |
122 | } | |
123 | } | |
124 | ||
125 | /* Generate an Path_t instance giving the shortest path to the node | |
126 | TO from the origin node. */ | |
127 | ||
128 | template <typename GraphTraits, typename Path_t> | |
129 | inline Path_t | |
130 | shortest_paths<GraphTraits, Path_t>::get_shortest_path (const node_t *to) const | |
131 | { | |
132 | Path_t result; | |
133 | ||
134 | while (m_prev[to->m_index]) | |
135 | { | |
136 | result.m_edges.safe_push (m_prev[to->m_index]); | |
137 | to = m_prev[to->m_index]->m_src; | |
138 | } | |
139 | ||
140 | result.m_edges.reverse (); | |
141 | ||
142 | return result; | |
143 | } | |
144 | ||
145 | #endif /* GCC_SHORTEST_PATHS_H */ |