Как сила притяжения Fruchterman Reingold работает с Boost Graph Library

Я изучаю алгоритм Фрухтермана-Рейнгольда в Библиотеке графов ускорения. Читая документ, я знаю, что алгоритм состоит в том, чтобы вычислять позиции для всех узлов с точки зрения разметки графа, но моя проблема в том, что я не могу понять шаги вычисления сил притяжения в Boost Graph Library.

Например, если топология является прямоугольником с высотой 100 и шириной 100, каждая вершина помечается как строка, а отношение между каждой парной вершиной как:

"0"  "5""Kevin" "Martin""Ryan" "Leo""Y" "S""Kevin" "S""American" "USA"

Каждая строка обозначает две помеченные вершины связаны. Формула силы притяжения для каждой вершины должна быть:

f = (d^2) / k

где d это расстояние между двумя вершинами и k это оптимальные расстояния. Но я не понимаю, как пройти расстояние d в коде Фрухтермана-Рейнгольда в библиотеке графов ускорения. В этом примере он вычисляет разницу значений ASCII между вершинами каждой пары как расстояние d? (Значение ASCII, равное 0, равно 48, а значение ASCII, равное 5, равно 53. Верно ли, что Fruchterman-Reingold вычисляет 53 — 48 = 5 как d в BGL?) Я действительно ценю, если кто-нибудь может мне помочь.

3

Решение

Реализация Furchterman-Reingold использует топологию IN / OUT.

Ожидается, что топология будет инициализирована до некоторого состояния перед выполнением. Расстояние, пройденное до функции притяжения, будет тем же, что и в топологии на этой итерации.

Заметка Обратите внимание, что (если progressive установлен в trueFurterman-Reingold по умолчанию инициализирует топологию случайным образом (используя random_graph_layout).

Все вышеперечисленное взято из в документации.

Вот небольшая демонстрация, использующая ваш входной граф, который показывает, как реализовать такую ​​функцию average_force:

struct AttractionF {
template <typename EdgeDescriptor, typename Graph>
double operator()(EdgeDescriptor /*ed*/, double k, double d, Graph const& /*g*/) const {
//std::cout << "DEBUG af('" << g[source(ed, g)].name << " -> " << g[target(ed, g)].name << "; k:" << k << "; d:" << d << ")\n";
return (d*d/k);
}
};

Увидеть Жить на Колиру

#include <memory>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/fruchterman_reingold.hpp>
#include <boost/graph/random_layout.hpp>
#include <libs/graph/src/read_graphviz_new.cpp>
#include <boost/graph/topology.hpp>
#include <boost/random.hpp>

using namespace boost;

struct Vertex {
std::string name;
};

struct AttractionF {
template <typename EdgeDescriptor, typename Graph>
double operator()(EdgeDescriptor /*ed*/, double k, double d, Graph const& /*g*/) const {
//std::cout << "DEBUG af('" << g[source(ed, g)].name << " -> " << g[target(ed, g)].name << "; k:" << k << "; d:" << d << ")\n";
return (d*d/k);
}
};
using Graph = adjacency_list<vecS, vecS, undirectedS, Vertex>;

Graph make_sample();

int main() {
auto g = make_sample();

using Topology = square_topology<boost::mt19937>;
using Position = Topology::point_type;

std::vector<Position> positions(num_vertices(g));
square_topology<boost::mt19937> topology;

random_graph_layout(g,
make_iterator_property_map(positions.begin(), boost::identity_property_map{}),
topology);

fruchterman_reingold_force_directed_layout(
g,
make_iterator_property_map(positions.begin(), boost::identity_property_map{}),
topology,
attractive_force(AttractionF())
);

dynamic_properties dp;
dp.property("node_id", get(&Vertex::name, g));
write_graphviz_dp(std::cout, g, dp);
}

Graph make_sample() {
std::string const sample_dot = R"(
graph {
"0"        -- "5";
"Kevin"    -- "Martin";
"Ryan"     -- "Leo";
"Y"        -- "S";
"Kevin"    -- "S";
"American" -- "USA";
}
)";
Graph g;

dynamic_properties dp;
dp.property("node_id", get(&Vertex::name, g));

read_graphviz(sample_dot, g, dp);

return g;
}

Обратите внимание, что в C ++ 11 вы также можете использовать лямбду:

fruchterman_reingold_force_directed_layout(
g,
make_iterator_property_map(positions.begin(), boost::identity_property_map{}),
topology,
attractive_force([](Graph::edge_descriptor, double k, double d, Graph const&) { return (d*d)/k; })
);
3

Другие решения


По вопросам рекламы [email protected]