Теперь я хочу перейти от B к A. Я знаю, что это можно сделать с помощью [...]
Нет, код просто перечисляет вершины, даже без вершин и в произвольном порядке.
Когда я добираюсь до вершины A
Что значит «добраться до вершины А»? Вам нужен путь там, или вы просто собираетесь перечислить все вершины и ребра хода оттуда?
Я хочу иметь возможность рандомизировать строку из B, основываясь на некоторой математике на вес ребра от B до A
Я читаю это как «Я хочу вычислить строку на основе веса обнаруженных ребер и обновить строку метки для целевой вершины .
Это, по крайней мере, немного сбивает с толку, поскольку предлагает направление по краям неориентированного графа. Я предполагаю, что вы действительно хотите использовать направление (направление обхода во время обнаружения края).
И я знаю, как получить весовые коэффициенты, если перебрать этот путь: [... snip ...] Проблема в том, что он будет перебирать узлы графа и не обязательно заботиться о каком-либо из края.
Ха. Это полностью перевернуто. этот цикл делает итерации ребер, в частности. Вы меняли примеры кода?
Есть ли в надстройке что-то, что будет делать то, что я хочу?
Это не подлежит ответу, пока вы не знаете, чего хотите.
Я верю, что DFS - это то, что я хочу
Хорошо ... Давайте начнем немного:
Пример графика
Live On Coliru
#include <boost/graph/adjacency_list.hpp>
Давайте определим график, который может хранить метки (name) и веса:
struct Vertex { std::string name; };
struct Edge { double weight; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;
Теперь давайте распечатаем пример графика в формате Graphviz:
Graph make_sample();
void dump(Graph&);
int main() {
Graph g = make_sample();
dump(g);
}
Это немного похоже на читерство, но обычно помогает начать с общей картины и скрыть детали, поэтому давайте реализуем make_sample:
Graph make_sample() {
Graph g;
auto A = add_vertex({""}, g);
auto B = add_vertex({"Hello"}, g);
auto C = add_vertex({""}, g);
add_edge(A, B, {2.31}, g);
add_edge(B, C, {1.036}, g);
return g;
}
И dump:
#include <boost/graph/graphviz.hpp>
void dump(Graph& g) {
boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, g));
dp.property("label", get(&Vertex::name, g));
dp.property("label", get(&Edge::weight, g));
write_graphviz_dp(std::cout, g, dp);
}
График выглядит как это: 
Добавление DFS
Поиск прост:
#include <boost/graph/depth_first_search.hpp>
struct Visitor : boost::default_dfs_visitor {
};
void operate_on(Graph& g) {
Visitor vis;
std::vector<boost::default_color_type> color(num_vertices(g));
boost::depth_first_search(g, vis, color.data());
}
Но вы хотели сделать магию:
struct Visitor : boost::default_dfs_visitor {
void examine_edge(Graph::edge_descriptor e, const Graph& g) const {
std::cout << "Examining edge " << e << "\n";
}
};
Теперь уже печатаем:
Examining edge (0,1)
Examining edge (1,0)
Examining edge (1,2)
Examining edge (2,1)
Теперь давайте проверим свойства связанных вершин:
Vertex const& s = g[source(e, g)];
Vertex const& t = g[target(e, g)];
Теперь вы можете сделать некоторую логику:
if (s.name.empty() && !t.name.empty()) { // use your own logic here
std::cout << "Updating label for '" << t.name << "' in edge " << e << "\n";
}
Который уже печатает:
Updating label for 'Hello' in edge (0,1)
Updating label for 'Hello' in edge (2,1)
Запись - Доступ
Из соображений безопасности Graph получено const& в посетителе. Чтобы иметь возможность мутировать, нам нужна доступная для записи ссылка. Одним из способов является сохранение Graph& внутри посетителя:
struct Visitor : boost::default_dfs_visitor {
Graph& _g;
Visitor(Graph& g) : _g(g) {}
void examine_edge(Graph::edge_descriptor e, const Graph&) const {
// get vertex bundles
Vertex& s = _g[source(e, _g)];
Vertex& t = _g[target(e, _g)];
if (s.name.empty() && !t.name.empty()) { // use your own logic here
t.name += '(' + std::to_string(_g[e].weight) + ')';
}
return;
}
};
Возможно, более идиоматично было бы использовать Карты свойств - которые имеют похожий эффект:
struct Visitor : boost::default_dfs_visitor {
boost::property_map<Graph, std::string Vertex::*>::type _name;
boost::property_map<Graph, double Edge::*>::const_type _weight;
Visitor(Graph& g)
: _name(get(&Vertex::name, g)),
_weight(get(&Edge::weight, static_cast<Graph const&>(g)))
{ }
void examine_edge(Graph::edge_descriptor e, const Graph& g) const {
auto& sname = _name[source(e, g)];
auto& tname = _name[target(e, g)];
if (sname.empty() && !tname.empty()) { // use your own logic here
tname += '(' + std::to_string(_weight[e]) + ')';
}
return;
}
};
Предупреждение: доступ для записи во время алгоритма опасен. Будьте осторожны, чтобы не нарушить предварительные условия / инварианты алгоритма
Полная демонстрация
Live On Coliru
#include <boost/graph/adjacency_list.hpp>
struct Vertex { std::string name; };
struct Edge { double weight; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;
Graph make_sample();
void dump(Graph&);
void operate_on(Graph&);
int main() {
Graph g = make_sample();
operate_on(g);
dump(g);
}
Graph make_sample() {
Graph g;
auto A = add_vertex({""}, g);
auto B = add_vertex({"Hello"}, g);
auto C = add_vertex({""}, g);
add_edge(A, B, {2.31}, g);
add_edge(B, C, {1.036}, g);
return g;
}
#include <boost/graph/graphviz.hpp>
void dump(Graph& g) {
boost::dynamic_properties dp;
dp.property("node_id", get(boost::vertex_index, g));
dp.property("label", get(&Vertex::name, g));
dp.property("label", get(&Edge::weight, g));
write_graphviz_dp(std::cout, g, dp);
}
#include <boost/graph/depth_first_search.hpp>
struct Visitor : boost::default_dfs_visitor {
boost::property_map<Graph, std::string Vertex::*>::type _name;
boost::property_map<Graph, double Edge::*>::const_type _weight;
Visitor(Graph& g)
: _name(get(&Vertex::name, g)),
_weight(get(&Edge::weight, static_cast<Graph const&>(g)))
{ }
void examine_edge(Graph::edge_descriptor e, const Graph& g) const {
auto& sname = _name[source(e, g)];
auto& tname = _name[target(e, g)];
if (sname.empty() && !tname.empty()) { // use your own logic here
tname += '(' + std::to_string(_weight[e]) + ')';
}
}
};
void operate_on(Graph& g) {
Visitor vis { g };
std::vector<boost::default_color_type> color(num_vertices(g));
boost::depth_first_search(g, vis, color.data());
}
Печать:
graph G {
0 [label=""];
1 [label="Hello(2.310000)(1.036000)"];
2 [label=""];
0--1 [label=2.31];
1--2 [label=1.036];
}
Который выглядит как : 