将Boost图形库与顶点的自定义类一起使用 [英] Using boost graph library with a custom class for vertices

问题描述

我目前正在尝试在现有的c ++项目中使用升压图形库.我想将自定义类的对象存储在增强图中.下面是一个带有自定义类定义的小示例，该类定义包含两个成员(一个字符串和一个int)及其对应的getter方法.

I am currently trying to use the boost graph library in an existing c++ project. I would like to store objects of a custom class in a boost graph. Below is a small example with a custom class definition with two members (a string and an int) and their corresponding getter methods.

我有几个问题:

1. 如何在Graphviz输出中包括字符串和int值?我使用boost::make_label_writer找到了一个类似问题的答案，但我不确定自己的示例是否可以采用(我是使用自定义类和共享指针).
2. 在一个图形中不能多次存储相同的对象(相同的字符串和int值).因此，我在自定义类中重载了两个比较运算符.我还读到我必须将图形类型定义的第二个模板参数更改为boost::setS，但这会导致编译器出现非常长的错误消息...

3. 比方说，我创建了一个自定义类的新对象:如何检查它是否已经存储在图中?

1. How can I include the string and int value in the Graphviz output? I found this answer to a similar question using boost::make_label_writer but I not really sure if my example can be adopted to this (I am using a custom class and shared pointers).
2. It should not be possible to store an identical object (same string and int value) more than one time in the graph. Therefore I overloaded two comparison operators in my custom class. I also read that I have to change the second template parameter of the graph type definition to boost::setS but that results in a really long error message of the compiler ...

3. Let's say I created a new object of my custom class: How can I check if it is already stored in the graph?

#include <iostream>
#include <boost/graph/graphviz.hpp>

class my_custom_class {
    public:

    my_custom_class(const std::string &my_string,
                    int my_int) : my_string(my_string),
                                  my_int(my_int) {}

    virtual ~my_custom_class() {
    }

    std::string get_my_string() const {
        return my_string;
    }

    int get_int() const {
        return my_int;
    }

    bool operator==(const my_custom_class &rhs) const {
        return my_string == rhs.my_string &&
               my_int == rhs.my_int;
    }

    bool operator!=(const my_custom_class &rhs) const {
        return !(rhs == *this);
    }

    private:

    std::string my_string;

    int my_int;
};

namespace boost {
    enum vertex_my_custom_class_t {
        vertex_my_custom_class = 123
    };
    BOOST_INSTALL_PROPERTY(vertex,
                           my_custom_class);
}

int main() {
    typedef boost::adjacency_list<boost::vecS,
            boost::vecS,
            boost::directedS,
            boost::property<boost::vertex_my_custom_class_t,
                            std::shared_ptr<my_custom_class>>> graph_t;

    typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;

    std::shared_ptr<my_custom_class> object_one = std::make_shared<my_custom_class>("Lorem", 123);
    std::shared_ptr<my_custom_class> object_two = std::make_shared<my_custom_class>("ipsum", 456);
    std::shared_ptr<my_custom_class> object_three = std::make_shared<my_custom_class>("Lorem", 123);

    std::cout << "object one: " << object_one->get_int() << "; " << object_one->get_my_string() << std::endl;
    std::cout << "object two: " << object_two->get_int() << "; " << object_two->get_my_string() << std::endl;
    std::cout << "object three: " << object_three->get_int() << "; " << object_three->get_my_string() << std::endl;

    std::cout << std::endl;

    std::cout << "object one == object two: " << (*object_one == *object_two) << std::endl;
    std::cout << "object one == object three: " << (*object_one == *object_three) << std::endl;

    std::cout << std::endl;

    graph_t graph;

    vertex_t vertex_one = boost::add_vertex(object_one, graph);
    vertex_t vertex_two = boost::add_vertex(object_two, graph);
    vertex_t vertex_three = boost::add_vertex(object_three, graph);

    boost::add_edge(vertex_one, vertex_two, graph);
    boost::add_edge(vertex_one, vertex_three, graph);

    boost::write_graphviz(std::cout, graph);

    return 0;
}

程序输出:

object one: 123; Lorem
object two: 456; ipsum
object three: 123; Lorem

object one == object two: 0
object one == object three: 1

digraph G {
0;
1;
2;
0->1 ;
0->2 ;
}

推荐答案

1. 在不更改声明的情况下，这会有些痛苦，但可能会发生:

1. without changing your declarations, this is a bit painful, but possible:

{
    boost::dynamic_properties dp;
    boost::property_map<graph_t, boost::vertex_my_custom_class_t>::type custom = get(boost::vertex_my_custom_class, graph);
    dp.property("node_id", boost::make_transform_value_property_map(std::mem_fn(&my_custom_class::get_int), custom));
    dp.property("label", boost::make_transform_value_property_map(std::mem_fn(&my_custom_class::get_my_string), custom));
    boost::write_graphviz_dp(std::cout, graph, dp);
}

打印: 在Coliru上直播

digraph G {
123 [label=Lorem];
456 [label=ipsum];
123 [label=Lorem];
123->456 ;
123->123 ;
}

您将需要在外部进行处理.为什么不拥有一组侵入性节点，并以这种方式验证约束.如您所说，更改顶点容器选择器"没有任何效果(最终只会以升序存储顶点描述符，而它们却像以前一样保持唯一性).

You will want to take care of this externally. Why not have an intrusive set of nodes and verify the contraints that way. Changing the Vertex Container Selector as you say has no effect (it just ends up storing the vertex descriptors in ascending order, while they stay unique as they were before).

副作用是从连续分配的顶点存储变为基于节点的(pro:迭代器/引用稳定性，con:分配开销，减少的引用位置，非隐式vertex_index).后者是罪魁祸首:BGL中的许多东西都需要一个顶点索引，并且如果不隐含一个顶点索引(例如，通过使用vecS)，则必须传递一个顶点索引.

