[Boost-users] [Boost][Graph] vf2 implementation question

Subject: [Boost-users] [Boost][Graph] vf2 implementation question
From: Marc Viala (cram.viala_at_[hidden])
Date: 2014-04-20 11:59:50

Hi,

Recently,I tried to use Boost.Graph's VF2 implementation and after having
played few days with this module, I was wondering if this implementation
supports "adjacency_matrix" model as explained by the documentation (cf.
http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/vf2_sub_graph_iso.html).

To demonstrate my point, you will find hereafter an C++ example extracted
from the Boost.Graph's documentation. If the macro "ADJACENCY_LIST_STRUCT"
is commented out, this code can't be compiled w/ VS2012 aka VC11 because
the static assertion @line 837 of "boost/graph/vf2_sub_graph_iso.hpp" is
triggered.

My questions are:
 - Does this VF2 implementation supports "adjacency_matrix" model?
 - Is there any patch for supporting this model of graph?

FYI: If I comment two static assertations in file
"boost/graph/vf2_sub_graph_iso.hpp", at line 837 and line 843, the code
compiles and runs correctly for "adjacency_matrix" model.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>

using namespace boost;

//#define ADJACENCY_LIST_STRUCT

int main()
{
#ifdef ADJACENCY_LIST_STRUCT
  typedef adjacency_list<vecS, vecS, undirectedS> graph_type;
#else
  typedef adjacency_matrix<undirectedS>           graph_type;
#endif

  // Build graph1.
  const int  num_vertices1 = 8;
  graph_type graph1(num_vertices1);

  add_edge(0, 6, graph1); add_edge(0, 7, graph1);
  add_edge(1, 5, graph1); add_edge(1, 7, graph1);
  add_edge(2, 4, graph1); add_edge(2, 5, graph1); add_edge(2, 6, graph1);
  add_edge(3, 4, graph1);

  // Build graph2.
  const int  num_vertices2 = 9;
  graph_type graph2(num_vertices2);

  add_edge(0, 6, graph2); add_edge(0, 8, graph2);
  add_edge(1, 5, graph2); add_edge(1, 7, graph2);
  add_edge(2, 4, graph2); add_edge(2, 7, graph2); add_edge(2, 8, graph2);
  add_edge(3, 4, graph2); add_edge(3, 5, graph2); add_edge(3, 6, graph2);

  // Compute de subgraph isomorphing.
  vf2_print_callback<graph_type, graph_type> cb(graph1, graph2);
  vf2_subgraph_iso(graph1, graph2, cb);
}

Best regards,

Marc