那些遇到过的问题

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

AID*_*ubt 4 c++ boost graph boost-graph

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

vector<myVertex *> my_vertices;
vector<myEdge *> my_edges;
Run Code Online (Sandbox Code Playgroud)

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

我需要做哪些外部调整才能将 BGL 图与我的容器一起使用？我知道文档中的适配器示例，但非常感谢您的帮助！

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

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

adjacency_list<OutEdgeListS, VertexListS, DirectedS,
             VertexProperty, EdgeProperty, GraphProperty, EdgeListS>
Run Code Online (Sandbox Code Playgroud)
  • OutEdgeListS和VertexListS是容器的选择器，用于表示（1）每个顶点的边列表，以及（2）顶点列表。这些容器分别作为元素 vertex_descriptor和edge_descriptor。我的容器类型是简单的 std::vector，所以我想我不需要像 example/container_gen.cpp 那样创建新的容器类型。我必须简单地精确，可能使用 graph_traits，我的容器元素的类型是指向对象的指针。
  • VertexProperty并且EdgeProperty旨在用作附加信息的内部大容量存储，例如颜色标签、边缘权重……并且几年来提供捆绑属性功能。

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

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

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

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

MyGraph g(const& my_edges,const& my_vertices,
  undirected_tag, some_color, someweights, allow_parallel_edges_tag);
Run Code Online (Sandbox Code Playgroud)

PS我对在property_map中填充对象指针不感兴趣。我愿意不使用“默认 vecS”，这是一个 std::vector，其中描述符是一个整数。我愿意使用“自定义 vecS”作为对象指针的 std::vector ；对于 OutEdgeList 和 VertexList。

编辑：这是与“1”完全相同的问题。的这一个。除了它从未得到回答......并且建议的解决方案是“2。”，带有property_map和昂贵的双重映射:)。在挖掘了数百个 SO 主题数小时之后，看起来大多数人建议使用 property_maps 而不是使用自定义容器。人们倾向于使用 property_maps 来存储实际的节点和边——它们的对象指针，并让 vertex&edge_descriptors 保存纯粹的默认整数索引。然而，从我在这里读到的内容来看，在 vertex_descriptor 的“下方”有一个内部的真实索引层来提升。

作为上下文：我计划使用 dijkstra/johnson_all_pairs_shortest_paths（带有前驱地图和访问者？），并进一步使用http://paal.mimuw.edu.pl/对 steiner 树进行优化-dreyfus-wagner ，这是一个位于血糖。为 dbms-erd 工具 pgmodeler https://github.com/pgmodeler/pgmodeler/pull/1232制作 sql join-solver 。

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

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

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

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

seh*_*ehe 5

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

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

所以让我挑一个例子：BFS。文档说它需要：

有向图或无向图。图类型必须是Vertex List Graph和Incidence Graph的模型。

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

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

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

在实践中，我想你的边列表可能像经典的邻接列表一样组织（例如，按源顶点排序，所以你可以按源顶点进行 O(log(n)) 查找）。

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

复杂性保证

的source()，target()和out_edges()功能都必须是恒定的时间。该out_degree()函数在出边数方面必须是线性的。

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

那么，让我们试一试：

模拟你的图书馆

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 *>;
}
Run Code Online (Sandbox Code Playgroud)

实现图形概念

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

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)  { }
    };
}
Run Code Online (Sandbox Code Playgroud)

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

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

}
Run Code Online (Sandbox Code Playgroud)

最后重新打开命名空间，以便 ADL 可以找到满足“有效表达式”条件所需的这些函数：

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);
    }
}
Run Code Online (Sandbox Code Playgroud)

这在功能上大致等同于setS顶点容器的 adjacency_list 。

看见 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)));
}
Run Code Online (Sandbox Code Playgroud)

结论

算法是有要求的，只要你满足了，你就可以使用任何你想要的数据结构。

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

assert(std::is_sorted(_edges.begin(), _edges.end(), EdgeOrder{}));
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

308 次

最近记录：

6 年，5 月 前
为什么图形的C++数据结构隐藏了连续的整数索引？ 8
更多相关链接
相关归档
C++ 11中COW std :: string实现的合法性 114
C++ 11的原始字符串文字R"(...)"中括号的基本原理是什么？ 68
可以从函数中获取函数的返回类型吗？ 42
铸造到'void'真的有什么作用？ 29
如何折叠STL容器？ 26
如何在C/C++中最好地处理动态多维数组？ 25
shared_dynamic_cast和dynamic_pointer_cast之间的区别 19
提升Asio serial_port - 需要帮助io 15
具有复杂参数的Riemann zeta函数 6
找不到boost_process cmake find_package 6
难疑归档
C++中的" - >"运算符是什么？ 8590
使用"let"和"var"在JavaScript中声明变量有什么区别？ 4199
你如何获得JavaScript的时间戳？ 3844
何时在CSS中使用margin和padding 2277
正确使用IDisposable接口 1586
检查变量是否是JavaScript中的字符串 1550
如何从文件内容创建Java字符串？ 1440
对JavaScript对象数组进行排序 1233
servlet如何工作？实例化,会话,共享变量和多线程 1105
致命错误:Python.h:没有这样的文件或目录 1042