如何使用C++ Boost Graph Library(BGL)检测带节点类型的同构图？

我需要筛选出满足节点类型（A/B）约束的同构图，第一步会先排除边数不同的图。以下是匹配与不匹配的结构示例：

# 匹配的结构（绿色框示例）：
nodes: {A,B,B,B}; bonds: {{0,1},{1,2},{1,3}}
nodes: {B,B,B,A}; bonds: {{3,2},{2,0},{3,1}}
nodes: {B,B,B,A}; bonds: {{0,1},{1,2},{1,3}}

# 不匹配的结构（红色框示例）：
nodes: {B,A,B,B}; bonds: {{0,1},{1,2},{1,3}}  # A类型节点度数不符，无法匹配
nodes: {B,B,B,B}; bonds: {{0,1},{1,2},{1,3}}  # 缺少A类型节点，类型分布不匹配
nodes: {A,B,B};   bonds: {{0,1},{1,2}}         # 节点数、边数均不匹配

我已经写了一个Boost Graph Library（BGL）的最小示例代码，想知道如何用BGL实现上述需求，同时确认BGL是否是合适的工具。

原示例代码：

// (C) Copyright Jeremy Siek 2001.
// 基于Boost软件许可证1.0版本发布（可查看附带文件LICENSE_1_0.txt或复制到
// http://www.boost.org/LICENSE_1_0.txt）

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/graph_utility.hpp>

/*
  示例输出：
  isomorphic? 1
  f: 9 10 11 0 1 3 2 4 6 8 7 5 
 */

int
main()
{
  using namespace boost;
  
  const int n = 12;

  typedef adjacency_list<vecS, listS, undirectedS,
    property<vertex_index_t, int> > graph_t;
  graph_t g1(n), g2(n);

  std::vector<graph_traits<graph_t>::vertex_descriptor> v1(n), v2(n);

  property_map<graph_t, vertex_index_t>::type 
    v1_index_map = get(vertex_index, g1),
    v2_index_map = get(vertex_index, g2);

  graph_traits<graph_t>::vertex_iterator i, end;
  int id = 0;
  for (tie(i, end) = vertices(g1); i != end; ++i, ++id) {
    put(v1_index_map, *i, id);
    v1[id] = *i;
  }
  id = 0;
  for (tie(i, end) = vertices(g2); i != end; ++i, ++id) {
    put(v2_index_map, *i, id);
    v2[id] = *i;
  }
  add_edge(v1[0], v1[1], g1); add_edge(v1[1], v1[2], g1); 
  add_edge(v1[0], v1[2], g1);
  add_edge(v1[3], v1[4], g1);  add_edge(v1[4], v1[5], g1);
  add_edge(v1[5], v1[6], g1);  add_edge(v1[6], v1[3], g1);
  add_edge(v1[7], v1[8], g1);  add_edge(v1[8], v1[9], g1);
  add_edge(v1[9], v1[10], g1);
  add_edge(v1[10], v1[11], g1);  add_edge(v1[11], v1[7], g1);

  add_edge(v2[9], v2[10], g2);  add_edge(v2[10], v2[11], g2);  
  add_edge(v2[11], v2[9], g2);
  add_edge(v2[0], v2[1], g2);  add_edge(v2[1], v2[3], g2); 
  add_edge(v2[3], v2[2], g2);  add_edge(v2[2], v2[0], g2);
  add_edge(v2[4], v2[5], g2); add_edge(v2[5], v2[7], g2); 
  add_edge(v2[7], v2[8], g2);
  add_edge(v2[8], v2[6], g2); add_edge(v2[6], v2[4], g2);

  std::vector<graph_traits<graph_t>::vertex_descriptor> f(n);

  bool ret = isomorphism
    (g1, g2, isomorphism_map
     (make_iterator_property_map(f.begin(), v1_index_map, f[0])));

  std::cout << "isomorphic? " << ret << std::endl;

  std::cout << "f: ";
  for (std::size_t v = 0; v != f.size(); ++v)
    std::cout << get(get(vertex_index, g2), f[v]) << " ";
  std::cout << std::endl;
  
  return 0;
}

解答 #

1. BGL是否适合该需求？

完全适合。BGL提供了成熟的图同构检测接口isomorphism，并且支持通过自定义谓词添加顶点/边的属性约束，正好满足你对节点类型（A/B）的匹配要求。

2. 如何修改代码实现节点类型约束？

核心步骤是给顶点添加类型属性，并自定义顶点匹配谓词，确保只有类型相同的顶点才能被匹配。以下是修改后的完整代码：

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>

