boost.graph：fruchterman_reingold_force_directed_layout导致节点卡在左上角

Question

我在fruchterman_reingold_force_directed_layout算法上遇到了一些问题。

• 许多节点总是最终在左上角包装。
• 如果我使用非矩形拓扑，我只会得到NAN的位置。
• 布局完全根据初始位置变化；我看到的其他实现似乎总是融合到相同的最终位置。

这是我的布局代码，我在做什么错？：

using edge_property_t = boost::property<boost::edge_weight_t, float>;
using graph_t         = boost::adjacency_list<boost::vecS,
                                      boost::vecS,
                                      boost::directedS,
                                      boost::no_property,
                                      edge_property_t>;
using topology_type   = boost::rectangle_topology<std::mt19937>;
using point_type      = topology_type::point_type;

using pos_map = boost::iterator_property_map<
    std::vector<point_type>::iterator,
    boost::property_map<graph_t, boost::vertex_index_t>::type>;

graph_t graph_;
pos_map position_;
 
const auto N = 1234; // vertex count
std::vector<point_type> targetPositions_(N);

// ... vertices are added to the graph ... //
// ... positions are randomized in an initial step ... //

position_ = pos_map{targetPositions_.begin(), get(boost::vertex_index, graph_)};

topology_type topo{0,0,1000,1000};

const auto attraction =
    [this](auto e, double k, double d, const auto& g) -> double {
    return this->attraction_ * std::pow(d, this->attractionPower_) / k;
};
const auto repulsion =
    [this](auto v1, auto v2, double k, double d, const auto&) -> double {
    return this->repulsion_ * std::pow(k, this->repulsionPower_) / d;
};

const auto force_pairs = all_force_pairs();
const auto cooling = linear_cooling<double>(this->coolingIterations_, this->coolingTemp_);

auto displacements = std::vector<typename topology_type::point_difference_type>(N);
fruchterman_reingold_force_directed_layout(
    graph_, // graph_t
    position_, // pos_map
    topo,
    attraction,
    repulsion,
    force_pairs,
    cooling,
    make_iterator_property_map(displacements.begin(),
                               boost::identity_property_map{}));

我尝试了各种值的吸引力和排斥常数，但无法使任何远程满足。

Answer 1

我已经拿走了您的（原始）代码，并使其独立。然后，我继续添加逐帧输出。在高温下看起来确实很忙，但是当它冷却时，一切看起来都很好。

这是一个可管理的尺寸：

在编译器探险家

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/fruchterman_reingold.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/random_layout.hpp>
#include <boost/graph/topology.hpp>
#include <boost/progress.hpp>
#include <random>

using edge_property_t = boost::property<boost::edge_weight_t, float>;
using graph_t         = boost::adjacency_list<boost::vecS,
                                    boost::vecS,
                                    boost::directedS,
                                    boost::no_property,
                                    edge_property_t>;
using topology_type   = boost::rectangle_topology<std::mt19937>;
using point_type      = topology_type::point_type;

using pos_map = boost::iterator_property_map<
    std::vector<point_type>::iterator,
    boost::property_map<graph_t, boost::vertex_index_t>::type>;

using Layout = std::vector<point_type>;

static void save_frame(std::string_view caption, int number, auto const& g,
                    auto const& posmap, topology_type const& topo) {
    std::stringstream graphprops;
    graphprops << std::setprecision(3) << std::fixed;

    {
        auto x1 = topo.origin()[0];
        auto y1 = topo.origin()[1];
        auto x2 = x1 + topo.extent()[0];
        auto y2 = y1 + topo.extent()[1];

        graphprops << "bb=\"" << x1 << "," << y1 << "," << x2 << "," << y2 << "\";\n";
    }
    graphprops << "label=" << std::quoted(caption) << ";\n";

    struct {
        decltype(g)                    g_;
        std::decay_t<decltype(posmap)> p_;
        std::string                    gp_;

        void operator()(std::ostream& os, graph_t::vertex_descriptor v) const {
            auto& pos = p_[v];

            os << "[label=vertex]";
            os << "[pos=\"" << pos[0] << "," << pos[1] << "!\"]";
        }
        void operator()(std::ostream& os, graph_t::edge_descriptor e) const {
            os << "[label=" << get(boost::edge_weight, g_, e) << "]";
        }
        void operator()(std::ostream& os) const { os << gp_; }
    } w{g, posmap, graphprops.str()};

    std::ofstream ofs("frame_" + std::to_string(number) + ".dot");
    ofs << std::setprecision(3) << std::fixed;
    write_graphviz(ofs, g, w, w, w);
}

