Re: [Boost-users] modifying brandes_betweenness_centrality_impl

Subject: Re: [Boost-users] modifying brandes_betweenness_centrality_impl
From: The Maschine (justthemaschine_at_[hidden])
Date: 2014-12-08 05:55:34

Anyone with boost graph experience that might at least point me to the
right direction?
Any information missing from my previus post that might help?

Thanks

On Wed, Dec 3, 2014 at 2:38 PM, The Maschine <justthemaschine_at_[hidden]
> wrote:

> Hello all,
>
> Im trying to modify the brandes centrality in order to analyse only a
> subset
> of the graph based on a cutoff distance calculated by some
> other edge weight than the one used for the brandes call.
>
> What I have done so far is to add a shortest path search call before the
> main
> path search inside brandes_betweenness_centrality_impl.
> The first search uses the edge::m_metric_weight and constructs the
> distance map
> from 's' based on that weight.
>
> Then I feed the metric distance map in the 'brandes special visitor' and I
> check inside visitor's examine_vertex. Reminder that the brandes
> call uses the m_special_weight.
>
> While this works as a principle I have no idea how people with experience
> would do it!
> A problem with this is that while the metric cutoff can be small you still
> run
> both searches to the max (as if there is no cutoff).
> Any help on how to change the first 'dijkstra_shortest_paths' so that after
> reaching the cutoff the search stops gracefully and leaves the
> rest of the 'distance_map' to infinity?
>
> Thanks a lot and please let me know if something need more clarification.
>
> ###############
>
> struct EdgeProperties
> {
>     double m_special_weight;
>     double m_metric_distance_weight;
> };
>
> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
>  VertexProperties, EdgeProperties> unGraph;
>
>
>  // test my_brandes_dijkstra_visitor //
>   template<typename Graph, typename WeightMap, typename IncomingMap,
>            typename DistanceMap, typename PathCountMap>
>   struct my_brandes_dijkstra_visitor : public bfs_visitor<>
>   {
>     typedef typename graph_traits<Graph>::vertex_descriptor
> vertex_descriptor;
>     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
>
>     my_brandes_dijkstra_visitor(std::stack<vertex_descriptor>&
>  iordered_vertices,
>                              WeightMap iweight,
>                              IncomingMap iincoming,
>                              DistanceMap idistance,
>                              PathCountMap ipath_count,
>                              std::vector<float> c_dists,
>                              float coff)
>       : ordered_vertices(iordered_vertices), weight(iweight),
>         incoming(iincoming), distance(idistance),
>         path_count(ipath_count), cutoff_dists(c_dists), cutoff(coff)
>     { }
>
>     /**
>      * Whenever an edge e = (v, w) is relaxed, the incoming edge list
>      * for w is set to {(v, w)} and the shortest path count of w is set to
>      * the number of paths that reach {v}.
>      */
>     void edge_relaxed(edge_descriptor e, const Graph& g)
>     {
>       vertex_descriptor v = source(e, g), w = target(e, g);
>       incoming[w].clear();
>       incoming[w].push_back(e);
>       put(path_count, w, get(path_count, v));
>     }
>
>     /**
>      * If an edge e = (v, w) was not relaxed, it may still be the case
>      * that we've found more equally-short paths, so include {(v, w)} in
> the
>      * incoming edges of w and add all of the shortest paths to v to the
>      * shortest path count of w.
>      */
>     void edge_not_relaxed(edge_descriptor e, const Graph& g)
>     {
>       typedef typename property_traits<WeightMap>::value_type weight_type;
>       typedef typename property_traits<DistanceMap>::value_type
> distance_type;
>       vertex_descriptor v = source(e, g), w = target(e, g);
>       distance_type d_v = get(distance, v), d_w = get(distance, w);
>       weight_type w_e = get(weight, e);
>
>       closed_plus<distance_type> combine;
>       if (d_w == combine(d_v, w_e)) {
>         put(path_count, w, get(path_count, w) + get(path_count, v));
>         incoming[w].push_back(e);
>       }
>     }
>
>     /// Keep track of vertices as they are reached
>     void examine_vertex(vertex_descriptor w, const Graph&)
>     {
> // add only if this is within the 'cutoff'. cutoff_dists holds
> // the metric distances from s.
>         if( cutoff_dists[w] < cutoff ) ordered_vertices.push(w);
>     }
>
>   private:
>     std::stack<vertex_descriptor>& ordered_vertices;
>     WeightMap weight;
>     IncomingMap incoming;
>     DistanceMap distance;
>     PathCountMap path_count;
>
>     std::vector<float> cutoff_dists;
>     float cutoff;
>   };
>
> ////////////////////////////////////////////////////////////////////
>
>   template<typename WeightMap>
>   struct my_brandes_dijkstra_shortest_paths
>   {
>     my_brandes_dijkstra_shortest_paths(WeightMap iweight_map)
>       : weight_map(iweight_map) { }
>
>     template<typename Graph, typename IncomingMap, typename DistanceMap,
>              typename PathCountMap, typename VertexIndexMap>
>     void
>     operator()(Graph& g,
>                typename graph_traits<Graph>::vertex_descriptor s,
>                std::stack<typename
> graph_traits<Graph>::vertex_descriptor>& ov,
>                IncomingMap incoming,
>                DistanceMap distance,
>                PathCountMap path_count,
>                VertexIndexMap vertex_index , std::vector<float> c_dists,
>    float coff) // modified cutoff vector and value
>     {
>       typedef my_brandes_dijkstra_visitor<Graph, WeightMap, IncomingMap,
>                                        DistanceMap, PathCountMap>
> visitor_type;
>
>       visitor_type visitor(ov, weight_map, incoming, distance,
>    path_count,c_dists,coff); // modified cutoff vector and value
>
>       dijkstra_shortest_paths(g, s,
>                               boost::weight_map(weight_map)
>                               .vertex_index_map(vertex_index)
>                               .distance_map(distance)
>                               .visitor(visitor));
>     }
>
>   private:
>     WeightMap weight_map;
>   };
>
> //////////////////////////////
>
>     template<typename Graph, typename CentralityMap, typename
> EdgeCentralityMap,
>                typename IncomingMap, typename DistanceMap,
>                typename DependencyMap, typename PathCountMap,
>                typename VertexIndexMap, typename ShortestPaths>
>       void
>       my_brandes_betweenness_centrality_impl(const Graph& g,
>                                           CentralityMap centrality,     //
> C_B
>                                           EdgeCentralityMap
> edge_centrality_map,
>                                           IncomingMap, //incoming, // P
>   // OpenMP mod
>                                           DistanceMap, //distance,// d
>   // OpenMP mod
>                                           DependencyMap, //dependency,//
> delta
>   // OpenMP mod
>                                           PathCountMap, //path_count,//
> sigma
>   // OpenMP mod
>                                           VertexIndexMap vertex_index,
>                                           ShortestPaths shortest_paths)
>       {
>         typedef typename graph_traits<Graph>::vertex_iterator
> vertex_iterator;
>         typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
>         typedef typename graph_traits<Graph>::vertex_descriptor
>  vertex_descriptor;
>
>         // Initialize centrality
>         init_centrality_map(vertices(g), centrality);
>         init_centrality_map(edges(g), edge_centrality_map);
>
>         int i, N = num_vertices(g);
>         #pragma omp parallel for default(shared) private(i)
> schedule(dynamic)
>         for (i = 0; i < N; ++i)
>         {
>           typename graph_traits<Graph>::vertex_descriptor s = vertex(i, g);
>           if (s == graph_traits<Graph>::null_vertex())
>               continue;
>
>   // First we build a map of all distances from 's' based
>   // on m_metric_distance_weight.
>           typedef typename boost::property_map < Graph,
>    boost::vertex_index_t >::type CIndexMap;
>           typedef typename boost::iterator_property_map <
> vertex_descriptor*,
>    CIndexMap, vertex_descriptor, vertex_descriptor& > CPredecessorMap;
>           typedef typename boost::iterator_property_map < float*,
> CIndexMap,
>    float, float& > CDistanceMap;
>           float co = 2200.0f;
>
>           std::vector<vertex_descriptor>
>    cut_predecessors(boost::num_vertices(g)); // To store parents
>           std::vector<float> cut_distances(boost::num_vertices(g),
>    std::numeric_limits<double>::max() ); // To store distances
>           CIndexMap cut_indexMap = boost::get(boost::vertex_index, g);
>           CPredecessorMap cut_predecessorMap(&cut_predecessors[0],
>    cut_indexMap);
>           CDistanceMap cut_distanceMap(&cut_distances[0], cut_indexMap);
>           //
>           boost::dijkstra_shortest_paths(g, s,
>    boost::weight_map(get(&EdgeProperties::m_metric_distance_weight,
> g)).predecessor_map(cut_predecessorMap).distance_map(cut_distanceMap));
>           ///////////
>
>   // Local storage for OpenMP
>           std::stack<vertex_descriptor> ordered_vertices;
>           vector_property_map<typename property_traits<IncomingMap>::
>    value_type,VertexIndexMap> incoming(vertex_index);
>           vector_property_map<typename property_traits<DistanceMap>::
>    value_type,VertexIndexMap> distance(vertex_index);
>           vector_property_map<typename property_traits<DependencyMap>::
>    value_type,VertexIndexMap> dependency(vertex_index);
>           vector_property_map<typename property_traits<PathCountMap>::
>    value_type,VertexIndexMap> path_count(vertex_index);
>
>           // Initialize for this iteration
>           vertex_iterator w, w_end;
>           for (tie(w, w_end) = vertices(g); w != w_end; ++w) {
>             incoming[*w].clear();
>             put(path_count, *w, 0);
>             put(dependency, *w, 0);
>           }
>           put(path_count, s, 1);
>
>   // co - cutoff added. b_centrality is calculated based on
>   // Edge::m_special_weight while we are testing
>   // to be inside the 'cutoff' that is based on the
>   // Edge::m_metric_weight.
>           shortest_paths(g, s, ordered_vertices, incoming, distance,
>    path_count, vertex_index, cut_distances, co);
>
>           while (!ordered_vertices.empty())
>           {
>               vertex_descriptor u = ordered_vertices.top();
>               ordered_vertices.pop();
>
>               typedef typename property_traits<IncomingMap>::value_type
>                   incoming_type;
>               typedef typename incoming_type::iterator incoming_iterator;
>               typedef typename property_traits<DependencyMap>::value_type
>                   dependency_type;
>
>               for (incoming_iterator vw = incoming[u].begin();
>                    vw != incoming[u].end(); ++vw) {
>                   vertex_descriptor v = source(*vw, g);
>                   dependency_type factor = dependency_type(get(path_count,
> v))
>                       / dependency_type(get(path_count, u));
>                   factor *= (dependency_type(1) + get(dependency, u));
>                   put(dependency, v, get(dependency, v) + factor);
>                   update_centrality(edge_centrality_map, *vw, factor);
>               }
>
>               if (u != s) {
>                   #pragma omp critical(globalupdate)
>                   {
>                       update_centrality(centrality, u, get(dependency, u));
>                   }
>               }
>           }
>         }
>
>       typedef typename graph_traits<Graph>::directed_category
> directed_category;
>       const bool is_undirected =
>         is_convertible<directed_category*, undirected_tag*>::value;
>       if (is_undirected) {
>               divide_centrality_by_two(vertices(g), centrality);
>               divide_centrality_by_two(edges(g), edge_centrality_map);
>       }
>     }
>       //
>
>