File: dag_shortest_paths.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (159 lines) | stat: -rw-r--r-- 6,210 bytes parent folder | download | duplicates (14)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//=======================================================================
// Copyright 2002 Indiana University.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#ifndef BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP
#define BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP

#include <boost/graph/topological_sort.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

// single-source shortest paths for a Directed Acyclic Graph (DAG)

namespace boost {

  // Initalize distances and call depth first search
  template <class VertexListGraph, class DijkstraVisitor, 
            class DistanceMap, class WeightMap, class ColorMap, 
            class PredecessorMap,
            class Compare, class Combine, 
            class DistInf, class DistZero>
  inline void
  dag_shortest_paths
    (const VertexListGraph& g,
     typename graph_traits<VertexListGraph>::vertex_descriptor s, 
     DistanceMap distance, WeightMap weight, ColorMap color,
     PredecessorMap pred,
     DijkstraVisitor vis, Compare compare, Combine combine, 
     DistInf inf, DistZero zero)
  {
    typedef typename graph_traits<VertexListGraph>::vertex_descriptor Vertex;
    std::vector<Vertex> rev_topo_order;
    rev_topo_order.reserve(num_vertices(g));

    // Call 'depth_first_visit', not 'topological_sort', because we don't
    // want to traverse the entire graph, only vertices reachable from 's',
    // and 'topological_sort' will traverse everything. The logic below
    // is the same as for 'topological_sort', only we call 'depth_first_visit'
    // and 'topological_sort' calls 'depth_first_search'.
    topo_sort_visitor<std::back_insert_iterator<std::vector<Vertex> > >
        topo_visitor(std::back_inserter(rev_topo_order));
    depth_first_visit(g, s, topo_visitor, color);

    typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
    for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
      put(distance, *ui, inf);
      put(pred, *ui, *ui);
    }

    put(distance, s, zero);
    vis.discover_vertex(s, g);
    typename std::vector<Vertex>::reverse_iterator i;
    for (i = rev_topo_order.rbegin(); i != rev_topo_order.rend(); ++i) {
      Vertex u = *i;
      vis.examine_vertex(u, g);
      typename graph_traits<VertexListGraph>::out_edge_iterator e, e_end;
      for (boost::tie(e, e_end) = out_edges(u, g); e != e_end; ++e) {
        vis.discover_vertex(target(*e, g), g);
        bool decreased = relax(*e, g, weight, pred, distance, 
                               combine, compare);
        if (decreased)
          vis.edge_relaxed(*e, g);
        else
          vis.edge_not_relaxed(*e, g);
      }
      vis.finish_vertex(u, g);      
    }
  }

  namespace detail {

    // Defaults are the same as Dijkstra's algorithm

    // Handle Distance Compare, Combine, Inf and Zero defaults
    template <class VertexListGraph, class DijkstraVisitor, 
      class DistanceMap, class WeightMap, class ColorMap, 
      class IndexMap, class Params>
    inline void
    dag_sp_dispatch2
      (const VertexListGraph& g,
       typename graph_traits<VertexListGraph>::vertex_descriptor s, 
       DistanceMap distance, WeightMap weight, ColorMap color, IndexMap /*id*/,
       DijkstraVisitor vis, const Params& params)
    {
      typedef typename property_traits<DistanceMap>::value_type D;
      dummy_property_map p_map;
      D inf =
        choose_param(get_param(params, distance_inf_t()), 
                     (std::numeric_limits<D>::max)());
      dag_shortest_paths
        (g, s, distance, weight, color, 
         choose_param(get_param(params, vertex_predecessor), p_map),
         vis, 
         choose_param(get_param(params, distance_compare_t()), std::less<D>()),
         choose_param(get_param(params, distance_combine_t()), closed_plus<D>(inf)),
         inf,
         choose_param(get_param(params, distance_zero_t()), 
                      D()));
    }

    // Handle DistanceMap and ColorMap defaults
    template <class VertexListGraph, class DijkstraVisitor, 
              class DistanceMap, class WeightMap, class ColorMap,
              class IndexMap, class Params>
    inline void
    dag_sp_dispatch1
      (const VertexListGraph& g,
       typename graph_traits<VertexListGraph>::vertex_descriptor s, 
       DistanceMap distance, WeightMap weight, ColorMap color, IndexMap id,
       DijkstraVisitor vis, const Params& params)
    {
      typedef typename property_traits<WeightMap>::value_type T;
      typename std::vector<T>::size_type n;
      n = is_default_param(distance) ? num_vertices(g) : 1;
      std::vector<T> distance_map(n);
      n = is_default_param(color) ? num_vertices(g) : 1;
      std::vector<default_color_type> color_map(n);

      dag_sp_dispatch2
        (g, s, 
         choose_param(distance, 
                      make_iterator_property_map(distance_map.begin(), id,
                                                 distance_map[0])),
         weight, 
         choose_param(color,
                      make_iterator_property_map(color_map.begin(), id, 
                                                 color_map[0])),
         id, vis, params);
    }
    
  } // namespace detail 
  
  template <class VertexListGraph, class Param, class Tag, class Rest>
  inline void
  dag_shortest_paths
    (const VertexListGraph& g,
     typename graph_traits<VertexListGraph>::vertex_descriptor s,
     const bgl_named_params<Param,Tag,Rest>& params)
  {
    // assert that the graph is directed...
    null_visitor null_vis;
    detail::dag_sp_dispatch1
      (g, s, 
       get_param(params, vertex_distance),
       choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
       get_param(params, vertex_color),
       choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
       choose_param(get_param(params, graph_visitor),
                    make_dijkstra_visitor(null_vis)),
       params);
  }
  
} // namespace boost

#endif // BOOST_GRAPH_DAG_SHORTEST_PATHS_HPP