Boost DFS 如何保存访问过的顶点？

问题描述 投票：0回答：2

我正在查看解决方案here，这对我不起作用（但请阅读 === 行以实际查看当前问题）。

我尝试过：

boost::undirected_dfs(G, vertex(0,G), boost::visitor(vis));

但我明白了

error C2780: 'void boost::undirected_dfs(const Graph &,const boost::bgl_named_params<P,T,R> &)' : expects 2 arguments - 3 provided
error C2780: 'void boost::undirected_dfs(const Graph &,DFSVisitor,VertexColorMap,EdgeColorMap)' : expects 4 arguments - 3 provided

等等。我有点明白问题是什么（我需要向它传递一些命名参数，但我认为我的图表中没有任何参数。另外，我根本不明白颜色图的处理是什么.

====================================================== ==============================

我的图表已定义：

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeInfoProperty > Graph;
typedef Graph::edge_descriptor Edge;
typedef Graph::vertex_descriptor Vertex;

我只想做 DFS，至少现在是这样。

所以我把它改成了

boost::depth_first_search
，看起来好像有效了。

我有（注意 

const
与上面链接的解决方案相比缺少 
void discover_vertex
）：

class MyVisitor : public boost::default_dfs_visitor {
public:
    void discover_vertex(Vertex v, const Graph& g)  { //note the lack of const
        if(boost::in_degree(v,g)!=0){ //only print the vertices in the connected component (I already did MCC and removed edges so all the extra vertices are isolated)
            std::cerr << v << std::endl;
            vv.push_back(v);
        }
        return;
    }
    std::vector<Vertex> GetVector() const  { return vv; }
private: 
    std::vector<Vertex> vv;
};

如果我离开 

const
那里，我就会得到 
error C2663: 'std::vector<_Ty>::push_back' : 2 overloads have no legal conversion for 'this' pointer with [  _Ty=size_t  ]
。

现在，这工作正常，或者至少它以正确的顺序打印出正确访问的顶点：

MyVisitor vis;
boost::depth_first_search(G, boost::visitor(vis));

但是当我这样做时：

std::vector<Vertex> vctr = vis.GetVector();
std::cout<<vctr.size();

尺寸为零，因为我的

vv
没有改变...

那么，当类用作 

boost::visitor
的参数时，如何获得适当的类行为？ （我什至不确定这是一个合适的问题）。我需要能够根据之前访问过的节点（或者更确切地说，根据 DFS 遍历中当前顶点的父顶点是哪个顶点，所以这可能只是实现这一点的第一步）来更改 
EdgeInfoProperty
。

c++ boost graph depth-first-search
2个回答
3
投票

访问者是按值传递的，因此您需要与复制到函数调用中的 MyVisitor 实例共享它所保存的向量。

试试这个：

class MyVisitor : public boost::default_dfs_visitor {
public:
    MyVisitor(): vv(new std::vector<Vertex>()){}

    void discover_vertex(Vertex v, const Graph& g)  { //note the lack of const
        if(boost::in_degree(v,g)!=0){ //only print the vertices in the connected component (I already did MCC and removed edges so all the extra vertices are isolated)
            std::cerr << v << std::endl;
            vv->push_back(v);
        }
        return;
    }
    std::vector<Vertex>& GetVector() const  { return *vv; }
private: 
    boost::shared_ptr< std::vector<Vertex> > vv;
};
0
投票

也可以使用全局变量或静态数据成员来存储遍历结果。

全局变量

Coliru 直播

这种方法非常通用，但也感觉有点快速和肮脏。请注意，在开始新的遍历之前，您需要重置

g_vertices
。使用全局变量和带有 
Visitor
方法的 
void operator()(...)
模板有两个好处。

  1. 您可以使用 
    EventVisitor
     在前序和后序遍历之间切换，甚至可以将其扩展到其他事件。
  2. 我将访问者命名为 
    MyVisitor
    ，而不是更严格的 
    MyDFSVisitor
    ，因为您还可以将其应用于其他 Boost Graph Library 算法，例如 
    breadth_first_search()
    。
// Pre-order and post-order DFS traversal on an undirected graph with a global
// variable
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>

using MyGraph = boost::adjacency_list<
    boost::listS, boost::vecS, boost::undirectedS,
    boost::property<boost::vertex_color_t, boost::default_color_type>>;
using MyVertex = boost::graph_traits<MyGraph>::vertex_descriptor;

namespace {
// Global variable to store traversal results
std::vector<MyVertex> g_vertices;
} // namespace

template <typename Event> struct MyVisitor : public boost::null_visitor {
  // Capture event type to allow both pre-order and post-order traversal
  using event_filter = Event;

  template <typename Vertex, typename Graph>
  void operator()(Vertex v, const Graph &g) {
    g_vertices.push_back(v);
  }
};

int main() {
  MyGraph g{};
  boost::add_edge(0, 1, g);
  boost::add_edge(0, 2, g);
  boost::add_edge(1, 2, g);
  boost::add_edge(1, 3, g);

  auto root = boost::vertex(0, g);
  auto color_map = boost::get(boost::vertex_color, g);

  {
    // Pre-order [0, 1, 2, 3]
    std::cout << "pre-order traversal:\n";
    auto vis = boost::make_dfs_visitor(MyVisitor<boost::on_discover_vertex>());
    boost::depth_first_search(g, vis, color_map, root);
    for (auto v : g_vertices) {
      std::cout << v << std::endl;
    }
    g_vertices.clear();
  }
  {
    // Post-order [2, 3, 1, 0]
    std::cout << "post-order traversal:\n";
    auto vis = boost::make_dfs_visitor(MyVisitor<boost::on_finish_vertex>());
    boost::depth_first_search(g, vis, color_map, root);
    for (auto v : g_vertices) {
      std::cout << v << std::endl;
    }
    g_vertices.clear();
  }
}

静态数据成员

在这里，我将 

MyDFSVisitor
编写为模板结构，以使其更容易转移到其他用例。

Coliru 直播

// Pre-order and post-order DFS traversal on an undirected graph with a static
// data member
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>

using MyGraph = boost::adjacency_list<
    boost::listS, boost::vecS, boost::undirectedS,
    boost::property<boost::vertex_color_t, boost::default_color_type>>;

using MyVertex = boost::graph_traits<MyGraph>::vertex_descriptor;

template <typename Vertex>
struct MyDFSVisitor : public boost::default_dfs_visitor {
  inline static std::vector<Vertex> m_preorder_vertices;
  inline static std::vector<Vertex> m_postorder_vertices;

  // pre-order traversal
  template <typename Graph> void discover_vertex(Vertex v, const Graph &g) {
    m_preorder_vertices.push_back(v);
  }

  // post-order traversal
  template <typename Graph> void finish_vertex(Vertex v, const Graph &g) {
    m_postorder_vertices.push_back(v);
  }
};

int main() {
  MyGraph g{};
  boost::add_edge(0, 1, g);
  boost::add_edge(0, 2, g);
  boost::add_edge(1, 2, g);
  boost::add_edge(1, 3, g);

  auto root = boost::vertex(0, g);
  auto color_map = boost::get(boost::vertex_color, g);

  MyDFSVisitor<MyVertex> vis;
  boost::depth_first_search(g, vis, color_map, root);
  std::cout << "Pre-order traversal : \n"; // 0 1 2 3
  for (auto v : vis.m_preorder_vertices) {
    std::cout << v << std::endl;
  }
  std::cout << "Post-order traversal : \n"; // 2 3 1 0
  for (auto v : vis.m_postorder_vertices) {
    std::cout << v << std::endl;
  }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.