Остановка условие для размещения Камада-Kawai

Question

Я использую следующий код для получения Камада-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); 

    // http://stackoverflow.com/q/33903879/2725810 
    // http://stackoverflow.com/a/8555715/2725810 
    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. Учитывая, что исходный макет случайный, это действительно странно. Вот картина, которую я получаю:

Как вы можете видеть, случайная компоновка некрасивая, и Камада-Каваи ничего не делал с ней.

Я попробовал другое состояние остановки: layout_tolerance<CostType>(0.01). Это приводит к тому, что Камада-Кавай работает вечно.

Что я здесь делаю неправильно?

P.S .: Поскольку я не вижу изображение в своем браузере, на всякий случай он не привязан, вот структура смежности графика. Граф представляет собой пространство состояний головоломки «Блины» для случая трех блинов. А именно, вершины соответствуют различным перестановкам чисел 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) 

UPDATE: Вот мой код для реализации принятых ответ:

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 на 20 вместо 100 на 100) приводит к менее красивой компоновке, используя layout_tolerance<double>(0.01) в качестве условия остановки.

Answer 1

Я думаю, что промежуточное приближение может быть сохранено в реальных свойствах связки ребер, что делает его преобразованием в целое.

Из-за масштаба ввода он, по-видимому, теряет цифры, значимые для достижения (локального) оптимального макета. Я бы посоветовал пойти с двойником для краевого расслоения, видя, что происходит.