c++ - Boost Graph initialize_vertex 改变顶点颜色(访问者)

Question

我想构建一个访问者(用于 dikstra)，并将 initialise_vertex 用作“颜色映射”修饰符。我想根据条件从搜索中排除一些顶点。所以我想在算法的初始部分将一些顶点设置为“黑色”。

class dijkstra_2step : public boost::default_dijkstra_visitor
{
     public:
        dijkstra_2step(std::vector<Weight> dists, double threshold): distances(dists), threshold(threshold) {}

// THIS PART IS NOT CORRECT!!!! //
        void initialize_vertex(boost::graph_traits <unGraph>::vertex_descriptor u, const unGraph& g){
             if( distances[u] > threshold ) color[u] = black; // ??????
        }
//////////

     std::vector<Weight> distances;
     double threshold;
};

对上述访问者有什么帮助吗？如何访问颜色图？我在网上找不到任何东西。

Answer 1

你想要的大概是这样的:

在 Dijkstra 的情况下，您实际上可以将任意容器(例如 std::map 甚至 std::vector)作为颜色映射传递；你只需要正确包装它:

  #include "boost/graph/properties.hpp"   
  std::vector<int> colorMap(num_vertices(g), boost::white_color);

之后，您可以将此容器中的一些顶点标记为“黑色”。然后你必须调用 Dijkstra 的 dijkstra_shortest_paths_no_init 变体。

 dijkstra_shortest_paths_no_init(g, src, ..., ..., &colorMap[0]);

仅作记录，获取颜色图的标准方法是使用如下代码

boost::property_map< unGraph, boost::vertex_color_t >::type colorMap =
            boost::get(boost::vertex_color, g);

(前提是为给定的图形类型定义了此类 map )。

顺便说一句，您也可以使用 filtered_graph作为您的输入而不是 unGraph；您将必须提供一个顶点过滤器，它指定图中有哪些顶点。