Difference between revisions of "CPP/Boost/BGL/d ary heap indirect"
From ProgrammingExamples
< CPP
Daviddoria (Talk | contribs) |
(→d_ary_heap_indirect.cpp) |
||
Line 2: | Line 2: | ||
<source lang="cpp"> | <source lang="cpp"> | ||
#include <iostream> | #include <iostream> | ||
− | + | #include <iomanip> | |
+ | |||
#include <boost/graph/grid_graph.hpp> | #include <boost/graph/grid_graph.hpp> | ||
#include <boost/graph/detail/d_ary_heap.hpp> | #include <boost/graph/detail/d_ary_heap.hpp> | ||
#include <boost/property_map/property_map.hpp> | #include <boost/property_map/property_map.hpp> | ||
+ | #include <cstdlib> | ||
+ | |||
template <typename T> | template <typename T> | ||
struct LessThanFunctor | struct LessThanFunctor | ||
Line 15: | Line 18: | ||
} | } | ||
}; | }; | ||
− | + | ||
int main(int argc, char*argv[]) | int main(int argc, char*argv[]) | ||
{ | { | ||
+ | srand((unsigned int)time(NULL)); | ||
+ | |||
boost::array<std::size_t, 2> lengths = { { 5,5 } }; | boost::array<std::size_t, 2> lengths = { { 5,5 } }; | ||
typedef boost::grid_graph<2> GraphType; | typedef boost::grid_graph<2> GraphType; | ||
Line 24: | Line 29: | ||
typedef boost::property_map<GraphType, boost::vertex_index_t>::const_type GridIndexMapType; | typedef boost::property_map<GraphType, boost::vertex_index_t>::const_type GridIndexMapType; | ||
GridIndexMapType gridIndexMap(get(boost::vertex_index, graph)); | GridIndexMapType gridIndexMap(get(boost::vertex_index, graph)); | ||
− | + | ||
typedef boost::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap; | typedef boost::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap; | ||
− | IndexInHeapMap index_in_heap; | + | IndexInHeapMap index_in_heap(gridIndexMap); |
− | + | ||
− | + | boost::graph_traits<GraphType>::vertex_iterator ui, ui_end; | |
− | + | for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui) | |
+ | put(index_in_heap, *ui, static_cast<std::size_t>(-1)); | ||
+ | |||
typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType; | typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType; | ||
PriorityMapType priorityMap(gridIndexMap); | PriorityMapType priorityMap(gridIndexMap); | ||
− | + | for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui) | |
− | + | put(priorityMap, *ui, rand() % 1000); | |
+ | |||
+ | std::cout << "Given the following random grid-graph: " << std::endl; | ||
+ | Vertex v = vertex(0,graph); | ||
+ | for(std::size_t i = 0; i < lengths[0]; ++i) { | ||
+ | Vertex u = v; | ||
+ | for(std::size_t j = 0; j < lengths[1]; ++j) { | ||
+ | std::cout << std::setw(5) << get(priorityMap, u); | ||
+ | u = graph.next(u,1); | ||
+ | }; | ||
+ | v = graph.next(v,0); | ||
+ | std::cout << std::endl; | ||
+ | }; | ||
+ | |||
typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, LessThanFunctor<float> > MutableQueue; | typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, LessThanFunctor<float> > MutableQueue; | ||
− | + | ||
LessThanFunctor<float> lessThanFunctor; | LessThanFunctor<float> lessThanFunctor; | ||
MutableQueue mutableQueue(priorityMap, index_in_heap, lessThanFunctor); | MutableQueue mutableQueue(priorityMap, index_in_heap, lessThanFunctor); | ||
+ | |||
+ | for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui) | ||
+ | mutableQueue.push(*ui); | ||
− | Vertex | + | std::cout << "We get the following priority queue: " << std::endl; |
− | + | while( ! mutableQueue.empty() ) { | |
+ | Vertex u = mutableQueue.top(); mutableQueue.pop(); | ||
+ | std::cout << std::setw(5) << get(priorityMap, u); | ||
+ | }; | ||
+ | std::cout << std::endl; | ||
return 0; | return 0; | ||
} | } |
Latest revision as of 18:58, 25 January 2012
d_ary_heap_indirect.cpp
#include <iostream> #include <iomanip> #include <boost/graph/grid_graph.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/property_map/property_map.hpp> #include <cstdlib> template <typename T> struct LessThanFunctor { bool operator()(const T& a, const T& b) { return a < b; } }; int main(int argc, char*argv[]) { srand((unsigned int)time(NULL)); boost::array<std::size_t, 2> lengths = { { 5,5 } }; typedef boost::grid_graph<2> GraphType; GraphType graph(lengths); typedef boost::graph_traits<GraphType>::vertex_descriptor Vertex; typedef boost::property_map<GraphType, boost::vertex_index_t>::const_type GridIndexMapType; GridIndexMapType gridIndexMap(get(boost::vertex_index, graph)); typedef boost::vector_property_map<std::size_t, GridIndexMapType> IndexInHeapMap; IndexInHeapMap index_in_heap(gridIndexMap); boost::graph_traits<GraphType>::vertex_iterator ui, ui_end; for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui) put(index_in_heap, *ui, static_cast<std::size_t>(-1)); typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType; PriorityMapType priorityMap(gridIndexMap); for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui) put(priorityMap, *ui, rand() % 1000); std::cout << "Given the following random grid-graph: " << std::endl; Vertex v = vertex(0,graph); for(std::size_t i = 0; i < lengths[0]; ++i) { Vertex u = v; for(std::size_t j = 0; j < lengths[1]; ++j) { std::cout << std::setw(5) << get(priorityMap, u); u = graph.next(u,1); }; v = graph.next(v,0); std::cout << std::endl; }; typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, LessThanFunctor<float> > MutableQueue; LessThanFunctor<float> lessThanFunctor; MutableQueue mutableQueue(priorityMap, index_in_heap, lessThanFunctor); for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui) mutableQueue.push(*ui); std::cout << "We get the following priority queue: " << std::endl; while( ! mutableQueue.empty() ) { Vertex u = mutableQueue.top(); mutableQueue.pop(); std::cout << std::setw(5) << get(priorityMap, u); }; std::cout << std::endl; return 0; }
CMakeLists.txt
cmake_minimum_required(VERSION 2.6) Project(d_ary_heap_indirect) set(Boost_USE_MULTITHREADED ON) FIND_PACKAGE(Boost 1.38 COMPONENTS) INCLUDE_DIRECTORIES(${INCLUDE_DIRECTORIES} ${Boost_INCLUDE_DIRS}) LINK_DIRECTORIES(${LINK_DIRECTORIES} ${Boost_LIBRARY_DIRS}) ADD_EXECUTABLE(d_ary_heap_indirect d_ary_heap_indirect.cpp)