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