gcc/shortest-paths.h

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