如何在Boost的Bron-Kerbosch算法实现中将clique保存至代码内向量？

问题描述 #

我用Boost实现Bron-Kerbosch算法识别图中的clique，目前能将结果写入文件，但没法在代码里把每个clique的节点列表保存到向量中，求帮助！

用户提供的代码：

class Visitor {
public:
    template<typename Clique, typename Graph>
    void clique(const Clique& c, const Graph& g)
    {
        // 将每个clique的顶点写入文件，每行一个clique
        std::ofstream clique_file;
        clique_file.open("../output/cliques.txt", std::ios_base::app);
        for (auto it = c.begin(); it!=c.end(); ++it)
            clique_file << *it << " ";
        clique_file << std::endl;
        clique_file.close();

        // 显示clique
        /*std::cout << "Clique: ";
        for (auto vertex : c)
            std::cout << vertex << " ";
        std::cout << std::endl;*/
    }
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;
Graph g;

boost::add_edge(1, 2, g);
boost::add_edge(2, 3, g);
boost::add_edge(3, 1, g);

std::ofstream clique_file;
clique_file.open("../output/cliques.txt", std::ios_base::trunc);
clique_file.close();

// 运行Bron-Kerbosch算法识别所有clique
Visitor visitor;
boost::bron_kerbosch_all_cliques(g, visitor, 1);

解决方案 #

给Visitor类添加一个成员变量存储所有clique的集合，在回调方法中把每个clique转换为vector存入即可。

修改后的完整代码 #

#include <vector>
#include <iostream>
#include <fstream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bron_kerbosch_all_cliques.hpp>

class Visitor {
public:
    // 存储所有clique的向量，每个元素是一个clique的节点列表
    std::vector<std::vector<int>> all_cliques;

    template<typename Clique, typename Graph>
    void clique(const Clique& c, const Graph& g)
    {
        // 保留写入文件的逻辑
        std::ofstream clique_file;
        clique_file.open("../output/cliques.txt", std::ios_base::app);
        for (auto it = c.begin(); it!=c.end(); ++it)
            clique_file << *it << " ";
        clique_file << std::endl;
        clique_file.close();

        // 将当前clique转换为vector并添加到all_cliques
        std::vector<int> current_clique;
        for (auto vertex : c) {
            current_clique.push_back(static_cast<int>(vertex));
        }
        all_cliques.push_back(current_clique);
    }
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;

int main() {
    Graph g;

    boost::add_edge(1, 2, g);
    boost::add_edge(2, 3, g);
    boost::add_edge(3, 1, g);

    // 清空文件内容
    std::ofstream clique_file;
    clique_file.open("../output/cliques.txt", std::ios_base::trunc);
    clique_file.close();

    // 运行Bron-Kerbosch算法
    Visitor visitor;
    boost::bron_kerbosch_all_cliques(g, visitor, 1);

    // 示例：访问保存的所有clique
    std::cout << "所有保存的clique:" << std::endl;
    for (const auto& clique : visitor.all_cliques) {
        std::cout << "Clique: ";
        for (int vertex : clique) {
            std::cout << vertex << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

关键说明 #

• 给Visitor类添加std::vector<std::vector<int>> all_cliques成员，作为存储所有clique的容器
• 在clique回调方法中，遍历当前clique的节点，将其存入临时vector后添加到all_cliques中
• 算法执行完成后，通过visitor.all_cliques即可直接访问所有保存的clique节点列表

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