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

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.

我希望像这样初始化:

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?:

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

推荐答案

Graph 概念的文档在这里很方便:https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/graph_concepts.html

The documentation for the Graph concepts is conveniently here: https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/graph_concepts.html

所以 - 你从来没有告诉我们你打算使用什么算法.

So - you never told us what algorithms you intend to use.

让我挑一个例子:BFS.文档说它需要:

So let me pick an examples: BFS. The docs say it requires:

有向图或无向图.图类型必须是顶点列表图 和 发生率图.

A directed or undirected graph. The graph type must be a model of Vertex List Graph and Incidence Graph.

看看您预先存在的数据结构，您似乎只能轻松涵盖顶点列表用例.

Looking at your pre-existing data structures, it looks like you only cover the Vertex List use case easily.

边缘更多地实现为边缘列表.如果没有运行时或存储开销(这是数学问题，与库或代码质量无关)，就不可能从 Edge List 模拟发生率图.

The edges are implemented more as an Edge List. It's not possible to emulate Incidence Graph from Edge List without runtime or storage overhead (that's mathematics, nothing to do with library or code quality).

实际上，您很可能忽略了与问题相关的部分预先存在的数据结构，因为大多数算法仅在 Vertex+Edge 列表上是非常次优的.

In reality, it's pretty likely that you omitted parts of your pre-existing data-structures that are relevant to the problem, as most algorithms will be highly sub-optimal on just Vertex+Edge lists.

在实践中，我认为您的边列表可能像经典的邻接列表一样组织(例如，按源顶点排序，因此您可以按源顶点进行 O(log(n)) 查找).

In practice I suppose you Edge list might be organized like a classical adjacency list (e.g. ordering by source vertex, so you CAN have a O(log(n)) lookup by source vertex).

对于下面的示例我假设是这种情况.请记住，我们只是接近事件图概念的复杂性保证:

For the example below I'm assuming this is the case. Keep in mind we're only approaching the complexity guarantees from Incidence Graph Concept:

source()、target() 和 out_edges() 函数都必须是常数时间.out_degree() 函数必须与出边数成线性.

Complexity guarantees

The source(), target(), and out_edges() functions must all be constant time. The out_degree() function must be linear in the number of out-edges.

要真正满足这些要求，您需要为每个顶点专门存储外边

那么，让我们开始吧:

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 *>;
}

实现图形概念

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

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.

看到它住在 Coliru

另外需要的是算法的参数.您需要颜色图和顶点索引图.这是完全正常的，如果您有例如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:

生活在 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{}));