boost vf2 可以像这种情况一样处理多图吗？

Question

我想在这种情况下使用vf2。

Graph gsmall,glarge;
add_vertex(vertex_prop('a'),gsmall);
add_vertex(vertex_prop('b'),gsmall);
add_edge(0, 1, edge_prop('m'), gsmall);

add_vertex(vertex_prop('a'),glarge);
add_vertex(vertex_prop('b'),glarge);
add_edge(0, 1, edge_prop('m'), glarge);
add_edge(0, 1, edge_prop('n'), glarge);
std::cout << is_subgraph_isomorphic(gsmall,glarge) << std::endl;

如果pattern的属性边可以匹配graph的边的部分属性，则return为真，但现在必须全部匹配。该示例 return 是错误的。我想让它成真，那怎么办？

编辑：

我解决了这个问题。使用向量和重载运算符“==”

http://coliru.stacked-crooked.com/a/6307210b2861bc63

但是我又发现了一个问题。当图中有自环时会给出错误的结果。

http://coliru.stacked-crooked.com/a/46d336ecfddbbab9 为真

但是 http://coliru.stacked-crooked.com/a/413d56146ceffd42 是错误的。

我认为他们都是真的。搞不懂怎么会这样

请再次帮助我！谢谢！

Answer 1

Boost可以应付。但是，您不是在寻找库意义上的同构：

An isomorphism between two graphs G1=(V1, E1) and G2=(V2, E2) is a bijective mapping M of the vertices of one graph to vertices of the other graph that preserves the edge structure of the graphs

因此，对于所有对应的顶点，需要存在相同的边。换句话说，子图可能更小（低阶）但每个顶点必须具有等效结构（这意味着相同数量的边）。

在你的例子中，小图在结构上是不同的，因为大图有一个自循环，而小图没有。（自循环很重要，因为两个顶点都存在于子图中）。

如果您真的认为出于您的目的需要忽略自循环，则必须将它们过滤掉。

这是一个使用 filtered_graph 适配器来实现的示例：

Live On Coliru

#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/container/flat_set.hpp>
#include <boost/container/small_vector.hpp>

template <typename  SortedRange1, typename  SortedRange2,
    typename V = std::common_type_t<typename boost::range_value<SortedRange1>::type, typename boost::range_value<SortedRange2>::type>,
    typename Cmp = std::less<V> >
static inline bool has_intersection(SortedRange1 const& a, SortedRange2 const& b, Cmp cmp = {}) {
    auto equivalent = [cmp](V const& a, V const& b) 
        { return !cmp(a,b) && !cmp(b,a); };

    auto ai = a.begin();
    auto bi = b.begin();

    while (ai != a.end() && (bi = b.lower_bound(*ai)) != b.end())
        if (equivalent(*ai++, *bi))
            return true;

    return false;
}

// Define graph type
using Label = char; 

struct  EdgeProperties {
    using Labels = boost::container::flat_set<char, std::less<>, boost::container::small_vector<char, 3> >;

    EdgeProperties(std::initializer_list<Label> elabels = {}) :_elabels(elabels) {}

    bool operator==(EdgeProperties const& other) const {
        return has_intersection(_elabels, other._elabels);
    }

    Labels _elabels;
};

typedef boost::property<boost::edge_name_t, EdgeProperties> edge_prop;
typedef boost::property<boost::vertex_name_t, long/*, boost::property<boost::vertex_index_t, int>*/ > vertex_prop;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, vertex_prop, edge_prop> Graph;


int main()
{
    Graph gsmall, glarge;
    add_vertex(vertex_prop('a'),gsmall);
    add_vertex(vertex_prop('b'),gsmall);
    add_edge(0, 1, edge_prop({'m'}), gsmall);
    //add_edge(0, 0, edge_prop({'n'}), gsmall);

    add_vertex(vertex_prop('a'),glarge);
    add_vertex(vertex_prop('b'),glarge);
    add_vertex(vertex_prop('c'),glarge);
    add_edge(0, 1, edge_prop({'m'}), glarge);
    add_edge(0, 0, edge_prop({'n'}), glarge);
    add_edge(0, 2, edge_prop({'o'}), glarge);

    // Create predicate of edge
    auto edge_comp = make_property_map_equivalent(
            get(boost::edge_name, gsmall),
            get(boost::edge_name, glarge));

    // Create callback
    boost::vf2_print_callback<Graph, Graph> callback(gsmall, glarge);

    struct FilterSelfEdges {
        Graph const* _g;
        bool operator()(Graph::edge_descriptor ed) const {
            return source(ed, *_g) != target(ed, *_g);
        }
    };

    using Filtered = boost::filtered_graph<Graph, FilterSelfEdges>;

    // Execute
    const bool result = boost::vf2_subgraph_iso(
            gsmall, Filtered(glarge, FilterSelfEdges{&glarge}), callback, boost::vertex_order_by_mult(gsmall),
            boost::edges_equivalent(edge_comp));

    std::cout << "subgraph isomorphic? " << std::boolalpha << result << std::endl;
}

版画

(0, 0) (1, 1) 
subgraph isomorphic? true

boost vf2 可以像这种情况一样处理多图吗？

can boost vf2 deal with muti-graph like this situation?

c++

boost

graph

boost-graph