Может ли boost vf2 иметь дело с muti-графом, как эта ситуация? - PullRequest
Новая
       31

Может ли boost vf2 иметь дело с muti-графом, как эта ситуация?

1 голос
/ 15 марта 2019

Я хочу использовать 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;

Если свойство грани шаблона может совпадать с частью графа свойств грани, вернуть true, но теперь оно должно совпадать со всеми.Этот пример возвращает ложь.Я хочу сделать это правдой, ну и как?

Редактировать:

Я решил этот вопрос.Используйте вектор и оператор перегрузки "=="

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

Но я обнаружил другую проблему.Это даст неверные результаты, когда на графике есть самопетли.

http://coliru.stacked -crooked.com / a / 46d336ecfddbbab9 имеет значение

, но http://coliru.stacked -crooked.com / a / 413d56146ceffd42 неверно.

Я думаю, что они оба тьюре.Я не могу понять, как это могло быть так.

Пожалуйста, помогите мне снова!Спасибо!

1 Ответ

1 голос
/ 18 марта 2019

Повышение может справиться с этим. Однако вы не ищете изоморфизм в смысле библиотеки:

Изоморфизм между двумя графами G1 = (V1, E1) и G2 = (V2, E2) является биективным отображением M вершин одного графа в вершины другого графа, который сохраняет структуру ребер графов

Таким образом, для всех соответствующих вершин должны присутствовать одинаковые ребра. Другими словами, подграф может быть меньше (более низкого порядка), но каждая вершина должна иметь эквивалентную структуру (это подразумевает одинаковое количество ребер).

В вашем случае маленький граф структурно отличается, потому что у большого графа есть собственный цикл, а у маленького нет. (Цикл self важен, поскольку в подграфе существуют обе вершины).

Если вы действительно думаете, что для своей цели вам нужно игнорировать циклы, вам придется их отфильтровать.

Вот пример, который использует адаптер 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
...