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 template <class VertexAndEdgeListGraph, class DistanceMatrix, 37 class VertexID, class Weight, typename BinaryPredicate, 38 typename BinaryFunction, typename Infinity, class DistanceZero> 39 bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph & g1,DistanceMatrix & D,VertexID id1,Weight w1,const BinaryPredicate & compare,const BinaryFunction & combine,const Infinity & inf,DistanceZero zero)40 johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g1, 41 DistanceMatrix& D, 42 VertexID id1, Weight w1, const BinaryPredicate& compare, 43 const BinaryFunction& combine, const Infinity& inf, 44 DistanceZero zero) 45 { 46 typedef graph_traits<VertexAndEdgeListGraph> Traits1; 47 typedef typename property_traits<Weight>::value_type DT; 48 BOOST_CONCEPT_ASSERT(( BasicMatrixConcept<DistanceMatrix, 49 typename Traits1::vertices_size_type, DT> )); 50 51 typedef typename Traits1::directed_category DirCat; 52 bool is_undirected = is_same<DirCat, undirected_tag>::value; 53 54 typedef adjacency_list<vecS, vecS, directedS, 55 property< vertex_distance_t, DT>, 56 property< edge_weight_t, DT, 57 property< edge_weight2_t, DT > > > Graph2; 58 typedef graph_traits<Graph2> Traits2; 59 60 Graph2 g2(num_vertices(g1) + 1); 61 typename property_map<Graph2, edge_weight_t>::type 62 w = get(edge_weight, g2); 63 typename property_map<Graph2, edge_weight2_t>::type 64 w_hat = get(edge_weight2, g2); 65 typename property_map<Graph2, vertex_distance_t>::type 66 d = get(vertex_distance, g2); 67 typedef typename property_map<Graph2, vertex_index_t>::type VertexID2; 68 VertexID2 id2 = get(vertex_index, g2); 69 70 // Construct g2 where V[g2] = V[g1] U {s} 71 // and E[g2] = E[g1] U {(s,v)| v in V[g1]} 72 std::vector<typename Traits1::vertex_descriptor> 73 verts1(num_vertices(g1) + 1); 74 typename Traits2::vertex_descriptor s = *vertices(g2).first; 75 { 76 typename Traits1::vertex_iterator v, v_end; 77 int i = 1; 78 for (boost::tie(v, v_end) = vertices(g1); v != v_end; ++v, ++i) { 79 typename Traits2::edge_descriptor e; 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 typename Traits2::edge_descriptor e2; bool z; 87 boost::tie(e2, z) = add_edge(get(id1, source(*e, g1)) + 1, 88 get(id1, target(*e, g1)) + 1, g2); 89 put(w, e2, get(w1, *e)); 90 if (is_undirected) { 91 boost::tie(e2, z) = add_edge(get(id1, target(*e, g1)) + 1, 92 get(id1, source(*e, g1)) + 1, g2); 93 put(w, e2, get(w1, *e)); 94 } 95 } 96 } 97 typename Traits2::vertex_iterator v, v_end, u, u_end; 98 typename Traits2::edge_iterator e, e_end; 99 shared_array_property_map<DT,VertexID2> h(num_vertices(g2), id2); 100 101 for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) 102 put(d, *v, inf); 103 104 put(d, s, zero); 105 // Using the non-named parameter versions of bellman_ford and 106 // dijkstra for portability reasons. 107 dummy_property_map pred; bellman_visitor<> bvis; 108 if (bellman_ford_shortest_paths 109 (g2, num_vertices(g2), w, pred, d, combine, compare, bvis)) { 110 for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) 111 put(h, *v, get(d, *v)); 112 // Reweight the edges to remove negatives 113 for (boost::tie(e, e_end) = edges(g2); e != e_end; ++e) { 114 typename Traits2::vertex_descriptor a = source(*e, g2), 115 b = target(*e, g2); 116 put(w_hat, *e, combine((get(h, a) - get(h, b)), get(w, *e))); 117 } 118 for (boost::tie(u, u_end) = vertices(g2); u != u_end; ++u) { 119 dijkstra_visitor<> dvis; 120 dijkstra_shortest_paths 121 (g2, *u, pred, d, w_hat, id2, compare, combine, inf, zero,dvis); 122 for (boost::tie(v, v_end) = vertices(g2); v != v_end; ++v) { 123 if (*u != s && *v != s) { 124 D[get(id2, *u)-1][get(id2, *v)-1] = combine((get(h, *v) - get(h, *u)), get(d, *v)); 125 } 126 } 127 } 128 return true; 129 } else 130 return false; 131 } 132 133 template <class VertexAndEdgeListGraph, class DistanceMatrix, 134 class VertexID, class Weight, class DistanceZero> 135 bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph & g1,DistanceMatrix & D,VertexID id1,Weight w1,DistanceZero zero)136 johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph& g1, 137 DistanceMatrix& D, 138 VertexID id1, Weight w1, DistanceZero zero) 139 { 140 typedef typename property_traits<Weight>::value_type WT; 141 return johnson_all_pairs_shortest_paths(g1, D, id1, w1, 142 std::less<WT>(), 143 closed_plus<WT>(), 144 (std::numeric_limits<WT>::max)(), 145 zero); 146 } 147 148 namespace detail { 149 150 template <class VertexAndEdgeListGraph, class DistanceMatrix, 151 class P, class T, class R, class Weight, 152 class VertexID> 153 bool johnson_dispatch(VertexAndEdgeListGraph & g,DistanceMatrix & D,const bgl_named_params<P,T,R> & params,Weight w,VertexID id)154 johnson_dispatch(VertexAndEdgeListGraph& g, 155 DistanceMatrix& D, 156 const bgl_named_params<P, T, R>& params, 157 Weight w, VertexID id) 158 { 159 typedef typename property_traits<Weight>::value_type WT; 160 161 return johnson_all_pairs_shortest_paths 162 (g, D, id, w, 163 choose_param(get_param(params, distance_compare_t()), 164 std::less<WT>()), 165 choose_param(get_param(params, distance_combine_t()), 166 closed_plus<WT>()), 167 choose_param(get_param(params, distance_inf_t()), 168 std::numeric_limits<WT>::max BOOST_PREVENT_MACRO_SUBSTITUTION()), 169 choose_param(get_param(params, distance_zero_t()), WT()) ); 170 } 171 172 } // namespace detail 173 174 template <class VertexAndEdgeListGraph, class DistanceMatrix, 175 class P, class T, class R> 176 bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph & g,DistanceMatrix & D,const bgl_named_params<P,T,R> & params)177 johnson_all_pairs_shortest_paths 178 (VertexAndEdgeListGraph& g, 179 DistanceMatrix& D, 180 const bgl_named_params<P, T, R>& params) 181 { 182 return detail::johnson_dispatch 183 (g, D, params, 184 choose_const_pmap(get_param(params, edge_weight), g, edge_weight), 185 choose_const_pmap(get_param(params, vertex_index), g, vertex_index) 186 ); 187 } 188 189 template <class VertexAndEdgeListGraph, class DistanceMatrix> 190 bool johnson_all_pairs_shortest_paths(VertexAndEdgeListGraph & g,DistanceMatrix & D)191 johnson_all_pairs_shortest_paths 192 (VertexAndEdgeListGraph& g, DistanceMatrix& D) 193 { 194 bgl_named_params<int,int> params(1); 195 return detail::johnson_dispatch 196 (g, D, params, get(edge_weight, g), get(vertex_index, g)); 197 } 198 199 } // namespace boost 200 201 #endif // BOOST_GRAPH_JOHNSON_HPP 202 203 204