Как получить отображение краев с помощью boost :: vf2_subgraph_iso - PullRequest
Новая
       55

Как получить отображение краев с помощью boost :: vf2_subgraph_iso

1 голос
/ 25 апреля 2019

boost::vf2_subgraph_iso должен найти индуцированный подграф данного меньшего графа внутри данного большого графа. Переданный ему обратный вызов получит отображение в качестве входных данных. 

template <typename CorrespondenceMap1To2, typename CorrespondenceMap2To1>
bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1 g) const{
    // boost::get(f, u) maps u in small to v in large
}

Однако в документации упоминаются только отображения вершин. Я понимаю, что сопоставление ребер можно понять, сопоставив источник и цель каждого ребра. Но мне нужны связанные свойства сопоставленного ребра.

Кажется, что boost::get не работает с дескрипторами отображения и ребер. boost::get(f, e) выдает следующее сообщение об ошибке. 

error: no match for ‘operator[]’ (operand types are ‘const boost::iterator_property_map<__gnu_cxx::__normal_iterator<long unsigned int*, std::vector<long unsigned int, std::allocator<long unsigned int> > >, boost::vec_adj_list_vertex_id_map<bya::util::isomorphism::vertex_data, long unsigned int>, long unsigned int, long unsigned int&>’ and ‘const boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>’)

1 Ответ

0 голосов
/ 26 апреля 2019

Да, отображение не работает с дескрипторами ребер, потому что они не являются дескрипторами вершин.

Я бы посоветовал посмотреть ребро на "другом" графике.Так, например,

Live On Coliru 

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

using namespace boost;

struct VBundle { std::string name; };
struct EBundle { int data = 0; };

using G = adjacency_list<vecS, vecS, bidirectionalS, VBundle, EBundle>;
using Edge = G::edge_descriptor;

int main() {
    G small(4), large(5);
    small[0].name = "zero";
    small[1].name = "one";
    small[2].name = "two";
    small[3].name = "three";
    add_edge(0, 1, {33}, small);
    add_edge(1, 3, {44}, small);
    add_edge(2, 3, {55}, small);

    add_edge(4, 2, large); // 0->4, 1->2, 3->0, 2->3
    add_edge(2, 0, large);
    add_edge(3, 0, large);

    auto cb = [&](auto&& f, auto&&) {
        for (auto small_vd: make_iterator_range(vertices(small))) {
            auto large_vd = get(f, small_vd);

            std::cout << '(' << small_vd << ", " << large_vd << ") ";
            large[large_vd] = small[small_vd];

            for (Edge small_ed: make_iterator_range(out_edges(small_vd, small))) {
                auto large_src = get(f, source(small_ed, small));
                auto large_tgt = get(f, target(small_ed, small));

                auto [large_ed, found] = edge(large_src, large_tgt, large);
                assert(found);

                // e.g. copy edge bundle to the smaller graph
                large[large_ed] = small[small_ed];
            }
        }

        std::cout << std::endl;
        return true;
    };

    bool ok = vf2_subgraph_iso(small, large, cb);

    std::cout << std::boolalpha << ok << "\n";
}

Это печатает 

(0, 4) (1, 2) (2, 3) (3, 0) 
true

но также скопировал соответствующие вершинные и реберные расслоения из маленького графа в большой граф.

...