struct QuestionCode {

    struct Impl {
        graph_t& graph_;
        Layout   position_storage_{boost::num_vertices(graph_)};

        pos_map position_ = boost::
            make_iterator_property_map( // prefer
                                        // make_safe_iterator_property_map!
                position_storage_.begin() /*, position_storage_.size()*/,
                get(boost::vertex_index, graph_));
    };

    float attraction_      = 0.5;
    int   attractionPower_ = 2;
    float repulsion_       = 0.6;
    int   repulsionPower_  = 3;

    size_t coolingIterations_ = 100;
    double coolingTemp_       = 5.0;

    Layout do_layout(graph_t& g) {
        // ... positions are randomized in an initial step ... //
        auto impl_ = std::make_unique<Impl>(Impl{g});

        //topology_type topo{0, 0, 10, 10};
        topology_type topo{-5, -5, 5, 5};
        random_graph_layout(impl_->graph_, impl_->position_, topo);

        const auto attraction =
            [this](auto /*e*/, double k, double d, const auto& /*g*/) -> double {
                return this->attraction_ * std::pow(d, this->attractionPower_) / k;
            };
        const auto repulsion =
            [this](auto /*v1*/, auto /*v2*/, double k, double d, const auto&) -> double {
                return this->repulsion_ * std::pow(k, this->repulsionPower_) / d;
            };

        boost::linear_cooling<double> linear_cooling(coolingIterations_, coolingTemp_);
        boost::progress_display progress(coolingIterations_ + 1, std::cerr);

        const auto cooling = [&, frame_number = 0]() mutable {
            ++progress;
            auto current_temp = linear_cooling();
            save_frame("temperature: " + std::to_string(current_temp),
                    frame_number++, impl_->graph_, impl_->position_, topo);
            return current_temp;
        };

        auto displacements =
            std::vector</*typename*/ topology_type::point_difference_type>(num_vertices(g));

        auto idmap = get(boost::vertex_index, g); // identity iff vecS

        fruchterman_reingold_force_directed_layout(
            impl_->graph_,            // graph_t
            impl_->position_,         // pos_map
            topo,                     //
            attraction,               //
            repulsion,                //
            boost::all_force_pairs{}, //
            cooling,                  //
            make_safe_iterator_property_map(displacements.begin(),
                                            displacements.size(), idmap));

        return impl_->position_storage_;
    }
};

int main() {
    graph_t g;

    std::mt19937 prng{std::random_device{}()};
    generate_random_graph(g, 10, 20, prng, false);
    std::uniform_real_distribution<float> weights(0, 5);
    for (auto e : boost::make_iterator_range(edges(g)))
        put(boost::edge_weight, g, e, weights(prng));

    Layout layout;
    {
        QuestionCode so;
        layout = so.do_layout(g);
    }
}

时

rm frame_*; ./sotest; time (for a in {0..101}; do neato -Tpng -o frame_$a.png frame_$a.dot; done  && convert frame_{0..101}.png test.gif && gifsicle -O9 -k2 test.gif -o small.gif)

，

0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
***************************************************

real    0m17,135s
user    0m20,336s
sys     0m1,655s

测试 small.gif喜欢：

​始终使用-fsanitize = undefined，地址构建。