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)