C++ Boost kamada_kawai_spring_layout 问题

Question

为了实现某些顶点位置固定的平面嵌入，

1. 我目前使用的是力导向布局方法。这个办法可行吗？
2. 我目前面临着从 Boost 库编译 kamada_kawai_spring_layout 的问题。

typedef geometry::model::point<double, 2, geometry::cs::cartesian> point ;
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, int> >
graph;
graph g(this->HubSet.size());

//Add edge
map<pairs,int>::iterator iter;
for(iter = this->edge.begin() ; iter != this->edge.end() ; iter++)
{
   pairs tmpPair = iter->first;
   add_edge(tmpPair.first, tmpPair.second, 1.0, g);
}

//Position Map
typedef 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));

//Topology
std::minstd_rand gen;
rectangle_topology<std::minstd_rand> topo(gen, 0.0, 0.0, 9000.0, 9000.0);
random_graph_layout(g, position_map, topo);

//Call Force directed algorithm
boost::kamada_kawai_spring_layout(g,
                                  position_map,
                                  get(edge_weight, g),
                                  topo,
                                  edge_length(100.0) );

我想咨询一下我的代码编译的问题。您能帮我确定成功编译所需的修改吗？

Answer 1

不可能弄清楚你遇到了什么错误，因为你发布了 代码不完整。

如果我弥补一些缺失的代码，我最好的猜测是你的位置图 不符合记录的标准：

类型

PositionMap

必须是

Writable Property Map

的模型，其中 图的顶点描述符类型作为其键类型，

Topology::point_type

作为 它的值类型。

所以，改用：

using Topology = boost::rectangle_topology<std::minstd_rand>;
using Point    = Topology::point_type;

然后，当我们还使边权重在算术上与坐标类型兼容时，就有可能编译：

住在Coliru

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

using Topology = boost::rectangle_topology<std::minstd_rand>;
using Point    = Topology::point_type;
using Graph    = 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> //
                                                    >>;
struct Program {
    std::vector<int> HubSet;
    using pairs = std::pair<size_t, size_t>;
    std::map<pairs, int> edge;

    Program()
        : HubSet(42) // no clue, just made it big enough for position[35] to be a valid index
    {}

    void foo() {
        Graph g(this->HubSet.size());

        // Add edge
        std::map<pairs, int>::iterator iter;
        for (iter = this->edge.begin(); iter != this->edge.end(); iter++) {
            pairs tmpPair = iter->first;
            add_edge(tmpPair.first, tmpPair.second, 1.0, g);
        }

        // Position Map
        using PositionMap = std::vector<Point>;
        PositionMap position(num_vertices(g));

        auto make_point = [](double x, double y) {
            Point p;
            p[0] = x;
            p[1] = y;
            return p;
        };
        position[33] = make_point(250.0, 2000.0);
        position[35] = make_point(8000.0, 2000.0);
        auto position_map = boost::make_iterator_property_map(position.begin(), get(boost::vertex_index, g));

        // Topology
        std::minstd_rand gen;
        Topology         topo(gen, 0.0, 0.0, 9000.0, 9000.0);
        random_graph_layout(g, position_map, topo);

        // Call Force directed algorithm
        boost::kamada_kawai_spring_layout(g, position_map, get(boost::edge_weight, g), topo,
                                          boost::edge_length(100.0));
    }
};

int main() {
    Program p;
    p.foo();
}

奖金

如果您必须在未来获得几何支持，您可以调整点类型：

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/register/point.hpp>

namespace bg = boost::geometry;
using Point  = Topology::point_type;

namespace boost::geometry::traits {
    template<> struct tag<Point>               { using type = point_tag;         };
    template<> struct coordinate_type<Point>   { using type = double;            };
    template<> struct coordinate_system<Point> { using type = bg::cs::cartesian; };
    template<> struct dimension<Point> : std::integral_constant<std::size_t, 2> {};
    template<> struct access<Point, 0> {
        static inline double get(Point const& p) { return p[0]; }
        static inline void   set(Point& p, double const& value) { p[0] = value; }
    };
    template <> struct access<Point, 1> {
        static inline double get(Point const& p) { return p[1]; }
        static inline void   set(Point& p, double const& value) { p[1] = value; }
    };
} // namespace boost::geometry::traits

此时您可以使用

boost::geometry::make<Point>(x,y)

代替定制的 lambda。