我想写一个Dijkstra的算法，我喜欢利用boost图库的代码，但我想使用我自己实现的二项堆和堆，而不是默认的优先级队列。这是我第一次使用下载的库代码，我只是不知道如何做到这一点。有人知道怎么做吗，或者这是不可能的?
有人知道如何做到这一点，或者如果这是不可能的?
不，dijkstra_shortest_paths不接受队列类型。
这并不意味着不可能。Boost的Dijkstra是BFS的一个应用。BFS,支持自定义缓冲区类型
请记住Dijkstra需要一个支持递减键操作的优先级队列
减少键操作可以针对您的队列类型进行专门化:
/**
* @brief Updates a particular value in a queue used by Dijkstra's
* algorithm.
*
* This routine is called by Dijkstra's algorithm after it has
* decreased the distance from the source vertex to the given @p
* vertex. By default, this routine will just call @c
* Q.update(vertex). However, other queues may provide more
* specialized versions of this routine.
*
* @param Q the queue that will be updated.
* @param vertex the vertex whose distance has been updated
* @param old_distance the previous distance to @p vertex
*/
template < typename Buffer, typename Vertex, typename DistanceType >
inline void dijkstra_queue_update(
Buffer& Q, Vertex vertex, DistanceType old_distance)
{
(void)old_distance;
Q.update(vertex);
}
所有Dijkstra调用都经过dijkstra_shortest_paths_no_init，它负责调用BFS:
// Call breadth first search
template < class Graph, class SourceInputIter, class DijkstraVisitor,
class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap,
class Compare, class Combine, class DistZero, class ColorMap >
inline void dijkstra_shortest_paths_no_init(const Graph& g,
SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor,
DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare,
Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)
{
typedef indirect_cmp< DistanceMap, Compare > IndirectCmp;
IndirectCmp icmp(distance, compare);
typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
// Now the default: use a d-ary heap
boost::scoped_array< std::size_t > index_in_heap_map_holder;
typedef detail::vertex_property_map_generator< Graph, IndexMap,
std::size_t >
IndexInHeapMapHelper;
typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
IndexInHeapMap index_in_heap
= IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder);
typedef d_ary_heap_indirect< Vertex, 4, IndexInHeapMap, DistanceMap,
Compare >
MutableQueue;
MutableQueue Q(distance, index_in_heap, compare);
detail::dijkstra_bfs_visitor< DijkstraVisitor, MutableQueue, WeightMap,
PredecessorMap, DistanceMap, Combine, Compare >
bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
}
您可以在自己的入口点包装器函数中用自己的队列替换d_ary_heap。(您可以绕过现有的BGL Dijkstra算法入口点，或者您可以通过重载启动特定参数类型(图类型或任何其他参数)来破解它)。
概念证明
。任意包装Graph类型的概念验证。事后看来，用比较谓词来包装会容易得多。
Live On Coliru
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>
#include <queue>
using G = boost::adjacency_list<>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;
namespace PoC {
template <typename Graph> struct Wrapped : Graph {
using Graph::Graph;
Graph& get() { return *this; }
Graph const& get() const { return *this; }
};
template <class Graph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap,
class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine,
class DistZero, class ColorMap>
inline void dijkstra_shortest_paths_no_init(Wrapped<Graph> const& g, SourceInputIter s_begin,
SourceInputIter s_end, PredecessorMap predecessor,
DistanceMap distance, WeightMap weight, IndexMap index_map,
Compare compare, Combine combine, DistZero zero,
DijkstraVisitor vis, ColorMap color) {
using namespace boost;
indirect_cmp<DistanceMap, Compare> icmp(distance, compare);
using Vertex = typename graph_traits<Graph>::vertex_descriptor;
// Now the default: use a d-ary heap
boost::scoped_array<std::size_t> index_in_heap_map_holder;
using IndexInHeapMapHelper = detail::vertex_property_map_generator<Graph, IndexMap, std::size_t>;
using IndexInHeapMap = typename IndexInHeapMapHelper::type;
using MutableQueue = d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>;
IndexInHeapMap index_in_heap = IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder);
MutableQueue Q(distance, index_in_heap, compare);
std::cerr << "SEHE WAS HERE - pretend we use different MutableQueue" << std::endl;
detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap, PredecessorMap, DistanceMap,
Combine, Compare>
bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
breadth_first_visit(g, s_begin, s_end, Q, bfs_vis, color);
}
}
template <typename G>
struct boost::graph_traits<PoC::Wrapped<G>> : graph_traits<G> {};
template <typename G, typename P>
struct boost::graph_property<PoC::Wrapped<G>, P> : graph_property<G, P> {};
int main() {
PoC::Wrapped<G> g(10);
add_edge(1, 3, g);
add_edge(2, 4, g);
add_edge(3, 2, g);
add_edge(4, 8, g);
add_edge(8, 3, g);
print_graph(g);
std::vector<V> pred(num_vertices(g));
std::priority_queue<V> q;
dijkstra_shortest_paths( //
g, 0,
boost::predecessor_map(pred.data()) //
.weight_map(boost::constant_property_map<E, double>(0.0)) //
.max_priority_queue(q) //
);
}
打印，如预期:
0 -->
1 --> 3
2 --> 4
3 --> 2
4 --> 8
5 -->
6 -->
7 -->
8 --> 3
9 -->
SEHE WAS HERE - pretend we use different MutableQueue
Notes/警告注意:我认为有两个理由将此作为一个问题/特性请求报告给库维护者:
- 添加的代码将取决于
detail::dijkstra_bfs_visitor;这个名字暗示它不是公共接口 - 从概念上讲，BGL试图在算法和方面具有通用性数据结构;从算法参数中遗漏队列可能是疏忽