Boost Graph Library: subgraph isomorphism with adjacency_matrix

Question

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)

Answer 1

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:

Live On Coliru

#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

Closing Notes

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.

Answer 2

So, after digging through the Boost Graph Library (BGL) header files, I think I have a better idea of what's happening.

Boost discourages you, or rather stops you, from using bidirectionalS with adjacency_matrix, apparently because the list in_edge, list out_edge, in_degree, and out_degree functions violate the constant time promise of BGL's bidirectional graphs. This is extremely irritating, because adjacency_list graphs violate the constant time promise for edge access that adjacency_matrix provides, but that doesn't prevent you from using adjacency_list whenever you want and accepting whatever trade-offs result.

In addition, some functions in adjacency_matrix remain unimplemented, which is rather alarming for a 20 year old library. BGL's developers and maintainers appear not to have done anything at except minor bug fixes for nearly 20 years. Given all the research on graph data structures and algorithms in that time, and all the changes in C++, I would say BGL is really showing its age. That is too bad, because I like the idea of it, and I enjoy using it (when it works).

In my application, I don't care about memory, only speed, and my large, dense graph is fixed (no changes to vertices or edges) after initial creation, so I really would like to set up a new graph type which uses both adjacency matrix and adjacency list and picks the fastest structure to respond to any query (e.g., adjacency matrix when querying the presence of a edge between two given vertices, and adjacency list when querying the out edges of a vertex). However, it feels like you would need a PhD in abstract algebra to set up a new graph type BGL. I exaggerate, but bottom line is, I can get up to speed with an alternative faster than I can get BGL to do what I want.

So, my solution to my problem is to use the LEMON graph library.