LCOV - code coverage report
Current view: top level - gcc - shortest-paths.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 35 35 100.0 %
Date: 2020-04-04 11:58:09 Functions: 4 4 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       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                 :        149 : 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                 :        447 :   m_prev (graph.m_nodes.length ())
      69                 :            : {
      70                 :        298 :   auto_timevar tv (TV_ANALYZER_SHORTEST_PATHS);
      71                 :            : 
      72                 :        298 :   auto_vec<int> queue (graph.m_nodes.length ());
      73                 :            : 
      74                 :      27714 :   for (unsigned i = 0; i < graph.m_nodes.length (); i++)
      75                 :            :     {
      76                 :      13708 :       m_dist.quick_push (INT_MAX);
      77                 :      13708 :       m_prev.quick_push (NULL);
      78                 :      13708 :       queue.quick_push (i);
      79                 :            :     }
      80                 :        149 :   m_dist[origin->m_index] = 0;
      81                 :            : 
      82                 :      13857 :   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                 :    4796524 :       for (unsigned i = 0; i < queue.length (); i++)
      90                 :            :         {
      91                 :    4782812 :           int idx = queue[i];
      92                 :    4782812 :           if (m_dist[queue[i]] < min_dist)
      93                 :            :             {
      94                 :      22589 :               min_dist = m_dist[idx];
      95                 :      22589 :               idx_with_min_dist = idx;
      96                 :      22589 :               idx_in_queue_with_min_dist = i;
      97                 :            :             }
      98                 :            :         }
      99                 :      13708 :       gcc_assert (idx_with_min_dist != -1);
     100                 :      13708 :       gcc_assert (idx_in_queue_with_min_dist != -1);
     101                 :            : 
     102                 :            :       // FIXME: this is confusing: there are two indices here
     103                 :            : 
     104                 :      13708 :       queue.unordered_remove (idx_in_queue_with_min_dist);
     105                 :            : 
     106                 :      13708 :       node_t *n
     107                 :      13708 :         = static_cast <node_t *> (m_graph.m_nodes[idx_with_min_dist]);
     108                 :            : 
     109                 :            :       int i;
     110                 :            :       edge_t *succ;
     111                 :      42676 :       FOR_EACH_VEC_ELT (n->m_succs, i, succ)
     112                 :            :         {
     113                 :            :           // TODO: only for dest still in queue
     114                 :      15111 :           node_t *dest = succ->m_dest;
     115                 :      15111 :           int alt = m_dist[n->m_index] + 1;
     116                 :      15111 :           if (alt < m_dist[dest->m_index])
     117                 :            :             {
     118                 :      13559 :               m_dist[dest->m_index] = alt;
     119                 :      13559 :               m_prev[dest->m_index] = succ;
     120                 :            :             }
     121                 :            :         }
     122                 :            :    }
     123                 :        149 : }
     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                 :        475 : shortest_paths<GraphTraits, Path_t>::get_shortest_path (const node_t *to) const
     131                 :            : {
     132                 :      10979 :   Path_t result;
     133                 :            : 
     134                 :      10979 :   while (m_prev[to->m_index])
     135                 :            :     {
     136                 :      10504 :       result.m_edges.safe_push (m_prev[to->m_index]);
     137                 :      10504 :       to = m_prev[to->m_index]->m_src;
     138                 :            :     }
     139                 :            : 
     140                 :        475 :   result.m_edges.reverse ();
     141                 :            : 
     142                 :        475 :   return result;
     143                 :            : }
     144                 :            : 
     145                 :            : #endif /* GCC_SHORTEST_PATHS_H */

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.