Boost Kamada-Kawai弹簧布局编译问题及定点平面嵌入可行性咨询

1. 力导向布局实现部分顶点固定是否可行？ #

完全可行。力导向布局（比如你用的Kamada-Kawai算法）天生支持部分顶点固定的场景：只需要提前给固定顶点设置好初始坐标，在算法迭代过程中保持这些顶点的位置不被更新即可。Boost的Kamada-Kawai实现可以通过预先初始化position_map中固定顶点的坐标，配合正确的参数设置，达到固定部分顶点的效果。

2. Boost Kamada-Kawai代码编译错误修正 #

你的代码存在多个语法、类型匹配和命名空间问题，以下是具体修改点和修正后的代码：

核心修改点 #

• 补全命名空间：geometry、rectangle_topology等属于Boost命名空间，需添加boost::前缀
• 修复adjacency_list定义：typedef末尾缺失闭合尖括号>
• 定义pairs类型：明确std::pair<int, int>作为边的顶点对类型
• 统一边权重类型：将edge_weight_t的类型从int改为double，匹配add_edge传入的1.0
• 补充必要头文件：确保包含所有Boost相关头文件和标准库头文件
• 调整算法参数：确保kamada_kawai_spring_layout的参数类型完全匹配

修正后的代码 #

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kamada_kawai_spring_layout.hpp>
#include <boost/graph/random_layout.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/random/minstd_rand.hpp>
#include <map>
#include <vector>

// 明确命名空间别名或使用完整命名空间
typedef boost::geometry::model::point<double, 2, boost::geometry::cs::cartesian> point;
typedef std::pair<int, int> pairs;

// 修正adjacency_list的定义，补全闭合尖括号，统一边权重类型为double
typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    boost::property<boost::vertex_index_t, int>,
    boost::property<boost::edge_index_t, int,
        boost::property<boost::edge_weight_t, double> >
> graph;

// 假设HubSet和edge是类成员，此处模拟调用场景
void layout_example() {
    std::vector<int> HubSet(100); // 模拟HubSet
    std::map<pairs, int> edge;    // 模拟edge集合
    edge.insert(std::make_pair(pairs(33,35), 1));

    graph g(HubSet.size());

    // 添加边
    for (auto& iter : edge) {
        pairs tmpPair = iter.first;
        add_edge(tmpPair.first, tmpPair.second, 1.0, g);
    }

    // 位置映射初始化，固定顶点33和35的坐标
    typedef std::vector<point> PositionMap;
    PositionMap position(num_vertices(g));
    position[33] = point(250.0, 2000.0);
    position[35] = point(8000.0, 2000.0);
    auto position_map = boost::make_iterator_property_map(
        position.begin(), 
        get(boost::vertex_index, g)
    );

    // 拓扑与随机初始化非固定顶点
    std::minstd_rand gen;
    boost::rectangle_topology<std::minstd_rand> topo(gen, 0.0, 0.0, 9000.0, 9000.0);
    boost::random_graph_layout(g, position_map, topo);

    // 调用Kamada-Kawai算法，固定顶点坐标会被保留
    boost::kamada_kawai_spring_layout(
        g,
        position_map,
        get(boost::edge_weight, g),
        topo,
        boost::edge_length(100.0)
    );
}

额外说明 #

• 如果需要更严格地固定顶点，可以考虑使用Boost Graph的fixed_vertices属性映射，将固定顶点标记为不可移动，部分版本的Kamada-Kawai实现支持该参数
• 确保Boost库已正确编译并链接，编译时需添加Boost的包含路径和链接库参数（比如-lboost_graph）

内容的提问来源于stack exchange，提问作者Cyantttt