用列表容器实现BoostGraph VF2 subgraph_iso

Question

我尝试用顶点/边缘容器作为列表来实现Boost VF2子图Iso算法，但它不起作用。

下面是一个工作的例子，但是容器是向量。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
using namespace boost;
using namespace std;


int main() {

    typedef adjacency_list<setS, vecS, bidirectionalS> graph_type;

    // Build graph1
    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
    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);

    // Create callback to print mappings
    vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);

    // Print out all subgraph isomorphism mappings between graph1 and graph2.
    // Vertices and edges are assumed to be always equivalent.
    vf2_subgraph_iso(graph1, graph2, callback);

    return 0;
}

下面是我尝试对列表容器进行调整的尝试：

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/graph_traits.hpp>
using namespace boost;
using namespace std;


int main() {

    typedef adjacency_list<listS, listS, bidirectionalS> graph_type;
    typedef boost::graph_traits<graph_type>::vertex_descriptor vertexID;
    typedef map<size_t, vertexID> Index_2_Node_Map;


    // Build graph1
    int num_vertices1 = 8; graph_type graph1(num_vertices1);
    Index_2_Node_Map map1;
    boost::associative_property_map<Index_2_Node_Map> propmap1(map1);
    int counter = 0;
    BGL_FORALL_VERTICES(v,graph1,graph_type)
    {
        boost::put(propmap1, counter++, v);
    }

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


    // Build graph2
    int num_vertices2 = 9; graph_type graph2(num_vertices2);
    Index_2_Node_Map map2;
    boost::associative_property_map<Index_2_Node_Map> propmap2(map2);
    counter = 0;
    BGL_FORALL_VERTICES(v,graph2,graph_type)
    {
        boost::put(propmap2, counter++, v);
    }

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

    // Create callback to print mappings
    vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);

    // Print out all subgraph isomorphism mappings between graph1 and graph2.
    // Vertices and edges are assumed to be always equivalent.
    vf2_subgraph_iso(graph1, graph2, callback);

    return 0;
}

虽然这些图构造得很好，但当我运行它时，会得到大量的错误，例如

error: cannot form a reference to 'void'
error: no matching function for call to 'get'

Answer 1

正如前面的注释中所提到的，我想您还需要提供顶点索引映射和自定义回调。下面您将看到一个稍微修改过的代码版本，它编译。

#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp> // needed for always_equivalent predicates
using namespace boost;
using namespace std;

template <typename Graph1,
          typename Graph2,
          typename VertexIndexMap1,
          typename VertexIndexMap2>
  struct print_callback {

    print_callback(const Graph1& graph1, const Graph2& graph2,
            const VertexIndexMap1& map1, const VertexIndexMap2& map2) 
      : graph1_(graph1), graph2_(graph2), map1_(map1), map2_(map2) {}

    template <typename CorrespondenceMap1To2,
              typename CorrespondenceMap2To1>
    bool operator()(CorrespondenceMap1To2 f, CorrespondenceMap2To1) const {

      // Print (sub)graph isomorphism map
      BGL_FORALL_VERTICES_T(v, graph1_, Graph1) 
        std::cout << '(' << get(map1_, v) << ", " 
                  << get(map2_, get(f, v)) << ") ";

      std::cout << std::endl;

      return true;
    }

  private:
    const Graph1& graph1_;
    const Graph2& graph2_;
    const VertexIndexMap1& map1_;
    const VertexIndexMap2& map2_;
  };

int main() {
    typedef adjacency_list<listS, listS, bidirectionalS> graph_type;
    typedef boost::graph_traits<graph_type>::vertex_descriptor vertexID;
    typedef map<size_t, vertexID> Index_2_Node_Map;
    typedef map<vertexID, size_t> Node_2_Index_Map;
    vector<vertexID> vertex_g1_order;

    // Build graph1
    int num_vertices1 = 8; graph_type graph1(num_vertices1);
    Index_2_Node_Map map1;
    boost::associative_property_map<Index_2_Node_Map> propmap1(map1);
    Node_2_Index_Map map3;
    boost::associative_property_map<Node_2_Index_Map> vertex_index_map1(map3);
    int counter = 0;
    BGL_FORALL_VERTICES(v,graph1,graph_type)
    {
        boost::put(propmap1, counter++, v);
        boost::put(vertex_index_map1, v, counter);
        vertex_g1_order.push_back(v);
    }

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


    // Build graph2
    int num_vertices2 = 9; graph_type graph2(num_vertices2);
    Index_2_Node_Map map2;
    boost::associative_property_map<Index_2_Node_Map> propmap2(map2);
    Node_2_Index_Map map4;
    boost::associative_property_map<Node_2_Index_Map> vertex_index_map2(map4);
    counter = 0;
    BGL_FORALL_VERTICES(v,graph2,graph_type)
    {
        boost::put(propmap2, counter++, v);
        boost::put(vertex_index_map2, v, counter);
    }

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

    // Create callback to print mappings
    print_callback<graph_type, graph_type,
                  boost::associative_property_map<Node_2_Index_Map>,
                  boost::associative_property_map<Node_2_Index_Map> > callback(graph1, graph2, 
            vertex_index_map1, vertex_index_map2);

    // Print out all subgraph isomorphism mappings between graph1 and graph2.
    // Vertices and edges are assumed to be always equivalent.
    vf2_subgraph_iso(graph1, graph2, callback, 
                     vertex_index_map1, vertex_index_map2,
                     vertex_g1_order,
                     always_equivalent(), always_equivalent());

    return 0;
}

也许使用内部顶点属性来存储顶点id更为方便，如下面的示例所示：

#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/graph_traits.hpp>
using namespace boost;
using namespace std;

int main() {
    typedef property<vertex_name_t, int, property<vertex_index_t, int> > vertex_property;
    typedef adjacency_list<listS, listS, bidirectionalS, vertex_property> graph_type;
    typedef boost::graph_traits<graph_type>::vertex_descriptor vertexID;
    typedef map<size_t, vertexID> Index_2_Node_Map;

    // Build graph1
    int num_vertices1 = 8; graph_type graph1(num_vertices1);
    Index_2_Node_Map map1;
    boost::associative_property_map<Index_2_Node_Map> propmap1(map1);
    int counter = 0;
    BGL_FORALL_VERTICES(v,graph1,graph_type)
    {
        boost::put(propmap1, counter++, v);
        boost::put(vertex_index_t(), graph1, v, counter);
    }

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


    // Build graph2
    int num_vertices2 = 9; graph_type graph2(num_vertices2);
    Index_2_Node_Map map2;
    boost::associative_property_map<Index_2_Node_Map> propmap2(map2);
    counter = 0;
    BGL_FORALL_VERTICES(v,graph2,graph_type)
    {
        boost::put(propmap2, counter++, v);
        boost::put(vertex_index_t(), graph2, v, counter);
    }

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

    // Create callback to print mappings
    vf2_print_callback<graph_type, graph_type> callback(graph1, graph2);

    // Print out all subgraph isomorphism mappings between graph1 and graph2.
    // Vertices and edges are assumed to be always equivalent.
    vf2_subgraph_iso(graph1, graph2, callback); 

    return 0;
}

我希望这能帮上忙。谨致问候。