Saving cliques in Boost's implementation of Bron Kerbosch algorithm

Question

I tried using Boost's implementation of the Bron-Kerbosch algorithm to save the cliques in a graph. I am able to write it to a file but not save it within my code directly in a vector of list of nodes belonging to each clique. Any help is greatly appreciated!

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);

Answer 1

You are very close. Just store a reference to the target collection in your visitor, e.g. if defining cliques like

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>;

Define a visitor to collect them:

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

That's all: 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);
}

Printing

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

BONUS

Making things potentially more efficient and C++11 compatible by using deque<V> for Clique:

Live On 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);