1 // 2 //======================================================================= 3 // Copyright 2007 Stanford University 4 // Authors: David Gleich 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 // 11 #ifndef BOOST_GRAPH_CORE_NUMBERS_HPP 12 #define BOOST_GRAPH_CORE_NUMBERS_HPP 13 14 #include <boost/graph/detail/d_ary_heap.hpp> 15 #include <boost/graph/breadth_first_search.hpp> 16 #include <boost/iterator/reverse_iterator.hpp> 17 #include <boost/concept/assert.hpp> 18 19 /* 20 * core_numbers 21 * 22 * Requirement: IncidenceGraph 23 */ 24 25 // History 26 // 27 // 30 July 2007 28 // Added visitors to the implementation 29 // 30 // 8 February 2008 31 // Fixed headers and missing typename 32 33 namespace boost { 34 35 // A linear time O(m) algorithm to compute the indegree core number 36 // of a graph for unweighted graphs. 37 // 38 // and a O((n+m) log n) algorithm to compute the in-edge-weight core 39 // numbers of a weighted graph. 40 // 41 // The linear algorithm comes from: 42 // Vladimir Batagelj and Matjaz Zaversnik, "An O(m) Algorithm for Cores 43 // Decomposition of Networks." Sept. 1 2002. 44 45 template <typename Visitor, typename Graph> 46 struct CoreNumbersVisitorConcept { constraintsboost::CoreNumbersVisitorConcept47 void constraints() 48 { 49 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> )); 50 vis.examine_vertex(u,g); 51 vis.finish_vertex(u,g); 52 vis.examine_edge(e,g); 53 } 54 Visitor vis; 55 Graph g; 56 typename graph_traits<Graph>::vertex_descriptor u; 57 typename graph_traits<Graph>::edge_descriptor e; 58 }; 59 60 template <class Visitors = null_visitor> 61 class core_numbers_visitor : public bfs_visitor<Visitors> { 62 public: core_numbers_visitor()63 core_numbers_visitor() {} core_numbers_visitor(Visitors vis)64 core_numbers_visitor(Visitors vis) 65 : bfs_visitor<Visitors>(vis) {} 66 67 private: 68 template <class Vertex, class Graph> initialize_vertex(Vertex,Graph &)69 void initialize_vertex(Vertex, Graph&) {} 70 71 template <class Vertex, class Graph> discover_vertex(Vertex,Graph &)72 void discover_vertex(Vertex , Graph&) {} 73 74 template <class Vertex, class Graph> gray_target(Vertex,Graph &)75 void gray_target(Vertex, Graph&) {} 76 77 template <class Vertex, class Graph> black_target(Vertex,Graph &)78 void black_target(Vertex, Graph&) {} 79 80 template <class Edge, class Graph> tree_edge(Edge,Graph &)81 void tree_edge(Edge, Graph&) {} 82 83 template <class Edge, class Graph> non_tree_edge(Edge,Graph &)84 void non_tree_edge(Edge, Graph&) {} 85 }; 86 87 template <class Visitors> make_core_numbers_visitor(Visitors vis)88 core_numbers_visitor<Visitors> make_core_numbers_visitor(Visitors vis) 89 { return core_numbers_visitor<Visitors>(vis); } 90 91 typedef core_numbers_visitor<> default_core_numbers_visitor; 92 93 namespace detail { 94 95 // implement a constant_property_map to simplify compute_in_degree 96 // for the weighted and unweighted case 97 // this is based on dummy property map 98 template <typename ValueType> 99 class constant_value_property_map 100 : public boost::put_get_helper<ValueType, 101 constant_value_property_map<ValueType> > 102 { 103 public: 104 typedef void key_type; 105 typedef ValueType value_type; 106 typedef const ValueType& reference; 107 typedef boost::readable_property_map_tag category; constant_value_property_map(ValueType cc)108 inline constant_value_property_map(ValueType cc) : c(cc) { } constant_value_property_map(const constant_value_property_map<ValueType> & x)109 inline constant_value_property_map(const constant_value_property_map<ValueType>& x) 110 : c(x.c) { } 111 template <class Vertex> operator [](Vertex) const112 inline reference operator[](Vertex) const { return c; } 113 protected: 114 ValueType c; 115 }; 116 117 118 // the core numbers start as the indegree or inweight. This function 119 // will initialize these values 120 template <typename Graph, typename CoreMap, typename EdgeWeightMap> compute_in_degree_map(Graph & g,CoreMap d,EdgeWeightMap wm)121 void compute_in_degree_map(Graph& g, CoreMap d, EdgeWeightMap wm) 122 { 123 typename graph_traits<Graph>::vertex_iterator vi,vi_end; 124 typename graph_traits<Graph>::out_edge_iterator ei,ei_end; 125 for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) { 126 put(d,*vi,0); 127 } 128 for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) { 129 for (boost::tie(ei,ei_end) = out_edges(*vi,g); ei!=ei_end; ++ei) { 130 put(d,target(*ei,g),get(d,target(*ei,g))+get(wm,*ei)); 131 } 132 } 133 } 134 135 // the version for weighted graphs is a little different 136 template <typename Graph, typename CoreMap, 137 typename EdgeWeightMap, typename MutableQueue, 138 typename Visitor> 139 typename property_traits<CoreMap>::value_type core_numbers_impl(Graph & g,CoreMap c,EdgeWeightMap wm,MutableQueue & Q,Visitor vis)140 core_numbers_impl(Graph& g, CoreMap c, EdgeWeightMap wm, 141 MutableQueue& Q, Visitor vis) 142 { 143 typename property_traits<CoreMap>::value_type v_cn = 0; 144 typedef typename graph_traits<Graph>::vertex_descriptor vertex; 145 while (!Q.empty()) 146 { 147 // remove v from the Q, and then decrease the core numbers 148 // of its successors 149 vertex v = Q.top(); 150 vis.examine_vertex(v,g); 151 Q.pop(); 152 v_cn = get(c,v); 153 typename graph_traits<Graph>::out_edge_iterator oi,oi_end; 154 for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) { 155 vis.examine_edge(*oi,g); 156 vertex u = target(*oi,g); 157 // if c[u] > c[v], then u is still in the graph, 158 if (get(c,u) > v_cn) { 159 // remove the edge 160 put(c,u,get(c,u)-get(wm,*oi)); 161 if (Q.contains(u)) 162 Q.update(u); 163 } 164 } 165 vis.finish_vertex(v,g); 166 } 167 return (v_cn); 168 } 169 170 template <typename Graph, typename CoreMap, typename EdgeWeightMap, 171 typename IndexMap, typename CoreNumVisitor> 172 typename property_traits<CoreMap>::value_type core_numbers_dispatch(Graph & g,CoreMap c,EdgeWeightMap wm,IndexMap im,CoreNumVisitor vis)173 core_numbers_dispatch(Graph&g, CoreMap c, EdgeWeightMap wm, 174 IndexMap im, CoreNumVisitor vis) 175 { 176 typedef typename property_traits<CoreMap>::value_type D; 177 typedef std::less<D> Cmp; 178 // build the mutable queue 179 typedef typename graph_traits<Graph>::vertex_descriptor vertex; 180 std::vector<std::size_t> index_in_heap_data(num_vertices(g)); 181 typedef iterator_property_map<std::vector<std::size_t>::iterator, IndexMap> 182 index_in_heap_map_type; 183 index_in_heap_map_type index_in_heap_map(index_in_heap_data.begin(), im); 184 typedef d_ary_heap_indirect<vertex, 4, index_in_heap_map_type, CoreMap, Cmp> MutableQueue; 185 MutableQueue Q(c, index_in_heap_map, Cmp()); 186 typename graph_traits<Graph>::vertex_iterator vi,vi_end; 187 for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) { 188 Q.push(*vi); 189 } 190 return core_numbers_impl(g, c, wm, Q, vis); 191 } 192 193 // the version for the unweighted case 194 // for this functions CoreMap must be initialized 195 // with the in degree of each vertex 196 template <typename Graph, typename CoreMap, typename PositionMap, 197 typename Visitor> 198 typename property_traits<CoreMap>::value_type core_numbers_impl(Graph & g,CoreMap c,PositionMap pos,Visitor vis)199 core_numbers_impl(Graph& g, CoreMap c, PositionMap pos, Visitor vis) 200 { 201 typedef typename graph_traits<Graph>::vertices_size_type size_type; 202 typedef typename graph_traits<Graph>::degree_size_type degree_type; 203 typedef typename graph_traits<Graph>::vertex_descriptor vertex; 204 typename graph_traits<Graph>::vertex_iterator vi,vi_end; 205 206 // store the vertex core numbers 207 typename property_traits<CoreMap>::value_type v_cn = 0; 208 209 // compute the maximum degree (degrees are in the coremap) 210 typename graph_traits<Graph>::degree_size_type max_deg = 0; 211 for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) { 212 max_deg = (std::max<typename graph_traits<Graph>::degree_size_type>)(max_deg, get(c,*vi)); 213 } 214 215 // store the vertices in bins by their degree 216 // allocate two extra locations to ease boundary cases 217 std::vector<size_type> bin(max_deg+2); 218 for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) { 219 ++bin[get(c,*vi)]; 220 } 221 222 // this loop sets bin[d] to the starting position of vertices 223 // with degree d in the vert array for the bucket sort 224 size_type cur_pos = 0; 225 for (degree_type cur_deg = 0; cur_deg < max_deg+2; ++cur_deg) { 226 degree_type tmp = bin[cur_deg]; 227 bin[cur_deg] = cur_pos; 228 cur_pos += tmp; 229 } 230 231 // perform the bucket sort with pos and vert so that 232 // pos[0] is the vertex of smallest degree 233 std::vector<vertex> vert(num_vertices(g)); 234 for (boost::tie(vi,vi_end) = vertices(g); vi!=vi_end; ++vi) { 235 vertex v=*vi; 236 size_type p=bin[get(c,v)]; 237 put(pos,v,p); 238 vert[p]=v; 239 ++bin[get(c,v)]; 240 } 241 // we ``abused'' bin while placing the vertices, now, 242 // we need to restore it 243 std::copy(boost::make_reverse_iterator(bin.end()-2), 244 boost::make_reverse_iterator(bin.begin()), 245 boost::make_reverse_iterator(bin.end()-1)); 246 // now simulate removing the vertices 247 for (size_type i=0; i < num_vertices(g); ++i) { 248 vertex v = vert[i]; 249 vis.examine_vertex(v,g); 250 v_cn = get(c,v); 251 typename graph_traits<Graph>::out_edge_iterator oi,oi_end; 252 for (boost::tie(oi,oi_end) = out_edges(v,g); oi!=oi_end; ++oi) { 253 vis.examine_edge(*oi,g); 254 vertex u = target(*oi,g); 255 // if c[u] > c[v], then u is still in the graph, 256 if (get(c,u) > v_cn) { 257 degree_type deg_u = get(c,u); 258 degree_type pos_u = get(pos,u); 259 // w is the first vertex with the same degree as u 260 // (this is the resort operation!) 261 degree_type pos_w = bin[deg_u]; 262 vertex w = vert[pos_w]; 263 if (u!=v) { 264 // swap u and w 265 put(pos,u,pos_w); 266 put(pos,w,pos_u); 267 vert[pos_w] = u; 268 vert[pos_u] = w; 269 } 270 // now, the vertices array is sorted assuming 271 // we perform the following step 272 // start the set of vertices with degree of u 273 // one into the future (this now points at vertex 274 // w which we swapped with u). 275 ++bin[deg_u]; 276 // we are removing v from the graph, so u's degree 277 // decreases 278 put(c,u,get(c,u)-1); 279 } 280 } 281 vis.finish_vertex(v,g); 282 } 283 return v_cn; 284 } 285 286 } // namespace detail 287 288 // non-named parameter version for the unweighted case 289 template <typename Graph, typename CoreMap, typename CoreNumVisitor> 290 typename property_traits<CoreMap>::value_type core_numbers(Graph & g,CoreMap c,CoreNumVisitor vis)291 core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis) 292 { 293 typedef typename graph_traits<Graph>::vertices_size_type size_type; 294 detail::compute_in_degree_map(g,c, 295 detail::constant_value_property_map< 296 typename property_traits<CoreMap>::value_type>(1) ); 297 return detail::core_numbers_impl(g,c, 298 make_iterator_property_map( 299 std::vector<size_type>(num_vertices(g)).begin(),get(vertex_index, g)), 300 vis 301 ); 302 } 303 304 // non-named paramter version for the unweighted case 305 template <typename Graph, typename CoreMap> 306 typename property_traits<CoreMap>::value_type core_numbers(Graph & g,CoreMap c)307 core_numbers(Graph& g, CoreMap c) 308 { 309 return core_numbers(g, c, make_core_numbers_visitor(null_visitor())); 310 } 311 312 // non-named parameter version for the weighted case 313 template <typename Graph, typename CoreMap, typename EdgeWeightMap, 314 typename VertexIndexMap, typename CoreNumVisitor> 315 typename property_traits<CoreMap>::value_type core_numbers(Graph & g,CoreMap c,EdgeWeightMap wm,VertexIndexMap vim,CoreNumVisitor vis)316 core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm, VertexIndexMap vim, 317 CoreNumVisitor vis) 318 { 319 detail::compute_in_degree_map(g,c,wm); 320 return detail::core_numbers_dispatch(g,c,wm,vim,vis); 321 } 322 323 // non-named parameter version for the weighted case 324 // template <typename Graph, typename CoreMap, typename EdgeWeightMap> 325 // typename property_traits<CoreMap>::value_type 326 // core_numbers(Graph& g, CoreMap c, EdgeWeightMap wm) 327 // { 328 // typedef typename graph_traits<Graph>::vertices_size_type size_type; 329 // detail::compute_in_degree_map(g,c,wm); 330 // return detail::core_numbers_dispatch(g,c,wm,get(vertex_index,g), 331 // make_core_numbers_visitor(null_visitor())); 332 // } 333 334 template <typename Graph, typename CoreMap> 335 typename property_traits<CoreMap>::value_type weighted_core_numbers(Graph & g,CoreMap c)336 weighted_core_numbers(Graph& g, CoreMap c) 337 { 338 return weighted_core_numbers( 339 g,c, make_core_numbers_visitor(null_visitor()) 340 ); 341 } 342 343 template <typename Graph, typename CoreMap, typename CoreNumVisitor> 344 typename property_traits<CoreMap>::value_type weighted_core_numbers(Graph & g,CoreMap c,CoreNumVisitor vis)345 weighted_core_numbers(Graph& g, CoreMap c, CoreNumVisitor vis) 346 { return core_numbers(g,c,get(edge_weight,g),get(vertex_index,g),vis); } 347 348 } // namespace boost 349 350 #endif // BOOST_GRAPH_CORE_NUMBERS_HPP 351 352