带权顶点最大权子图同构的Boost实现及替代方案咨询

云上老周

2026-7-21

带权顶点的最大权子图同构实现方案

一、Boost库的支持情况与实现思路

Boost的VF2子图同构算法默认仅支持无权重匹配，但可以通过自定义顶点匹配谓词和扩展回调函数实现带权顶点的最大权子图同构，核心思路是：先确保结构同构，再跟踪所有合法映射的权重总和，筛选出最大值。

具体实现步骤

定义带顶点权重的图类型
修改adjacency_list，添加顶点权重属性：

#include <boost/graph/properties.hpp>
// 顶点权重属性
typedef property<vertex_weight_t, int> VertexWeightProperty;
// 带权重的图类型
typedef adjacency_list<setS, vecS, bidirectionalS, VertexWeightProperty> graph_type;

设置顶点权重
使用put函数为图的顶点赋值权重：

// 为模式图（graph1）顶点设置权重
put(vertex_weight_t(), graph1, 0, 5);
put(vertex_weight_t(), graph1, 1, 3);
put(vertex_weight_t(), graph1, 2, 4);
// ... 其他顶点同理
// 为目标图（graph2）顶点设置权重
put(vertex_weight_t(), graph2, 0, 5);
put(vertex_weight_t(), graph2, 1, 3);
put(vertex_weight_t(), graph2, 8, 9);
// ... 其他顶点同理

自定义顶点匹配谓词
用于判断两个顶点是否满足匹配条件（可根据需求调整，比如要求权重相等，或仅做结构兼容检查）：

struct VertexWeightChecker {
    template <typename Graph1, typename Graph2>
    bool operator()(typename Graph1::vertex_descriptor v1, typename Graph2::vertex_descriptor v2,
                    const Graph1& g1, const Graph2& g2) const {
        // 示例：要求顶点权重相等，同时确保邻接结构匹配前置条件
        if (get(vertex_weight_t(), g1, v1) != get(vertex_weight_t(), g2, v2)) return false;
        // 检查已匹配邻居的对应关系
        for (auto neighbor : make_iterator_range(adjacent_vertices(v1, g1))) {
            if (get(vertex_to_vertex_map, neighbor) != Graph1::null_vertex()) {
                auto t_neighbor = get(vertex_to_vertex_map, neighbor);
                if (!edge(t_neighbor, v2, g2).second) return false;
            }
        }
        return true;
    }
};

自定义回调跟踪最大权映射
不再仅打印映射，而是计算每个合法映射的总权重，记录最大值和对应映射：

struct MaxWeightCallback {
    const graph_type& pattern;
    const graph_type& target;
    int max_total_weight = INT_MIN;
    std::map<typename graph_type::vertex_descriptor, typename graph_type::vertex_descriptor> best_mapping;

    MaxWeightCallback(const graph_type& pat, const graph_type& tar) : pattern(pat), target(tar) {}

    template <typename CorrMap1To2, typename CorrMap2To1>
    bool operator()(CorrMap1To2 f, CorrMap2To1) {
        int current_total = 0;
        // 计算当前映射的总权重
        for (auto v : make_iterator_range(vertices(pattern))) {
            current_total += get(vertex_weight_t(), target, get(f, v));
        }
        // 更新最大权重与最优映射
        if (current_total > max_total_weight) {
            max_total_weight = current_total;
            best_mapping.clear();
            for (auto v : make_iterator_range(vertices(pattern))) {
                best_mapping[v] = get(f, v);
            }
        }
        return true; // 返回true继续枚举所有可能的映射
    }
};

调用VF2算法并传入自定义组件

MaxWeightCallback callback(graph1, graph2);
bool found = vf2_subgraph_iso(graph1, graph2, callback,
                              vertex_order_by_mult(graph1),
                              edges_equivalent(always_true()),
                              vertices_equivalent(VertexWeightChecker()));

if (found) {
    std::cout << "最大权值: " << callback.max_total_weight << std::endl;
    std::cout << "最优映射:" << std::endl;
    for (auto& pair : callback.best_mapping) {
        std::cout << "graph1顶点" << pair.first << " → graph2顶点" << pair.second << std::endl;
    }
} else {
    std::cout << "未找到子图同构" << std::endl;
}

注意：这种方式会枚举所有合法的子图同构映射，对于大规模图可能效率有限，可通过添加剪枝策略（如权重上下界预判）优化。

二、其他可用库

如果Boost的扩展方案无法满足效率需求，可考虑以下工具：

LEMON Graph Library（C++）：轻量高效的图库，支持自定义顶点/边属性，可扩展实现带权子图同构，内置多种图算法优化。
Graph-tool（Python）：底层基于C++实现，性能优于NetworkX，支持带属性的子图同构，适合快速开发与大规模图处理。
NetworkX（Python）：提供VF2等子图同构算法，可通过自定义节点属性过滤匹配，适合原型验证与中小规模图场景。

三、VF2带权最大子图同构简洁实现

