在现有数据结构上使用BGL算法(作为矢量< Object >的边和顶点)需要使用什么? [英] What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object >)?

查看：60 发布时间：2020/9/22 5:26:47 c++ boost graph boost-graph

本文介绍了在现有数据结构上使用BGL算法(作为矢量< Object *>的边和顶点)需要使用什么?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有这样的自定义数据结构:

I have custom data structures like this :

vector<myVertex *> my_vertices;
vector<myEdge *> my_edges;

我的类myEdge具有source()和target()方法，返回myVertex *，所以它应该已经准备好了，对吧?

My class myEdge has source() and target() methods, returning myVertex*, so it should be quite ready as is, right?

要在容器中使用BGL图，我需要做什么外部适应?我知道文档中的适配器示例，但将不胜感激！

What external adaptation do I need to do to use a BGL graph with my containers? I am aware of the adaptor examples in the doc, yet some help would be much appreciated!

我感兴趣的是纯粹的adjacency_list基本图类型，还不确定我需要的图遍历概念.

I am interested is the sheer adjacency_list basic-graph type, not sure about the graph traversal concepts I need yet.

到目前为止，我对adjacency_list参数的了解:

What I understood so far about the adjacency_list parameters :

adjacency_list<OutEdgeListS, VertexListS, DirectedS,
             VertexProperty, EdgeProperty, GraphProperty, EdgeListS>

OutEdgeListS和VertexListS是用于表示每个顶点的(1)边缘列表和(2)顶点列表的容器的选择器.这些容器分别保存为元素vertex_descriptor和edge_descriptor.我的容器类型是简单的std :: vector，所以我想我不需要像example/container_gen.cpp中那样创建新的容器类型.一世必须简单地(可能使用graph_traits)精确地确定我的容器元素的类型是指向对象的指针.
VertexProperty和EdgeProperty旨在用作内部大容量存储，以获取其他信息，例如颜色标签，边缘权重...并自几年以来提供捆绑属性功能.

OutEdgeListS and VertexListS are selectors for the containers used to represent the (1) edge-list for each of the vertices, and (2) the vertex list. These containers hold as elements vertex_descriptor and edge_descriptor respectively. My container type is the simple std::vector, so I guess I do not need to create a new container type as in example/container_gen.cpp. I must need to simply precise, probably with graph_traits, that the type of my container elements is pointer-to-object.
VertexProperty and EdgeProperty are intended to be used as internal bulk storage for additional information, for example color tags, edge weights... and offer since a few years the bundled-property feature.

我希望顶点和边缘描述符不默认为整数，而是指向我的对象的指针. BGL文档明确指出，在2002年版的中，这是可行的这本书，12.1.2:

I would like the vertex and edge descriptors to not default to integers, but to be pointers to my objects. BGL documentation explicitly states that this is feasible in the 2002-version of the book, 12.1.2 :

面向对象的图形实现可能使用指针进行堆分配的顶点对象.使用图特征类，这些差异由顶点描述符关联类型隐藏.

An object-oriented graph implementation might use pointers to heap allocated vertex objects. With the graph traits class, these differences are hidden by the vertex descriptor associated type.

尽管它似乎已从当前的1.70在线文档中消失了.

Although it seems to have disapeared from the current 1.70 online doc.

理想情况下，我想这样初始化:

I would ideally like to initialize like this :

MyGraph g(const& my_edges,const& my_vertices,
  undirected_tag, some_color, someweights, allow_parallel_edges_tag);

P.S.我对在property_map中填充对象指针不感兴趣.我不愿意使用'default vecS'，这是一个std :: vector，其中描述符是一个整数. 我愿意使用自定义vecS"作为对象指针的std :: vector；对于OutEdgeList和VertexList.

P.S. I am not interested in stuffing object pointers in the property_map. I am willing to not use 'default vecS', a std::vector where the descriptor is an integer. I am willing to use a 'custom vecS' as a std::vector of object pointers ; for both OutEdgeList and VertexList.

这与"1"是完全相同的问题. 这个.除非它从未得到答案...而且建议的解决方案是针对"2."，并带有property_map和昂贵的双重映射:).在研究了数百个SO主题数小时之后，大多数人似乎建议使用property_maps而不是使用自定义容器.人们倾向于使用property_maps存储实际的节点和边线-它们的对象指针，并让vertex& edge_descriptor保留纯粹的默认整数索引.然而，根据我的阅读，在这里，在"vertex_descriptor"下方有一个内部索引层来增强.

Edit : this is the same exact question as the "1." of this one. Except that it never got answered... and the proposed solution was for "2.", with property_map and expensive double mapping :). It looks, after having digged hundreds of SO topics for hours, that most people recommend using property_maps rather than working with custom containers. People tend to use property_maps to store the actual nodes and edges - their object pointers, and let the vertex&edge_descriptors hold sheer default integer indexes. Yet, from what I read here, there is "below" vertex_descriptor a real-index layer internal to boost.

