在现有数据结构(边和顶点作为向量<对象*>)上使用 BGL 算法需要什么?

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

问题描述

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

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. Imust 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 :

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

虽然它似乎已经从当前的 1.70 在线文档中消失了.

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

我希望像这样初始化:

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

附言我对在 property_map 中填充对象指针不感兴趣.我愿意不使用默认 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_descriptors 保存纯粹的默认整数索引.然而，从我读到的在这里，下面"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(带有前驱映射和访问者?)，并进一步使用 http://paal.mimuw.edu.pl/，一个位于 bgl 之上的图书馆.为 dbms-erd 工具 pgmodeler 制作 sql join-solver 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 :

保持我的数据结构不变，以及你的自定义图形解决方案.一世将花费相当多的时间初始化，但可能很多更多的时间来寻找边缘.空间复杂度低，但时间长复杂性.
相同的方法，但重构我的库，添加专用存储，使用每个顶点的事件边向量(作为我的顶点?).恒定时间出边查找而不是 O(log(n)) 与(1) std::equal_range ?可能是最好的选择.
使用 adjacency_list 但具有 bgl 时间复杂度保证.
- 实例化一个默认的邻接表，设置双向映射与我的库容器/使用捆绑/内部属性.高空间复杂性；低时间复杂度但仅适用于 bgl 算法，初始化时间会很长.
- 您是否还想详细说明是否有合适的 OutEdgeList 和VertexList 使用自定义的 adjacency-list 类容器是一种选择吗?保留对那些 last 的引用?我猜测此时 adjacency_list 的实现可能不是那样灵活.

实现图形概念

您想保留对预先存在的数据结构的引用:

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的adjacency_list.

This would be roughly functionally equivalent to an adjacency_list with a setS for the vertex container.

看到它

另外需要的是算法的参数.您需要颜色图和顶点索引图.这是完全正常的，如果您有例如adjacency_list.

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:

#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 算法需要什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！