c++ - Kamada-Kawai 布局的停止条件

Question

我正在使用以下代码获取 Kamada-Kawai 布局:

template <class PointMap>
PointMap layout() const {
    PointMap res;
    boost::associative_property_map<PointMap> temp(res);

    minstd_rand gen;
    rectangle_topology<> rect_top(gen, 0, 0, 50, 50);
    random_graph_layout(g_, temp, rect_top); // random layout to show that
                                             // Kamada-Kawai isn't doing the job

    // circle_graph_layout(g_, temp, 10.0);

    // http://stackoverflow.com/q/33903879/2725810
    // http://stackoverflow.com/a/8555715/2725810
    typedef std::map<VertexDescriptor, std::size_t> IndexMap;
    IndexMap mapIndex;
    associative_property_map<IndexMap> propmapIndex(mapIndex);
    // http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/bundles.html
    kamada_kawai_spring_layout(
        g_, temp,
        boost::make_transform_value_property_map([](int i)
                                                     ->double { return i; },
                                                 get(edge_bundle, g_)),
        //get(edge_bundle, g_),
        square_topology<>(50.0), side_length(50.0),
        //layout_tolerance<CostType>(0.01),
        kamada_kawai_done(),
        CostType(1), propmapIndex);

    return res;
}

使用了以下类型:

• 图表类型为:

  boost::adjacency_list<vecS, setS, undirectedS, State, CostType>;
  

  哪里CostType是int .

• PointMap是:

  std::map<VertexDescriptor, square_topology<>::point_type>
  

这是我使用的停止条件:

struct kamada_kawai_done
{
    kamada_kawai_done() : last_delta() {}

    template<typename Graph>
    bool operator()(double delta_p,
                    typename boost::graph_traits<Graph>::vertex_descriptor /*p*/,
                    const Graph& /*g*/,
                    bool global)
    {
        if (global) {
            double diff = last_delta - delta_p;
            if (diff < 0) diff = -diff;
            std::cout << "delta_p: " << delta_p << std::endl;
            last_delta = delta_p;
            return diff < 0.01;
        } else {
            return delta_p < 0.01;
        }
    }

    double last_delta;
};

请注意，它显示 delta_p在每次迭代中。

我正在为一个只有六个顶点的简单图运行它。 delta_p仅显示一次且为 0。考虑到初始布局是随机的，这确实很奇怪。这是我得到的图片:

正如您所看到的，随机布局并不漂亮，Kamada-Kawai 没有对它做任何事情。

我尝试了另一个停止条件:layout_tolerance<CostType>(0.01) .这导致 Kamada-Kawai 永远运行。

我在这里做错了什么？

P.S.:由于我在浏览器中看不到图片，以防万一它没有附加，这里是图的邻接结构。该图表示三个煎饼情况下煎饼拼图的状态空间。即，顶点对应于数字 0、1、2 的不同排列，并且每个顶点有两条边(权重均为 1):

[0, 2, 1]:
    [2, 0, 1] (w=1)
    [1, 2, 0] (w=1)
[2, 0, 1]:
    [0, 2, 1] (w=1)
    [1, 0, 2] (w=1)
[1, 2, 0]:
    [0, 2, 1] (w=1)
    [2, 1, 0] (w=1)
[2, 1, 0]:
    [1, 2, 0] (w=1)
    [0, 1, 2] (w=1)
[1, 0, 2]:
    [2, 0, 1] (w=1)
    [0, 1, 2] (w=1)
[0, 1, 2]:
    [1, 0, 2] (w=1)
    [2, 1, 0] (w=1)

更新:这是我实现已接受答案的代码:

template <class PointMap> PointMap layout() const {
    PointMap res;

    // Make a copy into a graph that is easier to deal with:
    //     -- vecS for vertex set, so there is index map
    //     -- double for edge weights
    using LayoutGraph =
        boost::adjacency_list<vecS, vecS, undirectedS, int, double>;
    using LayoutVertexDescriptor =
        typename graph_traits<LayoutGraph>::vertex_descriptor;
    std::map<VertexDescriptor, LayoutVertexDescriptor> myMap;
    std::map<LayoutVertexDescriptor, VertexDescriptor> myReverseMap;

    LayoutGraph lg; // This is the copy

    // Copy vertices
    for (auto vd : vertexRange()) {
        auto lvd = add_vertex(lg);
        myMap[vd] = lvd;
        myReverseMap[lvd] = vd;
    }

    // Copy edges
    for (auto from: vertexRange()) {
        for (auto to: adjacentVertexRange(from)) {
            auto lfrom = myMap[from], lto = myMap[to];
            if (!edge(lfrom, lto, lg).second)
                add_edge(lfrom, lto, (double)(g_[edge(to, from, g_).first]),
                         lg);
        }
    }
    // Done copying

    using LayoutPointMap =
        std::map<LayoutVertexDescriptor, square_topology<>::point_type>;
    LayoutPointMap intermediateResults;
    boost::associative_property_map<LayoutPointMap> temp(
        intermediateResults);

    minstd_rand gen;
    rectangle_topology<> rect_top(gen, 0, 0, 100, 100);
    random_graph_layout(lg, temp, rect_top);

    // circle_graph_layout(lg, temp, 10.0);

    kamada_kawai_spring_layout(lg, temp, get(edge_bundle, lg),
                               square_topology<>(100.0), side_length(100.0),
                               //layout_tolerance<CostType>(0.01));
                               kamada_kawai_done());

    for (auto el: intermediateResults)
        res[myReverseMap[el.first]] = el.second;

    return res;
}

对于 6 个顶点，布局是一个完美的六边形，所以它有效!对于 24 个顶点，最后显示的是 delta_p是 ~2.25(它不应该低于 0.01 吗？)。此外，从随机布局开始的布局比从圆形布局开始的布局更漂亮...

使用较小的矩形(例如 20 x 20 而不是 100 x 100)会导致布局不美观，使用 layout_tolerance<double>(0.01) 也是如此。作为停止条件。

Answer 1

我认为中间近似值可能存储在实际的边束属性中，这使得它转换为整数。

由于输入的规模，它显然丢失了对实现(局部)最佳布局很重要的数字。我建议使用 double 作为 edge bundle，看看会发生什么。