graph_betweenness.cc 7.9 KB
 Tiago Peixoto committed Feb 14, 2009 1 2 ``````// graph-tool -- a general graph modification and manipulation thingy // `````` Tiago Peixoto committed Jun 05, 2019 3 ``````// Copyright (C) 2006-2019 Tiago de Paula Peixoto `````` Tiago Peixoto committed Feb 14, 2009 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 ``````// // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation; either version 3 // of the License, or (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see . #include "graph_filtering.hh" #include #include #include "graph.hh" #include "graph_selectors.hh" #include "graph_util.hh" using namespace std; using namespace boost; using namespace graph_tool; template void normalize_betweenness(const Graph& g, `````` Tiago Peixoto committed Nov 02, 2017 33 `````` std::vector& pivots, `````` Tiago Peixoto committed Feb 14, 2009 34 35 36 37 `````` EdgeBetweenness edge_betweenness, VertexBetweenness vertex_betweenness, size_t n) { `````` Tiago Peixoto committed Nov 02, 2017 38 39 40 41 `````` size_t p = pivots.size(); double pfactor = (p > 1 && n > 2) ? ((p - 1) * (n - 2)) : .0; double vfactor = (p > 0 && n > 2) ? (p * (n - 2)) : .0; double efactor = (p > 0 && n > 1) ? (p * (n - 1)) : .0; `````` Tiago Peixoto committed Nov 10, 2013 42 43 `````` if (std::is_convertible::directed_category, undirected_tag>::value) `````` Tiago Peixoto committed Feb 14, 2009 44 `````` { `````` Tiago Peixoto committed Nov 02, 2017 45 46 47 `````` pfactor /= 2; vfactor /= 2; efactor /= 2; `````` Tiago Peixoto committed Feb 14, 2009 48 49 `````` } `````` Tiago Peixoto committed Nov 02, 2017 50 51 52 53 54 55 56 57 58 `````` pfactor = (pfactor > 0) ? 1./pfactor : 0; vfactor = (vfactor > 0) ? 1./vfactor : 0; efactor = (efactor > 0) ? 1./efactor : 0; typedef typename vprop_map_t::type::unchecked_t vprop_t; vprop_t is_pivot(get(vertex_index, g), num_vertices(g)); parallel_loop(pivots, [&](size_t, auto v){ is_pivot[v] = true;}); `````` Tiago Peixoto committed Apr 22, 2016 59 60 61 62 `````` parallel_vertex_loop (g, [&](auto v) { `````` Tiago Peixoto committed Nov 02, 2017 63 64 65 66 `````` if (is_pivot[v]) put(vertex_betweenness, v, pfactor * get(vertex_betweenness, v)); else put(vertex_betweenness, v, vfactor * get(vertex_betweenness, v)); `````` Tiago Peixoto committed Apr 22, 2016 67 `````` }); `````` Tiago Peixoto committed Feb 14, 2009 68 `````` `````` Tiago Peixoto committed Apr 22, 2016 69 70 71 72 73 74 `````` parallel_edge_loop (g, [&](const auto& e) { put(edge_betweenness, e, efactor * get(edge_betweenness, e)); }); `````` Tiago Peixoto committed Feb 14, 2009 75 76 77 78 ``````} struct get_betweenness { `````` Tiago Peixoto committed Nov 10, 2013 79 `````` typedef void result_type; `````` Tiago Peixoto committed Feb 14, 2009 80 `````` template `````` Tiago Peixoto committed Mar 10, 2009 81 `````` void operator()(Graph& g, `````` Tiago Peixoto committed Nov 02, 2017 82 `````` std::vector& pivots, `````` Tiago Peixoto committed Feb 14, 2009 83 84 85 86 87 88 `````` GraphInterface::vertex_index_map_t index_map, EdgeBetweenness edge_betweenness, VertexBetweenness vertex_betweenness, bool normalize, size_t n) const { vector::edge_descriptor> > `````` Tiago Peixoto committed Mar 10, 2009 89 90 `````` incoming_map(num_vertices(g)); vector distance_map(num_vertices(g)); `````` Tiago Peixoto committed Feb 14, 2009 91 `````` vector::value_type> `````` Tiago Peixoto committed Mar 10, 2009 92 93 `````` dependency_map(num_vertices(g)); vector path_count_map(num_vertices(g)); `````` Tiago Peixoto committed Feb 14, 2009 94 `````` brandes_betweenness_centrality `````` Tiago Peixoto committed Nov 02, 2017 95 `````` (g, pivots, vertex_betweenness, edge_betweenness, `````` Tiago Peixoto committed Feb 14, 2009 96 97 98 99 100 101 `````` make_iterator_property_map(incoming_map.begin(), index_map), make_iterator_property_map(distance_map.begin(), index_map), make_iterator_property_map(dependency_map.begin(), index_map), make_iterator_property_map(path_count_map.begin(), index_map), index_map); if (normalize) `````` Tiago Peixoto committed Nov 02, 2017 102 `````` normalize_betweenness(g, pivots, edge_betweenness, vertex_betweenness, n); `````` Tiago Peixoto committed Feb 14, 2009 103 104 105 106 107 `````` } }; struct get_weighted_betweenness { `````` Tiago Peixoto committed Nov 10, 2013 108 `````` typedef void result_type; `````` Tiago Peixoto committed Feb 14, 2009 109 110 `````` template `````` Tiago Peixoto committed Nov 02, 2017 111 112 113 114 115 116 `````` void operator()(Graph& g, std::vector& pivots, VertexIndexMap vertex_index, EdgeBetweenness edge_betweenness, VertexBetweenness vertex_betweenness, boost::any weight_map, bool normalize, size_t n, size_t max_eindex) const `````` Tiago Peixoto committed Feb 14, 2009 117 118 `````` { vector::edge_descriptor> > `````` Tiago Peixoto committed Mar 10, 2009 119 `````` incoming_map(num_vertices(g)); `````` Tiago Peixoto committed Feb 14, 2009 120 `````` vector::value_type> `````` Tiago Peixoto committed Mar 10, 2009 121 `````` distance_map(num_vertices(g)); `````` Tiago Peixoto committed Feb 14, 2009 122 `````` vector::value_type> `````` Tiago Peixoto committed Mar 10, 2009 123 124 `````` dependency_map(num_vertices(g)); vector path_count_map(num_vertices(g)); `````` Tiago Peixoto committed Feb 14, 2009 125 `````` `````` Tiago Peixoto committed May 08, 2009 126 127 128 `````` typename EdgeBetweenness::checked_t weight = any_cast(weight_map); `````` Tiago Peixoto committed Feb 14, 2009 129 `````` brandes_betweenness_centrality `````` Tiago Peixoto committed Nov 02, 2017 130 `````` (g, pivots, vertex_betweenness, edge_betweenness, `````` Tiago Peixoto committed Feb 14, 2009 131 132 133 134 `````` make_iterator_property_map(incoming_map.begin(), vertex_index), make_iterator_property_map(distance_map.begin(), vertex_index), make_iterator_property_map(dependency_map.begin(), vertex_index), make_iterator_property_map(path_count_map.begin(), vertex_index), `````` Tiago Peixoto committed May 08, 2009 135 `````` vertex_index, weight.get_unchecked(max_eindex+1)); `````` Tiago Peixoto committed Feb 14, 2009 136 `````` if (normalize) `````` Tiago Peixoto committed Nov 02, 2017 137 `````` normalize_betweenness(g, pivots, edge_betweenness, vertex_betweenness, n); `````` Tiago Peixoto committed Feb 14, 2009 138 139 140 `````` } }; `````` Tiago Peixoto committed Nov 02, 2017 141 142 ``````void betweenness(GraphInterface& g, std::vector& pivots, boost::any weight, `````` Tiago Peixoto committed Feb 14, 2009 143 144 145 146 147 `````` boost::any edge_betweenness, boost::any vertex_betweenness, bool normalize) { if (!belongs()(edge_betweenness)) `````` Tiago Peixoto committed Aug 13, 2009 148 `````` throw ValueException("edge property must be of floating point value" `````` Tiago Peixoto committed May 08, 2009 149 `````` " type"); `````` Tiago Peixoto committed Feb 14, 2009 150 151 `````` if (!belongs()(vertex_betweenness)) `````` Tiago Peixoto committed Aug 13, 2009 152 `````` throw ValueException("vertex property must be of floating point value" `````` Tiago Peixoto committed May 08, 2009 153 `````` " type"); `````` Tiago Peixoto committed Feb 14, 2009 154 155 156 157 `````` if (!weight.empty()) { run_action<>() `````` Tiago Peixoto committed Nov 10, 2013 158 `````` (g, std::bind<>(get_weighted_betweenness(), `````` Tiago Peixoto committed Nov 02, 2017 159 160 161 `````` std::placeholders::_1, std::ref(pivots), g.get_vertex_index(), `````` Tiago Peixoto committed Nov 10, 2013 162 163 `````` std::placeholders::_2, std::placeholders::_3, weight, normalize, `````` Tiago Peixoto committed Nov 05, 2015 164 `````` g.get_num_vertices(), g.get_edge_index_range()), `````` Tiago Peixoto committed Feb 14, 2009 165 166 167 168 169 170 171 `````` edge_floating_properties(), vertex_floating_properties()) (edge_betweenness, vertex_betweenness); } else { run_action<>() `````` Tiago Peixoto committed Nov 10, 2013 172 `````` (g, std::bind(get_betweenness(), std::placeholders::_1, `````` Tiago Peixoto committed Nov 02, 2017 173 `````` std::ref(pivots), `````` Tiago Peixoto committed Sep 13, 2015 174 `````` g.get_vertex_index(), std::placeholders::_2, `````` Tiago Peixoto committed Nov 10, 2013 175 `````` std::placeholders::_3, normalize, `````` Tiago Peixoto committed Sep 13, 2015 176 `````` g.get_num_vertices()), `````` Tiago Peixoto committed Feb 14, 2009 177 178 179 180 181 182 183 184 185 `````` edge_floating_properties(), vertex_floating_properties()) (edge_betweenness, vertex_betweenness); } } struct get_central_point_dominance { template `````` Tiago Peixoto committed Mar 10, 2009 186 `````` void operator()(Graph& g, VertexBetweenness vertex_betweenness, double& c) `````` Tiago Peixoto committed Feb 14, 2009 187 188 `````` const { `````` Tiago Peixoto committed Jun 03, 2012 189 `````` c = double(central_point_dominance(g, vertex_betweenness)); `````` Tiago Peixoto committed Feb 14, 2009 190 191 192 193 194 195 196 197 `````` } }; double central_point(GraphInterface& g, boost::any vertex_betweenness) { double c = 0.0; run_action() `````` Tiago Peixoto committed Nov 10, 2013 198 199 `````` (g, std::bind<>(get_central_point_dominance(), std::placeholders::_1, std::placeholders::_2, std::ref(c)), `````` Tiago Peixoto committed Feb 14, 2009 200 201 202 203 204 205 206 207 208 209 `````` vertex_scalar_properties()) (vertex_betweenness); return c; } void export_betweenness() { using namespace boost::python; def("get_betweenness", &betweenness); def("get_central_point_dominance", ¢ral_point); }``````