ceph/src/boost/boost/graph/johnson_all_pairs_shortest.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 /*
  11   This file implements the function
  12
  13   template <class VertexAndEdgeListGraph, class DistanceMatrix,
  14             class P, class T, class R>
  15   bool
  16   johnson_all_pairs_shortest_paths
  17     (VertexAndEdgeListGraph& g,
  18      DistanceMatrix& D,
  19      const bgl_named_params<P, T, R>& params)
  20  */
  21
  22 #ifndef BOOST_GRAPH_JOHNSON_HPP
  23 #define BOOST_GRAPH_JOHNSON_HPP
  24
  25 #include <boost/graph/graph_traits.hpp>
  26 #include <boost/property_map/property_map.hpp>
  27 #include <boost/property_map/shared_array_property_map.hpp>
  28 #include <boost/graph/bellman_ford_shortest_paths.hpp>
  29 #include <boost/graph/dijkstra_shortest_paths.hpp>
  30 #include <boost/graph/adjacency_list.hpp>
  31 #include <boost/type_traits/same_traits.hpp>
  32 #include <boost/concept/assert.hpp>
  33
  34 namespace boost
  35 {
  36
  37 template < class VertexAndEdgeListGraph, class DistanceMatrix, class VertexID,
  38     class Weight, typename BinaryPredicate, typename BinaryFunction,
  39     typename Infinity, class DistanceZero >
  40 bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g1,
  41     DistanceMatrix& D, VertexID id1, Weight w1, const BinaryPredicate& compare,
  42     const BinaryFunction& combine, const Infinity& inf, DistanceZero zero)
  43 {
  44     typedef graph_traits< VertexAndEdgeListGraph > Traits1;
  45     typedef typename property_traits< Weight >::value_type DT;
  46     BOOST_CONCEPT_ASSERT((BasicMatrixConcept< DistanceMatrix,
  47         typename Traits1::vertices_size_type, DT >));
  48
  49     typedef typename Traits1::directed_category DirCat;
  50     bool is_undirected = is_same< DirCat, undirected_tag >::value;
  51
  52     typedef adjacency_list< vecS, vecS, directedS,
  53         property< vertex_distance_t, DT >,
  54         property< edge_weight_t, DT, property< edge_weight2_t, DT > > >
  55         Graph2;
  56     typedef graph_traits< Graph2 > Traits2;
  57
  58     Graph2 g2(num_vertices(g1) + 1);
  59     typename property_map< Graph2, edge_weight_t >::type w
  60         = get(edge_weight, g2);
  61     typename property_map< Graph2, edge_weight2_t >::type w_hat
  62         = get(edge_weight2, g2);
  63     typename property_map< Graph2, vertex_distance_t >::type d
  64         = get(vertex_distance, g2);
  65     typedef typename property_map< Graph2, vertex_index_t >::type VertexID2;
  66     VertexID2 id2 = get(vertex_index, g2);
  67
  68     // Construct g2 where V[g2] = V[g1] U {s}
  69     //   and  E[g2] = E[g1] U {(s,v)| v in V[g1]}
  70     std::vector< typename Traits1::vertex_descriptor > verts1(
  71         num_vertices(g1) + 1);
  72     typename Traits2::vertex_descriptor s = *vertices(g2).first;
  73     {
  74         typename Traits1::vertex_iterator v, v_end;
  75         int i = 1;
  76         for (boost::tie(v, v_end) = vertices(g1); v != v_end; ++v, ++i)
  77         {
  78             typename Traits2::edge_descriptor e;
  79             bool z;
  80             boost::tie(e, z) = add_edge(s, get(id1, *v) + 1, g2);
  81             put(w, e, zero);
  82             verts1[i] = *v;
  83         }
  84         typename Traits1::edge_iterator e, e_end;
  85         for (boost::tie(e, e_end) = edges(g1); e != e_end; ++e)
  86         {
  87             typename Traits2::edge_descriptor e2;
  88             bool z;
  89             boost::tie(e2, z) = add_edge(
  90                 get(id1, source(*e, g1)) + 1, get(id1, target(*e, g1)) + 1, g2);
  91             put(w, e2, get(w1, *e));
  92             if (is_undirected)
  93             {
  94                 boost::tie(e2, z) = add_edge(get(id1, target(*e, g1)) + 1,
  95                     get(id1, source(*e, g1)) + 1, g2);
  96                 put(w, e2, get(w1, *e));
  97             }
  98         }
  99     }
 100     typename Traits2::vertex_iterator v, v_end, u, u_end;
 101     typename Traits2::edge_iterator e, e_end;
 102     shared_array_property_map< DT, VertexID2 > h(num_vertices(g2), id2);
 103
 104     for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v)
 105         put(d, *v, inf);
 106
 107     put(d, s, zero);
 108     // Using the non-named parameter versions of bellman_ford and
 109     // dijkstra for portability reasons.
 110     dummy_property_map pred;
 111     bellman_visitor<> bvis;
 112     if (bellman_ford_shortest_paths(
 113             g2, num_vertices(g2), w, pred, d, combine, compare, bvis))
 114     {
 115         for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v)
 116             put(h, *v, get(d, *v));
 117         // Reweight the edges to remove negatives
 118         for (boost::tie(e, e_end) = edges(g2); e != e_end; ++e)
 119         {
 120             typename Traits2::vertex_descriptor a = source(*e, g2),
 121                                                 b = target(*e, g2);
 122             put(w_hat, *e, combine((get(h, a) - get(h, b)), get(w, *e)));
 123         }
 124         for (boost::tie(u, u_end) = vertices(g2); u != u_end; ++u)
 125         {
 126             dijkstra_visitor<> dvis;
 127             dijkstra_shortest_paths(
 128                 g2, *u, pred, d, w_hat, id2, compare, combine, inf, zero, dvis);
 129             for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v)
 130             {
 131                 if (*u != s && *v != s)
 132                 {
 133                     D[get(id2, *u) - 1][get(id2, *v) - 1]
 134                         = combine((get(h, *v) - get(h, *u)), get(d, *v));
 135                 }
 136             }
 137         }
 138         return true;
 139     }
 140     else
 141         return false;
 142 }
 143
 144 template < class VertexAndEdgeListGraph, class DistanceMatrix, class VertexID,
 145     class Weight, class DistanceZero >
 146 bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g1,
 147     DistanceMatrix& D, VertexID id1, Weight w1, DistanceZero zero)
 148 {
 149     typedef typename property_traits< Weight >::value_type WT;
 150     return johnson_all_pairs_shortest_paths(g1, D, id1, w1, std::less< WT >(),
 151         closed_plus< WT >(), (std::numeric_limits< WT >::max)(), zero);
 152 }
 153
 154 namespace detail
 155 {
 156
 157     template < class VertexAndEdgeListGraph, class DistanceMatrix, class P,
 158         class T, class R, class Weight, class VertexID >
 159     bool johnson_dispatch(VertexAndEdgeListGraph& g, DistanceMatrix& D,
 160         const bgl_named_params< P, T, R >& params, Weight w, VertexID id)
 161     {
 162         typedef typename property_traits< Weight >::value_type WT;
 163
 164         return johnson_all_pairs_shortest_paths(g, D, id, w,
 165             choose_param(
 166                 get_param(params, distance_compare_t()), std::less< WT >()),
 167             choose_param(
 168                 get_param(params, distance_combine_t()), closed_plus< WT >()),
 169             choose_param(get_param(params, distance_inf_t()),
 170                 std::numeric_limits< WT >::max
 171                     BOOST_PREVENT_MACRO_SUBSTITUTION()),
 172             choose_param(get_param(params, distance_zero_t()), WT()));
 173     }
 174
 175 } // namespace detail
 176
 177 template < class VertexAndEdgeListGraph, class DistanceMatrix, class P, class T,
 178     class R >
 179 bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g,
 180     DistanceMatrix& D, const bgl_named_params< P, T, R >& params)
 181 {
 182     return detail::johnson_dispatch(g, D, params,
 183         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
 184         choose_const_pmap(get_param(params, vertex_index), g, vertex_index));
 185 }
 186
 187 template < class VertexAndEdgeListGraph, class DistanceMatrix >
 188 bool johnson_all_pairs_shortest_paths(
 189     VertexAndEdgeListGraph& g, DistanceMatrix& D)
 190 {
 191     bgl_named_params< int, int > params(1);
 192     return detail::johnson_dispatch(
 193         g, D, params, get(edge_weight, g), get(vertex_index, g));
 194 }
 195
 196 } // namespace boost
 197
 198 #endif // BOOST_GRAPH_JOHNSON_HPP