提升图形拷贝和删除顶点 [英] boost graph copy and removing vertex

查看：138
本文介绍了提升图形拷贝和删除顶点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

如何复制提振图进入第二升压曲线，这样我就可以利用从第一张图中提取的顶点描述符修改，而无需修改第一个第二个？

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 ?

我有一个提升图形 G1 从中我摘录了一对夫妇的顶点描述符。现在，我想用这个顶点描述符做了一些处理，以 G1 名为 G2 的副本。如果我使用的线沿线的东西：

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;

复制的图形，然后我可以访问 G2 利用提取顶点描述符G1 使用的东西的一个顶点属性像 G2 [vertex_descriptor的] ，但我无法从图中删除顶点。

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.

我知道有可用的 copy_graph 功能，但我真的不明白（或我不知道如何读取）的 DOC 并做的boost :: copy_graph（G1， G2）产生了很多错误的：

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).

和为硬道理，没有这将在所有工作如果顶点描述符不是一个整数类型，首先，如当顶点容器选择是别的东西比的boost ::血管内皮细胞（列表，集合等）。

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.).

BGL的有两个基本要素，在这里适用似乎：

The BGL has two primitives that seem applicable here:


  1. 过滤图;

在这里，你没有创建一个实际的副本，只需通过提供（可选）顶点和边过滤predicates创建原始图的过滤视图。

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.

子图

如果你想（嵌套）父母与子女之间的图表双向可变的关系，这是最合适的。即如果你知道的在构建图表的是，其中一个图层次的级别是什么节点，你可以前preSS与的boost ::子＆LT;＆GT ; 层次结构。这些将自动保持同步;即如果添加一个节点到子图，父图将包含太;在子图，如果你修改/删除一条边，同样的改变，是活体现在所有父图形。

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.

在这种情况下我觉得 filtered_graph＆LT;＆GT; 是真正贴近您的需求。下面是一个使用 STD演示写入的图形，而活的过滤器，它::设为＆LT;顶点描述＆GT; 。的结果使用GraphViz的可视化：

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:

<大骨节病> 住在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);
}

这篇关于提升图形拷贝和删除顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
C/C++开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