ui做标注的网站,湖南省建设厅李云,二建注册信息查询系统官网,网页模板素材大全Boost Graph Library#xff0c;简称BGL#xff0c;库中有各种各样经典的Graph算法#xff0c;这里介绍其中的VF2算法——vf2_subgraph_iso。
数据怎么存
在BGL中#xff0c;图是用adjacency_list类型数据存储#xff0c;也就是邻接列表#xff0c;里面可以存顶点信息简称BGL库中有各种各样经典的Graph算法这里介绍其中的VF2算法——vf2_subgraph_iso。
数据怎么存
在BGL中图是用adjacency_list类型数据存储也就是邻接列表里面可以存顶点信息连接边信息以下面的代码为例介绍下这个接口的使用方法具体详情如下代码所示
#includestring
#includeiostream
#includevector
#includestack
#includeboost/property_map/property_map.hpp
#includeboost/graph/adjacency_list.hpp
#include boost/graph/named_function_params.hpp
#include boost/graph/graphviz.hpp
#include boost/graph/properties.hpp
#include boost/graph/vf2_sub_graph_iso.hpp
using namespace std;
using namespace boost;//自定义顶点信息结构体
struct V {string m_name;int m_id;bool operator(const V other) // 这里需要重写这个运算符当使用自定义类型作为顶点类型时算法判断顶点是否相等最终会走到顶点的运算符中。{return m_id other.m_id;}};struct E {string m_name;double m_wight;bool operator(const E other)// 同顶点信息的运算符{return m_wight other.m_wight;}
};template typename Graph1, typename Graph2
struct MyVF2Callback // 自定义回调函数当算法运算完毕需要输出结果时是采用回调的方式输出结果所以会在重载的运算符()输出结果
{MyVF2Callback(const Graph1 graph1, const Graph2 graph2): graph1_(graph1), graph2_(graph2){}template typename CorrespondenceMap1To2, typename CorrespondenceMap2To1 bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const{// Print (sub)graph isomorphism mapBGL_FORALL_VERTICES_T(v, graph1_, Graph1)std::cout ( get(vertex_index_t(), graph1_, v) , get(vertex_index_t(), graph2_, get(f, v)) ) ;return true;}private:const Graph1 graph1_;const Graph2 graph2_;
};// 自定义比较函数根据顶点属性中的m_id进行排序,这里只是随便例举了一个属性当然可以使用任意的属性作比较
templatetypename PropertyMap
struct CompareById {const PropertyMap property_map;CompareById(const PropertyMap map): property_map(map) {}// 是以自定义顶点结构体的m_id作为判断依据bool operator()(const typename boost::property_traitsPropertyMap::key_type u,const typename boost::property_traitsPropertyMap::key_type v) const {return property_map[u].m_id property_map[v].m_id;}
};// 自定义顶点排序搜索函数
templatetypename Graph
std::vectortypename boost::graph_traitsGraph::vertex_descriptor
vertex_order_by_id(const Graph graph) {auto property_map get(vertex_name, graph);typedef decltype(property_map) PropertyMap;typedef typename boost::graph_traitsGraph::vertex_descriptor Vertex;std::vectorVertex vertex_order;std::copy(boost::vertices(graph).first, boost::vertices(graph).second,std::back_inserter(vertex_order));std::sort(vertex_order.begin(), vertex_order.end(), CompareByIdPropertyMap(property_map));return vertex_order;
}void main()
{typedef property edge_name_t, E edge_property; //定义边的属性其中E是自定义类型在途中使用get(edge_name, Graph)返回的就是E类型的property_map。typedef property vertex_name_t, V, property vertex_index_t, int //定义顶点的属性property vertex_index_t, int 表示顶点容器的索引值为int类型vertex_property;// Using a vecS graphs the index maps are implicit.typedef adjacency_list vecS, vecS, bidirectionalS, vertex_property,edge_property graph_type;// Build graph1graph_type graph1;add_vertex(V({ 1, 1 }), graph1); // 加入第一个顶点信息顶点属性数据是V({ 1, 1 })add_vertex(V({ 2, 2 }), graph1);// 加入第二个顶点信息顶点属性数据是V({ 2, 2 })add_vertex(V({ 3, 3 }), graph1);add_edge(0, 1, E({ e0, 11 }), graph1);// 加入边信息边的两个顶点idx是0和1边的属性数据是E({ e0, 11 })// Build graph2graph_type graph2;add_vertex(V({ 11, 1 }), graph2); // 同graph1add_vertex(V({ 22, 2 }), graph2);add_vertex(V({ 33, 3 }), graph2);add_edge(2, 2, E({e1, 10}), graph2);// create predicatestypedef property_map graph_type, vertex_name_t ::type vertex_name_map_t;typedef property_map_equivalent vertex_name_map_t, vertex_name_map_t vertex_comp_t;vertex_comp_t vertex_comp make_property_map_equivalent(get(vertex_name, graph1), get(vertex_name, graph2)); // 定义顶点的比较器最终会走到顶点类型中operator()里typedef property_map graph_type, edge_name_t ::type edge_name_map_t;typedef property_map_equivalent edge_name_map_t, edge_name_map_t edge_comp_t;edge_comp_t edge_comp make_property_map_equivalent(get(edge_name, graph1), get(edge_name, graph2));// 定义边的比较器最终会走到边类型中operator()里// Create callbackMyVF2Callback graph_type, graph_type callback(graph1, graph2); /*定义回调函数算法匹配结果会在这里输出如果使用BGL默认的 “vf2_print_callbackgraph_type, graph_type callback(graph1, graph2);”是没办法以自己的方式去处理输出数据默认的只是将输出输出在控制平台*//**这里是算法的入口主要是callback 和vertex_order_by_id(graph1)参数我们可以修改callback是回调函数算法结果输出的位置* vertex_order_by_id这个是小图搜索顶点的数组也就是这里容器的顺序就是算法搜索顶点的顺序默认的是 vertex_order_by_mult(graph1)* 是以顶点的入读和出度的乘积作为排序的参数如果希望自定义排序就需要按照要求定义一个排序参照上述代码中的vertex_order_by_id也就是输出的类型需要时是 std::vector typename graph_traits Graph ::vertex_descriptor 就是小图 vertex_descriptor可以理解为索引的数组。*/vf2_subgraph_iso(graph1, graph2, callback, vertex_order_by_id(graph1), edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));}详细的接口与参数的含义都在代码中注释了如果还有不理解的问题请留言一起讨论~
