在 Boost 实现 Bron Kerbosch 算法时保存集团

Saving cliques in Boost's implementation of Bron Kerbosch algorithm

提问人:tr244 提问时间:11/8/2023 更新时间:11/8/2023 访问量:30

问:

我尝试使用 Boost 的 Bron-Kerbosch 算法实现将集团保存在图形中。我能够将其写入文件,但不能将其直接保存在我的代码中,以属于每个集团的节点列表向量中。任何帮助都非常感谢!

class Visitor {
public:
    template<typename Clique, typename Graph>
    void clique(const Clique& c, const Graph& g)
    {
        // Write the clique details to a file with vertices of each clique in a new line
        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();

        // Display the cliques
        /*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();

// Run Bron-Kerbosch algorithm to identify all cliques
Visitor visitor;
boost::bron_kerbosch_all_cliques(g, visitor, 1);
C++ Boost Clique Clique-Problem

评论


答:

1赞 sehe 11/8/2023 #1

你离得很近。只需在访问者中存储对目标集合的引用,例如,如果定义像

using Graph   = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using V       = Graph::vertex_descriptor;
using Clique  = std::vector<V>;
using Cliques = std::vector<Clique>;

定义要收集它们的访客:

struct Collector {
    Cliques& target;

    void clique(auto const& clique, Graph const&) const {
        for (auto& t = target.emplace_back(); Graph::vertex_descriptor v : clique)
            t.push_back(v);
    }
};

仅此而已:Live On Coliru

int main() {
    Graph g;

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

    std::vector<Clique> cliques;
    bron_kerbosch_all_cliques(g, Collector {cliques}, 1);

    fmt::print("All cliques: {}\n", cliques);
}

印刷

All cliques: [[0], [1, 2, 3]]

奖金

通过使用 for 使事情可能更高效和 C++11 兼容:deque<V>Clique

在 Coliru 上直播

std::vector<Clique> cliques;
struct {
    Cliques& target;
    void clique(std::deque<V> clique, Graph const&) const { target.push_back(std::move(clique)); }
} collect{cliques};

bron_kerbosch_all_cliques(g, collect, 1);

评论

0赞 sehe 11/8/2023
旁注:Bron-Kerbosch 对于非矩阵模型效率低下,请考虑 coliru.stacked-crooked.com/a/75be196674178fc4
0赞 tr244 11/9/2023
像魅力一样工作。我真的很感激。非常感谢!