123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520 |
- // Copyright 2004 The Trustees of Indiana University.
- // Use, modification and distribution is subject to the Boost Software
- // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- // Authors: Douglas Gregor
- // Andrew Lumsdaine
- #include <boost/graph/betweenness_centrality.hpp>
- #include <boost/graph/adjacency_list.hpp>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <boost/property_map/property_map.hpp>
- #include <boost/test/minimal.hpp>
- #include <boost/random/uniform_01.hpp>
- #include <boost/random/linear_congruential.hpp>
- #include <boost/lexical_cast.hpp>
- using namespace boost;
- const double error_tolerance = 0.001;
- typedef property<edge_weight_t, double,
- property<edge_index_t, std::size_t> > EdgeProperties;
- struct weighted_edge
- {
- int source, target;
- double weight;
- };
- template<typename Graph>
- void
- run_weighted_test(Graph*, int V, weighted_edge edge_init[], int E,
- double correct_centrality[])
- {
- Graph g(V);
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
- std::vector<Vertex> vertices(V);
- {
- vertex_iterator v, v_end;
- int index = 0;
- for (boost::tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
- put(vertex_index, g, *v, index);
- vertices[index] = *v;
- }
- }
- std::vector<Edge> edges(E);
- for (int e = 0; e < E; ++e) {
- edges[e] = add_edge(vertices[edge_init[e].source],
- vertices[edge_init[e].target],
- g).first;
- put(edge_weight, g, edges[e], 1.0);
- }
- std::vector<double> centrality(V);
- brandes_betweenness_centrality(
- g,
- centrality_map(
- make_iterator_property_map(centrality.begin(), get(vertex_index, g),
- double()))
- .vertex_index_map(get(vertex_index, g)).weight_map(get(edge_weight, g)));
- for (int v = 0; v < V; ++v) {
- BOOST_CHECK(centrality[v] == correct_centrality[v]);
- }
- }
- struct unweighted_edge
- {
- int source, target;
- };
- template<typename Graph>
- void
- run_unweighted_test(Graph*, int V, unweighted_edge edge_init[], int E,
- double correct_centrality[],
- double* correct_edge_centrality = 0)
- {
- Graph g(V);
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
- std::vector<Vertex> vertices(V);
- {
- vertex_iterator v, v_end;
- int index = 0;
- for (boost::tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
- put(vertex_index, g, *v, index);
- vertices[index] = *v;
- }
- }
- std::vector<Edge> edges(E);
- for (int e = 0; e < E; ++e) {
- edges[e] = add_edge(vertices[edge_init[e].source],
- vertices[edge_init[e].target],
- g).first;
- put(edge_weight, g, edges[e], 1.0);
- put(edge_index, g, edges[e], e);
- }
- std::vector<double> centrality(V);
- std::vector<double> edge_centrality1(E);
- brandes_betweenness_centrality(
- g,
- centrality_map(
- make_iterator_property_map(centrality.begin(), get(vertex_index, g),
- double()))
- .edge_centrality_map(
- make_iterator_property_map(edge_centrality1.begin(),
- get(edge_index, g), double()))
- .vertex_index_map(get(vertex_index, g)));
- std::vector<double> centrality2(V);
- std::vector<double> edge_centrality2(E);
- brandes_betweenness_centrality(
- g,
- vertex_index_map(get(vertex_index, g)).weight_map(get(edge_weight, g))
- .centrality_map(
- make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
- double()))
- .edge_centrality_map(
- make_iterator_property_map(edge_centrality2.begin(),
- get(edge_index, g), double())));
- std::vector<double> edge_centrality3(E);
- brandes_betweenness_centrality(
- g,
- edge_centrality_map(
- make_iterator_property_map(edge_centrality3.begin(),
- get(edge_index, g), double())));
- for (int v = 0; v < V; ++v) {
- BOOST_CHECK(centrality[v] == centrality2[v]);
- double relative_error =
- correct_centrality[v] == 0.0? centrality[v]
- : (centrality[v] - correct_centrality[v]) / correct_centrality[v];
- if (relative_error < 0) relative_error = -relative_error;
- BOOST_CHECK(relative_error < error_tolerance);
- }
- for (int e = 0; e < E; ++e) {
- BOOST_CHECK(edge_centrality1[e] == edge_centrality2[e]);
- BOOST_CHECK(edge_centrality1[e] == edge_centrality3[e]);
- if (correct_edge_centrality) {
- double relative_error =
- correct_edge_centrality[e] == 0.0? edge_centrality1[e]
- : (edge_centrality1[e] - correct_edge_centrality[e])
- / correct_edge_centrality[e];
- if (relative_error < 0) relative_error = -relative_error;
- BOOST_CHECK(relative_error < error_tolerance);
- if (relative_error >= error_tolerance) {
- std::cerr << "Edge " << e << " has edge centrality "
- << edge_centrality1[e] << ", should be "
- << correct_edge_centrality[e] << std::endl;
- }
- }
- }
- }
- template<typename Graph>
- void
- run_wheel_test(Graph*, int V)
- {
- typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::edge_descriptor Edge;
- Graph g(V);
- Vertex center = *boost::vertices(g).first;
- std::vector<Vertex> vertices(V);
- {
- vertex_iterator v, v_end;
- int index = 0;
- for (boost::tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
- put(vertex_index, g, *v, index);
- vertices[index] = *v;
- if (*v != center) {
- Edge e = add_edge(*v, center, g).first;
- put(edge_weight, g, e, 1.0);
- }
- }
- }
- std::vector<double> centrality(V);
- brandes_betweenness_centrality(
- g,
- make_iterator_property_map(centrality.begin(), get(vertex_index, g),
- double()));
- std::vector<double> centrality2(V);
- brandes_betweenness_centrality(
- g,
- centrality_map(
- make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
- double()))
- .vertex_index_map(get(vertex_index, g)).weight_map(get(edge_weight, g)));
- relative_betweenness_centrality(
- g,
- make_iterator_property_map(centrality.begin(), get(vertex_index, g),
- double()));
- relative_betweenness_centrality(
- g,
- make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
- double()));
- for (int v = 0; v < V; ++v) {
- BOOST_CHECK(centrality[v] == centrality2[v]);
- BOOST_CHECK((v == 0 && centrality[v] == 1)
- || (v != 0 && centrality[v] == 0));
- }
- double dominance =
- central_point_dominance(
- g,
- make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
- double()));
- BOOST_CHECK(dominance == 1.0);
- }
- template<typename MutableGraph>
- void randomly_add_edges(MutableGraph& g, double edge_probability)
- {
- typedef typename graph_traits<MutableGraph>::directed_category
- directed_category;
- minstd_rand gen;
- uniform_01<minstd_rand, double> rand_gen(gen);
- typedef typename graph_traits<MutableGraph>::vertex_descriptor vertex;
- typename graph_traits<MutableGraph>::vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- vertex v = *vi;
- typename graph_traits<MutableGraph>::vertex_iterator wi
- = is_same<directed_category, undirected_tag>::value ? vi : vertices(g).first;
- while (wi != vi_end) {
- vertex w = *wi++;
- if (v != w) {
- if (rand_gen() < edge_probability) add_edge(v, w, g);
- }
- }
- }
- }
- template<typename Graph, typename VertexIndexMap, typename CentralityMap>
- void
- simple_unweighted_betweenness_centrality(const Graph& g, VertexIndexMap index,
- CentralityMap centrality)
- {
- typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex;
- typedef typename boost::graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename boost::graph_traits<Graph>::adjacency_iterator adjacency_iterator;
- typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
- typedef typename boost::property_traits<CentralityMap>::value_type centrality_type;
- vertex_iterator vi, vi_end;
- for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
- put(centrality, *vi, 0);
- vertex_iterator si, si_end;
- for (boost::tie(si, si_end) = vertices(g); si != si_end; ++si) {
- vertex s = *si;
- // S <-- empty stack
- std::stack<vertex> S;
- // P[w] <-- empty list, w \in V
- typedef std::vector<vertex> Predecessors;
- std::vector<Predecessors> predecessors(num_vertices(g));
- // sigma[t] <-- 0, t \in V
- std::vector<vertices_size_type> sigma(num_vertices(g), 0);
- // sigma[s] <-- 1
- sigma[get(index, s)] = 1;
- // d[t] <-- -1, t \in V
- std::vector<int> d(num_vertices(g), -1);
- // d[s] <-- 0
- d[get(index, s)] = 0;
- // Q <-- empty queue
- std::queue<vertex> Q;
- // enqueue s --> Q
- Q.push(s);
- while (!Q.empty()) {
- // dequeue v <-- Q
- vertex v = Q.front(); Q.pop();
- // push v --> S
- S.push(v);
- adjacency_iterator wi, wi_end;
- for (boost::tie(wi, wi_end) = adjacent_vertices(v, g); wi != wi_end; ++wi) {
- vertex w = *wi;
- // w found for the first time?
- if (d[get(index, w)] < 0) {
- // enqueue w --> Q
- Q.push(w);
-
- // d[w] <-- d[v] + 1
- d[get(index, w)] = d[get(index, v)] + 1;
- }
- // shortest path to w via v?
- if (d[get(index, w)] == d[get(index, v)] + 1) {
- // sigma[w] = sigma[w] + sigma[v]
- sigma[get(index, w)] += sigma[get(index, v)];
- // append v --> P[w]
- predecessors[get(index, w)].push_back(v);
- }
- }
- }
- // delta[v] <-- 0, v \in V
- std::vector<centrality_type> delta(num_vertices(g), 0);
- // S returns vertices in order of non-increasing distance from s
- while (!S.empty()) {
- // pop w <-- S
- vertex w = S.top(); S.pop();
- const Predecessors& w_preds = predecessors[get(index, w)];
- for (typename Predecessors::const_iterator vi = w_preds.begin();
- vi != w_preds.end(); ++vi) {
- vertex v = *vi;
- // delta[v] <-- delta[v] + (sigma[v]/sigma[w])*(1 + delta[w])
- delta[get(index, v)] +=
- ((centrality_type)sigma[get(index, v)]/sigma[get(index, w)])
- * (1 + delta[get(index, w)]);
- }
- if (w != s) {
- // C_B[w] <-- C_B[w] + delta[w]
- centrality[w] += delta[get(index, w)];
- }
- }
- }
- typedef typename graph_traits<Graph>::directed_category directed_category;
- const bool is_undirected =
- is_same<directed_category, undirected_tag>::value;
- if (is_undirected) {
- vertex_iterator v, v_end;
- for(boost::tie(v, v_end) = vertices(g); v != v_end; ++v) {
- put(centrality, *v, get(centrality, *v) / centrality_type(2));
- }
- }
- }
- template<typename Graph>
- void random_unweighted_test(Graph*, int n)
- {
- Graph g(n);
- {
- typename graph_traits<Graph>::vertex_iterator v, v_end;
- int index = 0;
- for (boost::tie(v, v_end) = boost::vertices(g); v != v_end; ++v, ++index) {
- put(vertex_index, g, *v, index);
- }
- }
- randomly_add_edges(g, 0.20);
- std::cout << "Random graph with " << n << " vertices and "
- << num_edges(g) << " edges.\n";
- std::cout << " Direct translation of Brandes' algorithm...";
- std::vector<double> centrality(n);
- simple_unweighted_betweenness_centrality(g, get(vertex_index, g),
- make_iterator_property_map(centrality.begin(), get(vertex_index, g),
- double()));
- std::cout << "DONE.\n";
- std::cout << " Real version, unweighted...";
- std::vector<double> centrality2(n);
- brandes_betweenness_centrality(g,
- make_iterator_property_map(centrality2.begin(), get(vertex_index, g),
- double()));
- std::cout << "DONE.\n";
- if (!std::equal(centrality.begin(), centrality.end(),
- centrality2.begin())) {
- for (std::size_t v = 0; v < centrality.size(); ++v) {
- double relative_error =
- centrality[v] == 0.0? centrality2[v]
- : (centrality2[v] - centrality[v]) / centrality[v];
- if (relative_error < 0) relative_error = -relative_error;
- BOOST_CHECK(relative_error < error_tolerance);
- }
- }
- std::cout << " Real version, weighted...";
- std::vector<double> centrality3(n);
- for (typename graph_traits<Graph>::edge_iterator ei = edges(g).first;
- ei != edges(g).second; ++ei)
- put(edge_weight, g, *ei, 1);
- brandes_betweenness_centrality(g,
- weight_map(get(edge_weight, g))
- .centrality_map(
- make_iterator_property_map(centrality3.begin(), get(vertex_index, g),
- double())));
- std::cout << "DONE.\n";
- if (!std::equal(centrality.begin(), centrality.end(),
- centrality3.begin())) {
- for (std::size_t v = 0; v < centrality.size(); ++v) {
- double relative_error =
- centrality[v] == 0.0? centrality3[v]
- : (centrality3[v] - centrality[v]) / centrality[v];
- if (relative_error < 0) relative_error = -relative_error;
- BOOST_CHECK(relative_error < error_tolerance);
- }
- }
- }
- int test_main(int argc, char* argv[])
- {
- int random_test_num_vertices = 300;
- if (argc >= 2) random_test_num_vertices = boost::lexical_cast<int>(argv[1]);
- typedef adjacency_list<listS, listS, undirectedS,
- property<vertex_index_t, int>, EdgeProperties>
- Graph;
- typedef adjacency_list<listS, listS, directedS,
- property<vertex_index_t, int>, EdgeProperties>
- Digraph;
- struct unweighted_edge ud_edge_init1[5] = {
- { 0, 1 },
- { 0, 3 },
- { 1, 2 },
- { 3, 2 },
- { 2, 4 }
- };
- double ud_centrality1[5] = { 0.5, 1.0, 3.5, 1.0, 0.0 };
- run_unweighted_test((Graph*)0, 5, ud_edge_init1, 5, ud_centrality1);
- // Example borrowed from the JUNG test suite
- struct unweighted_edge ud_edge_init2[10] = {
- { 0, 1 },
- { 0, 6 },
- { 1, 2 },
- { 1, 3 },
- { 2, 4 },
- { 3, 4 },
- { 4, 5 },
- { 5, 8 },
- { 7, 8 },
- { 6, 7 },
- };
- double ud_centrality2[9] = {
- 0.2142 * 28,
- 0.2797 * 28,
- 0.0892 * 28,
- 0.0892 * 28,
- 0.2797 * 28,
- 0.2142 * 28,
- 0.1666 * 28,
- 0.1428 * 28,
- 0.1666 * 28
- };
- double ud_edge_centrality2[10] = {
- 10.66666,
- 9.33333,
- 6.5,
- 6.5,
- 6.5,
- 6.5,
- 10.66666,
- 9.33333,
- 8.0,
- 8.0
- };
- run_unweighted_test((Graph*)0, 9, ud_edge_init2, 10, ud_centrality2,
- ud_edge_centrality2);
- weighted_edge dw_edge_init1[6] = {
- { 0, 1, 1.0 },
- { 0, 3, 1.0 },
- { 1, 2, 0.5 },
- { 3, 1, 1.0 },
- { 3, 4, 1.0 },
- { 4, 2, 0.5 }
- };
- double dw_centrality1[5] = { 0.0, 1.5, 0.0, 1.0, 0.5 };
- run_weighted_test((Digraph*)0, 5, dw_edge_init1, 6, dw_centrality1);
- run_wheel_test((Graph*)0, 15);
- random_unweighted_test((Graph*)0, random_test_num_vertices);
- return 0;
- }
|