Как я могу обнаружить изоморфизм подграфа на мультиграфе, используя Boost vf2_subgraph_iso?

Question

Я пытаюсь использовать Boost's vf2_subgraph_iso() для обнаружения изоморфизма подграфа.

Я могу успешно сделать это на простом графике, но не могу на multigraph (граф, которому разрешено иметь несколько ребер).

Рассмотрите возможность обнаружения изоморфизма подграфа между следующими G1 и G2:

G1 является подграфом G2,и я хочу обнаружить это, используя следующий код:

#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;
}

Ожидаемый результат:

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

Фактический результат:

subgraph isomorphic? false

Где мой код неверен?

Извините за мой плохой английский.Спасибо!

Answer 1

vf2_subgraph_iso будет сравнивать свойства ребра.В ваших кодах свойство ребра 1-> 2 - это «b» в графе 1, но это «a», «b» в графе 2.Таким образом, они не имеют одинаковую структуру.

Если вы хотите, чтобы она возвращала true при сопоставлении только частей всех свойств, вы можете использовать оператор struct и overload "==" по вашим правилам.Для вашего примера подойдут следующие коды.

#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;
}