增强图形复制和删除顶点

2021-12-24 00:00:00 graph c++ 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) 产生很多错误:

在/usr/include/boost/graph/adjacency_list.hpp:246:0 包含的文件中，来自/home/malcolm/AASS/sketch_maker/includes/TopologicalMap/Global.hpp:6，来自/home/malcolm/AASS/sketch_maker/includes/MapComparator/Match.hpp:4，来自/home/malcolm/AASS/sketch_maker/includes/MapComparator/Hypothese.hpp:4，来自/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:4，来自/home/malcolm/AASS/sketch_maker/Test/test_comparisor.cpp:11:/usr/include/boost/graph/detail/adjacency_list.hpp:在 '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: 需要来自'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: 需要来自'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: 来自'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: 来自'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:需要替换‘模板<类配置、类基类、类属性>typename boost::property_map::const_type boost::get(Property, const boost::adj_list_helper&) [with Config = boost::detail::adj_list_gen, boost::listS, boost::listS, boost::undirectedS,topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property, boost::listS>::config;Base = boost::undirected_graph_helper, boost::listS, boost::listS, boost::undirectedS, topologicalmap::Place, topologicalmap::Gateway_struct, boost::no_property, boost::listS>::config>;属性 = boost::vertex_index_t]'/usr/include/boost/graph/copy.hpp:353:57: 来自 '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]’/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:32:150:从这里需要/usr/include/boost/graph/detail/adjacency_list.hpp:2498:29: 错误:形成对无效的引用typedef value_type&参考;^/usr/include/boost/graph/detail/adjacency_list.hpp:2499:35: 错误:形成对无效的引用typedef const value_type&const_reference;^/usr/include/boost/graph/detail/adjacency_list.hpp:2502:47: 错误:形成对无效的引用<图形、值类型、参考、标签>类型;^/usr/include/boost/graph/detail/adjacency_list.hpp:2504:53: 错误:形成对无效的引用<图形、value_type、const_reference、标签>const_type;^在/home/malcolm/AASS/sketch_maker/includes/TopologicalMap/GraphPlace.hpp:13:0 包含的文件中，来自/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:5，来自/home/malcolm/AASS/sketch_maker/Test/test_comparisor.cpp:11:/usr/include/boost/graph/copy.hpp: 在实例化 '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]’:/home/malcolm/AASS/sketch_maker/includes/MapComparator/Cluster.hpp:32:150:从这里需要/usr/include/boost/graph/copy.hpp:353:57: 错误:没有匹配的函数调用'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]),

错误信息比那更大，但我只取了开头.

解决方案

天真的方法有什么问题?

正如我在另一个答案中评论的那样，简单地通过源顶点描述符删除一个顶点将不会按预期工作，因为它会使变异副本中的所有更高的顶点无效.

因此，如果您要移除第二个顶点，很可能您会移除另一个与预期不同的顶点.

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

对于硬钳来说，如果顶点描述符不是一开始的整数类型，例如，这些都不会起作用.当顶点容器选择器不是 boost::vecS(listS、setS 等)时.

如何解决?

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

过滤图；
这里不创建实际副本，只需通过提供(可选)顶点和边过滤谓词来创建原始图的过滤视图".
子图
如果您想要(嵌套)父图和子图之间的双向可变关系，这是最合适的.IE.如果您知道在构建图形时哪些节点位于图形层次结构"的哪个级别"中，那么您可以使用 boost::subgraph<> 层次结构来表达.这些将自动保持同步；即如果你向子图中添加一个节点，父图也将包含它；如果您修改/删除子图中的边，所有父图中都会实时"反映相同的更改.

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

生活在 Coliru

#include #include 使用命名空间提升；结构顶点属性{内部标识；std::string 标签；};结构边属性{双倍重量；};使用 Graph_t = boost::adjacency_list;////////////////////////////////////////////////////保存点文件以渲染到 PNG#include 模板void save_dot_file(std::string const& fname, G& graph) {动态属性 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);}////////////////////////////////////////////////////使用简单的顶点过滤器过滤图#include #include 使用 V = Graph_t::vertex_descriptor;使用 Filtered = filters_graph>;////////////////////////////////////////////////////演示int main(){图_tg;//有一个过滤的副本"f，它只是删除了一组顶点:std::set移除_设置；过滤后的 f(g, keep_all{}, [&](V v){ return removed_set.end() == removed_set.find(v); });//构建一个具有 3 个顶点的演示图auto u = boost::add_vertex(VertexProperties{ 10, "十" }, g);auto v = boost::add_vertex(VertexProperties{ 20, "Twenty" }, g);auto w = boost::add_vertex(VertexProperties{ 30, "三十" }, 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_dot_file("original.dot", g);//空过滤器:save_dot_file("filtered1.dot", f);//移除 `v` ("Twenty")remove_set.insert(v);save_dot_file("filtered2.dot", f);}

How do I copy a boost graph into a second boost graph so that I can use the vertex descriptor extracted from the first graph to modify the second one without modifying the first one ?

I have a boost graph g1 from which I extracted a couple of vertex descriptor. Now I want to use this vertex descriptor to do some processing to a copy of g1 named g2. If I use something along the lines of :

g2 = g1;

to copy the graph then I can access the vertex properties of g2 using vertex descriptor extracted from g1 using something like g2[vertex_descriptor] but I cannot remove a vertex from the graph.

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

Does nothing to my graph and the vertex is still there.

I know there is a copy_graph function available but I don't really understand (or I don't know how to read) the doc and doing boost::copy_graph(g1, g2) yield a lot of errors :

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]),

The error message is bigger than that but I took only the beginning.

解决方案

What's wrong with the naive approach?

As I commented on the other answer, simply removing a vertex by the source vertex-descriptor will not work as expected, because it invalidates all the higher vertices in the mutated copy.

So if you were to remove a second vertex, chances are that you'd be removing a different vertex than the one intended.

What's worse, all the property lookups would be invalid (if done against original property maps).

And for the clincher, none of this would work at all if the vertex descriptor wasn't an integral type to begin with, e.g. when the vertex container selector was something else than boost::vecS (listS, setS etc.).

How to solve it?

The BGL has two primitives that seem applicable here:

Filtered Graphs;

Here you do not create an actual copy, just create a "filtered view" of the original graph by supplying (optional) vertex and edge filtering predicates.
Subgraphs

This is most suitable if you want a two-way mutable relation between (nested) parent and child graphs. I.e. if you know while building the graphs what nodes are in which "level" of a graph "hierarchy", you can express that with boost::subgraph<> hierarchies. These will automatically stay in synch; i.e. if you add a node to a child graph, the parent graph will contain it too; if you modify/remove an edge in a child graph, the same changes are "live" reflected in all parent graphs.

In this scenario I think that filtered_graph<> is really close to your need. Here's a demo that writes the graph, and "live-filters" it using a std::set<vertex_descriptor>. The result is visualized using 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);
}

相关文章