CPP/Boost/BGL/d ary heap indirect - Revision history

Mikael.s.persson: /* d_ary_heap_indirect.cpp */

2012-01-25T22:58:26Z

‎d_ary_heap_indirect.cpp

Daviddoria at 19:58, 25 January 2012

2012-01-25T19:58:14Z

Daviddoria: Created page with '==d_ary_heap_indirect.cpp== #include #include #include #include
2012-01-25T19:19:30Z

Created page with '==d_ary_heap_indirect.cpp== <source lang="cpp"> #include <iostream> #include <boost/graph/grid_graph.hpp> #include <boost/graph/detail/d_ary_heap.hpp> #include <boost/property_m…'

New page
==d_ary_heap_indirect.cpp==
<source lang="cpp">
#include <iostream>

#include <boost/graph/grid_graph.hpp>
#include <boost/graph/detail/d_ary_heap.hpp>
#include <boost/property_map/property_map.hpp>

template <typename T>
struct LessThanFunctor
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};

int main(int argc, char*argv[])
{
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> IndexInHeapMap;
IndexInHeapMap index_in_heap;

//put(index_in_heap, 0, (std::size_t)(-1));
put(index_in_heap, 0, static_cast<std::size_t>(-1));

typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
PriorityMapType priorityMap(gridIndexMap);

//typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, KeyMap, KeyCompareType> MutableQueue;
typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, LessThanFunctor<float> > MutableQueue;

LessThanFunctor<float> lessThanFunctor;
MutableQueue mutableQueue(priorityMap, index_in_heap, lessThanFunctor);

Vertex v = vertex(0, graph);
mutableQueue.push(v); // Compiler error - no match for operator[]
return 0;
}

</source>

==CMakeLists.txt==
<source lang="cmake">
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)

</source>

@@ Line 2: / Line 2: @@
 <source lang="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>
 template <typename T>
 struct LessThanFunctor
@@ Line 15: / Line 18: @@
+   }
 };
-−
 int main(int argc, char*argv[])
+{
    boost::array<std::size_t, 2> lengths = { { 5,5 } };
    typedef boost::grid_graph<2> GraphType;
@@ Line 24: / Line 29: @@
    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;
+   IndexInHeapMap index_in_heap(gridIndexMap);
-−
-   put(index_in_heap, vertex(0, graph), static_cast<std::size_t>(-1));
+   boost::graph_traits<GraphType>::vertex_iterator ui, ui_end;
+  for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui)
    typedef boost::vector_property_map<float, GridIndexMapType> PriorityMapType;
    PriorityMapType priorityMap(gridIndexMap);
+  for( tie(ui,ui_end) = vertices(graph); ui != ui_end; ++ui)
-   //typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, KeyMap, KeyCompareType> MutableQueue;
+    put(priorityMap, *ui, rand() % 1000);
    typedef boost::d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, PriorityMapType, LessThanFunctor<float> > MutableQueue;
-−
    LessThanFunctor<float> lessThanFunctor;
    MutableQueue mutableQueue(priorityMap, index_in_heap, lessThanFunctor);
-   Vertex v = vertex(0, graph);
+   std::cout << "We get the following priority queue: " << std::endl;
-  mutableQueue.push(v); // Compiler error - no match for operator[]
+  while( ! mutableQueue.empty() ) {
    return 0;
+}