平面图绘制C ++ [英] Planar graph drawing C++

问题描述

我已经阅读了许多有关在飞机上绘制平面图的文章，我试过很多库。最后，我需要指定输入图，输出以获得其顶点的新坐标，以便边不相交。 选择来自Boost图的函数 chrobak_payne_straight_line_drawing 图书馆。

我在下面的图表上测试了它： http://cboard.cprogramming.com/attachments/cplusplus-programming/11153d1322430048-graph-planarization-boost-library-1grb.jpg

但它不起作用，并在文件chrobak_payne_drawing.hpp的125行处调用 System.AccessViolationException ：

  delta_x [v3] = 1; 
  

但是在这张图上它起作用：

请帮助，我需要运行所有平面图并且不会导致严重错误。下面我介绍一下代码，我测试了第一张图，并得到了一个严重错误，顺便说一下，我使用的是visual studio 2010.

  #include< iostream> 
 #include< boost / graph / adjacency_list.hpp> 
 #include< boost / graph / properties.hpp> 
 #include< boost / graph / graph_traits.hpp> 
 #include< boost / property_map / property_map.hpp> 
 #include< vector> 
 #include< stack> 
 
 #include< boost / graph / planar_canonical_ordering.hpp> 
 #include< boost / graph / is_straight_line_drawing.hpp> 
 #include< boost / graph / chrobak_payne_drawing.hpp> 
 #include< boost / graph / boyer_myrvold_planar_test.hpp> 
 
使用命名空间boost; 
 
 //一个类来保存直线嵌入的坐标
 struct coord_t 
 {
 std :: size_t x; 
 std :: size_t y; 
}; 
 
 int main（int argc，char ** argv）
 {
 typedef adjacency_list 
< vecS，
 vecS，
 undirectedS，
 property< vertex_index_t，int> 
>图形; 
 
 //定义平面嵌入的存储类型
 typedef std :: vector<的std ::矢量< graph_traits< graph> :: edge_descriptor> > 
 embedding_storage_t; 
 typedef boost :: iterator_property_map 
< embedding_storage_t :: iterator，
 property_map< graph，vertex_index_t> :: type 
> 
 embedding_t; 
 
 //创建图形 -  7个顶点上的最大平面图形。函数
 // planar_canonical_ordering和chrobak_payne_straight_line_drawing 
 // //都需要一个最大的平面图。如果你从一个不是
 //最大平面的图形开始（或者你不确定），你可以在
中使用
 // make_connected，make_biconnected_planar和make_maximal平面函数//序列将一组边添加到任何无向平面图中以使
 //最大平面。 
 
图g（5）; 
 add_edge（0,3，g）; 
 add_edge（0,4，g）; 
 add_edge（1,3，g）; 
 add_edge（1,4，g）; 
 add_edge（2,3，g）; 
 add_edge（2,4，g）; 
 
 //创建平面嵌入
 embedding_storage_t embedding_storage（num_vertices（g））; 
 embedding_t嵌入（embedding_storage.begin（），get（vertex_index，g））; 
 
 boyer_myrvold_planarity_test（boyer_myrvold_params :: graph = g，
 boyer_myrvold_params :: embedding = embedding 
）; 
 
 
 
 //找到一个规范排序
 std :: vector< graph_traits< graph> :: vertex_descriptor>排序; 
 planar_canonical_ordering（g，嵌入，std :: back_inserter（排序））; 
 
 
 //设置一个属性映射来保存从顶点到coord_t的映射
 typedef std :: vector< coord_t> straight_line_drawing_storage_t; 
 typedef boost :: iterator_property_map 
< straight_line_drawing_storage_t :: iterator，
 property_map< graph，vertex_index_t> :: type 
> 
 straight_line_drawing_t; 
 
 straight_line_drawing_storage_t straight_line_drawing_storage 
（num_vertices（g））; 
 straight_line_drawing_t straight_line_drawing 
（straight_line_drawing_storage.begin（），
 get（vertex_index，g）
）; 
 
 
 
 //计算直线图
 chrobak_payne_straight_line_drawing（g，
嵌入，
 ordering.begin（），
 orders.end（），
 straight_line_drawing 
）; 
 
 
 
 std :: cout<< 直线图是：<<的std :: ENDL; 
 graph_traits< graph> :: vertex_iterator vi，vi_end; （vi，vi_end）=顶点（g）; vi！= vi_end; ++ vi）
 {
 coord_t coord（get（straight_line_drawing，* vi））
; 
 std :: cout<< * vi<<  - >（<<< coord.x<<，<<<<<"）" 
<<的std :: ENDL; 
} 
 
 //如果（is_straight_line_drawing（g，straight_line_drawing））
 std :: cout<<>确认绘图实际上是绘制
的平面。 是平面图。 <<的std :: ENDL; 
 else 
 std :: cout<< 不是平面图。 <<的std :: ENDL; 
返回0; 
} 
  

Mayber我必须首先制作最大平面图吗？但我没有成功..请帮我添加到我的代码的必要功能，我不太清楚转换图表的步骤。

谢谢先进的，你 - 我的最后希望！

解决方案

