Find all cycles of directed graph in boost

Question

Can someone tell me how to find all cycles of a directed graph using the boost graph library?

Answer 1

Google turns up the - otherwise undocumented - tiernan_all_cycles. There is an example though.

The example presupposes less-than-optimal graph models. According to issue #182 you should really be able to satisfy the missing concept requirement for adjacency-list (provided that it has a correct vertex index):

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&) {} }

Here's a modernized example:

Live On Compiler Explorer

#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{});
}

Prints

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