5

I'm trying to use Boost's vf2_subgraph_iso() to detect subgraph isomorphism.

I can successfully do this on simple graph, but can not on multigraph (a graph which is permitted to have multiple edges).

Consider detecting subgraph isomorphism between following G1 and G2:

graphs

G1 is a subgraph of G2, and I want to detect that using following code:

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

int main()
{
  // Define edge property
  typedef boost::property<
    boost::edge_name_t,
    char
  > edge_property;

  // Define graph type
  typedef boost::adjacency_list<
    boost::vecS,           // OutEdgeListS
    boost::vecS,           // VertexListS
    boost::bidirectionalS, // DirectedS
    boost::no_property,    // VertexProperties
    edge_property,         // EdgeProperties
    boost::no_property,    // GraphProperties
    boost::listS           // EdgeListS
  > MyGraphType;

  // Build graph G1
  MyGraphType g1;
  std::vector<MyGraphType::vertex_descriptor> v1(3);
  for (auto itr = v1.begin(); itr != v1.end(); ++itr) {
    *itr = boost::add_vertex(g1);
  }
  boost::add_edge(v1[0], v1[1], edge_property('a'), g1);
  boost::add_edge(v1[0], v1[2], edge_property('a'), g1);
  boost::add_edge(v1[1], v1[2], edge_property('b'), g1);

  // Build graph G2
  MyGraphType g2;
  std::vector<MyGraphType::vertex_descriptor> v2(3);
  for (auto itr = v2.begin(); itr != v2.end(); ++itr) {
    *itr = boost::add_vertex(g2);
  }
  boost::add_edge(v2[0], v2[1], edge_property('a'), g2);
  boost::add_edge(v2[0], v2[2], edge_property('a'), g2);
  boost::add_edge(v2[1], v2[2], edge_property('a'), g2);
  boost::add_edge(v2[1], v2[2], edge_property('b'), g2);

  // Create predicate of edge
  typedef boost::property_map<MyGraphType, boost::edge_name_t>::type edge_name_map_t;
  typedef boost::property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
  edge_comp_t edge_comp = boost::make_property_map_equivalent(
    boost::get(boost::edge_name, g1), boost::get(boost::edge_name, g2));

  // Create callback
  boost::vf2_print_callback<MyGraphType, MyGraphType> callback(g1, g2);

  // Execute
  const bool result = boost::vf2_subgraph_iso(
    g1, g2, callback, boost::vertex_order_by_mult(g1),
    boost::edges_equivalent(edge_comp));

  std::cout << "subgraph isomorphic? " << std::boolalpha << result << std::endl;

  return 0;
}

Expected result:

(0, 0) (1, 1) (2, 2)
subgraph isomorphic? true

Actual result:

subgraph isomorphic? false

Where is my code wrong?

Sorry for my poor English. Thanks!

1

1 Answer 1

0

The vf2_subgraph_iso will compare the properties of edge. In your codes, the property of edge 1->2 is 'b' in graph1, but it's 'a','b' in graph2. So they're not the same structure.

If you wanna it return true when matching only parts of all properties, you can use a struct and overload operator "==" by your rules. For your example, the following codes will be fine.

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

int main()
{
  // Define edge property
  struct  EdgeProperties {
      EdgeProperties() {}
      EdgeProperties(char elabel) { _elabels.emplace_back(elabel);}
      EdgeProperties(std::vector<char>& elabels) :_elabels(elabels) {}
      /* overload == */
      bool operator==(EdgeProperties const& other) const {
        for (auto& my_l:_elabels) {
          for (auto& o_l:other._elabels) {
            if (my_l == o_l) return true;
          }
        }
        return false;
      }
      std::vector<char> _elabels;
  };

  typedef boost::property<
    boost::edge_name_t,
    EdgeProperties
  > edge_property;

  // Define graph type
  typedef boost::adjacency_list<
    boost::vecS,           // OutEdgeListS
    boost::vecS,           // VertexListS
    boost::bidirectionalS, // DirectedS
    boost::no_property,    // VertexProperties
    edge_property,         // EdgeProperties
    boost::no_property,    // GraphProperties
    boost::listS           // EdgeListS
  > MyGraphType;

  // Build graph G1
  MyGraphType g1;
  std::vector<MyGraphType::vertex_descriptor> v1(3);
  for (auto itr = v1.begin(); itr != v1.end(); ++itr) {
    *itr = boost::add_vertex(g1);
  }
  boost::add_edge(v1[0], v1[1], edge_property('a'), g1);
  boost::add_edge(v1[0], v1[2], edge_property('a'), g1);
  boost::add_edge(v1[1], v1[2], edge_property('b'), g1);

  // Build graph G2
  MyGraphType g2;
  std::vector<MyGraphType::vertex_descriptor> v2(3);
  for (auto itr = v2.begin(); itr != v2.end(); ++itr) {
    *itr = boost::add_vertex(g2);
  }
  boost::add_edge(v2[0], v2[1], edge_property('a'), g2);
  boost::add_edge(v2[0], v2[2], edge_property('a'), g2);
  std::vector<char> tmp;
  tmp.emplace_back('a');
  tmp.emplace_back('b');
  boost::add_edge(v2[1], v2[2], edge_property(tmp), g2);

  // Create predicate of edge
  typedef boost::property_map<MyGraphType, boost::edge_name_t>::type edge_name_map_t;
  typedef boost::property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
  edge_comp_t edge_comp = boost::make_property_map_equivalent(
    boost::get(boost::edge_name, g1), boost::get(boost::edge_name, g2));

  // Create callback
  boost::vf2_print_callback<MyGraphType, MyGraphType> callback(g1, g2);

  // Execute
  const bool result = boost::vf2_subgraph_iso(
    g1, g2, callback, boost::vertex_order_by_mult(g1),
    boost::edges_equivalent(edge_comp));

  std::cout << "subgraph isomorphic? " << std::boolalpha << result << std::endl;

  return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.