首页 文章

Boost Graph Library - Depth First仅通过连接的顶点搜索

提问于
浏览 次
1

我试图通过我的图形运行DFS，其中有多个不相交的图形 . 我想指定起始顶点并使DFS仅遍历该树，保持在向量中访问的顶点ID . 要做到这一点，我需要depth_first_visit函数http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/depth_first_visit.html

该函数需要我初始化一个颜色贴图，我无能为力，因为我还有一个自定义顶点和一个自定义边 . 我得到的最好的例子是this和this帖子，其中讨论了深度优先搜索而不是深度第一次访问 . 如果我用我使用的结构替换顶点那么它将是下面的代码 .

所以重申一下，我对如何初始化颜色图并为自定义顶点类型设置起始顶点一无所知 . 我希望有人可以给我一个简单的例子 . 谷歌搜索过去几个小时，但找不到一个例子 .

// Boost DFS example on an undirected graph.
// Create a sample graph, traverse its nodes
// in DFS order and print out their values.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
using namespace std;

//======================================================================================================
//information representing each vertex
struct Vertex {

public:

    //id
    int id = 0;
    int parent_id = -1;
    int l_child = -1, r_child = -1;

    Vertex(int id = -1) : id(id) {}
};

//======================================================================================================
//information representing each weight
//it carries the boundary length and also the distance
struct Edge {

    //distance
    float boundary_length = 0;
    float weight = 1;
    //float L, a, b = 1;

    Edge(float boundary_length = 1) : boundary_length(boundary_length) {}
};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex, Edge> Graph;

class MyVisitor : public boost::default_dfs_visitor
{
public:

    MyVisitor() : vv(new std::vector<int>()) {}

    void discover_vertex(int v, const Graph& g) const
    {
        vv->push_back(g[v].id);
        return;
    }

    std::vector<int>& GetVector() const { return *vv; }

    private:
    boost::shared_ptr< std::vector<int> > vv;
};

int main()
{

  Graph 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);

  boost::add_edge(5, 6, g);
  boost::add_edge(5, 8, g);

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

  std::vector<int> vctr = vis.GetVector();

  return 0;
}
c++ boost

1 回答

  • 1

    最简单的方法是创建一个向量来包含每个顶点的颜色 .

    最简单的方法是：

    auto indexmap = boost::get(boost::vertex_index, g);
auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

    你然后传递的那样

    boost::depth_first_search(g, vis, colormap);

    这相当于使用命名参数idiom，如：

    boost::depth_first_search(g, boost::visitor(vis) .color_map(colormap));

    要提供起始顶点，只需使用该重载：

    boost::depth_first_search(g, vis, colormap, 1);

    Live On Coliru

    #include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
using namespace std;

//======================================================================================================
// information representing each vertex
struct Vertex {

    int id = 0;
    int parent_id = -1;
    int l_child = -1, r_child = -1;

    Vertex(int id = -1) : id(id) {}
};

//======================================================================================================
// information representing each weight
// it carries the boundary length and also the distance
struct Edge {

    // distance
    float boundary_length = 0;
    float weight = 1;
    // float L, a, b = 1;

    Edge(float boundary_length = 1) : boundary_length(boundary_length) {}
};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, Vertex, Edge> Graph;

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

    void discover_vertex(int v, const Graph &g) const {
        vv->push_back(g[v].id);
        return;
    }

    std::vector<int> &GetVector() const { return *vv; }

  private:
    boost::shared_ptr<std::vector<int> > vv;
};

int main() {

    Graph 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);

    boost::add_edge(5, 6, g);
    boost::add_edge(5, 8, g);

    for (auto v : boost::make_iterator_range(boost::vertices(g)))
        g[v] = Vertex(v);

    auto indexmap = boost::get(boost::vertex_index, g);
    auto colormap = boost::make_vector_property_map<boost::default_color_type>(indexmap);

    MyVisitor vis;
    boost::depth_first_search(g, vis, colormap, 1);

    std::vector<int> vctr = vis.GetVector();

    for(auto id : vctr)
        std::cout << id << " ";
}

    打印

    1 0 2 3 4 5 6 8 7
    回复于

相关问题