如何使用Boost 1.41.0图形布局算法

Question

我在使用Boost图形布局算法时遇到了一些问题。

我的Boost版本是1_41_0，编译器是mingw g++ 4.4.0。

我遇到的问题如下，请问你能否给我提供建议？

1. 函数fruchterman_reingold_force_directed_layout没有被编译。
2. 函数kamada_kawai_spring_layout已编译，但程序崩溃。
3. Boost文档中关于布局算法的说明有误，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;
}

- Daniil

Answer 1

你不能仅仅通过将vertexIdPropertyMap命名为ID来使用它（如果你想提供自己的ID，你应该安装一个顶点ID属性，但这很少需要）。

将你的图声明为

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

除非你有充分的理由，否则这种方式可以确保vertex_id在[0，n)之间。

如果从vertexId索引中删除虚构的“+2”，则您的顶点ID应该与顶点的实际顶点ID匹配（因此您的程序不应再次segfault）。

这对于kamada_kaway来说应该足够了，但是在仔细查看BGL示例代码后，我认为您的代码可以在许多方面进行改进。

编辑：修正了拼写错误s/setS/vecS/

- baol

---

谢谢你的回答。我正在学习boost图形库。你能否提供一个使用boost图形库布局算法的示例？我认为boost图形库的示例和文档已经过时了。Daniil - Daniil