你使用的图不是最大的平面。在进行规范排序或嵌入之前，您需要使用函数make_connected，make_biconnected_planar和make_maximal_planar。尽管源代码中的注释解释了这一点，但它们的使用并不直观，我无法使用它们和函数chrobak_payne_straight_line_drawing结合使用它们。 下面是我根据原始来源和其他示例改编的示例。

I have read many articles on drawing planar graphs on the plane, I tried a lot of libraries.

In the end, I need to specify the input graph, the output to obtain new coordinates of its vertices, so that the edges do not intersect.

The choice fell on the function chrobak_payne_straight_line_drawing from Boost Graph Library.

I tested it on the following graph: http://cboard.cprogramming.com/attachments/cplusplus-programming/11153d1322430048-graph-planarization-boost-library-1grb.jpg

But it did not work and calls System.AccessViolationException at the 125 line of file chrobak_payne_drawing.hpp:

delta_x[v3] = 1;

But on this graph it works: http://cboard.cprogramming.com/attachments/cplusplus-programming/11154d1322430090-graph-planarization-boost-library-2gr.jpg

Please help, I need to function to work with all planar graphs and does not cause critical errors. Below I present the code, which I tested the first graph and got a critical error, by the way, I'm using visual studio 2010.

    #include <iostream>
    #include <boost/graph/adjacency_list.hpp>
    #include <boost/graph/properties.hpp>
    #include <boost/graph/graph_traits.hpp>
    #include <boost/property_map/property_map.hpp>
    #include <vector>
    #include <stack>

    #include <boost/graph/planar_canonical_ordering.hpp>
    #include <boost/graph/is_straight_line_drawing.hpp>
    #include <boost/graph/chrobak_payne_drawing.hpp>
    #include <boost/graph/boyer_myrvold_planar_test.hpp>

    using namespace boost;

    //a class to hold the coordinates of the straight line embedding
    struct coord_t
    {
      std::size_t x;
      std::size_t y;
    };

    int main(int argc, char** argv)
    {
      typedef adjacency_list
        < vecS,
          vecS,
          undirectedS,
          property<vertex_index_t, int>
        > graph;  

      //Define the storage type for the planar embedding
      typedef std::vector< std::vector< graph_traits<graph>::edge_descriptor > > 
        embedding_storage_t;
      typedef boost::iterator_property_map
        < embedding_storage_t::iterator, 
          property_map<graph, vertex_index_t>::type 
        >
        embedding_t;

      // Create the graph - a maximal planar graph on 7 vertices. The functions
      // planar_canonical_ordering and chrobak_payne_straight_line_drawing both
      // require a maximal planar graph. If you start with a graph that isn't
      // maximal planar (or you're not sure), you can use the functions
      // make_connected, make_biconnected_planar, and make_maximal planar in
      // sequence to add a set of edges to any undirected planar graph to make
      // it maximal planar.

      graph g(5);
      add_edge(0,3, g);
      add_edge(0,4, g);
      add_edge(1,3, g);
      add_edge(1,4, g);
      add_edge(2,3, g);
      add_edge(2,4, g);

      // Create the planar embedding
      embedding_storage_t embedding_storage(num_vertices(g));
      embedding_t embedding(embedding_storage.begin(), get(vertex_index,g));

      boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
                                   boyer_myrvold_params::embedding = embedding
                                   );



      // Find a canonical ordering
      std::vector<graph_traits<graph>::vertex_descriptor> ordering;
      planar_canonical_ordering(g, embedding, std::back_inserter(ordering));


      //Set up a property map to hold the mapping from vertices to coord_t's
      typedef std::vector< coord_t > straight_line_drawing_storage_t;
      typedef boost::iterator_property_map
        < straight_line_drawing_storage_t::iterator, 
          property_map<graph, vertex_index_t>::type 
        >
        straight_line_drawing_t;

      straight_line_drawing_storage_t straight_line_drawing_storage
        (num_vertices(g));
      straight_line_drawing_t straight_line_drawing
        (straight_line_drawing_storage.begin(), 
         get(vertex_index,g)
         );



      // Compute the straight line drawing
      chrobak_payne_straight_line_drawing(g, 
                                          embedding, 
                                          ordering.begin(),
                                          ordering.end(),
                                          straight_line_drawing
                                          );



      std::cout << "The straight line drawing is: " << std::endl;
      graph_traits<graph>::vertex_iterator vi, vi_end;
      for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
        {
          coord_t coord(get(straight_line_drawing,*vi));
          std::cout << *vi << " -> (" << coord.x << ", " << coord.y << ")" 
                    << std::endl;
        }

      // Verify that the drawing is actually a plane drawing
      if (is_straight_line_drawing(g, straight_line_drawing))
       std::cout << "Is a plane drawing." << std::endl;
      else
        std::cout << "Is not a plane drawing." << std::endl;
      return 0;  
    }

Mayber i must first make graph maximal planar? But I did not succeed .. Please help me add to my code the necessary functions for this, I'm not quite sure what step to convert the graph.

Thanks in advance, you - my last hope!

解决方案

The graph you were using was not maximal planar. You need to use the functions make_connected, make_biconnected_planar and make_maximal_planar before you get to a canonical ordering or an embedding. Though the comment in the source explains this, their use is not exactly intuitive and I could not find a source using them and the function chrobak_payne_straight_line_drawing in combination. Here is an example I adapted from the original source and other examples.

这篇关于平面图绘制C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！