作为上下文:我计划使用dijkstra/johnson_all_pairs_shortest_paths(带有前身地图和访客吗?)，以及进一步优化带有 https://github.com/pgmodeler/pgmodeler/pull/1232 .

As context : I plan to use dijkstra/johnson_all_pairs_shortest_paths (with predecessor map and a visitor?), and further optimal-dreyfus-wagner for steiner trees with http://paal.mimuw.edu.pl/, a library on top of the bgl. To make a sql join-solver for the dbms-erd tool pgmodeler https://github.com/pgmodeler/pgmodeler/pull/1232.

很棒的信息，它们将所有信息粘合在一起，使我掌握了诸如图形概念之类的一些核心点. 我问我如何在自定义数据结构中使用邻接表，然后您去解释了如何定义一个完全自定义的图.

Awesome piece of information, that glues all pieces together and made me catch up on some core points such as graph concepts. I came asking how to use adjacency list with custom data structures, and you went to explain how to define an entirely custom graph.

我即将研究方法之间的权衡:

I am about to study tradeoffs between approaches :

按原样保留我的数据结构，以及您对自定义图形的解决方案.一世会花很多时间没有时间进行初始化，但可能会花费很多更多时间寻找前沿.空间复杂度低，但时间长复杂性.
相同的方法，但是重构我的库，添加专用存储，每个顶点的入射边向量(作为的类属性 myVertex?).恒定时间边缘查询，而不是O(log(n))与 (1)std :: equal_range吗?也许是最好的选择.
使用adjacency_list但具有bgl时间复杂性保证.
- 实例化默认邻接表，使用我的库容器/使用捆绑/内部属性.高空间复杂性;时间复杂度低，但仅适用于bgl算法，初始化会很长.
- 您是否还要详细说明是否拥有适当的OutEdgeList和 VertexList通过自定义使用邻接列表类容器选项?持续引用那些持续时间吗?我猜测在这一点上，adjacency_list的实现可能不是如此灵活.

keep my data structures as is, and your solution of a custom graph. I will be spending quite to no time initializing, but probably a lot more time finding out-edges. Low space complexity, but high time complexity.
Same approach, but refactor my library, add dedicated storage, with a vector of incident edges per vertex (as a class attribute of myVertex?). Constant-time out-edge lookup rather than O(log(n)) with (1) std::equal_range ? Probably the best option.
Use an adjacency_list but and have the bgl time-complexity guarantees.
- Instantiate a default adjacency list, setup dual-way mapping with my library containers / use bundled/internal properties. High space complexity ; low time complexity but for the bgl algos only, initialization will be long.
- Do you care to also elaborate if having a proper OutEdgeList and VertexList makes using the adjacency-list class with custom containers an option ? Keeping references to those lasts ? I suspect at this point that the implementation of adjacency_list might not be that flexible.

实现图形概念

您想保留对现有数据结构的引用:

Fulfilling the Graph Concepts

You wanted to keep references to the pre-existing data structures:

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        Vertices& _vertices;
        Edges& _edges;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  { }
    };
}

现在，我将逐个列出每个概念所需的特征类型列表:

Now, I'll just run down the list of required trait types per concept:

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

最后重新打开名称空间，以便ADL可以找到满足有效表达式"条件所需的以下功能:

And finally re-open the namespace so ADL can find these functions that are required to satisfy the "valid expressions" criteria:

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }
}

这大致上功能等同于顶点容器的邻接列表和setS.

查看 在Coliru上直播

除此以外，所有其他要求都是用于算法的参数的.您既需要颜色图又需要顶点索引图.这是完全正常的，如果您有例如adjacency_list<vecS, listS, directedS>.

All that's required in addition is for the arguments of the algorithm. You'd need both the color map and the vertex index map. This is completely normal and would also be required if you had e.g. adjacency_list<vecS, listS, directedS>.

我将把索引图隐藏在MyGraph包装器内，并显示颜色图，以便您选择首选项:

I'll hide the index map inside the MyGraph wrapper and expose the color map so you can pick your preference:

在Coliru上直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/container/flat_map.hpp>
#include <algorithm>

namespace YourLibrary {
    struct myVertex {
    };

    struct myEdge {
        myVertex* _s = nullptr;
        myVertex* _t = nullptr;

        myVertex* source() const { return _s; }
        myVertex* target() const { return _t; }
    };

    using Vertices = std::vector<myVertex *>;
    using Edges = std::vector<myEdge *>;
}

namespace Glue {

    struct MyGraph {
        struct EdgeOrder {
            template <typename A, typename B>
                bool operator()(A const* a, B const* b) const { return source(a) < source(b); }
            private:
            static auto source(YourLibrary::myVertex const* v) { return v; }
            static auto source(YourLibrary::myEdge const* e) { return e->source(); }
        };

