c++ - boost 图形复制和删除顶点

Question

如何将 boost 图复制到第二个 boost 图中，以便我可以使用从第一个图中提取的顶点描述符来修改第二个而不修改第一个？

我有一个 boost 图 g1，我从中提取了几个顶点描述符。现在我想使用这个顶点描述符对名为 g2 的 g1 拷贝进行一些处理。如果我使用以下内容:

g2 = g1;

复制图形然后我可以使用从 g1 中提取的顶点描述符访问 g2 的顶点属性，使用类似 g2[vertex_descriptor]但我无法从图中删除顶点。

boost::clear_vertex(v, _graph);
boost::remove_vertex(v, _graph);

对我的图表没有任何影响，顶点仍然存在。

我知道有一个可用的copy_graph 函数，但我不太理解(或者我不知道如何阅读)doc并执行 boost::copy_graph(g1, g2) 会产生很多错误:

In file included from /usr/include/boost/graph/adjacency_list.hpp:246:0,
                 from /home/malcolm/AASS/sketch_maker/includes/TopologicalMap/Global.hpp:6,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Match.hpp:4,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Hypothese.hpp:4,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:4,
                 from /home/malcolm/AASS/sketch_maker/Test/test_comparisor.cpp:11:
/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::adj_list_any_vertex_pa::bind_<boost::vertex_index_t, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, topologicalmap::Place>’:
/usr/include/boost/graph/detail/adjacency_list.hpp:2568:12:   required from ‘struct boost::detail::adj_list_choose_vertex_pa<boost::vertex_index_t, boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, topologicalmap::Place>’
/usr/include/boost/graph/detail/adjacency_list.hpp:2705:12:   required from ‘struct boost::adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, topologicalmap::Place, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:217:12:   required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:228:10:   required from ‘struct boost::property_map<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::vertex_index_t, void>’
/usr/include/boost/graph/detail/adjacency_list.hpp:1688:5:   required by substitution of ‘template<class Config, class Base, class Property> typename boost::property_map<typename Config::graph_type, Property>::const_type boost::get(Property, const boost::adj_list_helper<Config, Base>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property, boost::listS>::config; Base = boost::undirected_graph_helper<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>, boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property, boost::listS>::config>; Property = boost::vertex_index_t]’
/usr/include/boost/graph/copy.hpp:353:57:   required from ‘void boost::copy_graph(const VertexListGraph&, MutableGraph&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>; MutableGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>]’
/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:32:150:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2498:29: error: forming reference to void
         typedef value_type& reference;
                             ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2499:35: error: forming reference to void
         typedef const value_type& const_reference;
                                   ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2502:47: error: forming reference to void
           <Graph, value_type, reference, Tag> type;
                                               ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2504:53: error: forming reference to void
           <Graph, value_type, const_reference, Tag> const_type;
                                                     ^
In file included from /home/malcolm/AASS/sketch_maker/includes/TopologicalMap/GraphPlace.hpp:13:0,
                 from /home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:5,
                 from /home/malcolm/AASS/sketch_maker/Test/test_comparisor.cpp:11:
/usr/include/boost/graph/copy.hpp: In instantiation of ‘void boost::copy_graph(const VertexListGraph&, MutableGraph&) [with VertexListGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>; MutableGraph = boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>]’:
/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:32:150:   required from here
/usr/include/boost/graph/copy.hpp:353:57: error: no matching function for call to ‘get(boost::vertex_index_t, const boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property>&)’
                                   get(vertex_index, g_in), orig2copy[0]),

错误信息比那个大，但我只看了开头。

Answer 1

天真的方法有什么问题？

正如我对其他答案的评论，简单地通过源顶点描述符删除顶点将不会按预期工作，因为它会使变异拷贝中的所有更高顶点无效。

因此，如果您要删除第二个顶点，您可能会删除与预期顶点不同的顶点。

更糟糕的是，所有属性查找都将无效(如果针对原始属性映射进行)。

对于确定性来说，如果顶点描述符不是以整型开始的，那么这些方法都行不通，例如当顶点容器选择器不是 boost::vecS 时(listS、setS 等)。

如何解决？

BGL 有两个似乎适用于此的原语:

1. Filtered Graphs ;

   在这里您不创建实际拷贝，只是通过提供(可选)顶点和边过滤谓词创建原始图的“过滤 View ”。

2. Subgraphs

   如果你想要(嵌套的)父图和子图之间的双向可变关系，这是最合适的。 IE。如果您在构建图表时知道图表“层次结构”的哪个“级别”中有哪些节点，您可以用 boost::subgraph<> 表示层次结构。这些将自动保持同步；即，如果您将节点添加到子图，父图也将包含它；如果您修改/删除子图中的一条边，相同的更改会“实时”反射(reflect)在所有父图中。

在这种情况下，我认为 filtered_graph<>非常接近您的需要。这是一个编写图表的演示，并使用 std::set<vertex_descriptor> 对其进行“实时过滤” .使用 GraphViz 可视化结果:

Live On Coliru

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

using namespace boost;

struct VertexProperties {
    int id;
    std::string label;
};

struct EdgeProperties {
    double weight;
};

using Graph_t = boost::adjacency_list<listS, listS, directedS, VertexProperties, EdgeProperties>;

//////////////////////////////////////////////////
// saving dotfiles for rendering to PNG
#include <boost/graph/graphviz.hpp>

template <typename G>
void save_dot_file(std::string const& fname, G& graph) {
    dynamic_properties dp;
    dp.property("node_id", boost::get(&VertexProperties::id,    graph));
    dp.property("label",   boost::get(&VertexProperties::label, graph));
    dp.property("weight",  boost::get(&EdgeProperties::weight,  graph));

    std::ofstream ofs(fname);
    write_graphviz_dp(ofs, graph, dp);
}

//////////////////////////////////////////////////
// Filtering graphs with a simple vertex filter
#include <boost/graph/filtered_graph.hpp>
#include <boost/function.hpp>

using V        = Graph_t::vertex_descriptor;
using Filtered = filtered_graph<Graph_t, keep_all, boost::function<bool(V)> >;

//////////////////////////////////////////////////
// Demo
int main()
{
    Graph_t g;

    // have a filtered "copy" f that just removes a set of vertices:
    std::set<V> removed_set;
    Filtered f(g, keep_all{}, [&](V v){ return removed_set.end() == removed_set.find(v); });

    // build a demo graph with 3 vertices
    auto u = boost::add_vertex(VertexProperties{ 10, "Ten"    }, g);
    auto v = boost::add_vertex(VertexProperties{ 20, "Twenty" }, g);
    auto w = boost::add_vertex(VertexProperties{ 30, "Thirty" }, g);

    /*auto e1 =*/ boost::add_edge(u, v, EdgeProperties { 0.5 }, g);
    /*auto e2 =*/ boost::add_edge(v, w, EdgeProperties { 1.5 }, g);
    /*auto e3 =*/ boost::add_edge(w, u, EdgeProperties { 2.5 }, g);

    ///////////////////////////////////////
    // save the original graph
    save_dot_file("original.dot", g);

    // empty filter:
    save_dot_file("filtered1.dot", f);

    // removing `v` ("Twenty")
    removed_set.insert(v);
    save_dot_file("filtered2.dot", f);
}