Планарный график C ++

Question

Я прочитал много статей по рисованию плоских графов на плоскости, я перепробовал много библиотек.

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

Выбор пал на функцию chrobak_payne_straight_line_drawing из библиотеки графов ускорения.

Я тестировал ее на следующем графике: http://cboard.cprogramming.com/attachments/cplusplus-programming/11153d1322430048-graph-planarization-boost-library-1grb.jpg

Но это не сработало и вызывает System.AccessViolationException в строке 125 файла chrobak_payne_drawing.hpp:

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;  
    }

Майбер, я должен сначала сделать граф максимально плоским?Но у меня ничего не получилось .. Пожалуйста, помогите мне добавить в мой код необходимые для этого функции, я не совсем уверен, на каком шаге конвертировать граф.

Заранее спасибо, вы - моя последняя надежда!

Answer 1

График, который вы использовали, не был максимально плоским. Вам нужно использовать функции make_connected, make_biconnected_planar и make_maximal_planar, прежде чем вы попадете в канонический порядок или вложение. Хотя комментарий в источнике объясняет это, их использование не совсем интуитивно понятно, и я не смог найти источник, использующий их и функцию chrobak_payne_straight_line_drawing в сочетании. Вот пример, который я адаптировал из оригинального источника и других примеров .

Answer 2

Это похоже на ошибку в boost :: graph. У меня там другое нарушение доступа, возможно, из-за другой буст-версии, но определенно есть ошибка.

        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 остается неинициализированным. Крах! Вот что я вижу.