以下是手动实现的VF2带权扩展版本，加入剪枝与权重跟踪，适合中小规模图的高效处理：

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>

using namespace std;

// 带权图结构
struct WeightedGraph {
    int n; // 顶点数
    vector<vector<int>> adj; // 邻接表（无向图需双向添加）
    vector<int> weights; // 顶点权重

    WeightedGraph(int size) : n(size), adj(size), weights(size, 0) {}
};

class VF2MaxWeightSubgraphIso {
private:
    const WeightedGraph& pattern; // 模式图（待匹配的子图）
    const WeightedGraph& target; // 目标图
    map<int, int> mapping; // 模式顶点 → 目标顶点的映射
    map<int, int> reverse_mapping; // 目标顶点 → 模式顶点的逆映射
    int current_weight = 0;
    int max_weight = INT_MIN;
    map<int, int> best_mapping;

    // 检查模式顶点v与目标顶点u是否可匹配
    bool is_compatible(int v, int u) {
        // 权重匹配条件（可根据需求调整，如允许权重不同但累加最大）
        if (pattern.weights[v] != target.weights[u]) return false;
        // 检查已匹配邻居的邻接关系
        for (int p_neighbor : pattern.adj[v]) {
            if (mapping.count(p_neighbor)) {
                int t_neighbor = mapping[p_neighbor];
                if (find(target.adj[u].begin(), target.adj[u].end(), t_neighbor) == target.adj[u].end()) {
                    return false;
                }
            }
        }
        for (int t_neighbor : target.adj[u]) {
            if (reverse_mapping.count(t_neighbor)) {
                int p_neighbor = reverse_mapping[t_neighbor];
                if (find(pattern.adj[v].begin(), pattern.adj[v].end(), p_neighbor) == pattern.adj[v].end()) {
                    return false;
                }
            }
        }
        return true;
    }

    // 回溯搜索
    void backtrack(int depth) {
        if (depth == pattern.n) {
            // 找到完整同构，更新最大权重
            if (current_weight > max_weight) {
                max_weight = current_weight;
                best_mapping = mapping;
            }
            return;
        }

        // 选择下一个未匹配的模式顶点
        int v = -1;
        for (int i = 0; i < pattern.n; ++i) {
            if (!mapping.count(i)) {
                v = i;
                break;
            }
        }
        if (v == -1) return;

        // 尝试所有未匹配的目标顶点
        for (int u = 0; u < target.n; ++u) {
            if (!reverse_mapping.count(u) && is_compatible(v, u)) {
                // 记录映射
                mapping[v] = u;
                reverse_mapping[u] = v;
                current_weight += target.weights[u];

                backtrack(depth + 1);

                // 回溯
                current_weight -= target.weights[u];
                reverse_mapping.erase(u);
                mapping.erase(v);
            }
        }
    }

public:
    VF2MaxWeightSubgraphIso(const WeightedGraph& pat, const WeightedGraph& tar) : pattern(pat), target(tar) {}

    void search() {
        backtrack(0);
    }

    void print_result() {
        if (max_weight == INT_MIN) {
            cout << "未找到子图同构" << endl;
            return;
        }
        cout << "最大权值: " << max_weight << endl;
        cout << "最优映射:" << endl;
        for (auto& pair : best_mapping) {
            cout << "模式顶点" << pair.first << " → 目标顶点" << pair.second << endl;
        }
    }
};

// 示例用法
int main() {
    // 构建模式图
    WeightedGraph pattern(8);
    pattern.weights = {5,3,4,2,1,6,7,8};
    pattern.adj[0] = {6,7}; pattern.adj[6] = {0,2}; pattern.adj[7] = {0,1};
    pattern.adj[1] = {5,7}; pattern.adj[5] = {1,2};
    pattern.adj[2] = {4,5,6}; pattern.adj[4] = {2,3};
    pattern.adj[3] = {4};

    // 构建目标图
    WeightedGraph target(9);
    target.weights = {5,3,4,2,1,6,7,8,9};
    target.adj[0] = {6,8}; target.adj[6] = {0,3}; target.adj[8] = {0,2};
    target.adj[1] = {5,7}; target.adj[5] = {1,3};
    target.adj[2] = {4,7,8}; target.adj[7] = {1,2};
    target.adj[3] = {4,5,6}; target.adj[4] = {2,3};

    VF2MaxWeightSubgraphIso solver(pattern, target);
    solver.search();
    solver.print_result();

    return 0;
}

优化建议：针对大规模图，可添加顶点度数预判、权重上下界剪枝、启发式顶点排序等策略，进一步提升搜索效率。

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

带权顶点最大权子图同构的Boost实现及替代方案咨询

一、Boost库的支持情况与实现思路 #

具体实现步骤 #

二、其他可用库 #

三、VF2带权最大子图同构简洁实现 #

一、Boost库的支持情况与实现思路

具体实现步骤

二、其他可用库

三、VF2带权最大子图同构简洁实现