1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/bc_clustering.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,164 @@
1.4 +// Copyright 2004 The Trustees of Indiana University.
1.5 +
1.6 +// Distributed under the Boost Software License, Version 1.0.
1.7 +// (See accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// Authors: Douglas Gregor
1.11 +// Andrew Lumsdaine
1.12 +#ifndef BOOST_GRAPH_BETWEENNESS_CENTRALITY_CLUSTERING_HPP
1.13 +#define BOOST_GRAPH_BETWEENNESS_CENTRALITY_CLUSTERING_HPP
1.14 +
1.15 +#include <boost/graph/betweenness_centrality.hpp>
1.16 +#include <boost/graph/graph_traits.hpp>
1.17 +#include <boost/pending/indirect_cmp.hpp>
1.18 +#include <algorithm>
1.19 +#include <vector>
1.20 +#include <boost/property_map.hpp>
1.21 +
1.22 +namespace boost {
1.23 +
1.24 +/** Threshold termination function for the betweenness centrality
1.25 + * clustering algorithm.
1.26 + */
1.27 +template<typename T>
1.28 +struct bc_clustering_threshold
1.29 +{
1.30 + typedef T centrality_type;
1.31 +
1.32 + /// Terminate clustering when maximum absolute edge centrality is
1.33 + /// below the given threshold.
1.34 + explicit bc_clustering_threshold(T threshold)
1.35 + : threshold(threshold), dividend(1.0) {}
1.36 +
1.37 + /**
1.38 + * Terminate clustering when the maximum edge centrality is below
1.39 + * the given threshold.
1.40 + *
1.41 + * @param threshold the threshold value
1.42 + *
1.43 + * @param g the graph on which the threshold will be calculated
1.44 + *
1.45 + * @param normalize when true, the threshold is compared against the
1.46 + * normalized edge centrality based on the input graph; otherwise,
1.47 + * the threshold is compared against the absolute edge centrality.
1.48 + */
1.49 + template<typename Graph>
1.50 + bc_clustering_threshold(T threshold, const Graph& g, bool normalize = true)
1.51 + : threshold(threshold), dividend(1.0)
1.52 + {
1.53 + if (normalize) {
1.54 + typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
1.55 + dividend = T((n - 1) * (n - 2)) / T(2);
1.56 + }
1.57 + }
1.58 +
1.59 + /** Returns true when the given maximum edge centrality (potentially
1.60 + * normalized) falls below the threshold.
1.61 + */
1.62 + template<typename Graph, typename Edge>
1.63 + bool operator()(T max_centrality, Edge, const Graph&)
1.64 + {
1.65 + return (max_centrality / dividend) < threshold;
1.66 + }
1.67 +
1.68 + protected:
1.69 + T threshold;
1.70 + T dividend;
1.71 +};
1.72 +
1.73 +/** Graph clustering based on edge betweenness centrality.
1.74 + *
1.75 + * This algorithm implements graph clustering based on edge
1.76 + * betweenness centrality. It is an iterative algorithm, where in each
1.77 + * step it compute the edge betweenness centrality (via @ref
1.78 + * brandes_betweenness_centrality) and removes the edge with the
1.79 + * maximum betweenness centrality. The @p done function object
1.80 + * determines when the algorithm terminates (the edge found when the
1.81 + * algorithm terminates will not be removed).
1.82 + *
1.83 + * @param g The graph on which clustering will be performed. The type
1.84 + * of this parameter (@c MutableGraph) must be a model of the
1.85 + * VertexListGraph, IncidenceGraph, EdgeListGraph, and Mutable Graph
1.86 + * concepts.
1.87 + *
1.88 + * @param done The function object that indicates termination of the
1.89 + * algorithm. It must be a ternary function object thats accepts the
1.90 + * maximum centrality, the descriptor of the edge that will be
1.91 + * removed, and the graph @p g.
1.92 + *
1.93 + * @param edge_centrality (UTIL/OUT) The property map that will store
1.94 + * the betweenness centrality for each edge. When the algorithm
1.95 + * terminates, it will contain the edge centralities for the
1.96 + * graph. The type of this property map must model the
1.97 + * ReadWritePropertyMap concept. Defaults to an @c
1.98 + * iterator_property_map whose value type is
1.99 + * @c Done::centrality_type and using @c get(edge_index, g) for the
1.100 + * index map.
1.101 + *
1.102 + * @param vertex_index (IN) The property map that maps vertices to
1.103 + * indices in the range @c [0, num_vertices(g)). This type of this
1.104 + * property map must model the ReadablePropertyMap concept and its
1.105 + * value type must be an integral type. Defaults to
1.106 + * @c get(vertex_index, g).
1.107 + */
1.108 +template<typename MutableGraph, typename Done, typename EdgeCentralityMap,
1.109 + typename VertexIndexMap>
1.110 +void
1.111 +betweenness_centrality_clustering(MutableGraph& g, Done done,
1.112 + EdgeCentralityMap edge_centrality,
1.113 + VertexIndexMap vertex_index)
1.114 +{
1.115 + typedef typename property_traits<EdgeCentralityMap>::value_type
1.116 + centrality_type;
1.117 + typedef typename graph_traits<MutableGraph>::edge_iterator edge_iterator;
1.118 + typedef typename graph_traits<MutableGraph>::edge_descriptor edge_descriptor;
1.119 + typedef typename graph_traits<MutableGraph>::vertices_size_type
1.120 + vertices_size_type;
1.121 +
1.122 + if (edges(g).first == edges(g).second) return;
1.123 +
1.124 + // Function object that compares the centrality of edges
1.125 + indirect_cmp<EdgeCentralityMap, std::less<centrality_type> >
1.126 + cmp(edge_centrality);
1.127 +
1.128 + bool is_done;
1.129 + do {
1.130 + brandes_betweenness_centrality(g,
1.131 + edge_centrality_map(edge_centrality)
1.132 + .vertex_index_map(vertex_index));
1.133 + edge_descriptor e = *max_element(edges(g).first, edges(g).second, cmp);
1.134 + is_done = done(get(edge_centrality, e), e, g);
1.135 + if (!is_done) remove_edge(e, g);
1.136 + } while (!is_done && edges(g).first != edges(g).second);
1.137 +}
1.138 +
1.139 +/**
1.140 + * \overload
1.141 + */
1.142 +template<typename MutableGraph, typename Done, typename EdgeCentralityMap>
1.143 +void
1.144 +betweenness_centrality_clustering(MutableGraph& g, Done done,
1.145 + EdgeCentralityMap edge_centrality)
1.146 +{
1.147 + betweenness_centrality_clustering(g, done, edge_centrality,
1.148 + get(vertex_index, g));
1.149 +}
1.150 +
1.151 +/**
1.152 + * \overload
1.153 + */
1.154 +template<typename MutableGraph, typename Done>
1.155 +void
1.156 +betweenness_centrality_clustering(MutableGraph& g, Done done)
1.157 +{
1.158 + typedef typename Done::centrality_type centrality_type;
1.159 + std::vector<centrality_type> edge_centrality(num_edges(g));
1.160 + betweenness_centrality_clustering(g, done,
1.161 + make_iterator_property_map(edge_centrality.begin(), get(edge_index, g)),
1.162 + get(vertex_index, g));
1.163 +}
1.164 +
1.165 +} // end namespace boost
1.166 +
1.167 +#endif // BOOST_GRAPH_BETWEENNESS_CENTRALITY_CLUSTERING_HPP