Kamada-Kawai布局的停止条件 - IT屋-程序员软件开发技术分享社区

来自 : www.it1352.com/4907...html 发布时间：2021-03-25

我使用以下代码来获取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）; //随机布局以显示
 // Kamada-Kawai不执行此任务
 
 // 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; 
 associationative_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_） b $ b square_topology （50.0），side_length（50.0），
 //layout_tolerance CostType (0.01),b 
 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。由于初始布局是随机的，这真的很奇怪。这是我得到的图片：

如你所见，随机布局是\'

我尝试了另一个停止条件： layout_tolerance CostType （0.01）。

PS：因为我在这里做错了。无法在我的浏览器中看到图片，以防万一它没有附加，这里是图的邻接结构。该图表示对于三个煎饼的情况的煎饼拼图的状态空间。即，顶点对应于数字0,1,2的不同排列，并且来自每个顶点的两个边（所有权重为1）：

 [0,2,1]：
 [2,0,1]（w = 1）
 [1,0,0]（w = 1）
 [ 2,0,1]：
 [0,2,1]（w = 1）
 [1,0,2]（w = 1）
 [1,0,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] b $ b [2,1,0]（w = 1）
 

UPDATE ：这里是我的代码实现接受的答案：

 template class PointMap& PointMap layout（）const {
 PointMap res; 
 
 //将副本复制到更容易处理的图形中：
 // - vecS用于顶点集，所以有索引映射
 // - double边缘权重
使用LayoutGraph = 
 boost :: adjacency_list vecS，vecS，undirectedS，int，double 
使用LayoutVertexDescriptor = 
 typename graph_traits LayoutGraph :: vertex_descriptor; 
 std :: map VertexDescriptor，LayoutVertexDescriptor myMap; 
 std :: map LayoutVertexDescriptor，VertexDescriptor myReverseMap; 
 
 LayoutGraph lg; //这是副本
 
 //复制顶点
 for（auto vd：vertexRange（））{
 auto lvd = add_vertex（lg）; 
 myMap [vd] = lvd; 
 myReverseMap [lvd] = vd; 
} 
 
 //复制边
 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 _）。 b lg）; 
} 
} 
 //使用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乘20而不是100乘100）导致不太漂亮的布局，并且使用 layout_tolerance double （0.01）作为停止条件。

解决方案

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

由于输入的比例，它显然丢失了用于实现（局部）最佳布局的数字。我建议用双边的边缘束看看会发生什么。

本文地址：IT屋 Kamada-Kawai布局的停止条件