Fruchterman Reingold的吸引力如何與Boost圖庫共同工作

Question

我正在學習Boost圖庫的Fruchterman-Reingold算法。通過閱讀文檔，我知道算法是根據圖形佈局計算所有節點的位置，但是我的問題是我無法理解Boost圖庫中吸引力的計算步驟。

例如，如果該拓撲結構是具有高度100和寬度100的矩形，每個頂點被標記爲字符串，並且每對頂點爲之間的關係：

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

每一行表示兩個標記的頂點是連接的。的每個頂點吸引力的公式應該是：

f = (d^2)/k 

其中d是兩個頂點和k之間的距離爲最佳距離。但我不明白如何在Boost Graph Library的Fruchterman-Reingold的代碼中獲得距離d。在這個例子中，它是否計算每對頂點之間的ASCII值差異爲距離d？ （'0'的ASCII值是48，'5'的ASCII值是53. Fruchterman-Reingold在BGL中計算53 - 48 = 5是真的嗎？）我非常感謝任何人都可以幫助我。

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