The following program is based on an example provided by the boost website https://www.boost.org/doc/libs/master/libs/graph/example/vf2_sub_graph_iso_multi_example.cpp
#include <boost/graph/vf2_sub_graph_iso.hpp>
using namespace boost;
int main() {
typedef property<edge_name_t, char> edge_property;
typedef property<vertex_name_t, char, property<vertex_index_t, int> >
vertex_property;
typedef adjacency_list<vecS, listS, bidirectionalS, vertex_property,
edge_property>
graph_type;
// Build graph1
graph_type graph1;
auto v0 = add_vertex(vertex_property('a'), graph1);
auto v1 = add_vertex(vertex_property('a'), graph1);
auto v2 = add_vertex(vertex_property('a'), graph1);
add_edge(v0, v1, edge_property('b'), graph1);
add_edge(v1, v2, edge_property('b'), graph1);
add_edge(v0, v2, edge_property('d'), graph1);
// Build graph2
graph_type graph2;
auto w0 = add_vertex(vertex_property('a'), graph2);
auto w1 = add_vertex(vertex_property('a'), graph2);
auto w2 = add_vertex(vertex_property('a'), graph2);
add_edge(w0, w1, edge_property('b'), graph2);
add_edge(w1, w2, edge_property('b'), graph2);
add_edge(w0, w2, edge_property('d'), graph2);
// create predicates
typedef property_map<graph_type, vertex_name_t>::type vertex_name_map_t;
typedef property_map_equivalent<vertex_name_map_t, vertex_name_map_t>
vertex_comp_t;
vertex_comp_t vertex_comp = make_property_map_equivalent(
get(vertex_name, graph1), get(vertex_name, graph2));
typedef property_map<graph_type, edge_name_t>::type edge_name_map_t;
typedef property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
edge_comp_t edge_comp = make_property_map_equivalent(get(edge_name, graph1),
get(edge_name, graph2));
// Create callback
vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);
vf2_graph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
edges_equivalent(edge_comp).vertices_equivalent(vertex_comp));
return 0;
}
The callback function doesn't print anything. But if I change listS at line 9 to vecS, the code works fine. I don't understand why using listS fails the isomorphism check. Is it possible to make it work even if I use listS?
vecS has an implicit vertex index.
listS doesn't. Therefore it uses the internal property vertex_index_t but you didn't initialize it.
Here's modernized version that tests all combinations of vecS/listS possible for graph1/graph2:
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/property_map/property_map.hpp>
template <typename Graph>
void fill_vertex_index(Graph& g) {
auto idmap = get(boost::vertex_index, g);
using Prop = boost::property_traits<decltype(idmap)>;
// only if the property is writable
if constexpr (std::is_convertible_v<
typename Prop::category,
boost::read_write_property_map_tag>)
{
std::cout << " - Filling vertex_index\n";
typename Prop::value_type id = 0; // or just int id = 0; for us
for (auto v : boost::make_iterator_range(vertices(g)))
put(idmap, v, id++);
}
}
template <typename Graph>
Graph create_graph() {
Graph g;
auto v0 = add_vertex({'a'}, g);
auto v1 = add_vertex({'a'}, g);
auto v2 = add_vertex({'a'}, g);
fill_vertex_index(g);
add_edge(v0, v1, {'b'}, g);
add_edge(v1, v2, {'b'}, g);
add_edge(v0, v2, {'d'}, g);
return g;
}
using edge_property = boost::property<boost::edge_name_t, char>;
using vertex_property = boost::property<boost::vertex_name_t, char, boost::property<boost::vertex_index_t, int> >;
template <typename Selector>
using graph_type = boost::adjacency_list<
boost::vecS,
Selector,
boost::bidirectionalS,
vertex_property,
edge_property>;
template <typename Selector1, typename Selector2> void do_test() {
std::cout << "\n ---" << __PRETTY_FUNCTION__ << " --- \n";
// Build graphs
using G1 = graph_type<Selector1>;
using G2 = graph_type<Selector2>;
auto graph1 = create_graph<G1>();
auto graph2 = create_graph<G2>();
// create predicates
auto vertex_comp = make_property_map_equivalent(
get(boost::vertex_name, graph1), get(boost::vertex_name, graph2));
auto edge_comp = make_property_map_equivalent(
get(boost::edge_name, graph1), get(boost::edge_name, graph2));
boost::vf2_print_callback<G1, G2> callback(graph1, graph2);
vf2_graph_iso(graph1, graph2, callback, vertex_order_by_mult(graph1),
edges_equivalent(edge_comp)
.vertices_equivalent(vertex_comp));
}
int main() {
do_test<boost::vecS, boost::vecS>();
do_test<boost::vecS, boost::listS>();
do_test<boost::listS, boost::vecS>();
do_test<boost::listS, boost::listS>();
}
Printing
---void do_test() [with Selector1 = boost::vecS; Selector2 = boost::vecS] ---
(0, 0) (1, 1) (2, 2)
---void do_test() [with Selector1 = boost::vecS; Selector2 = boost::listS] ---
- Filling vertex_index
(0, 0) (1, 1) (2, 2)
---void do_test() [with Selector1 = boost::listS; Selector2 = boost::vecS] ---
- Filling vertex_index
(0, 0) (1, 1) (2, 2)
---void do_test() [with Selector1 = boost::listS; Selector2 = boost::listS] ---
- Filling vertex_index
- Filling vertex_index
(0, 0) (1, 1) (2, 2)