为什么Boost VF2子图同构给出错误的答案?

问题描述

我正在尝试使用Boost的 vf2_subgraph_iso ，并且在测试一对小图之间的子图同构时，我得到了错误的答案.代码如下:

I'm trying to use Boost's vf2_subgraph_iso, and I'm getting the wrong answer when testing subgraph isomorphism between a pair of small graphs. The code is as follows :

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <sstream>
#include <iterator>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/property_map/property_map.hpp>

using namespace boost;


typedef property<edge_name_t, char> edge_prop;
typedef property<vertex_name_t, char, property<vertex_index_t, int> > vertex_prop;

typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_prop, edge_prop> Graph;

typedef property_map<Graph, vertex_name_t>::type vertex_name_map_t;
typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t> vertex_comp_t;

typedef property_map<Graph, edge_name_t>::type edge_name_map_t;
typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;

bool is_subgraph_isomorphic(Graph smallGraph, Graph bigGraph)
{
    vertex_comp_t vertex_comp =
        make_property_map_equivalent(get(vertex_name, smallGraph), get(vertex_name, bigGraph));
    edge_comp_t edge_comp =
        make_property_map_equivalent(get(edge_name, smallGraph), get(edge_name, bigGraph));
    vf2_print_callback<Graph, Graph> callback(smallGraph, bigGraph);
    bool res = vf2_subgraph_iso(smallGraph, bigGraph, callback, vertex_order_by_mult(smallGraph),
        edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
    return res;
}

int main()
{
    Graph gsmall,glarge;
    add_vertex(vertex_prop('a'),gsmall);
    add_vertex(vertex_prop('b'),gsmall);
    add_edge(0, 1, edge_prop('a'), gsmall);
    add_vertex(vertex_prop('a'),glarge);
    add_vertex(vertex_prop('b'),glarge);
    add_vertex(vertex_prop('a'),glarge);
    add_edge(0, 1, edge_prop('b'), glarge);
    add_edge(1, 2, edge_prop('a'), glarge);
    std::cout << "Is first pair subisomorphic ? : " << is_subgraph_isomorphic(gsmall,glarge) << std::endl;

    Graph graph1;

    add_vertex(vertex_prop('a'), graph1);
    add_vertex(vertex_prop('a'), graph1);
    add_vertex(vertex_prop('a'), graph1);

    add_edge(0, 1, edge_prop('b'), graph1);
    add_edge(0, 1, edge_prop('b'), graph1);
    add_edge(0, 1, edge_prop('d'), graph1);

    add_edge(1, 2, edge_prop('s'), graph1);

    add_edge(2, 2, edge_prop('l'), graph1);
    add_edge(2, 2, edge_prop('l'), graph1);

    // Build graph2
    Graph graph2;

    add_vertex(vertex_prop('a'), graph2);
    add_vertex(vertex_prop('a'), graph2);
    add_vertex(vertex_prop('a'), graph2);
    add_vertex(vertex_prop('a'), graph2);
    add_vertex(vertex_prop('a'), graph2);
    add_vertex(vertex_prop('a'), graph2);

    add_edge(0, 1, edge_prop('a'), graph2);
    add_edge(0, 1, edge_prop('a'), graph2);
    add_edge(0, 1, edge_prop('b'), graph2);

    add_edge(1, 2, edge_prop('s'), graph2);

    add_edge(2, 3, edge_prop('b'), graph2);
    add_edge(2, 3, edge_prop('d'), graph2);
    add_edge(2, 3, edge_prop('b'), graph2);

    add_edge(3, 4, edge_prop('s'), graph2);

    add_edge(4, 4, edge_prop('l'), graph2);
    add_edge(4, 4, edge_prop('l'), graph2);

    add_edge(4, 5, edge_prop('c'), graph2);
    add_edge(4, 5, edge_prop('c'), graph2);
    add_edge(4, 5, edge_prop('c'), graph2);

    add_edge(5, 0, edge_prop('s'), graph2);
    std::cout << "Is second pair subisomorphic ? : " << is_subgraph_isomorphic(graph1,graph2) << std::endl;
}

第一个是一对简单图形，第二个是示例.

The first is a pair of simple graphs, and the second is the graph from the example given in the Boost docs.

对于Boost示例，代码似乎给出了正确的答案，但对于第一个示例，给出了错误的答案.这是输出:

The code seems to give the right answer for the Boost example but gives the wrong answer for the first. Here is the output :

Is first pair subisomorphic ? : 0
(0, 2) (1, 3) (2, 4)
Is second pair subisomorphic ? : 1

第一对显然是子图同构.

The first pair obviously is subgraph isomorphic.

我注意到的另一件奇怪的事情是，当我改变

Another curious thing I noticed was that when I changed

typedef adjacency_list<vecS, vecS, bidirectionalS, vertex_prop, edge_prop> Graph;

到

typedef adjacency_list<vecS, vecS, undirectedS, vertex_prop, edge_prop> Graph;

现在输出为

(0, 2) (1, 1)
Is first pair subisomorphic ? : 1
Is second pair subisomorphic ? : 0

第一对是正确的，而第二对是错误的.

Which is correct for the first pair but wrong for the second.

编译命令:

g++ "-std=c++11" code.cpp -lboost_graph -o exec

据我所知，此版本在Xubuntu 16.04上运行.使用存储库中的Boost库.

Running on Xubuntu 16.04, up to date as far as I can tell. Using the Boost library from the repositories.

有人可以告诉我我在做什么错吗?

Could someone please tell me what I'm doing wrong ?

推荐答案

我认为您发现了一个或两个错误.您的示例显示，当使用 undirectedS 时， vf2_subgraph_iso 无法处理自循环.如果删除它们，您的示例应该可以正常工作.第二个是不一致的.在文档中，如果存在图-子图同构，则 vf2_subgraph_iso 返回true，否则返回false.但实际上，如果对整个搜索空间进行了探索，则返回true，否则返回false.最好的问候，

I think you discovered a bug or actually two. Your example shows that vf2_subgraph_iso can't handle self-loops when using undirectedS. If you remove them, your example should work.The second one is an inconsistency. In the documentation it's said that vf2_subgraph_iso returns true if a graph-subgraph isomorphism exists and false otherwise. But actually it returns true if the entire search space was explored and false otherwise.Best regards,

这篇关于为什么Boost VF2子图同构给出错误的答案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！