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