Boost 图库：子图边引用原始图边

Question

我想要两种类型的图表（具有不同的捆绑属性，如下简化）。其中一种类型用于表示另一种类型的子图，因此我希望能够将子图的顶点和边映射到原始图中相应的顶点和边。

`// main graph structure
struct VertexProperties
{
    ...
};
struct EdgeProperties{
    double cost;
    ...
};
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperties, EdgeProperties>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
using Edge = boost::graph_traits<Graph>::edge_descriptor;

// subgraph structure
struct SubVertexProperties
{
    Vertex original_vertex;
};
struct SubEdgeProperties{
    Edge original_edge;
    ...
};

using SubGraph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, SubVertexProperties, SubEdgeProperties>;
using SubVertex = boost::graph_traits<Graph>::vertex_descriptor;
using SubEdge = boost::graph_traits<Graph>::edge_descriptor;

我创建了一个 Graph 类型的“原始”图和许多 SubGraph 类型的子图，此时我可以按预期访问原始图的边缘：

Graph g = ...;
SubGraph sg = ...; 
vector<int> sg_to_g_vertex; // maps each vertex in the subgraph to the corresponding vertex in original graph

for (auto e : make_iterator_range(edges(g))) {
     Vertex u = source(e, g);
     Vertex v = target(e, g);

    if (someCondition(u,v)) {
        boost::add_edge(vertex_map[u], vertex_map[v], {e, ...}, com_graph);
    }
}


for (auto e : make_iterator_range(edges(sg))
{
    std::cout << g[sg[e].original_edge].cost << std::endl;
}

这将打印出原始图中与子图中每条边相对应的边的成本。接下来，我将原始图和子图存储在一个结构中，该结构在我的代码中传递。一旦我将此结构传递给另一个函数，执行像上面最后一个这样的循环会导致乱码值。但是，如果我打印出原始图和子图的边缘以及相关的捆绑属性，它们看起来就很好。所以我假设边缘标识符

original_edge

不再有效。有没有办法存储这些标识符以使其保持可用？ 如果有帮助，在初始构建后，我不会从这些图中添加或删除顶点。

我尝试阅读 boost 文档和所有听起来相关的 stackoverflow 帖子，但我并不真正理解这些边缘标识符的类型以及如何获得更稳定的边缘标识符。

Answer 1

简单地说，某些因素会导致您的数据被重新分配，例如

• 由于按值传递而不是按引用移动/传递。
• 改变主图。描述符失效规则记录在此处：表：描述符和迭代器失效摘要

您需要添加更多代码以便我们指出错误。

这是我想象的代码，毫不奇怪，没有问题。请注意它如何举例说明引用传递和移动语义：

科利鲁

#include <boost/graph/random.hpp>
#include <iostream>
#include <random>

// main graph structure
struct VertexProperties {
    //...
};
struct EdgeProperties {
    double cost;
    //...
};

using boost::adjacency_list;
using boost::bidirectionalS;
using boost::vecS;
using Graph  = adjacency_list<vecS, vecS, bidirectionalS, VertexProperties, EdgeProperties>;
using Vertex = Graph::vertex_descriptor;
using Edge   = Graph::edge_descriptor;

// subgraph structure
struct SubVertexProperties {
    Vertex original_vertex;
};
struct SubEdgeProperties {
    Edge original_edge;
    //...
};

using SubGraph  = adjacency_list<vecS, vecS, bidirectionalS, SubVertexProperties, SubEdgeProperties>;
using SubVertex = Graph::vertex_descriptor;
using SubEdge   = Graph::edge_descriptor;
using boost::make_iterator_range;

struct LinkedSubgraph {
    Graph const& g;
    SubGraph     sg;

    std::map<Vertex, SubVertex> vertex_map;
    std::vector<int> sg_to_g_vertex;

    LinkedSubgraph(Graph const& g, auto condition) : g(g) {
        for (auto e : make_iterator_range(edges(g))) {
            Vertex u = source(e, g), v = target(e, g);

            if (condition(u, v)) {
                sg_to_g_vertex.push_back(v);
                add_edge(sub_vertex_for(u), sub_vertex_for(v), SubEdgeProperties{e}, sg);
            }
        }
    }

    SubVertex sub_vertex_for(Vertex v) {
        auto it = vertex_map.find(v);

        if (it == vertex_map.end())
            it = vertex_map.emplace(v, add_vertex(SubVertexProperties{v}, sg)).first;

        return it->second;
    };

    void report() const {
        for (auto se : make_iterator_range(edges(sg))) {
            auto e = sg[se].original_edge;
            std::cout << " (" << e << ":" << g[e].cost << ")";
        }
        std::cout << "\n";
    }
};

struct MyStruct {
    Graph g;
    std::list<LinkedSubgraph> subgraphs;

    MyStruct() {
        std::mt19937 prng{std::random_device{}()};
        generate_random_graph(g, 10, 20, prng);
        for (auto e : make_iterator_range(edges(g)))
            g[e].cost = std::uniform_real_distribution<double>(1, 10)(prng);
    }

    void addSubgraph(auto condition) {
        subgraphs.emplace_back(g, condition);
    }

    void report() const {
        for (auto& sg : subgraphs)
            sg.report();
    }
};

static auto trisection(unsigned n) {
    return [n](Vertex u, Vertex v) { return (u % 3u) == n && (v % 3u) == n; };
}

void passByReference(MyStruct& data) {
    data.addSubgraph(trisection(0));
    data.report();
}

void passByValue(MyStruct data) {
    data.addSubgraph(trisection(1));
    data.addSubgraph(trisection(2));
    data.report();
}

int main() {
    MyStruct data;

    passByReference(data);
    std::cout << "----\n";
    passByValue(std::move(data)); // NOTE move!

    assert(data.subgraphs.empty()); // moved-from object is empty
}

可能的输出如：

简化？

请注意，给定问题代码，可以使用

filtered_graph

适配器来大大简化。

看到它实时：代码减少 40%

这可能不太适合实际问题，因为子图向边/顶点添加了属性。

但是，在这种情况下，我建议改为添加 外部属性映射，这就是 BGL 设计的最佳表现。再想象一下：

住在Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/random.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
#include <random>
using boost::make_iterator_range;

// main graph structure
struct VertexProperties {};
struct EdgeProperties { double cost; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, //
                                    VertexProperties, EdgeProperties>;
using Vertex = Graph::vertex_descriptor;
using Edge   = Graph::edge_descriptor;

using VertexFilter = std::function<bool(Vertex)>;
using EdgeFilter   = std::function<bool(Edge)>;
using SubGraph     = boost::filtered_graph<Graph, EdgeFilter, VertexFilter>;

struct MyStruct {
    Graph g;

    struct Entry : SubGraph {
        struct Extra { int a, b, c; };
        std::vector<Extra>                     vprop_storage{num_vertices(*this)};
        std::map<edge_descriptor, std::string> eprop_storage;

        using SubGraph::SubGraph;

        auto extra() {
            return make_safe_iterator_property_map(vprop_storage.data(), vprop_storage.size(),
                                                   get(boost::vertex_index, *this));
        }

        auto a_map() { return make_transform_value_property_map(std::mem_fn(&Extra::a), extra()); };
        auto b_map() { return make_transform_value_property_map(std::mem_fn(&Extra::b), extra()); };
        auto c_map() { return make_transform_value_property_map(std::mem_fn(&Extra::c), extra()); };

        auto edge_name() { return boost::make_assoc_property_map(eprop_storage); }
    };
    std::list<Entry> subgraphs;

    MyStruct(MyStruct&&)            = delete; // g needs to be stable
    MyStruct& operator=(MyStruct&&) = delete;

    MyStruct() {
        std::mt19937 prng{std::random_device{}()};
        generate_random_graph(g, 10, 20, prng);
        for (auto e : make_iterator_range(edges(g)))
            g[e].cost = std::uniform_real_distribution<double>(1, 10)(prng);
    }

    Entry& addSubgraph(auto condition) { //
        return subgraphs.emplace_back(g, boost::keep_all{}, condition);
    }

    void report() {
        for (auto& sg : subgraphs) {
            boost::dynamic_properties dp;
            dp.property("node_id", get(boost::vertex_index, sg));
            dp.property("label", sg.a_map());
            dp.property("color", sg.b_map());
            dp.property("shape", sg.c_map());
            dp.property("label", sg.edge_name());
            dp.property("cost", get(&EdgeProperties::cost, sg));
            write_graphviz_dp(std::cout, sg, dp);
        }
    }
};

void passByReference(MyStruct& data) {
    data.addSubgraph([](Vertex u) { return (u % 2u) == 0; });

    {
        auto& sg = data.addSubgraph([](Vertex u) { return (u % 2u) == 1; });
        for (auto name = sg.edge_name(); auto e : make_iterator_range(edges(sg)))
            name[e] = boost::lexical_cast<std::string>(e);
    }

    data.report();
}

int main() {
    MyStruct data;
    passByReference(data);
}

更多现场演示：