CODEWITHSUNDEEP
c++boost
Kong
Kong

Reputation: 2410

Boost Graph Library - Depth First Search only through connected vertices

I am trying to run a DFS through my graph which has multiple disjoint graphs. I'd like to specify the start vertex and have the DFS only traverse through that tree, keeping the vertex ID visited in a vector. To do this, I would need the depth_first_visit function http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/depth_first_visit.html

The function requires me to initialize a color map and I am clueless in doing it because I also have a custom vertex and a custom edge. The best example I got was from this and this post which talks about depth first search not depth first visit. If I were to replace the vertex with the structure I used then it would be the code below.

So to reiterate, I'm clueless as to how I should initialize a color map and set the start vertex for a custom vertex type. I hope someone can give me a simple example. Been googling the past several hours but couldn't find an example.

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

Upvotes: 2

Views: 2503

Answers (1)

sehe
sehe

Reputation: 392833

Simplest approach is to create a vector to contain a color for each vertex.

Simplest way to achieve that is:

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

Which you then pass like

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

That's equivalent to using the named parameter idiom like:

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

To also supply a start vertex, simply use that overload:

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

Prints

1 0 2 3 4 5 6 8 7

Upvotes: 3

Related Questions