c++ - 可以在这种情况下 boost vf2处理多图吗？

我想在这种情况下使用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的edge属性可以与graph的edge属性相匹配，则返回true，但现在必须全部匹配。该示例返回false。我想让它成为现实，那又如何呢？

编辑:

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

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

但是我发现了另一个问题。当图中存在自环时，它将给出错误的结果。

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

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

我认为他们俩都是真的。我不明白怎么可能这样。

请再次帮助我!谢谢!

最佳答案

Boost可以应对。但是，您并不是从库的意义上寻找同构:



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

在您的情况下，小图在结构上有所不同，因为大图具有自循环，而小图则没有。 (自循环很重要，因为两个顶点都存在于子图中)。

如果您确实出于自己的目的而想忽略自循环，则必须将其过滤掉。

这是一个使用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