在现有数据结构上使用 BGL 算法需要什么（边和顶点作为向量<Object *>）？

Question

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

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

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

我需要做什么外部改编才能在我的容器中使用 BGL 图？我知道 the adaptor examples in the doc，但如果能提供一些帮助，我们将不胜感激！

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

到目前为止我对 adjacency_list 参数的理解：

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 旨在用作内部大容量存储以存储附加信息，例如颜色标签、边缘权重...并在几年内提供捆绑的-属性特征。

我希望顶点和边描述符不默认为整数，而是指向我的对象的指针。 BGL 文档明确指出这是可行的 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 在线文档中消失了。

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

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。我愿意使用 'custom vecS' 作为对象指针的 std::vector ；对于 OutEdgeList 和 VertexList。

编辑：这是与“1”完全相同的问题。在 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 中，有 "below" vertex_descriptor 内部增强的实指数层。

作为上下文：我计划使用 dijkstra/johnson_all_pairs_shortest_paths（有前身地图和访客？），并进一步使用 optimal-dreyfus-wagner 用于带有 http://paal.mimuw.edu.pl/ 的 steiner 树，一个位于bgl。为 dbms-erd 工具 pgmodeler https://github.com/pgmodeler/pgmodeler/pull/1232.

创建一个 sql 连接求解器

20/05/19 : 回复sehe的回答

很棒的信息，将所有部分粘合在一起，让我了解了一些核心要点，例如图形概念。我来问如何使用自定义数据结构的邻接表，你去解释如何定义一个完全自定义的图。

我即将研究各种方法之间的权衡：

保持我的数据结构不变，以及你的自定义图的解决方案。我将花费相当多的时间进行初始化，但可能会花很多时间更多时间寻找优势。 space 复杂度低，但时间长复杂性。
相同的方法，但重构我的库，添加专用存储，使用每个顶点的入射边向量（作为 class 的属性我的顶点？）。恒定时间出边查找而不是 O(log(n)) 与 (1) std::equal_range ?可能是最好的选择。
使用 adjacency_list 但具有 bgl 时间复杂度保证。
- 实例化默认邻接表，设置双向映射库容器/使用 bundled/internal 属性。高space 复杂性；时间复杂度低，但仅适用于 bgl 算法，初始化会很长。
- 如果有合适的 OutEdgeList 和 VertexList 使邻接列表 class 与自定义一起使用容器是一种选择吗？保留对那些鞋楦的引用？我猜测在这一点上 adjacency_list 的实现可能不是那个灵活。

Answer 1

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

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

所以让我举一个例子：BFS。 The docs 说它需要：

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

查看您的 pre-existing 数据结构，您似乎只轻松涵盖了顶点列表用例。

边缘更多地作为边缘列表来实现。如果没有运行时间或存储开销（这是数学，与库或代码质量无关），就不可能从边列表中模拟 Incidence Graph。

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.

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:

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.

要真正满足这些要求，您需要为每个顶点提供 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 *>;
}

完成图形概念

您想保留对 pre-existing 数据结构的引用：

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

现在，我将运行列出每个概念所需的特征类型：

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

}

最后 re-open 命名空间，以便 ADL 可以找到满足 "valid expressions" 条件所需的这些函数：

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

这在功能上相当于顶点容器的 adjacency_list 和 setS。

看到了Live On Coliru

运行 BFS

另外需要的是算法的参数。您需要颜色图和顶点索引图。这是完全正常的，如果你有，也将是必需的。 adjacency_list<vecS, listS, directedS>.

我会将索引贴图隐藏在 MyGraph 包装器中并显示颜色贴图，以便您可以选择您的偏好：

Live On 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)));
}

结论

算法是有要求的，只要你满足了，你想用什么数据结构都行。

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

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

在现有数据结构上使用 BGL 算法需要什么（边和顶点作为向量<Object *>）？

What is needed to use BGL algorithms on existing data structures ( edges and vertices as vector<Object *>)?

c++

boost

graph

boost-graph

20/05/19 : 回复sehe的回答

Complexity guarantees

模拟你的图书馆

完成图形概念

运行 BFS

结论