- Boost-users - lists.preview.boost.org

modifying brandes_betweenness_centrality_impl
by The Maschine 08 Dec '14

08 Dec '14

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 '… [View More]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); } } // [View Less]

1 1

errors while compiling the boost-libraries
by steffen.wittek＠posteo.de 08 Dec '14

08 Dec '14

I was trying to compile the boost-libraries in order to use them in dolfin (1.4.0), as I got an error message in Dolfin as follows: > ImportError: /home/phoenix/Work/FEniCS/lib/libdolfin.so.1.4: > undefined symbol: _ZN5boost6thread4joinEv I thought that the undefined symbol pointed towards the boost libraries and so I tried to recompile them by including them into the dorsal script. A compilation of the latter stopped with another error however. The ..Work/FEniCS/src/boost_1_55_0/… [View More]

1 0

[ASIO][Windows] async_resolve() Blocking on Reverse Lookup?
by Kyle Ketterer 06 Dec '14

06 Dec '14

Hello, I am working on a simple utility which scans an IP range and performs a reverse lookup. Using ASIO, I would like to use async_resolve to accomplish this. However, it seems that when using async_resolve() with an ::endpoint overload, the call is blocking. I am wrapping all async functions in a strand and calling io_service::run() from multiple threads. Here is an example: ------------------------------------------------------------------- class client { public: client ( boost::… [View More]asio::io_service & io_service ) : io_service_(io_service), resolver_(io_service), strand_(io_service) { /* */ } void resolve_host ( const std::string & host ) { strand_.post( boost::bind(&client::start_resolve, this, host ) ); } void start_resolve ( const std::string & host_ ) { //boost::asio::ip::tcp::resolver::query query( tcp::v4(), host_, "" ); tcp::endpoint endpoint ( boost::asio::ip::address::from_string( host_) , 0 ); resolver_.async_resolve( endpoint, strand_.wrap( boost::bind( &client::handle_resolve, this, boost::asio::placeholders::error, boost::asio::placeholders::iterator ) ) ); } void handle_resolve ( const boost::system::error_code& err, tcp::resolver::iterator endpoint_iterator ) { if ( !err ) { /* attempt to connect */ tcp::endpoint endpoint = *endpoint_iterator; cout << endpoint.address() << "' >> " << (*endpoint_iterator).host_name() << endl; } } private: tcp::resolver resolver_; boost::asio::strand strand_; boost::asio::io_service & io_service_; }; int main( int argc, char* argv[] ) { /* io service */ boost::asio::io_service io_service; /* ip range */ std::string m_addr = "10.1.10."; /* client object */ boost::shared_ptr<client> m_client ( new client ( io_service ) ); /* add the entire subnet */ for ( int i=1; i<255; i++ ) { m_client->resolve_host ( m_addr + boost::to_string(i) ); } /* create threads and run io_service */ std::vector < boost::shared_ptr<boost::thread> > m_threads; for ( int i=0; i < CPU_CORES; i++ ) { m_threads.push_back ( boost::shared_ptr<boost::thread> ( new boost::thread(boost::bind(&boost::asio::io_service::run, &io_service ) ) ) ); } for ( int i=0; i < CPU_CORES; i++ ) { m_threads[i]->join(); } return 0; } ------------------------------------------------------ I am looking for suggestions on how I can take a multi-threaded approach to this. I am fairly new to ASIO so I appreciate any advice! Thanks -- Kyle Ketterer <reminisc3(a)gmail.com> [View Less]

1 0

phoenix bind template parameter
by Philipp Kraus 06 Dec '14

06 Dec '14

Hello, I try to use phoenix bind to bind std::pow for double values, but I get errors, because the template parameters not set: phoenix::bind(&std::pow, _val, _1) I would like to compile it with C++11. How can I setup the template parameter on the phoenix bind? At the moment I have defined a function double mypow(double a, double b) { return std::pow(a,b); } but can I do this directly with std::pow in the bind call? Thanks a lot Phil

2 1

[Boost.SIMD] Interest in library
by dariomt＠gmail.com 05 Dec '14

05 Dec '14

Hi, I'm interested in trying out Boost.SIMD. Where can I download the latest stable version? Any idea when it might get proposed for Boost review? I think it would be beneficial if it is added to the Boost Incubator until then. Also, in http://meetingcpp.com/tl_files/mcpp/slides/12/simd.pdf slide 36 I see mention of a vectorized Thomas Tri-diagonal Solver. I thought the data dependency made the algorithm unfeasible for vectorization, so I'm *very* interested to learn how Boost.SIMD helps in … [View More]

4 3

Boost Serialization - Overriding builtin implementation for std::wstring
by cpp_learner 04 Dec '14

04 Dec '14

Hi: The current serialization implementation for std::wstring is not portable across platforms. To make it cross platform, we would like to customize the serialization implementation for std::wstring (by splitting "serialize" and providing our own implementation for "save/load"). Is it possible to achieve this? One way to get around this is to provide our own implementation, and not include the header boost/serialization/string.hpp. This is not an option to us as there is no way for us to … [View More]

1 0

Fusion Move Semantics
by Ovanes Markarian 04 Dec '14

04 Dec '14

Hi! I would like to ask does fusion supports move semantics, or are all the values going to get copied. I use C++11 (clang with libstdcxx) and boost 1.54 (but can upgrade). In my use case I have boost::fusion::map and was wondering, that in case of moving of that map, is it going to forward the move call to contained values or not. Many thanks for help, Ovanes

3 2

Boost BGL question regarding depth_first_visit / undirected_depth_first_visit
by Mark Fanara 03 Dec '14

03 Dec '14

I am looking to add a TerminatorFunc to undirected_depth_first_visit similar to what is in depth_first_visit. I think I have successfully made the changes through mimicry (I am an old school C++ guy and still don't understand generic programming) My problem is that I don't know how to declare/define my own terminate function. Nor do I know how to call undirected_depth_first_visit with the new argument. I have tried searching for examples of calling depth_first_visit with a TerminatorFunc … [View More]

1 0

Marriage of boost::any_range and boost::fusion?
by Ernest Zaslavsky 03 Dec '14

03 Dec '14

I'm trying to achieve the following. I have an any_range of const items, in runtime I need dynamically calculate and store values for each item, lets say two additional integers, what I expect to get in the end is an any_range with something like joint view of my const item and two integers. Is it possible? [Read More]<http://feeds.feedburner.com/~r/sizmek-blog/~6/1> [http://www.sizmek.com/Sizmek.png]<http://www.sizmek.com/>

1 0

Re: [Boost-users] how to lisk unique keys in boost multi_index_container
by Bill Tian 03 Dec '14

03 Dec '14

thanks for JoaquÃn M LÃ³pez MuÃ±oz 's reply. i have tried your code, it works as i need exactly. for(auto it=data.get<1>().begin(),it_end=data.get<1>().end(); it!=it_end; it=data.get<1>().upper_bound(it->m2)){ std::cout<<it->m2<<"\n"; // or whatever you need to do with the key } i'll use this method in reality, thanks! Bill

1 0