Boost VF2子图同构对于无向图是不正确的？
Boost VF2子图同构对于无向图是不正确的？
提问于 2021-02-15 08:31:29
我正在尝试使用Boost的vf2_subgraph_iso，但是我不知道如何正确地使用它来处理小的无向图。
下面我给出一个例子，其中有4个顶点的图不是有4个顶点的完全连通图的子图(这对我来说似乎很奇怪)。有没有人能帮我弄明白我到底做错了什么？
我在Why is Boost VF2 subgraph isomorphism giving an incorrect answer上看过这篇文章，可能也有同样的问题。
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
using namespace boost;
int main()
{
typedef adjacency_list<vecS, vecS, undirectedS, no_property> Graph;
// 0---1
// | |
// 2---3
Graph smallGraph;
{
vertex(0, smallGraph);
vertex(1, smallGraph);
vertex(2, smallGraph);
vertex(3, smallGraph);
add_edge(0, 1, smallGraph);
add_edge(0, 2, smallGraph);
add_edge(2, 3, smallGraph);
add_edge(1, 3, smallGraph);
}
Graph largeGraph;
{
vertex(0, largeGraph);
vertex(1, largeGraph);
vertex(2, largeGraph);
vertex(3, largeGraph);
add_edge(0, 1, largeGraph);
add_edge(0, 2, largeGraph);
add_edge(2, 3, largeGraph);
add_edge(1, 3, largeGraph);
add_edge(0, 3, largeGraph);
add_edge(1, 2, largeGraph);
}
vf2_print_callback<Graph, Graph> callback(smallGraph, largeGraph);
auto val = vf2_subgraph_iso(smallGraph, largeGraph, callback);
if (val)
std::cout << "Found subgraph." << std::endl;
else
std::cout << "Did not find subgraph." << std::endl;
return 0;
}vf2_subgraph_iso documentation提出：“两个图G1=(V1，E1)和G2=(V2，E2)之间的同构是一个保持图的边结构的从一个图的顶点到另一个图的顶点的双射映射M，M称为图子图同构当且仅当M是G1和G2的子图之间的同构。”
在上面的示例中，G2 = largeGraph，G1 = smallGraph，并且存在G2的子图，使得该子图和G1之间的顶点映射(0-0，1-1，2-2，3-3)是双射的。
回答 1
Stack Overflow用户
发布于 2021-02-15 22:44:00
两个图G1=(V1，E1)和G2=(V2，E2)之间的同构是一个保持图的边结构的从一个图的顶点到另一个图的顶点的双射映射M
你期望持有什么样的映射？我在想，您可能期望{0 -> 0，1 -> 1，2 -> 2，3 -> 3}成为双射顶点映射
然而，情况并非如此，因为子图将丢失参与映射的顶点之间的边。例如，3 -- 0不在小图中，这使得它在结构上有所不同。
TL;DR当边是严格子集时，子图同构是而不是。相反，它侧重于映射顶点集。
计数器示例
这是一个反例，它在保留预期映射的同时生成一些随机边。请注意，给定足够多的随机边，您可能会遇到偶然的同构，因为子图在结构上是如此简单：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <iostream>
#include <random>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/algorithm/cxx11/all_of.hpp>
using boost::make_iterator_range;
using boost::adaptors::transformed;
using boost::algorithm::all_of;
int main()
{
using Graph =
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using V = Graph::vertex_descriptor;
// 0---1
// | |
// 2---3
Graph small(4);
add_edge(0, 1, small);
add_edge(0, 2, small);
add_edge(2, 3, small);
add_edge(1, 3, small);
Graph large(500);
add_edge(100, 200, large);
add_edge(100, 300, large);
add_edge(300, 400, large);
add_edge(200, 400, large);
// helper to recognizes (sets of) vertices from the intended subset
auto all_in_subset = [set = std::set{100, 200, 300, 400}](auto... vs) {
return ((0 != set.count(vs)) && ...);
};
// add some random edges for
auto randvertex = std::bind(
std::uniform_int_distribution<V>(0, boost::num_vertices(large) - 1),
std::mt19937{std::random_device{}()});
for (int n = 0; n < 400; ++n) {
V src = randvertex();
V tgt = randvertex();
// only add edges outside of the subset - preserving structure
if (!all_in_subset(src, tgt))
add_edge(src, tgt, large);
}
auto callback = [&](auto bijection, auto) {
auto vs = make_iterator_range(vertices(small));
auto mapped =
vs | transformed([&](auto v) { return get(bijection, v); });
if (boost::algorithm::all_of(mapped, all_in_subset)) {
std::cout << "In subset: ";
} else {
std::cout << "Random match: ";
}
for (auto v : vs) {
std::cout << '(' << v << " -> " << get(bijection, v) << ") ";
}
std::cout << std::endl;
return true;
};
bool found = boost::vf2_subgraph_iso(small, large, callback);
std::cout << "Found subgraph:" << std::boolalpha << found << std::endl;
}打印，例如
In subset: (0 -> 100) (1 -> 200) (2 -> 300) (3 -> 400)
In subset: (0 -> 100) (1 -> 300) (2 -> 200) (3 -> 400)
Random match: (0 -> 122) (1 -> 268) (2 -> 454) (3 -> 128)
Random match: (0 -> 122) (1 -> 454) (2 -> 268) (3 -> 128)
Random match: (0 -> 128) (1 -> 268) (2 -> 454) (3 -> 122)
Random match: (0 -> 128) (1 -> 454) (2 -> 268) (3 -> 122)
In subset: (0 -> 200) (1 -> 100) (2 -> 400) (3 -> 300)
In subset: (0 -> 200) (1 -> 400) (2 -> 100) (3 -> 300)
Random match: (0 -> 220) (1 -> 234) (2 -> 367) (3 -> 340)
Random match: (0 -> 220) (1 -> 367) (2 -> 234) (3 -> 340)
Random match: (0 -> 234) (1 -> 220) (2 -> 340) (3 -> 367)
Random match: (0 -> 234) (1 -> 340) (2 -> 220) (3 -> 367)
Random match: (0 -> 268) (1 -> 122) (2 -> 128) (3 -> 454)
Random match: (0 -> 268) (1 -> 128) (2 -> 122) (3 -> 454)
In subset: (0 -> 300) (1 -> 100) (2 -> 400) (3 -> 200)
In subset: (0 -> 300) (1 -> 400) (2 -> 100) (3 -> 200)
Random match: (0 -> 340) (1 -> 234) (2 -> 367) (3 -> 220)
Random match: (0 -> 340) (1 -> 367) (2 -> 234) (3 -> 220)
Random match: (0 -> 367) (1 -> 220) (2 -> 340) (3 -> 234)
Random match: (0 -> 367) (1 -> 340) (2 -> 220) (3 -> 234)
In subset: (0 -> 400) (1 -> 200) (2 -> 300) (3 -> 100)
In subset: (0 -> 400) (1 -> 300) (2 -> 200) (3 -> 100)
Random match: (0 -> 454) (1 -> 122) (2 -> 128) (3 -> 268)
Random match: (0 -> 454) (1 -> 128) (2 -> 122) (3 -> 268)
Found subgraph:true或者，根据运气，只是预期的：
In subset: (0 -> 100) (1 -> 200) (2 -> 300) (3 -> 400)
In subset: (0 -> 100) (1 -> 300) (2 -> 200) (3 -> 400)
In subset: (0 -> 200) (1 -> 100) (2 -> 400) (3 -> 300)
In subset: (0 -> 200) (1 -> 400) (2 -> 100) (3 -> 300)
In subset: (0 -> 300) (1 -> 100) (2 -> 400) (3 -> 200)
In subset: (0 -> 300) (1 -> 400) (2 -> 100) (3 -> 200)
In subset: (0 -> 400) (1 -> 200) (2 -> 300) (3 -> 100)
In subset: (0 -> 400) (1 -> 300) (2 -> 200) (3 -> 100)
Found subgraph:true页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66201481
复制相关文章
相似问题
腾讯云开发者
