Как привлекательная сила Fruchterman Reingold работает с библиотекой Boost Graph

Question

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

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

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

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

f = (d^2)/k 

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

Answer 1

Реализация Furchterman-Reingold принимает топологию IN/OUT.

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

Примечание Обратите внимание, что (если progressive не установлен в true) Furterman-Рейнгольд будет инициализировать топологию случайным образом по умолчанию (с использованием random_graph_layout).

Все вышеизложенное взято из in the documentation.

Вот крошечная демо с помощью графика ввода, который показывает, как реализовать такую ​​функцию attractive_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); 
     } 
}; 

См Live On Coliru

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