Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:37:23 

0001 // Copyright 2004 The Trustees of Indiana University.
0002 
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006 
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
0010 #define BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
0011 
0012 #include <stack>
0013 #include <vector>
0014 #include <boost/graph/overloading.hpp>
0015 #include <boost/graph/dijkstra_shortest_paths.hpp>
0016 #include <boost/graph/breadth_first_search.hpp>
0017 #include <boost/graph/relax.hpp>
0018 #include <boost/graph/graph_traits.hpp>
0019 #include <boost/tuple/tuple.hpp>
0020 #include <boost/type_traits/is_convertible.hpp>
0021 #include <boost/type_traits/is_same.hpp>
0022 #include <boost/mpl/if.hpp>
0023 #include <boost/property_map/property_map.hpp>
0024 #include <boost/graph/named_function_params.hpp>
0025 #include <algorithm>
0026 
0027 namespace boost
0028 {
0029 
0030 namespace detail
0031 {
0032     namespace graph
0033     {
0034 
0035         /**
0036          * Customized visitor passed to Dijkstra's algorithm by Brandes'
0037          * betweenness centrality algorithm. This visitor is responsible for
0038          * keeping track of the order in which vertices are discovered, the
0039          * predecessors on the shortest path(s) to a vertex, and the number
0040          * of shortest paths.
0041          */
0042         template < typename Graph, typename WeightMap, typename IncomingMap,
0043             typename DistanceMap, typename PathCountMap >
0044         struct brandes_dijkstra_visitor : public bfs_visitor<>
0045         {
0046             typedef typename graph_traits< Graph >::vertex_descriptor
0047                 vertex_descriptor;
0048             typedef
0049                 typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0050 
0051             brandes_dijkstra_visitor(
0052                 std::stack< vertex_descriptor >& ordered_vertices,
0053                 WeightMap weight, IncomingMap incoming, DistanceMap distance,
0054                 PathCountMap path_count)
0055             : ordered_vertices(ordered_vertices)
0056             , weight(weight)
0057             , incoming(incoming)
0058             , distance(distance)
0059             , path_count(path_count)
0060             {
0061             }
0062 
0063             /**
0064              * Whenever an edge e = (v, w) is relaxed, the incoming edge list
0065              * for w is set to {(v, w)} and the shortest path count of w is set
0066              * to the number of paths that reach {v}.
0067              */
0068             void edge_relaxed(edge_descriptor e, const Graph& g)
0069             {
0070                 vertex_descriptor v = source(e, g), w = target(e, g);
0071                 incoming[w].clear();
0072                 incoming[w].push_back(e);
0073                 put(path_count, w, get(path_count, v));
0074             }
0075 
0076             /**
0077              * If an edge e = (v, w) was not relaxed, it may still be the case
0078              * that we've found more equally-short paths, so include {(v, w)} in
0079              * the incoming edges of w and add all of the shortest paths to v to
0080              * the shortest path count of w.
0081              */
0082             void edge_not_relaxed(edge_descriptor e, const Graph& g)
0083             {
0084                 typedef typename property_traits< WeightMap >::value_type
0085                     weight_type;
0086                 typedef typename property_traits< DistanceMap >::value_type
0087                     distance_type;
0088                 vertex_descriptor v = source(e, g), w = target(e, g);
0089                 distance_type d_v = get(distance, v), d_w = get(distance, w);
0090                 weight_type w_e = get(weight, e);
0091 
0092                 closed_plus< distance_type > combine;
0093                 if (d_w == combine(d_v, w_e))
0094                 {
0095                     put(path_count, w, get(path_count, w) + get(path_count, v));
0096                     incoming[w].push_back(e);
0097                 }
0098             }
0099 
0100             /// Keep track of vertices as they are reached
0101             void examine_vertex(vertex_descriptor w, const Graph&)
0102             {
0103                 ordered_vertices.push(w);
0104             }
0105 
0106         private:
0107             std::stack< vertex_descriptor >& ordered_vertices;
0108             WeightMap weight;
0109             IncomingMap incoming;
0110             DistanceMap distance;
0111             PathCountMap path_count;
0112         };
0113 
0114         /**
0115          * Function object that calls Dijkstra's shortest paths algorithm
0116          * using the Dijkstra visitor for the Brandes betweenness centrality
0117          * algorithm.
0118          */
0119         template < typename WeightMap > struct brandes_dijkstra_shortest_paths
0120         {
0121             brandes_dijkstra_shortest_paths(WeightMap weight_map)
0122             : weight_map(weight_map)
0123             {
0124             }
0125 
0126             template < typename Graph, typename IncomingMap,
0127                 typename DistanceMap, typename PathCountMap,
0128                 typename VertexIndexMap >
0129             void operator()(Graph& g,
0130                 typename graph_traits< Graph >::vertex_descriptor s,
0131                 std::stack< typename graph_traits< Graph >::vertex_descriptor >&
0132                     ov,
0133                 IncomingMap incoming, DistanceMap distance,
0134                 PathCountMap path_count, VertexIndexMap vertex_index)
0135             {
0136                 typedef brandes_dijkstra_visitor< Graph, WeightMap, IncomingMap,
0137                     DistanceMap, PathCountMap >
0138                     visitor_type;
0139                 visitor_type visitor(
0140                     ov, weight_map, incoming, distance, path_count);
0141 
0142                 dijkstra_shortest_paths(g, s,
0143                     boost::weight_map(weight_map)
0144                         .vertex_index_map(vertex_index)
0145                         .distance_map(distance)
0146                         .visitor(visitor));
0147             }
0148 
0149         private:
0150             WeightMap weight_map;
0151         };
0152 
0153         /**
0154          * Function object that invokes breadth-first search for the
0155          * unweighted form of the Brandes betweenness centrality algorithm.
0156          */
0157         struct brandes_unweighted_shortest_paths
0158         {
0159             /**
0160              * Customized visitor passed to breadth-first search, which
0161              * records predecessor and the number of shortest paths to each
0162              * vertex.
0163              */
0164             template < typename Graph, typename IncomingMap,
0165                 typename DistanceMap, typename PathCountMap >
0166             struct visitor_type : public bfs_visitor<>
0167             {
0168                 typedef typename graph_traits< Graph >::edge_descriptor
0169                     edge_descriptor;
0170                 typedef typename graph_traits< Graph >::vertex_descriptor
0171                     vertex_descriptor;
0172 
0173                 visitor_type(IncomingMap incoming, DistanceMap distance,
0174                     PathCountMap path_count,
0175                     std::stack< vertex_descriptor >& ordered_vertices)
0176                 : incoming(incoming)
0177                 , distance(distance)
0178                 , path_count(path_count)
0179                 , ordered_vertices(ordered_vertices)
0180                 {
0181                 }
0182 
0183                 /// Keep track of vertices as they are reached
0184                 void examine_vertex(vertex_descriptor v, Graph&)
0185                 {
0186                     ordered_vertices.push(v);
0187                 }
0188 
0189                 /**
0190                  * Whenever an edge e = (v, w) is labelled a tree edge, the
0191                  * incoming edge list for w is set to {(v, w)} and the shortest
0192                  * path count of w is set to the number of paths that reach {v}.
0193                  */
0194                 void tree_edge(edge_descriptor e, Graph& g)
0195                 {
0196                     vertex_descriptor v = source(e, g);
0197                     vertex_descriptor w = target(e, g);
0198                     put(distance, w, get(distance, v) + 1);
0199 
0200                     put(path_count, w, get(path_count, v));
0201                     incoming[w].push_back(e);
0202                 }
0203 
0204                 /**
0205                  * If an edge e = (v, w) is not a tree edge, it may still be the
0206                  * case that we've found more equally-short paths, so include
0207                  * (v, w) in the incoming edge list of w and add all of the
0208                  * shortest paths to v to the shortest path count of w.
0209                  */
0210                 void non_tree_edge(edge_descriptor e, Graph& g)
0211                 {
0212                     vertex_descriptor v = source(e, g);
0213                     vertex_descriptor w = target(e, g);
0214                     if (get(distance, w) == get(distance, v) + 1)
0215                     {
0216                         put(path_count, w,
0217                             get(path_count, w) + get(path_count, v));
0218                         incoming[w].push_back(e);
0219                     }
0220                 }
0221 
0222             private:
0223                 IncomingMap incoming;
0224                 DistanceMap distance;
0225                 PathCountMap path_count;
0226                 std::stack< vertex_descriptor >& ordered_vertices;
0227             };
0228 
0229             template < typename Graph, typename IncomingMap,
0230                 typename DistanceMap, typename PathCountMap,
0231                 typename VertexIndexMap >
0232             void operator()(Graph& g,
0233                 typename graph_traits< Graph >::vertex_descriptor s,
0234                 std::stack< typename graph_traits< Graph >::vertex_descriptor >&
0235                     ov,
0236                 IncomingMap incoming, DistanceMap distance,
0237                 PathCountMap path_count, VertexIndexMap vertex_index)
0238             {
0239                 typedef typename graph_traits< Graph >::vertex_descriptor
0240                     vertex_descriptor;
0241 
0242                 visitor_type< Graph, IncomingMap, DistanceMap, PathCountMap >
0243                     visitor(incoming, distance, path_count, ov);
0244 
0245                 std::vector< default_color_type > colors(num_vertices(g),
0246                     color_traits< default_color_type >::white());
0247                 boost::queue< vertex_descriptor > Q;
0248                 breadth_first_visit(g, s, Q, visitor,
0249                     make_iterator_property_map(colors.begin(), vertex_index));
0250             }
0251         };
0252 
0253         // When the edge centrality map is a dummy property map, no
0254         // initialization is needed.
0255         template < typename Iter >
0256         inline void init_centrality_map(
0257             std::pair< Iter, Iter >, dummy_property_map)
0258         {
0259         }
0260 
0261         // When we have a real edge centrality map, initialize all of the
0262         // centralities to zero.
0263         template < typename Iter, typename Centrality >
0264         void init_centrality_map(
0265             std::pair< Iter, Iter > keys, Centrality centrality_map)
0266         {
0267             typedef typename property_traits< Centrality >::value_type
0268                 centrality_type;
0269             while (keys.first != keys.second)
0270             {
0271                 put(centrality_map, *keys.first, centrality_type(0));
0272                 ++keys.first;
0273             }
0274         }
0275 
0276         // When the edge centrality map is a dummy property map, no update
0277         // is performed.
0278         template < typename Key, typename T >
0279         inline void update_centrality(dummy_property_map, const Key&, const T&)
0280         {
0281         }
0282 
0283         // When we have a real edge centrality map, add the value to the map
0284         template < typename CentralityMap, typename Key, typename T >
0285         inline void update_centrality(
0286             CentralityMap centrality_map, Key k, const T& x)
0287         {
0288             put(centrality_map, k, get(centrality_map, k) + x);
0289         }
0290 
0291         template < typename Iter >
0292         inline void divide_centrality_by_two(
0293             std::pair< Iter, Iter >, dummy_property_map)
0294         {
0295         }
0296 
0297         template < typename Iter, typename CentralityMap >
0298         inline void divide_centrality_by_two(
0299             std::pair< Iter, Iter > keys, CentralityMap centrality_map)
0300         {
0301             typename property_traits< CentralityMap >::value_type two(2);
0302             while (keys.first != keys.second)
0303             {
0304                 put(centrality_map, *keys.first,
0305                     get(centrality_map, *keys.first) / two);
0306                 ++keys.first;
0307             }
0308         }
0309 
0310         template < typename Graph, typename CentralityMap,
0311             typename EdgeCentralityMap, typename IncomingMap,
0312             typename DistanceMap, typename DependencyMap, typename PathCountMap,
0313             typename VertexIndexMap, typename ShortestPaths >
0314         void brandes_betweenness_centrality_impl(const Graph& g,
0315             CentralityMap centrality, // C_B
0316             EdgeCentralityMap edge_centrality_map,
0317             IncomingMap incoming, // P
0318             DistanceMap distance, // d
0319             DependencyMap dependency, // delta
0320             PathCountMap path_count, // sigma
0321             VertexIndexMap vertex_index, ShortestPaths shortest_paths)
0322         {
0323             typedef
0324                 typename graph_traits< Graph >::vertex_iterator vertex_iterator;
0325             typedef typename graph_traits< Graph >::vertex_descriptor
0326                 vertex_descriptor;
0327 
0328             // Initialize centrality
0329             init_centrality_map(vertices(g), centrality);
0330             init_centrality_map(edges(g), edge_centrality_map);
0331 
0332             std::stack< vertex_descriptor > ordered_vertices;
0333             vertex_iterator s, s_end;
0334             for (boost::tie(s, s_end) = vertices(g); s != s_end; ++s)
0335             {
0336                 // Initialize for this iteration
0337                 vertex_iterator w, w_end;
0338                 for (boost::tie(w, w_end) = vertices(g); w != w_end; ++w)
0339                 {
0340                     incoming[*w].clear();
0341                     put(path_count, *w, 0);
0342                     put(dependency, *w, 0);
0343                 }
0344                 put(path_count, *s, 1);
0345 
0346                 // Execute the shortest paths algorithm. This will be either
0347                 // Dijkstra's algorithm or a customized breadth-first search,
0348                 // depending on whether the graph is weighted or unweighted.
0349                 shortest_paths(g, *s, ordered_vertices, incoming, distance,
0350                     path_count, vertex_index);
0351 
0352                 while (!ordered_vertices.empty())
0353                 {
0354                     vertex_descriptor w = ordered_vertices.top();
0355                     ordered_vertices.pop();
0356 
0357                     typedef typename property_traits< IncomingMap >::value_type
0358                         incoming_type;
0359                     typedef typename incoming_type::iterator incoming_iterator;
0360                     typedef
0361                         typename property_traits< DependencyMap >::value_type
0362                             dependency_type;
0363 
0364                     for (incoming_iterator vw = incoming[w].begin();
0365                          vw != incoming[w].end(); ++vw)
0366                     {
0367                         vertex_descriptor v = source(*vw, g);
0368                         dependency_type factor
0369                             = dependency_type(get(path_count, v))
0370                             / dependency_type(get(path_count, w));
0371                         factor *= (dependency_type(1) + get(dependency, w));
0372                         put(dependency, v, get(dependency, v) + factor);
0373                         update_centrality(edge_centrality_map, *vw, factor);
0374                     }
0375 
0376                     if (w != *s)
0377                     {
0378                         update_centrality(centrality, w, get(dependency, w));
0379                     }
0380                 }
0381             }
0382 
0383             typedef typename graph_traits< Graph >::directed_category
0384                 directed_category;
0385             const bool is_undirected
0386                 = is_convertible< directed_category*, undirected_tag* >::value;
0387             if (is_undirected)
0388             {
0389                 divide_centrality_by_two(vertices(g), centrality);
0390                 divide_centrality_by_two(edges(g), edge_centrality_map);
0391             }
0392         }
0393 
0394     }
0395 } // end namespace detail::graph
0396 
0397 template < typename Graph, typename CentralityMap, typename EdgeCentralityMap,
0398     typename IncomingMap, typename DistanceMap, typename DependencyMap,
0399     typename PathCountMap, typename VertexIndexMap >
0400 void brandes_betweenness_centrality(const Graph& g,
0401     CentralityMap centrality, // C_B
0402     EdgeCentralityMap edge_centrality_map,
0403     IncomingMap incoming, // P
0404     DistanceMap distance, // d
0405     DependencyMap dependency, // delta
0406     PathCountMap path_count, // sigma
0407     VertexIndexMap vertex_index BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0408         Graph, vertex_list_graph_tag))
0409 {
0410     detail::graph::brandes_unweighted_shortest_paths shortest_paths;
0411 
0412     detail::graph::brandes_betweenness_centrality_impl(g, centrality,
0413         edge_centrality_map, incoming, distance, dependency, path_count,
0414         vertex_index, shortest_paths);
0415 }
0416 
0417 template < typename Graph, typename CentralityMap, typename EdgeCentralityMap,
0418     typename IncomingMap, typename DistanceMap, typename DependencyMap,
0419     typename PathCountMap, typename VertexIndexMap, typename WeightMap >
0420 void brandes_betweenness_centrality(const Graph& g,
0421     CentralityMap centrality, // C_B
0422     EdgeCentralityMap edge_centrality_map,
0423     IncomingMap incoming, // P
0424     DistanceMap distance, // d
0425     DependencyMap dependency, // delta
0426     PathCountMap path_count, // sigma
0427     VertexIndexMap vertex_index,
0428     WeightMap weight_map BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0429         Graph, vertex_list_graph_tag))
0430 {
0431     detail::graph::brandes_dijkstra_shortest_paths< WeightMap > shortest_paths(
0432         weight_map);
0433 
0434     detail::graph::brandes_betweenness_centrality_impl(g, centrality,
0435         edge_centrality_map, incoming, distance, dependency, path_count,
0436         vertex_index, shortest_paths);
0437 }
0438 
0439 namespace detail
0440 {
0441     namespace graph
0442     {
0443         template < typename Graph, typename CentralityMap,
0444             typename EdgeCentralityMap, typename WeightMap,
0445             typename VertexIndexMap >
0446         void brandes_betweenness_centrality_dispatch2(const Graph& g,
0447             CentralityMap centrality, EdgeCentralityMap edge_centrality_map,
0448             WeightMap weight_map, VertexIndexMap vertex_index)
0449         {
0450             typedef typename graph_traits< Graph >::degree_size_type
0451                 degree_size_type;
0452             typedef
0453                 typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0454             typedef typename mpl::if_c<
0455                 (is_same< CentralityMap, dummy_property_map >::value),
0456                 EdgeCentralityMap, CentralityMap >::type a_centrality_map;
0457             typedef typename property_traits< a_centrality_map >::value_type
0458                 centrality_type;
0459 
0460             typename graph_traits< Graph >::vertices_size_type V
0461                 = num_vertices(g);
0462 
0463             std::vector< std::vector< edge_descriptor > > incoming(V);
0464             std::vector< centrality_type > distance(V);
0465             std::vector< centrality_type > dependency(V);
0466             std::vector< degree_size_type > path_count(V);
0467 
0468             brandes_betweenness_centrality(g, centrality, edge_centrality_map,
0469                 make_iterator_property_map(incoming.begin(), vertex_index),
0470                 make_iterator_property_map(distance.begin(), vertex_index),
0471                 make_iterator_property_map(dependency.begin(), vertex_index),
0472                 make_iterator_property_map(path_count.begin(), vertex_index),
0473                 vertex_index, weight_map);
0474         }
0475 
0476         template < typename Graph, typename CentralityMap,
0477             typename EdgeCentralityMap, typename VertexIndexMap >
0478         void brandes_betweenness_centrality_dispatch2(const Graph& g,
0479             CentralityMap centrality, EdgeCentralityMap edge_centrality_map,
0480             VertexIndexMap vertex_index)
0481         {
0482             typedef typename graph_traits< Graph >::degree_size_type
0483                 degree_size_type;
0484             typedef
0485                 typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0486             typedef typename mpl::if_c<
0487                 (is_same< CentralityMap, dummy_property_map >::value),
0488                 EdgeCentralityMap, CentralityMap >::type a_centrality_map;
0489             typedef typename property_traits< a_centrality_map >::value_type
0490                 centrality_type;
0491 
0492             typename graph_traits< Graph >::vertices_size_type V
0493                 = num_vertices(g);
0494 
0495             std::vector< std::vector< edge_descriptor > > incoming(V);
0496             std::vector< centrality_type > distance(V);
0497             std::vector< centrality_type > dependency(V);
0498             std::vector< degree_size_type > path_count(V);
0499 
0500             brandes_betweenness_centrality(g, centrality, edge_centrality_map,
0501                 make_iterator_property_map(incoming.begin(), vertex_index),
0502                 make_iterator_property_map(distance.begin(), vertex_index),
0503                 make_iterator_property_map(dependency.begin(), vertex_index),
0504                 make_iterator_property_map(path_count.begin(), vertex_index),
0505                 vertex_index);
0506         }
0507 
0508         template < typename WeightMap >
0509         struct brandes_betweenness_centrality_dispatch1
0510         {
0511             template < typename Graph, typename CentralityMap,
0512                 typename EdgeCentralityMap, typename VertexIndexMap >
0513             static void run(const Graph& g, CentralityMap centrality,
0514                 EdgeCentralityMap edge_centrality_map,
0515                 VertexIndexMap vertex_index, WeightMap weight_map)
0516             {
0517                 brandes_betweenness_centrality_dispatch2(g, centrality,
0518                     edge_centrality_map, weight_map, vertex_index);
0519             }
0520         };
0521 
0522         template <>
0523         struct brandes_betweenness_centrality_dispatch1< param_not_found >
0524         {
0525             template < typename Graph, typename CentralityMap,
0526                 typename EdgeCentralityMap, typename VertexIndexMap >
0527             static void run(const Graph& g, CentralityMap centrality,
0528                 EdgeCentralityMap edge_centrality_map,
0529                 VertexIndexMap vertex_index, param_not_found)
0530             {
0531                 brandes_betweenness_centrality_dispatch2(
0532                     g, centrality, edge_centrality_map, vertex_index);
0533             }
0534         };
0535 
0536         template < typename T > struct is_bgl_named_params
0537         {
0538             BOOST_STATIC_CONSTANT(bool, value = false);
0539         };
0540 
0541         template < typename Param, typename Tag, typename Rest >
0542         struct is_bgl_named_params< bgl_named_params< Param, Tag, Rest > >
0543         {
0544             BOOST_STATIC_CONSTANT(bool, value = true);
0545         };
0546 
0547     }
0548 } // end namespace detail::graph
0549 
0550 template < typename Graph, typename Param, typename Tag, typename Rest >
0551 void brandes_betweenness_centrality(const Graph& g,
0552     const bgl_named_params< Param, Tag, Rest >& params
0553         BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, vertex_list_graph_tag))
0554 {
0555     typedef bgl_named_params< Param, Tag, Rest > named_params;
0556 
0557     typedef typename get_param_type< edge_weight_t, named_params >::type ew;
0558     detail::graph::brandes_betweenness_centrality_dispatch1< ew >::run(g,
0559         choose_param(
0560             get_param(params, vertex_centrality), dummy_property_map()),
0561         choose_param(get_param(params, edge_centrality), dummy_property_map()),
0562         choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
0563         get_param(params, edge_weight));
0564 }
0565 
0566 // disable_if is required to work around problem with MSVC 7.1 (it seems to not
0567 // get partial ordering getween this overload and the previous one correct)
0568 template < typename Graph, typename CentralityMap >
0569 typename disable_if< detail::graph::is_bgl_named_params< CentralityMap >,
0570     void >::type
0571 brandes_betweenness_centrality(const Graph& g,
0572     CentralityMap centrality BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0573         Graph, vertex_list_graph_tag))
0574 {
0575     detail::graph::brandes_betweenness_centrality_dispatch2(
0576         g, centrality, dummy_property_map(), get(vertex_index, g));
0577 }
0578 
0579 template < typename Graph, typename CentralityMap, typename EdgeCentralityMap >
0580 void brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
0581     EdgeCentralityMap edge_centrality_map BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0582         Graph, vertex_list_graph_tag))
0583 {
0584     detail::graph::brandes_betweenness_centrality_dispatch2(
0585         g, centrality, edge_centrality_map, get(vertex_index, g));
0586 }
0587 
0588 /**
0589  * Converts "absolute" betweenness centrality (as computed by the
0590  * brandes_betweenness_centrality algorithm) in the centrality map
0591  * into "relative" centrality. The result is placed back into the
0592  * given centrality map.
0593  */
0594 template < typename Graph, typename CentralityMap >
0595 void relative_betweenness_centrality(const Graph& g, CentralityMap centrality)
0596 {
0597     typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator;
0598     typedef
0599         typename property_traits< CentralityMap >::value_type centrality_type;
0600 
0601     typename graph_traits< Graph >::vertices_size_type n = num_vertices(g);
0602     centrality_type factor
0603         = centrality_type(2) / centrality_type(n * n - 3 * n + 2);
0604     vertex_iterator v, v_end;
0605     for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
0606     {
0607         put(centrality, *v, factor * get(centrality, *v));
0608     }
0609 }
0610 
0611 // Compute the central point dominance of a graph.
0612 template < typename Graph, typename CentralityMap >
0613 typename property_traits< CentralityMap >::value_type central_point_dominance(
0614     const Graph& g,
0615     CentralityMap centrality BOOST_GRAPH_ENABLE_IF_MODELS_PARM(
0616         Graph, vertex_list_graph_tag))
0617 {
0618     using std::max;
0619 
0620     typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator;
0621     typedef
0622         typename property_traits< CentralityMap >::value_type centrality_type;
0623 
0624     typename graph_traits< Graph >::vertices_size_type n = num_vertices(g);
0625 
0626     // Find max centrality
0627     centrality_type max_centrality(0);
0628     vertex_iterator v, v_end;
0629     for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
0630     {
0631         max_centrality = (max)(max_centrality, get(centrality, *v));
0632     }
0633 
0634     // Compute central point dominance
0635     centrality_type sum(0);
0636     for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
0637     {
0638         sum += (max_centrality - get(centrality, *v));
0639     }
0640     return sum / (n - 1);
0641 }
0642 
0643 } // end namespace boost
0644 
0645 #endif // BOOST_GRAPH_BRANDES_BETWEENNESS_CENTRALITY_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!