graph depth_first_search metodu

Giriş
Şu satırı dahil ederiz.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

boost::dfs_visitor veya boost::default_dfs_visitor kullanarak graph'ı dolaşır.

Kullanım
Şöyle yaparız.

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

Daha sonra şöyle yaparız. graph + visitor + colormap parametre olarak verilir.

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

Eğer istersek named parameter olarak ta kullanabiliriz. Şöyle yaparız.

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

Başlangıç vertex'i vermek istersek şöyle yaparız.

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

Örnek
Elimizde şöyle bir graph olsun.

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

Bu graph'ı dolduralım.

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

Elimizde bir visitor olsun.

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

Bir colormap tanımlayalım.

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

DFS sonucunu almak için şöyle yaparız.

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

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

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