Fruchterman Reingold的吸引力如何与Boost Graph Library一起使用

一尘不染

Fruchterman Reingold的吸引力如何与Boost Graph Library一起使用

algorithm

我正在学习Boost Graph库中的Fruchterman-
Reingold算法。通过阅读文档，我知道算法是根据图形布局计算所有节点的位置，但是我的问题是我无法理解Boost Graph
Library中引力的计算步骤。

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

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

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

f = (d^2) / k

其中d，两个顶点之间的距离k是最佳距离。但是我不明白如何d在Boost Graph库中的Fruchterman-
Reingold代码中获得距离。在此示例中，是否将每对顶点之间的ASCII值差计算为距离d？（ASCII值“ 0”为48，ASCII值“
5”为53。Fruchterman-Reingold是否按BGL中的d计算53-48 = 5是真的吗？）如果有人可以帮助我，我非常感谢。

阅读 310

2020-07-28

共1个答案

一尘不染

Furchterman-Reingold实现采用IN / OUT拓扑。

它期望拓扑在执行之前被初始化为某种状态。传递给吸引函数的距离将是该迭代中距拓扑的距离。

注意请 注意，（除非progressive设置为true），Furterman-
Reingold将默认情况下（使用random_graph_layout）随机初始化拓扑。

以上所有内容均取自文档。

这是一个使用您的输入图的小演示，该演示演示了如何实现这种有吸引力的函数：

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](http://coliru.stacked- crooked.com/a/9aa6e4e16574db76)

#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：

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

2020-07-28