なぜBoost VF2サブグラフの同型異性が誤った答えを出すのですか？

Question

私はBoostのvf2_subgraph_isoを使用しようとしていますが、小さなグラフのペアの間でサブグラフの同形をテストするときに間違った答えを得ています。次のようにコードがある：

#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; 
} 

最初は単純なグラフの組であり、第二は、昇圧ドキュメントに与えられたexampleからグラフです。

コードはBoostの例で正しい答えを示しているようですが、最初のものに対して間違った答えを与えます。出力は次のとおりです。

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

最初のペアは明らかにサブグラフ同形です。私が気づいた別の好奇心の事は、私は

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

に

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

を変更したときに、出力は今最初のペアのためには正しいがために間違っている

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

であるということでした

二番目。

コンパイルコマンド：

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

は、私の知る限り、日付までのXubuntu 16.04、上で実行しています。リポジトリからBoostライブラリを使用する。

私が間違っていることを教えてもらえますか？

Answer 1

あなたはバグか実際に2つを発見したと思います。あなたの例では、undirectedSを使用すると、vf2_subgraph_isoは自己ループを処理できません。それらを削除すると、あなたの例がうまくいくはずです。 2番目のものは矛盾しています。ドキュメントでは、vf2_subgraph_isoは、グラフ部分グラフ同型が存在する場合はtrueを返し、それ以外の場合はfalseを返します。しかし、実際には、検索スペース全体が探索された場合はtrueを返し、それ以外の場合はfalseを返します。 よろしくお願いします。