I am using Boost 1.83 with the latest Cygwin. The problem I'm having also occurred with Boost 1.66.
I am trying to use the Boost Graph Library isomorphism function on an adjacency_matrix:
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <iostream>
//typedef boost::adjacency_list<boost::vecS,
// boost::vecS,
// boost::bidirectionalS> Graph;
typedef boost::adjacency_matrix<boost::bidirectionalS> Graph;
int main(int argc, char* argv[]) {
Graph g_small(3);
boost::add_edge(0, 1, g_small);
boost::add_edge(1, 2, g_small);
boost::add_edge(2, 0, g_small);
Graph g_large(5);
boost::add_edge(0, 1, g_large);
boost::add_edge(1, 2, g_large);
boost::add_edge(2, 3, g_large);
boost::add_edge(3, 4, g_large);
boost::add_edge(4, 2, g_large);
auto callback = [&](auto f, auto f_inv) {
std::cout << "isomorphism" << std::endl;
return true; // give us more isomorphisms if any
};
boost::vf2_subgraph_iso(g_small, g_large, callback);
return 0;
}
The code compiles with an adjacency list, but with an adjacency matrix I get the following error (only first few lines shown). It then complains about some missing functions (I assume the ones that are in the Bidirectional model but not the Directed model).
from /usr/local/include/boost/container_hash/hash.hpp:27,
from /usr/local/include/boost/functional/hash.hpp:6,
from /usr/local/include/boost/unordered/unordered_set.hpp:20,
from /usr/local/include/boost/unordered_set.hpp:17,
from /usr/local/include/boost/graph/adjacency_list.hpp:20,
from mwe.cc:1:
/usr/local/include/boost/graph/adjacency_matrix.hpp: In instantiation of ‘class boost::adjacency_matrix<boost::bidirectionalS>’:
mwe.cc:14:16: required from here
/usr/local/include/boost/graph/adjacency_matrix.hpp:455:5: error: static assertion failed: !(is_same< Directed, bidirectionalS >::value)
455 | BOOST_STATIC_ASSERT(!(is_same< Directed, bidirectionalS >::value));
| ^~~~~~~~~~~~~~~~~~~
/usr/local/include/boost/graph/adjacency_matrix.hpp:455:5: note: ‘!(bool)boost::integral_constant<bool, true>::value’ evaluates to false
I thought I understood the documentation that says it should work ... am I missing something? I can't use adjacency_list because it seems that subgraph isomorphism is waaay too slow on large adjacency list graphs.
Edit: If I change the typedef in the minimal working example I posted to
typedef boost::adjacency_matrix<boost::directedS> Graph;
I get an error that seems to say the subgraph function is expecting Bidirectional but instead it got Directed. See excerpt below.
/usr/local/include/boost/graph/graph_concepts.hpp:118:1: required from ‘static void boost::concepts::requirement<boost::concepts::failed************ Model::************>::failed() [with Model = boost::concepts::BidirectionalGraphConcept<boost::adjacency_matrix<boost::directedS> >]’
/usr/local/include/boost/graph/vf2_sub_graph_iso.hpp:931:9: required from ‘bool boost::detail::vf2_subgraph_morphism(const GraphSmall&, const GraphLarge&, SubGraphIsoMapCallback, IndexMapSmall, IndexMapLarge, const VertexOrderSmall&, EdgeEquivalencePredicate, VertexEquivalencePredicate)
I agree that this "puritan" restriction that you may not use AdjacencyMatrix as a (poor man's) BidirectionalGraph even if just for toying/comparison.
Turns out it's pretty easy to convince the library to "Trust Me, I Know What I'm Doing". You need a distinct graph type that you can specialize the traits for:
struct Graph : boost::adjacency_matrix<boost::directedS> {
using Impl = boost::adjacency_matrix<boost::directedS>;
};
Now you have a type that you can lie about:
namespace boost {
template <> struct graph_traits<Graph> : graph_traits<Graph::Impl> {
struct traversal_category
: boost::bidirectional_graph_tag
, Graph::Impl::traversal_category {};
};
// O(2N)
auto degree(Graph::vertex_descriptor u, Graph const& g) {
return size(out_edges(u, g)) + size(in_edges(u, g));
}
}; // namespace boost
That's all:
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <iostream>
struct Graph : boost::adjacency_matrix<boost::directedS> {
using Impl = boost::adjacency_matrix<boost::directedS>;
// using Impl::Impl;
// using Impl::operator=;
};
namespace boost {
template <> struct graph_traits<Graph> : graph_traits<Graph::Impl> {
struct traversal_category
: boost::bidirectional_graph_tag
, Graph::Impl::traversal_category {};
};
// O(2N)
auto degree(Graph::vertex_descriptor u, Graph const& g) {
return size(out_edges(u, g)) + size(in_edges(u, g));
}
}; // namespace boost
int main() {
Graph g_small(3);
add_edge(0, 1, g_small);
add_edge(1, 2, g_small);
add_edge(2, 0, g_small);
Graph g_large(5);
add_edge(0, 1, g_large);
add_edge(1, 2, g_large);
add_edge(2, 3, g_large);
add_edge(3, 4, g_large);
add_edge(4, 2, g_large);
auto callback = [&](auto f, auto /*f_inv*/) {
std::cout << "isomorphism";
for (auto v : boost::make_iterator_range(vertices(g_small))) {
std::cout << " " << v << "->" << f[v];
}
std::cout << std::endl;
return true; // give us more isomorphisms if any
};
vf2_subgraph_iso(g_small, g_large, callback);
}
Printing the output
isomorphism 0->2 1->3 2->4
isomorphism 0->3 1->4 2->2
isomorphism 0->4 1->2 2->3
YMMV: of course the performance won't be optimal, but as you said, neither will most other models. You might have your cake and eat it if you are able to pre-calculate/cache the degree for each vertex. Depending on your domain logic this may be easy to add.