Как использовать Boost 1.41.0 алгоритмы построения графиков

Question

У меня проблема с использованием алгоритмов компоновки ускорителей. boost verision 1_41_0 mingw g ++ 4.4.0.

Итак, есть проблемы, с которыми я столкнулся. Можете ли вы предложить мне их?

1. Функция fruchterman_reingold_force_directed_layout не скомпилирована.
2. Kamada_kawai_spring_layout скомпилирован, но программа разбилась.
3. Неправильная подготовка документации к алгоритмам макета, образец для fruchterman_reingold_force_directed_layout не скомпилирован.

Это мой пример. Чтобы использовать функцию, просто раскомментируйте ее. Строка 60, 61, 63.

#include <boost/config.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/graph_utility.hpp> 
#include <boost/graph/simple_point.hpp> 
#include <boost/property_map/property_map.hpp> 
#include <boost/graph/circle_layout.hpp> 
#include <boost/graph/fruchterman_reingold.hpp> 
#include <boost/graph/kamada_kawai_spring_layout.hpp> 
#include <iostream> 

//typedef boost::square_topology<>::point_difference_type Point; 
typedef boost::square_topology<>::point_type Point; 

struct VertexProperties 
{ 
    std::size_t index; 
    Point point; 
}; 

struct EdgeProperty 
{ 
    EdgeProperty(const std::size_t &w):weight(w) {} 
    double weight; 
}; 


typedef boost::adjacency_list<boost::listS, 
      boost::listS, boost::undirectedS, 
      VertexProperties, EdgeProperty > Graph; 

typedef boost::property_map<Graph, std::size_t VertexProperties::*>::type VertexIndexPropertyMap; 
typedef boost::property_map<Graph, Point VertexProperties::*>::type PositionMap; 
typedef boost::property_map<Graph, double EdgeProperty::*>::type WeightPropertyMap; 

typedef boost::graph_traits<Graph>::vertex_descriptor VirtexDescriptor; 

int main() 
{ 
    Graph graph; 

    VertexIndexPropertyMap vertexIdPropertyMap = boost::get(&VertexProperties::index, graph); 

    for (int i = 0; i < 3; ++i) { 
     VirtexDescriptor vd = boost::add_vertex(graph); 
     vertexIdPropertyMap[vd] = i + 2; 
    } 

    boost::add_edge(boost::vertex(1, graph), boost::vertex(0, graph), EdgeProperty(5), graph); 
    boost::add_edge(boost::vertex(2, graph), boost::vertex(0, graph), EdgeProperty(5), graph); 

    std::cout << "Vertices\n"; 
    boost::print_vertices(graph, vertexIdPropertyMap); 

    std::cout << "Edges\n"; 
    boost::print_edges(graph, vertexIdPropertyMap); 

    PositionMap positionMap = boost::get(&VertexProperties::point, graph); 
    WeightPropertyMap weightPropertyMap = boost::get(&EdgeProperty::weight, graph); 

    boost::circle_graph_layout(graph, positionMap, 100); 
    // boost::fruchterman_reingold_force_directed_layout(graph, positionMap, boost::square_topology<>()); 

    boost::kamada_kawai_spring_layout(graph, positionMap, weightPropertyMap, 
     boost::square_topology<>(), boost::side_length<double>(10), boost::layout_tolerance<>(), 
     1, vertexIdPropertyMap); 

    std::cout << "Coordinates\n"; 
    boost::graph_traits<Graph>::vertex_iterator i, end; 
    for (boost::tie(i, end) = boost::vertices(graph); i != end; ++i) { 
     std::cout << "ID: (" << vertexIdPropertyMap[*i] << ") x: " << positionMap[*i][0] << " y: " << positionMap[*i][1] << "\n"; 
    } 

    return 0; 
} 

Answer 1

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

Объявить свой график, как

typedef boost::adjacency_list<boost::vecS, 
      boost::vecS, boost::undirectedS, 
      VertexProperties, EdgeProperty > Graph; 

, если у вас есть хороший повод, чтобы сделать иначе, этот способ vertex_id уверен, что в [0, п).

Если вы удаляете фиктивные «+2» из ваших индексов vertexId, то ваш идентификатор вершин должен теперь соответствовать реальному вершинному id вершин (и поэтому ваша программа не должна segfault больше).

Это должно быть сделано для kamada_kaway, но IMHO ваш код может быть улучшен во многих отношениях, просто внимательно изучая пример кода BGL.

EDIT: фиксированная опечатка s/setS/vecS/