c++ - How does the attractive force of Fruchterman Reingold work with Boost Graph Library -

i learning fruchterman-reingold algorithm in boost graph library. reading document, know algorithm compute positions nodes in terms of graph layout, problem cannot understand calculation steps of attractive forces in boost graph library.

for example, if topology rectangle height 100 , width 100, each vertex labelled string, , relation between each pair vertex as:

"0"  "5" "kevin" "martin" "ryan" "leo" "y" "s" "kevin" "s" "american" "usa" 

each row denotes 2 labelled vertices connected. formula of attractive force each vertex supposed be:

f = (d^2) / k 

where d distance between 2 vertices , k optimal distances. don't understand how distance d in code of fruchterman-reingold in boost graph library. in example, compute ascii value difference between each pair vertices distance d? (ascii value of '0' 48, , ascii value of '5' 53. true fruchterman-reingold computes 53 - 48 = 5 d in bgl?) appreciate if can me.

furchterman-reingold implementation takes in/out topology.

it expects topology initialized state before execution. distance passed attraction function 1 topology @ iteration.

note note (unless progressive set true) furterman-reingold initialize topology randomly default (using random_graph_layout).

all above taken in documentation.

here's tiny demo using input graph shows how implement such attractive_force function:

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

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

note in c++11 can equally use lambda:

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