|
145
|
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 */
|
