提问人:tr244 提问时间:11/8/2023 更新时间:11/8/2023 访问量:30
在 Boost 实现 Bron Kerbosch 算法时保存集团
Saving cliques in Boost's implementation of Bron Kerbosch algorithm
问:
我尝试使用 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);
答:
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
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赞
tr244
11/9/2023
像魅力一样工作。我真的很感激。非常感谢!
评论