Kamada-Kawai 布局的停止条件
Stopping condition for Kamada-Kawai layout
我正在使用以下代码获取 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); // random layout to show that
// Kamada-Kawai isn't doing the job
// circle_graph_layout(g_, temp, 10.0);
//
//
typedef std::map<VertexDescriptor, std::size_t> IndexMap;
IndexMap mapIndex;
associative_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_),
square_topology<>(50.0), side_length(50.0),
//layout_tolerance<CostType>(0.01),
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。考虑到初始布局是随机的,这真的很奇怪。这是我得到的图片:
如您所见,随机布局并不漂亮,Kamada-Kawai 没有对它做任何事情。
我尝试了另一个停止条件:layout_tolerance<CostType>(0.01)
。这导致 Kamada-Kawai 永远 运行。
我做错了什么?
P.S.: 由于我在浏览器中看不到图片,以防万一它没有附加,这里是图的邻接结构。该图表示三个煎饼情况下煎饼拼图的状态 space。即,顶点对应于数字 0、1、2 的不同排列,并且每个顶点有两条边(权重均为 1):
[0, 2, 1]:
[2, 0, 1] (w=1)
[1, 2, 0] (w=1)
[2, 0, 1]:
[0, 2, 1] (w=1)
[1, 0, 2] (w=1)
[1, 2, 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] (w=1)
[2, 1, 0] (w=1)
更新:这是我实现已接受答案的代码:
template <class PointMap> PointMap layout() const {
PointMap res;
// Make a copy into a graph that is easier to deal with:
// -- vecS for vertex set, so there is index map
// -- double for edge weights
using LayoutGraph =
boost::adjacency_list<vecS, vecS, undirectedS, int, double>;
using LayoutVertexDescriptor =
typename graph_traits<LayoutGraph>::vertex_descriptor;
std::map<VertexDescriptor, LayoutVertexDescriptor> myMap;
std::map<LayoutVertexDescriptor, VertexDescriptor> myReverseMap;
LayoutGraph lg; // This is the copy
// Copy vertices
for (auto vd : vertexRange()) {
auto lvd = add_vertex(lg);
myMap[vd] = lvd;
myReverseMap[lvd] = vd;
}
// Copy edges
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_).first]),
lg);
}
}
// Done copying
using 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 x 20 而不是 100 x 100)会导致布局不美观,使用 layout_tolerance<double>(0.01)
作为停止条件也是如此。
我认为中间近似值可能会存储在实际的边束属性中,从而使其转换为整数。
由于输入的规模,它显然丢失了对实现(局部)最佳布局很重要的数字。我建议使用 double 作为 edge bundle,看看会发生什么。
我正在使用以下代码获取 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); // random layout to show that
// Kamada-Kawai isn't doing the job
// circle_graph_layout(g_, temp, 10.0);
//
//
typedef std::map<VertexDescriptor, std::size_t> IndexMap;
IndexMap mapIndex;
associative_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_),
square_topology<>(50.0), side_length(50.0),
//layout_tolerance<CostType>(0.01),
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。考虑到初始布局是随机的,这真的很奇怪。这是我得到的图片:
如您所见,随机布局并不漂亮,Kamada-Kawai 没有对它做任何事情。
我尝试了另一个停止条件:layout_tolerance<CostType>(0.01)
。这导致 Kamada-Kawai 永远 运行。
我做错了什么?
P.S.: 由于我在浏览器中看不到图片,以防万一它没有附加,这里是图的邻接结构。该图表示三个煎饼情况下煎饼拼图的状态 space。即,顶点对应于数字 0、1、2 的不同排列,并且每个顶点有两条边(权重均为 1):
[0, 2, 1]:
[2, 0, 1] (w=1)
[1, 2, 0] (w=1)
[2, 0, 1]:
[0, 2, 1] (w=1)
[1, 0, 2] (w=1)
[1, 2, 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] (w=1)
[2, 1, 0] (w=1)
更新:这是我实现已接受答案的代码:
template <class PointMap> PointMap layout() const {
PointMap res;
// Make a copy into a graph that is easier to deal with:
// -- vecS for vertex set, so there is index map
// -- double for edge weights
using LayoutGraph =
boost::adjacency_list<vecS, vecS, undirectedS, int, double>;
using LayoutVertexDescriptor =
typename graph_traits<LayoutGraph>::vertex_descriptor;
std::map<VertexDescriptor, LayoutVertexDescriptor> myMap;
std::map<LayoutVertexDescriptor, VertexDescriptor> myReverseMap;
LayoutGraph lg; // This is the copy
// Copy vertices
for (auto vd : vertexRange()) {
auto lvd = add_vertex(lg);
myMap[vd] = lvd;
myReverseMap[lvd] = vd;
}
// Copy edges
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_).first]),
lg);
}
}
// Done copying
using 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 x 20 而不是 100 x 100)会导致布局不美观,使用 layout_tolerance<double>(0.01)
作为停止条件也是如此。
我认为中间近似值可能会存储在实际的边束属性中,从而使其转换为整数。
由于输入的规模,它显然丢失了对实现(局部)最佳布局很重要的数字。我建议使用 double 作为 edge bundle,看看会发生什么。