3

Boost Graph Library で Fruchterman-Reingold アルゴリズムを学習しています。ドキュメントを読むと、グラフ レイアウトに関してすべてのノードの位置を計算するアルゴリズムであることがわかりますが、Boost Graph Library の引力の計算手順が理解できないという問題があります。

たとえば、トポロジが高さ 100、幅 100 の長方形の場合、各頂点は文字列としてラベル付けされ、各ペア頂点間の関係は次のようになります。

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

各行は、2 つのラベル付き頂点が接続されていることを示します。各頂点の引力の式は次のようになります。

f = (d^2) / k

ここdで、 は 2 つの頂点間の距離で、kは最適な距離です。dしかし、Boost Graph Library の Fruchterman-Reingold のコードで距離を取得する方法がわかりません。この例では、各ペアの頂点間の ASCII 値の差を距離として計算しdますか? ('0' の ASCII 値は 48 で、'5' の ASCII 値は 53 です。Fruchterman-Reingold が 53 - 48 = 5 を BGL の d として計算するというのは本当ですか?)

4

1 に答える 1

3

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

#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; })
        );
于 2015-04-23T12:07:21.793 に答える