Boost::Graph-算法不使用 PropertyMap 写入数据（kamada_kawai_spring_layout，捆绑属性）

Question

我有一个 adjacency_list 图，其中使用 Erdos-Renyi 边生成随机连接节点。该图通过为顶点（Graph_Node）和边（Graph_Edge）定义数据结构来使用捆绑属性，用于分配节点的位置和边的权重。

我正在尝试使用力导向图绘制来为节点分配好的位置，使用 kamada_kawai_spring_layout。

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>

using namespace boost;
struct Graph_Node
{
    typedef convex_topology<2>::point tPoint;
    tPoint Position;

};
struct Graph_Edge
{
    unsigned int ID;
    double weight = 100.;
};

typedef adjacency_list<vecS, vecS, undirectedS, Graph_Node, Graph_Edge> Graph;
static random::minstd_rand rng;
typedef erdos_renyi_iterator<random::minstd_rand, Graph> ERGen;
static const int ER_INIT_NODES = 50;
static const double p = 0.05;
static Graph g(ERGen(rng, ER_INIT_NODES, p), ERGen(), ER_INIT_NODES);

int main()
{
    ball_topology<2> T(1.);
    detail::graph::edge_or_side<1, double> scaling(1.);
    kamada_kawai_spring_layout(g, get(&Graph_Node::Position, g), get(&Graph_Edge::weight, g), T, scaling);
    Graph::vertex_iterator v, v_end;
    for (std::tie(v, v_end) = vertices(g); v != v_end; ++v)
        std::cout << g[*v].Position[0] << ", " << g[*v].Position[1] << std::endl;
}

Graph_Node::Position原本打算用kamada_kawai_spring_layout赋值，但是g中所有顶点的Position赋值后都是0,0。为什么？

Answer 1

算法的return值：

Returns: true if layout was successful or false if a negative weight cycle was detected or the graph is disconnected.

当你打印它时，你会发现它是假的。所以，你的图表不符合要求。

提高边概率使得连通图：

Live On Compiler Explorer

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/circle_layout.hpp>
#include <boost/graph/erdos_renyi_generator.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>
#include <boost/random/linear_congruential.hpp>
#include <fmt/ranges.h>

using tPoint = boost::convex_topology<2>::point;
struct Graph_Node { tPoint Position{}; };
struct Graph_Edge { /*unsigned int ID;*/ double weight = 100; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS,
                                    boost::undirectedS, Graph_Node, Graph_Edge>;

static constexpr int    ER_INIT_NODES = 20; // 50
static constexpr double p             = 1;  // 0.05

Graph make_graph() {
    boost::random::minstd_rand rng;
    using Gen = boost::erdos_renyi_iterator<boost::random::minstd_rand, Graph>;
    return {Gen(rng, ER_INIT_NODES, p), Gen(), ER_INIT_NODES};
}

int main()
{
    auto g = make_graph();
    //write_graphviz(std::cout, g);

    auto print_position = [pos = get(&Graph_Node::Position, g)](size_t v) {
        fmt::print("Vertex {:3} Position {:9.4f}, {:9.4f}\n", v, pos[v][0], pos[v][1]);
    };

    auto mid_vertex = vertex(ER_INIT_NODES / 2, g);
    print_position(mid_vertex);
    boost::circle_graph_layout(g, get(&Graph_Node::Position, g), 25.0);

    if (true) { // ball-topology
        print_position(mid_vertex);

        bool ok = kamada_kawai_spring_layout(                    //
            g,                                                   //
            get(&Graph_Node::Position, g),                       //
            get(&Graph_Edge::weight, g),                         //
            boost::ball_topology<2>(1.),                         //
            boost::detail::graph::edge_or_side<true, double>(1.) //
        );
        fmt::print("kamada_kawai_spring_layout ok: {}\n", ok);
    } else {
        print_position(mid_vertex);
        bool ok = kamada_kawai_spring_layout( //
            g,                                //
            get(&Graph_Node::Position, g),    //
            get(&Graph_Edge::weight, g),      //
            boost::square_topology<>(50.0),   //
            boost::side_length(50.0)          //
        );
        fmt::print("kamada_kawai_spring_layout ok: {}\n", ok);
    }

    print_position(mid_vertex);
    fmt::print("----\n");
    for (auto v : boost::make_iterator_range(vertices(g)))
        print_position(v);
}

版画

Vertex  10 Position    0.0000,    0.0000
Vertex  10 Position  -25.0000,    0.0000
kamada_kawai_spring_layout ok: true
Vertex  10 Position   20.3345, -102.5760
----
Vertex   0 Position  -35.8645,  -19.4454
Vertex   1 Position  -72.7690, -130.3436
Vertex   2 Position   -8.5828, -138.2843
Vertex   3 Position  -44.7830,  -52.9697
Vertex   4 Position  -43.0101,   30.9041
Vertex   5 Position  -69.7531,   38.7188
Vertex   6 Position   -0.4328,   43.2208
Vertex   7 Position   31.3758,  -30.9816
Vertex   8 Position   47.1809,   12.8283
Vertex   9 Position  -76.9535,    9.7684
Vertex  10 Position   20.3345, -102.5760
Vertex  11 Position  -19.5602, -103.9834
Vertex  12 Position  -68.2476,  -78.6953
Vertex  13 Position  -95.3881,  -46.8710
Vertex  14 Position -131.4928,    7.9270
Vertex  15 Position   24.0966,   -4.9534
Vertex  16 Position   59.0794,  -86.1642
Vertex  17 Position -102.4687, -148.9986
Vertex  18 Position  -10.8986,  -52.8234
Vertex  19 Position -131.8706,  -60.2588

Boost::Graph-算法不使用 PropertyMap 写入数据（kamada_kawai_spring_layout，捆绑属性）

Boost::Graph-algorithm does not write data with PropertyMap (kamada_kawai_spring_layout, bundled properties)

c++

boost

boost-graph

boost-property-map