        using Vertices = YourLibrary::Vertices;
        using Edges = YourLibrary::Edges;

        using Index = boost::container::flat_map<Vertices::value_type, std::size_t>;

        Vertices& _vertices;
        Edges& _edges;
        Index _index;

        MyGraph(Vertices& vv, Edges& ee) : _vertices(vv), _edges(ee)  {
            _index.reserve(vv.size());
            std::size_t i = 0;
            for(auto v : vv) { _index[v] = i++; }
        }
    };
}

namespace boost {

    template <> struct graph_traits<Glue::MyGraph> {
        // Due to Graph concept
        using vertex_descriptor      = YourLibrary::myVertex*;
        using edge_descriptor        = YourLibrary::myEdge*;
        using directed_category      = directed_tag;
        using edge_parallel_category = allow_parallel_edge_tag;
        static vertex_descriptor null_vertex() { return nullptr; }

        // Due to Vertex List concept
        struct traversal_category : vertex_list_graph_tag, incidence_graph_tag { };
        using vertex_iterator        = Glue::MyGraph::Vertices::const_iterator;
        using vertices_size_type     = std::size_t;

        // Due to Incidence Graph concept
        using out_edge_iterator = Glue::MyGraph::Edges::const_iterator;
        using degree_size_type = std::size_t;
    };

}

namespace Glue {
    // Due to Vertex List concept
    auto vertices(MyGraph const& g) {
        return std::make_pair(g._vertices.begin(), g._vertices.end());
    }

    std::size_t num_vertices(MyGraph const& g) {
        return g._vertices.size();
    }

    // Due to Incidence Graph concept
    auto source(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->source();
    }
    auto target(YourLibrary::myEdge const* e, MyGraph const& g) {
        return e->target();
    }

    auto out_edges(YourLibrary::myVertex const* v, MyGraph const& g) {
        return std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});;
    }
    std::size_t out_degree(YourLibrary::myVertex const* v, MyGraph const& g) {
        auto oee = std::equal_range(g._edges.begin(), g._edges.end(), v, MyGraph::EdgeOrder{});
        return std::distance(oee.first, oee.second);
    }

    // Due to BFD requiring the index_map
    auto get(boost::vertex_index_t, MyGraph const& g) {
        return boost::make_assoc_property_map(g._index);
    }
}

int main() {
    // I hate manual memory management, so let's own some objects
    auto a = std::make_unique<YourLibrary::myVertex>();
    auto b = std::make_unique<YourLibrary::myVertex>();
    auto c = std::make_unique<YourLibrary::myVertex>();
    auto ab = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{a.get(), b.get()});
    auto bc = std::make_unique<YourLibrary::myEdge>(YourLibrary::myEdge{b.get(), c.get()});

    // These were given in your question:
    YourLibrary::Vertices vv { a.get(), b.get(), c.get() };
    YourLibrary::Edges ee { ab.get(), bc.get() };

    // this is the glue required to fulfill the BGL concepts:
    Glue::MyGraph g(vv, ee);

    // this is showing that you can now BFS on it
    using V = boost::graph_traits<Glue::MyGraph>::vertex_descriptor;
    V start_vertex = a.get();
    std::map<V, boost::default_color_type> color_data;

    boost::breadth_first_search(g, start_vertex,
            boost::visitor(boost::default_bfs_visitor{})
            .color_map(boost::make_assoc_property_map(color_data)));
}

结论

算法有要求，只要满足要求，就可以使用所需的任何数据结构.

Conclusion

Algorithms have requirements, and as long as you satisfy them, you can use whatever data structure you want.

在这种情况下，您可能要真正确定所做的假设，并将其添加到MyGraph构造函数中:

In this case you MIGHT want to be really sure about the assumptions made and add this to the MyGraph constructor:

assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));

这篇关于在现有数据结构上使用BGL算法(作为矢量< Object *>的边和顶点)需要使用什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文

在现有数据结构上使用BGL算法(作为矢量< Object >的边和顶点)需要使用什么? [英] What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object >)?

问题描述

推荐答案

复杂性保证

Complexity guarantees

实现图形概念

Fulfilling the Graph Concepts

结论

Conclusion

相关文章

C/C++开发最新文章

热门教程

热门工具

登录关闭

在现有数据结构上使用BGL算法(作为矢量&lt; Object *&gt;的边和顶点)需要使用什么? [英] What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector&lt;Object *&gt;)?

问题描述

推荐答案

复杂性保证

Complexity guarantees

实现图形概念

Fulfilling the Graph Concepts

结论

Conclusion

相关文章

C/C++开发最新文章

热门教程

热门工具

登录 关闭

在现有数据结构上使用BGL算法(作为矢量< Object >的边和顶点)需要使用什么? [英] What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object >)?

登录关闭