提升DFS如何保存访问顶点？ [英] Boost DFS how to save visited vertices?

问题描述

我在寻找解决方案这里，这对我不起作用（但是在===行下阅读才能看到当前的问题）。

I尝试：

  boost :: undirected_dfs（G，vertex（0，G），boost :: visitor（vis））; 
  

但是我得到

  error C2780：'void boost :: undirected_dfs（const Graph&，const boost :: bgl_named_pa​​rams< P，T，R&&）'：期望2个参数 -  3提供
错误C2780 ：'void boost :: undirected_dfs（const Graph&，DFSVisitor，VertexColorMap，EdgeColorMap）'：需要4个参数 -  3提供
  

等。我想问一下问题是什么（我需要传递一些命名参数，但我认为我的图中没有任何内容，另外，我也没有得到与彩色地图有关的交易，完全没有。

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

我的图被定义为：

pre $ typedef boost :: adjacency_list< boost :: listS，boost： ：vecS，boost :: undirectedS，boost :: no_property，EdgeInfoProperty>图;
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（V ertex v，const Graph& g）{//注意缺少const 
 if（boost :: in_degree（v，g）！= 0）{//只打印连接组件中的顶点（我已经完成了MCC并删除了所有边额外的顶点是孤立的）
 std :: cerr<< v<的std :: ENDL; 
 vv.push_back（v）; 
} 
 return; 
} 
 std :: vector< Vertex> GetVector（）const {return vv; } 
 private：
 std :: vector< Vertex> VV; 
}; 
  

如果我离开 const code> error C2663：'std :: vector< _Ty> :: push_back'：2重载对'this'指针没有合法的转换，[_Ty = size_t] 。

现在，这可以正常工作，或者至少按照正确的顺序打印右侧访问的顶点：

  MyVisitor vis; 
 boost :: depth_first_search（G，boost :: visitor（vis））; 
  

但是当我这样做时：

 的std ::矢量<顶点> vctr = vis.GetVector（）; 
 std :: cout<< vctr.size（）; 
  

大小为零，因为我的 vv 不会改变...

那么，如何在类用作 boost :: boost的参数时获得适当的类行为？访问者？ （我甚至不确定这是合适的问题）。我需要能够根据之前访问的节点（或者基于哪个顶点是DFS遍历中当前顶点的父节点）来更改 EdgeInfoProperty ，所以这会可能只是第一步）。

解决方案

访问者是按值传递的，所以你需要分享它的向量

试试这个：

  class MyVisitor：public boost :: default_dfs_visitor {
 public：
 MyVisitor（）：vv（new std :: vector< Vertex>（））{} 
 
 void discover_vertex（Vertex v，const Graph& g）{//注意缺少const 
 if（boost :: in_degree（v，g）！= 0）{//只打印连接组件中的顶点我已经做了MCC并删除了所有额外顶点的边缘）
 std :: cerr<< v<的std :: ENDL; 
 vv-> push_back（v）; 
} 
 return; 
} 
 std :: vector< Vertex>& GetVector（）const {return * vv; } 
 private：
 boost :: shared_ptr<的std ::矢量<顶点> > VV; 
}; 
  

I'm looking at the solution here, which doesn't work for me (but read under the === line to actually see the current problem).

I tried:

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

but I get

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

etc. I sort of get what the problem is (I need to pass it some named parameters, but I don't have any in my graph, I think. Also, I don't get what the deal with the color maps is, at all.

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

My graph is defined:

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;

All I want is to do DFS, at least for now.

So I changed it to boost::depth_first_search, and it seems to work.

I have (note the lack of const for void discover_vertex vs. the solution linked above):

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;
};

If I leave const there I get error C2663: 'std::vector<_Ty>::push_back' : 2 overloads have no legal conversion for 'this' pointer with [ _Ty=size_t ].

Now, this works fine or at least it prints out the right visited vertices, in the right order:

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

But when I do:

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

the size is zero, because my vv doesn't change...

So, how can I get the appropriate class behavior when the class is used as an argument to boost::visitor? (I'm not even sure this is the appropriate question). I need to be able to change EdgeInfoProperty based on which nodes were visited before (or rather based on which vertex is the parent of the current vertex in the DFS traversal, so this would probably just be a first step towards that).

解决方案

The visitor is passed by value, so you need to share the vector it holds with the instance of MyVisitor copied into the function call.

Try this:

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;
};

这篇关于提升DFS如何保存访问顶点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！