before I proceed in actually fixing the checks and adding some tests, are you actually interested in adding this algorithm to the library?

Yes I think we want to add it. Some thoughts:

1. Two implementations is great, since these algorithms can be quite tricky and that's the best way to test it
2. The reference implementation can live in the tests, unless it has a value on its own
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
4. Any thoughts on using graph traits to implement this?
5. If you do a lot of edge existence testing on the same graph, there's a trait for making an adjacency matrix for O(1) lookup (GetAdjacencyMatrix). It's also a bitmap.
6. There's a quickcheck / Arbitrary implementation for generating random graphs. If their properties are ok, that might be neat to use.

Hey!! thanks for the suggestions. I will work on them as soon as I get the chance.

Does a reference implementation also not have a value in benchmarks? It gives a baseline that automatically adjusts for improvements in rustc or in the library itself.

That sounds useful, but it doesn't mean that petgraph has to have it in its public API

I agree it should not be in the public API. As far as I can tell, if it is not part of the public API then the tests and the benchmarks for the reference implementation must also be in the src/, because code in tests/ and benches/ can only call public API function.

Also I reimplemented the algorithm using graph traits and it got about 2x faster.

That's good. I'm sure it can be sped up twice more, but that's not necessarily the most important thing before merging.

This needs attention from me or others that volunteer to review.

I haven't yet implemented your suggestion of using a bitmap. I just ran perf on the algorithm and the output confirms the benefit of implementing your suggestion:

-   85.81%     7.39%  maximal_cliques  maximal_cliques-b72916c972f923d5  [.] petgraph::algo::bron_kerbosch_pivot::h644513b48bb8fa09
   - 91.60% petgraph::algo::bron_kerbosch_pivot::h644513b48bb8fa09
      + 67.13% _$LT$std..collections..hash..set..HashSet$LT$T$C$$u20$S$GT$$u20$as$u20$core..iter..traits..FromIterator$LT$T$GT$$GT$::from_iter::h0cbc11aef1b5d327
      + 11.09% _$LT$std..collections..hash..map..HashMap$LT$K$C$$u20$V$C$$u20$S$GT$$GT$::insert::h5da3f60beedb0ac9
      + 5.73% petgraph::algo::bron_kerbosch_pivot::h644513b48bb8fa09
      + 2.73% _$LT$std..collections..hash..map..HashMap$LT$K$C$$u20$V$C$$u20$S$GT$$GT$::remove::h4f7afa08dd1179d8
      + 1.16% __rust_dealloc
      + 1.02% _$LT$alloc..vec..Vec$LT$T$GT$$u20$as$u20$alloc..vec..SpecExtend$LT$T$C$$u20$I$GT$$GT$::from_iter::h48bffa9a3ceb72b0
      + 0.98% _$LT$std..collections..hash..table..RawTable$LT$K$C$$u20$V$GT$$u20$as$u20$core..clone..Clone$GT$::clone::ha9a3b2ba1486c9b5
      + 0.55% _$LT$alloc..raw_vec..RawVec$LT$T$C$$u20$A$GT$$GT$::reserve::h39e93582e4064490
      + 0.23% _init
        0.11% std::collections::hash::map::RandomState::new::KEYS::__getit::h9b962439dac88bb3
        0.09% _$LT$std..collections..hash..table..RawTable$LT$K$C$$u20$V$GT$$GT$::new_uninitialized::hc8244cf1918a33b3
      + 0.06% ProfileHandler::SignalHandler
      + 0.05% __rde_alloc
        0.03% std::collections::hash::table::calculate_allocation::ha384b58c8cace51b
        0.02% __rust_alloc
        0.02% std::collections::hash::map::DefaultResizePolicy::new::hf8248ff2eb42ae45
      + 0.01% 0xffffffff81846a96
        0.01% 0xffffffff81845658
      + 0.01% 0xffffffff81845b03

this is waiting on a PR to add the required methods to fixedbitset petgraph/fixedbitset#20

Thanks for pinging me.

@jrraymond can you please rebase and update your PR?

This seems great, why hasn't it been merged? I am probably going to use this algorithm in my current project, so if I can help resurrect this PR I would love to contribute.

Thank you all for the work done! A similar PR #662 was merged, and I will transfer the ideas from the discussion to #755 and plan to implement performance improvements in the future.