A side effect is changing from contiguously allocated vertex storage to node-based (pro: iterator/reference stability, con: allocation overhead, reduced locality of reference, non-implicit vertex_index). The latter is the culprit: many things in BGL require a vertex index and if one is not implied (by using vecS e.g.) you have to pass one.

有趣的是，由于我将write_graphviz_dp与特定的node_id属性一起使用，所以现在不需要隐式顶点索引，因此您可以将vecS更改为setS并观察行为: 在Coliru上直播

Interestingly, since I used write_graphviz_dp with a specific node_id property there's no need for the implicit vertex index just now, so you could change vecS to setS and observe the behaviour: Live On Coliru

我认为现在不是检查的正确时间.除了访问外部顶点，没有比访问所有顶点更好的方法了.

I think that's not the right time to check. There is not really a better way than to visit all vertices, unless you keep an external index updated.

样式/简化

由于std::shared_ptr表示您拥有c ++ 11，因此让我们使用它.

Style/Simplification

Since std::shared_ptr implies you have c++11, let's use it.

此外，带有自定义属性的整个舞蹈在进行属性捆绑时通常更笨拙:从语法上讲，这些捆绑更容易且得到更好的支持.

Also, the whole dance with a custom property is mostly a way more clumsy of doing property bundles: these are syntactically easier and better supported.

查看区别:

注意:我一秒钟都太热情了，使用shared-ptr还是需要transform-value-property-map:

Note I was over-enthusiastic for a second, using a shared-ptr you still require the the transform-value-property-map:

在Coliru上直播

#include <boost/graph/graphviz.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>

struct MyVertex {
    MyVertex(std::string label, int id) : _label(std::move(label)), _id(id) {}

    std::string label() const { return _label; }
    int         id()    const { return _id;    }

    bool operator<(const MyVertex &rhs) const { return std::tie(_id, _label) < std::tie(rhs._id, rhs._label); }
  private:
    std::string _label;
    int _id;
};

using graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, std::shared_ptr<MyVertex>>;

int main() {
    graph_t graph;

    auto v1 = add_vertex(std::make_shared<MyVertex>("Lorem", 123), graph);
    auto v2 = add_vertex(std::make_shared<MyVertex>("ipsum", 456), graph);
    auto v3 = add_vertex(std::make_shared<MyVertex>("Lorem", 123), graph);

    add_edge(v1, v2, graph);
    add_edge(v1, v3, graph);

    {
        boost::dynamic_properties dp;
        auto bundle = get(boost::vertex_bundle, graph);
        dp.property("node_id", make_transform_value_property_map(std::mem_fn(&MyVertex::id), bundle));
        dp.property("label", make_transform_value_property_map(std::mem_fn(&MyVertex::label), bundle));

        write_graphviz_dp(std::cout, graph, dp);
    }
}

比较:没有共享指针

我并不是说您一定不能使用它，但是我也不确信您需要它.因此，让我们将其删除，以便您看到不同之处:

Comparing: Without Shared Pointers

I'm not saying you must not use it, but I'm also not convinced you need it. So, let's remove it so you see the difference:

在Coliru上直播

#include <boost/graph/graphviz.hpp>
#include <iostream>

struct MyVertex {
    std::string label;
    int id;
    bool operator<(const MyVertex &rhs) const { return std::tie(id, label) < std::tie(rhs.id, rhs.label); }
};

using graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, MyVertex>;

int main() {
    graph_t graph;

    auto v1 = add_vertex({"Lorem", 123}, graph);
    auto v2 = add_vertex({"ipsum", 456}, graph);
    auto v3 = add_vertex({"Lorem", 123}, graph);

    add_edge(v1, v2, graph);
    add_edge(v1, v3, graph);

    boost::dynamic_properties dp;
    dp.property("node_id", boost::get(&MyVertex::id, graph));
    dp.property("label", boost::get(&MyVertex::label, graph));

    write_graphviz_dp(std::cout, graph, dp);
}

大约是代码的一半.从这里我们可以探索如何添加所需的功能

That's roughly half the code. From here we can explore how to add the desired feature(s)

最简单的方法是在添加新节点之前检查现有节点:

The simplest thing to do is to check the existing nodes before adding a new one:

在Coliru上直播

#include <boost/graph/graphviz.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>

struct MyVertex {
    std::string label;
    int id;

    auto key() const { return std::tie(id,label); }
    bool operator< (const MyVertex &rhs) const { return key() <  rhs.key(); }
    bool operator==(const MyVertex &rhs) const { return key() == rhs.key(); }
    bool operator!=(const MyVertex &rhs) const { return key() != rhs.key(); }
};

using graph_t = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, MyVertex>;

int main() {
    graph_t graph;

    auto node = [&graph](std::string name, int id) {
        for (auto&& v : boost::make_iterator_range(vertices(graph)))
            if (graph[v] == MyVertex{name, id})
                return v;
        return add_vertex({name, id}, graph);
    };

    auto v1 = node("Lorem", 123);
    auto v2 = node("ipsum", 456);
    auto v3 = node("Lorem", 123);

    assert(v3==v1);

    add_edge(v1, v2, graph);
    add_edge(v1, v3, graph);

    boost::dynamic_properties dp;
    dp.property("node_id", boost::get(&MyVertex::id, graph));
    dp.property("label", boost::get(&MyVertex::label, graph));

    write_graphviz_dp(std::cout, graph, dp);
}

请注意v3现在等于v1:

digraph G {
123 [label=Lorem];
456 [label=ipsum];
123->456 ;
123->123 ;
}

这篇关于将Boost图形库与顶点的自定义类一起使用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！