算法的返回值:
返回:如果布局成功,则返回 true;如果检测到负权重循环或图形断开连接,则返回 false。
当您打印它时,您会发现它是错误的。因此,您的图表不满足要求。
提高边缘概率可以得到连通图:
Live On 编译器资源管理器
#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