Let this issue be a place to discuss ideas for improving the current implementation of maximal_cliques.

Old discussions

In #72, some ways to improve the performance of the Bron-Kerbosch algorithm were discussed.

Quote from bluss:

...
3. Sets of node indices can just be bitmaps right, shouldn't that be much cheaper to compute intersections on? We just need to add the required methods to FixedBitSet

Handle oriented graphs

There is also an idea to use an UndirectedAdaptor inside the implementation to protect against panics on asymmetrical directed graphs. It will look like in the code below, but the issue is highly debatable. It seems to me that the more correct option is to return a certain MaxCliqueError instead of panicking and not making extra adaptations for directed graphs.

pub fn maximal_cliques<G>(g: G) -> Vec<HashSet<G::NodeId>>
where
    G: GetAdjacencyMatrix + IntoNodeIdentifiers + IntoNeighbors + IntoNeighborsDirected,
    G::NodeId: Eq + Hash,
{
    let g = UndirectedAdaptor(g);
    let adj_mat = g.adjacency_matrix();
    let r = HashSet::new();
    let p = g.node_identifiers().collect::<HashSet<G::NodeId>>();
    let x = HashSet::new();
    bron_kerbosch_pivot(g, &adj_mat, r, p, x)
}