如何Fruchterman莱因戈尔德的吸引力与Boost图库工作 [英] How does the attractive force of Fruchterman Reingold work with Boost Graph Library

问题描述

我学习的Fruchterman-莱因戈尔德算法加速图形库。通过阅读该文件，我知道，该算法是计算在图形布局上所有节点的位置，但我的问题是我无法理解Boost Graph库的计算步骤吸引力的。

I am learning the Fruchterman-Reingold algorithm in Boost Graph Library. By reading the document, I know that the algorithm is to compute the positions for all nodes in terms of graph layout, but my problem is I cannot understand the calculation steps of attractive forces in Boost Graph Library.

例如，如果该拓扑结构是矩形的高度100和宽度100中，每个顶点标记为字符串，并且每对顶点为之间的关系：

For example, if the topology is rectangle with height 100 and width 100, each vertex is labelled as string, and the relation between each pair vertex as:

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

每个行表示两个标记的顶点相连。的吸引力为每个顶点的公式应该是：

Each row denotes the two labelled vertices are connected. The formula of attractive force for each vertex is supposed to be:

f = (d^2) / k

其中， D 是两个顶点和 K 之间的距离为最佳距离。但我不知道如何得到Fruchterman-莱因戈尔德在Boost Graph库的code的距离 D 。在这个例子中，它计算的距离 D 每对顶点之间的ASCII值差？ （0的ASCII值是48，和5的ASCII值是53，这是真的Fruchterman-莱因戈尔德计算53 - 48 = 5为d的BGL）我真的AP preciate如果有人能帮助我的。

where d is the distance between two vertices and k is the optimal distances. But I don't understand how to get the distance d in the code of Fruchterman-Reingold in Boost Graph Library. In this example, does it compute the ASCII value difference between each pair vertices as the distance d? (ASCII value of '0' is 48, and ASCII value of '5' is 53. Is it true that Fruchterman-Reingold computes 53 - 48 = 5 as d in BGL?) I really appreciate if anyone can help me.

推荐答案

Furchterman-莱因戈尔德实施需要一个IN / OUT拓扑结构。

Furchterman-Reingold implementation takes an IN/OUT topology.

据预计，拓扑执行之前被初始化一些状态。传递给吸引功能的距离将是从拓扑在该迭代中之一。

It expects the topology to be initialized to some state before execution. The distance passed to the attraction function will be the one from the topology at that iteration.

注意请注意，（除非渐进设置为真）Furterman-莱因戈尔德将随机初始化拓扑默认情况下（使用 random_graph_layout ）。

Note Note that (unless progressive is set to true) Furterman-Reingold will initialize the topology randomly by default (using random_graph_layout).

以上所有取自文档

下面是一个使用你的输入图中的一个小小的演示，展示了如何实现这样一个attractive_force功能：

Here's a tiny demo using your input graph that shows how to implement such an 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);
        }
};

请参阅 <大骨节病> 住在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可以同样使用lambda：

Note that in c++11 you can equally well use a 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; })
        );

这篇关于如何Fruchterman莱因戈尔德的吸引力与Boost图库工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！