平面圖繪圖C++

Question

我已經閱讀了很多關於在飛機上繪製平面圖的文章，我嘗試了很多庫。最後，我需要指定輸入圖形，輸出獲得其頂點的新座標，以便邊緣不相交。

選擇落在函數chrobak_payne_straight_line_drawing來自Boost Graph Library。

我測試了下圖：http://cboard.cprogramming.com/attachments/cplusplus-programming/11153d1322430048-graph-planarization-boost-library-1grb.jpg

但它沒有工作，在125線文件chrobak_payne_drawing.hpp來電System.AccessViolationException：

delta_x[v3] = 1; 

但在這個圖它的工作原理：http://cboard.cprogramming.com/attachments/cplusplus-programming/11154d1322430090-graph-planarization-boost-library-2gr.jpg

請幫助，我需要功能與所有平面圖一起工作，不會導致嚴重錯誤。下面我介紹的代碼，這是我測試的第一個圖，得到了一個嚴重錯誤，順便說一句，我使用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我必須首先使圖形最大平面？但是我沒有成功。請幫助我爲我的代碼添加必要的功能，我不太確定轉換圖的步驟。

在此先感謝您 - 我的最後希望！

Answer 1

這看起來像是boost :: graph中的一個bug。我在那裏有一個不同的訪問衝突，也許是因爲一個不同的增強版本，但肯定有一個錯誤。

 left[v] = right[leftmost]; 
     vertex_t next_to_rightmost; 
     for(vertex_t temp = leftmost; temp != rightmost; 
      temp = right[temp] 
      ) 
      { 
      next_to_rightmost = temp; 
      } 

     right[next_to_rightmost] = graph_traits<Graph>::null_vertex(); 

這裏時leftmost==rightmost，不執行for環和next_to_rightmost仍然未初始化。崩潰！這就是我所看到的。

Answer 2

您使用的圖形不是最大的平面。在進行規範排序或嵌入之前，您需要使用函數make_connected，make_biconnected_planar和make_maximal_planar。儘管源代碼中的註釋解釋了這一點，但它們的使用並不直觀，我無法使用它們和函數chrobak_payne_straight_line_drawing結合使用它們。 Here is an example I adapted from the original source and other examples。