c – 提升图形复制并删除顶点
发布时间：2020-12-16 09:58:42 所属栏目：百科 来源：网络整理
导读：如何将增强图复制到第二个增强图中,以便我可以使用从第一个图中提取的顶点描述符来修改第二个图而不修改第一个图？ 我有一个增强图g1,我从中提取了几个顶点描述符.现在我想使用这个顶点描述符对名为g2的g1副本进行一些处理.如果我使用以下内容： g2 = g1; 为
|
如何将增强图复制到第二个增强图中,以便我可以使用从第一个图中提取的顶点描述符来修改第二个图而不修改第一个图？
我有一个增强图g1,我从中提取了几个顶点描述符.现在我想使用这个顶点描述符对名为g2的g1副本进行一些处理.如果我使用以下内容： g2 = g1; 为了复制图形,我可以使用g1 [vertex_descriptor]之类的东西,使用从g1中提取的顶点描述符来访问g2的顶点属性,但是我无法从图中删除顶点. 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,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::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::vertex_index_t>’
/usr/include/boost/graph/properties.hpp:228:10: required from ‘struct boost::property_map<boost::adjacency_list<boost::listS,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::no_property,boost::listS>::config; Base = boost::undirected_graph_helper<boost::detail::adj_list_gen<boost::adjacency_list<boost::listS,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::no_property>; MutableGraph = boost::adjacency_list<boost::listS,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,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&,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::no_property>&)’
get(vertex_index,g_in),orig2copy[0]),
错误消息比那个大,但我只采取了开头. 解决方法
天真的方法有什么问题？
正如我对另一个答案所评论的那样,简单地通过源顶点描述符移除顶点将无法按预期工作,因为它会使变异副本中的所有较高顶点无效. 因此,如果您要删除第二个顶点,则可能会删除与预期顶点不同的顶点. 更糟糕的是,所有属性查找都是无效的(如果针对原始属性映射完成). 而对于紧要关头,如果顶点描述符不是一个完整的类型,那么这一切都不会起作用,例如：当顶点容器选择器不是boost :: vecS(listS,setS等)时. 怎么解决？ BGL有两个原语似乎适用于此： > Filtered Graphs; 在这里,您不创建实际副本,只需通过提供(可选)顶点和边缘过滤谓词来创建原始图形的“过滤视图”. 如果您希望(嵌套)父图和子图之间存在双向可变关系,这是最合适的.即如果您在构建图形时知道哪些节点处于图形“层次结构”的“级别”,则可以使用boost :: subgraph<>表示.层次结构.这些将自动保持同步;即,如果将节点添加到子图中,父图也将包含它;如果修改/删除子图中的边,则所有父图中反映的“实时”变化相同. 在这种情况下,我认为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);
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |