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);
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]]
Making things potentially more efficient and C++11 compatible by using deque<V>
for 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);