How Fruchterman Reingold's Attractive Power Works with the Boost Graph Library

I am learning the Fruchterman-Reingold algorithm in the Boost Graph Library. While reading the document, I know that the algorithm is to calculate the positions for all nodes in terms of the graphical layout, but my problem is that I cannot figure out the steps for calculating gravity in the Boost Graph Library.

For example, if the topology is a rectangle with a height of 100 and a width of 100, each vertex is labeled as a row, and the ratio between each paired vertex is:

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

      

Each line indicates that the two marked vertices are connected. The gravity formula for each vertex should be:

f = (d^2) / k

      

where d

is the distance between two vertices, and k

are the optimal distances. But I don't understand how to get distance d

in Fruchterman-Reingold code in Boost Graph Library. In this example, it calculates the difference in ASCII values ​​between each vertex of a pair as a distance d

? (The ASCII value "0" is 48 and the ASCII value "5" is 53. Is it true that Fruchtermann-Reingold computes 53 - 48 = 5 as d in BGL?) I really appreciate if anyone can help me.

+3


source to share


1 answer


The Furchterman-Reingold implementation accepts an IN / OUT topology.

It expects the topology to be initialized to some state before executing. The distance traveled by the attraction function will be the unit from the topology at this iteration.

Note Please note that (if progressive

not set to true

) Furterman-Reingold will initialize the topology randomly by default (using random_graph_layout

).

Everything above is taken from in the documentation .

Here's a tiny demo using your input graph that shows how to implement an attractive_force function like this:



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

      

Cm. 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 that in C ++ 11 you can also 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; })
        );

      

+3


source







All Articles