How to get the edge mapping with boost::vf2_subgraph_iso

boost::vf2_subgraph_iso is supposed to find an induced subgraph of a given smaller graph inside the given large graph. The callback passed to it will get a mapping as an input.

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

However the documentation only mentions the vertex mappings. I understand that edge mappings can be understood by mapping the source and target of each edges. But I need the bundled properties of the mapped edge.

It seems that boost::get does not work with the mapping and edge descriptors. boost::get(f, e) yields the following error message.

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>’)

Solution

Yeah the mapping doesn't work with edge descriptors because they're not vertex descriptors.

I'd suggest looking up the edge in the "other" graph. So, e.g.

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

This prints

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

but will also have copied the corresponding vertex AND edge bundles from the small graph to the large graph.