graph dfs_visitor Sınıfı

Giriş
Şu satırları dahil ederiz.

#include <boost/graph/undirected_dfs.hpp>
#include <boost/graph/visitors.hpp>

Elimizde bir grah olsun

typedef boost::adjacency_list<
    boost::vecS,                        //OutEdgeList
    boost::vecS,                        //VertexList
    boost::undirectedS                  //Directed
> Graph;

typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
typedef boost::graph_traits < Graph >::edge_descriptor Edge;

Tanımlama
Şöyle yaparız.

struct detect_loops : public boost::dfs_visitor<>
{
  template <class Graph>
  void tree_edge(Edge e, const Graph& g) {
    ...
  }

  template <class Graph>
  void back_edge(Edge e, const Graph& g) {
    ...
  }

private:
  ...
};

Ayrıca şöyle yaparız.

struct detect_loops : public boost::dfs_visitor<>
{
  using colormap=std::map<Graph::vertex_descriptor, boost::default_color_type>;
  colormap vertex_coloring;

  using edgeColorMap=std::map<Graph::edge_descriptor, boost::default_color_type>;
  edgeColorMap  edge_coloring;
  ...
}

undirected_dfs metodu

Şu satırı dahil ederiz.

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

Açıklaması şöyle

This algorithm needs color values on vertices and edges to keep track of the ones that have been parsed.

Örnek
Birinci parametre graph, ikinci parametre visitor, üçüncü parametre vertex associated map, dördüncü parametre edge associated map nesnesidir. Şöyle yaparız.

Graph g;
detect_loops vis;

boost::undirected_dfs (g, vis ,
  make_assoc_property_map (vis.vertex_coloring),
  make_assoc_property_map (vis.edge_coloring)
);

Örnek
Graph şöyledir

struct my_vertex { int a1; float a2; };
struct my_edge   { int b1; float b2; };

typedef adjacency_list<vecS, vecS, undirectedS, my_vertex, my_edge> graph_t;

Visitor şöyledir.

struct detect_loops : public boost::dfs_visitor<> {
  template <class Edge, class Graph>
  void back_edge(Edge e, const Graph& g) {
    std::cout << g[source(e,g)].a1 << " -- " << g[target(e,g)].a1 << "\n";
  }
};

Birinci parametre graph, ikinci parametre visitor, üçüncü parametre vertex associated map, dördüncü parametre edge associated map nesnesidir, beşinci parametre başlangıç düğümüdür. Parametreleri atamak için şöyle yaparız.

std::vector<default_color_type> vertex_color(num_vertices(g));
std::map<graph_t::edge_descriptor, default_color_type> edge_color;

auto idmap = get(vertex_index, g);
auto vcmap = make_iterator_property_map(vertex_color.begin(), idmap);
auto ecmap = make_assoc_property_map(edge_color);

graph_t::vertex_descriptor const start = 0;

Şöyle yaparız.

undirected_dfs(g, vis, vcmap, ecmap, start);

named-argument olarak çağırmak için şöyle yaparız.

undirected_dfs(g, 
        root_vertex(graph_t::vertex_descriptor(0))
        .visitor(vis)
        .vertex_color_map(vcmap)
        .edge_color_map(ecmap)
    );