在boost中查找有向图的所有循环

Question

有人能告诉我如何使用boost图库找到有向图的所有循环吗？

Answer 1

谷歌打开了未记录的tiernan_all_cycles。不过有一个例子。

该示例假定了不太理想的图模型。根据问题#182，你应该真的能够满足相邻列表的缺失概念要求(前提是它有一个正确的顶点索引(：

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::/*un*/directedS>;
// see https://github.com/boostorg/graph/issues/182
namespace boost { void renumber_vertex_indices(Graph const&) {} }

下面是一个现代化的例子：

实时编译器资源管理器

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/tiernan_all_cycles.hpp>
#include <iostream>
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::/*un*/directedS>;
// see https://github.com/boostorg/graph/issues/182
namespace boost { void renumber_vertex_indices(Graph const&) {} }
struct Vis {
void cycle(auto const& path, Graph const& g) const {
auto indices = get(boost::vertex_index, g);
for (auto v : path)
std::cout << "ABCDEFGHIJKL"[get(indices, v)] << " ";
std::cout << "n";
};
};
int main()
{
enum { A, B, C, D, E, F, G, H, I, J, K, L, NUM };
Graph g(NUM);
// Graph from https://commons.wikimedia.org/wiki/File:Graph_with_Chordless_and_Chorded_Cycles.svg
for (auto [s, t] : { std::pair //
{A, B}, {B, C}, {C, D}, {D, E}, {E, F}, {F, A},
{G, H}, {H, I}, {I, J}, {J, K}, {K, L}, {L, G},
{C, L}, {D, K}, {B, G}, {C, G}, {I, K}
}) //
add_edge(s, t, g);
tiernan_all_cycles(g, Vis{});
}

打印

A B C D E F 
G H I J K L 
G H I K L