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
shortest_paths(const graph_t & graph,const node_t * origin)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
get_shortest_path(const node_t * to)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 */
146