c++ - 如何使用 Boost 的 vf2_subgraph_iso 检测多图上的子图同构?
问题描述
我正在尝试使用 Boostvf2_subgraph_iso()
来检测子图同构。
我可以在简单图上成功地做到这一点,但不能在多图(允许有多个边的图)上做到这一点。
考虑检测以下 G1 和 G2 之间的子图同构:
G1 是 G2 的子图,我想使用以下代码检测它:
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
int main()
{
// Define edge property
typedef boost::property<
boost::edge_name_t,
char
> edge_property;
// Define graph type
typedef boost::adjacency_list<
boost::vecS, // OutEdgeListS
boost::vecS, // VertexListS
boost::bidirectionalS, // DirectedS
boost::no_property, // VertexProperties
edge_property, // EdgeProperties
boost::no_property, // GraphProperties
boost::listS // EdgeListS
> MyGraphType;
// Build graph G1
MyGraphType g1;
std::vector<MyGraphType::vertex_descriptor> v1(3);
for (auto itr = v1.begin(); itr != v1.end(); ++itr) {
*itr = boost::add_vertex(g1);
}
boost::add_edge(v1[0], v1[1], edge_property('a'), g1);
boost::add_edge(v1[0], v1[2], edge_property('a'), g1);
boost::add_edge(v1[1], v1[2], edge_property('b'), g1);
// Build graph G2
MyGraphType g2;
std::vector<MyGraphType::vertex_descriptor> v2(3);
for (auto itr = v2.begin(); itr != v2.end(); ++itr) {
*itr = boost::add_vertex(g2);
}
boost::add_edge(v2[0], v2[1], edge_property('a'), g2);
boost::add_edge(v2[0], v2[2], edge_property('a'), g2);
boost::add_edge(v2[1], v2[2], edge_property('a'), g2);
boost::add_edge(v2[1], v2[2], edge_property('b'), g2);
// Create predicate of edge
typedef boost::property_map<MyGraphType, boost::edge_name_t>::type edge_name_map_t;
typedef boost::property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
edge_comp_t edge_comp = boost::make_property_map_equivalent(
boost::get(boost::edge_name, g1), boost::get(boost::edge_name, g2));
// Create callback
boost::vf2_print_callback<MyGraphType, MyGraphType> callback(g1, g2);
// Execute
const bool result = boost::vf2_subgraph_iso(
g1, g2, callback, boost::vertex_order_by_mult(g1),
boost::edges_equivalent(edge_comp));
std::cout << "subgraph isomorphic? " << std::boolalpha << result << std::endl;
return 0;
}
预期结果:
(0, 0) (1, 1) (2, 2)
subgraph isomorphic? true
实际结果:
subgraph isomorphic? false
我的代码哪里错了?
对不起我的英语不好。谢谢!
解决方案
vf2_subgraph_iso 将比较边缘的属性。在您的代码中,边 1->2 的属性在 graph1 中是“b”,但在 graph2 中是“a”、“b”。所以它们不是同一个结构。
如果您希望它在仅匹配所有属性的一部分时返回 true,您可以根据您的规则使用结构和重载运算符“==”。对于您的示例,以下代码会很好。
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
int main()
{
// Define edge property
struct EdgeProperties {
EdgeProperties() {}
EdgeProperties(char elabel) { _elabels.emplace_back(elabel);}
EdgeProperties(std::vector<char>& elabels) :_elabels(elabels) {}
/* overload == */
bool operator==(EdgeProperties const& other) const {
for (auto& my_l:_elabels) {
for (auto& o_l:other._elabels) {
if (my_l == o_l) return true;
}
}
return false;
}
std::vector<char> _elabels;
};
typedef boost::property<
boost::edge_name_t,
EdgeProperties
> edge_property;
// Define graph type
typedef boost::adjacency_list<
boost::vecS, // OutEdgeListS
boost::vecS, // VertexListS
boost::bidirectionalS, // DirectedS
boost::no_property, // VertexProperties
edge_property, // EdgeProperties
boost::no_property, // GraphProperties
boost::listS // EdgeListS
> MyGraphType;
// Build graph G1
MyGraphType g1;
std::vector<MyGraphType::vertex_descriptor> v1(3);
for (auto itr = v1.begin(); itr != v1.end(); ++itr) {
*itr = boost::add_vertex(g1);
}
boost::add_edge(v1[0], v1[1], edge_property('a'), g1);
boost::add_edge(v1[0], v1[2], edge_property('a'), g1);
boost::add_edge(v1[1], v1[2], edge_property('b'), g1);
// Build graph G2
MyGraphType g2;
std::vector<MyGraphType::vertex_descriptor> v2(3);
for (auto itr = v2.begin(); itr != v2.end(); ++itr) {
*itr = boost::add_vertex(g2);
}
boost::add_edge(v2[0], v2[1], edge_property('a'), g2);
boost::add_edge(v2[0], v2[2], edge_property('a'), g2);
std::vector<char> tmp;
tmp.emplace_back('a');
tmp.emplace_back('b');
boost::add_edge(v2[1], v2[2], edge_property(tmp), g2);
// Create predicate of edge
typedef boost::property_map<MyGraphType, boost::edge_name_t>::type edge_name_map_t;
typedef boost::property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
edge_comp_t edge_comp = boost::make_property_map_equivalent(
boost::get(boost::edge_name, g1), boost::get(boost::edge_name, g2));
// Create callback
boost::vf2_print_callback<MyGraphType, MyGraphType> callback(g1, g2);
// Execute
const bool result = boost::vf2_subgraph_iso(
g1, g2, callback, boost::vertex_order_by_mult(g1),
boost::edges_equivalent(edge_comp));
std::cout << "subgraph isomorphic? " << std::boolalpha << result << std::endl;
return 0;
}
推荐阅读
- c - 使 2 个循环并行运行
- c - 如何计算整数数组中的元素数
- python - 有没有办法在 tkinter 中获取动态添加的文本字段的值?
- vb.net - 选择列表框的特定行并将其分配给作为字符串的变量
- asp.net-core - 为什么 Microsoft.Extensions.Logging.Log4Net.AspNetCore 不支持 AdoNetAppender,是否有计划支持它?
- arrays - 我怎样才能得到剩余的房间空间?
- python - Python中列表中的枚举项集
- ssh - Ansible 动态添加代理主机,然后使用代理主机登录到它后面的机器,无需 ssh_config
- c++ - std 可选的复制构造函数
- python - Twisted UDP - 为什么不听就不能发送?