// 定义节点类型
enum NodeType { A, B };

int main() {
  using namespace boost;

  // 定义带顶点属性的图类型：包含顶点索引和节点类型
  typedef adjacency_list<vecS, listS, undirectedS,
    property<vertex_index_t, int, property<vertex_color_t, NodeType>> > graph_t;

  // 构造示例图1：节点类型{A,B,B,B}，边{{0,1},{1,2},{1,3}}
  graph_t g1(4);
  std::vector<graph_traits<graph_t>::vertex_descriptor> v1(4);
  auto v1_index_map = get(vertex_index, g1);
  auto v1_type_map = get(vertex_color, g1); // 用vertex_color_t存储节点类型
  int id = 0;
  for (auto [i, end] = vertices(g1); i != end; ++i, ++id) {
    put(v1_index_map, *i, id);
    v1[id] = *i;
    // 设置节点类型：0为A，其余为B
    put(v1_type_map, v1[id], (id == 0) ? A : B);
  }
  add_edge(v1[0], v1[1], g1);
  add_edge(v1[1], v1[2], g1);
  add_edge(v1[1], v1[3], g1);

  // 构造示例图2：节点类型{B,B,B,A}，边{{3,2},{2,0},{3,1}}
  graph_t g2(4);
  std::vector<graph_traits<graph_t>::vertex_descriptor> v2(4);
  auto v2_index_map = get(vertex_index, g2);
  auto v2_type_map = get(vertex_color, g2);
  id = 0;
  for (auto [i, end] = vertices(g2); i != end; ++i, ++id) {
    put(v2_index_map, *i, id);
    v2[id] = *i;
    // 设置节点类型：3为A，其余为B
    put(v2_type_map, v2[id], (id == 3) ? A : B);
  }
  add_edge(v2[3], v2[2], g2);
  add_edge(v2[2], v2[0], g2);
  add_edge(v2[3], v2[1], g2);

  // 构造示例图3：节点类型{B,A,B,B}，边{{0,1},{1,2},{1,3}}（预期不匹配）
  graph_t g3(4);
  std::vector<graph_traits<graph_t>::vertex_descriptor> v3(4);
  auto v3_index_map = get(vertex_index, g3);
  auto v3_type_map = get(vertex_color, g3);
  id = 0;
  for (auto [i, end] = vertices(g3); i != end; ++i, ++id) {
    put(v3_index_map, *i, id);
    v3[id] = *i;
    // 设置节点类型：1为A，其余为B
    put(v3_type_map, v3[id], (id == 1) ? A : B);
  }
  add_edge(v3[0], v3[1], g3);
  add_edge(v3[1], v3[2], g3);
  add_edge(v3[1], v3[3], g3);

  // 自定义顶点匹配谓词：检查两个顶点的类型是否相同
  auto vertex_match_1_2 = [&](auto u, auto v) {
    return get(v1_type_map, u) == get(v2_type_map, v);
  };

  std::vector<graph_traits<graph_t>::vertex_descriptor> f(num_vertices(g1));
  bool is_isomorphic_1_2 = isomorphism(g1, g2, 
    isomorphism_map(make_iterator_property_map(f.begin(), v1_index_map, f[0]))
    .vertex_invariant(vertex_match_1_2));

  std::cout << "g1与g2是否同构（带类型约束）？" << (is_isomorphic_1_2 ? "是" : "否") << std::endl;

  // 检查g1与g3的同构性
  auto vertex_match_1_3 = [&](auto u, auto v) {
    return get(v1_type_map, u) == get(v3_type_map, v);
  };
  bool is_isomorphic_1_3 = isomorphism(g1, g3, 
    isomorphism_map(make_iterator_property_map(f.begin(), v1_index_map, f[0]))
    .vertex_invariant(vertex_match_1_3));

  std::cout << "g1与g3是否同构（带类型约束）？" << (is_isomorphic_1_3 ? "是" : "否") << std::endl;

  return 0;
}

代码关键说明：

• 顶点属性扩展：在adjacency_list模板参数中添加property<vertex_color_t, NodeType>，用来存储节点类型（也可自定义属性标签，这里复用vertex_color_t简化实现）。
• 自定义顶点匹配谓词：用lambda表达式定义vertex_match，确保只有类型相同的顶点能参与同构匹配。
• 调用isomorphism函数：通过.vertex_invariant()传入自定义谓词，启用带类型约束的同构检测。
• 前置过滤优化：调用同构检测前，可先检查两图的节点数、边数、A/B类型节点数量是否一致，提前排除不可能匹配的情况，提升效率。

内容的提问来源于stack exchange，提问作者michael