feat: Add Bron-Kerbosch algorithm for maximal cliques#662
feat: Add Bron-Kerbosch algorithm for maximal cliques#662starovoid merged 1 commit intopetgraph:masterfrom qoqosz:feature/maximal_cliques
Conversation
|
I think you should rebase instead of merging
|
|
@praseodym indeed, thanks for noticing. |
|
@qoqosz Hi, please rebase. I plan to include this in the next release. |
qoqosz
changed the title
|
@starovoid sure, it's rebased now. |
|
It is also common for new algorithms to add a |
|
@starovoid thanks for the feedback. I have moved an already existing test to |
|
@qoqosz Nice! Last request: please squash all commits into new one to simplify commits history. git reset $(git merge-base master $(git branch --show-current))
git add -A
git commit -m "Implement Bron-Kerbosch algorithm for maximal cliques"
git push --force |
starovoid
left a comment
starovoid
left a comment
There was a problem hiding this comment.
Everything is great, thank you!
A sufficient number of proposed changes have accumulated to combine them and publish a new major release numbered `0.8.0`. BREAKING CHANGE: This will require the user to provide extra type parameter in some APIs (Read more in #747). ## List of changes - [x] #747 The main innovation of the current release, the long-awaited feature that has become very relevant due to the transition of dependent projects to support `no_std`. - [x] #662 - [x] #611 - [x] #728 - [x] #686 - [x] #737 - [x] #720 - [x] #718 ## Note There are still a large number of PRs that we want to adopt in the near future, so we should expect at least a release of `0.8.1` soon after the completion of `0.8.0`. Thank you all for participating! --------- Co-authored-by: Agustin Borgna <[email protected]>
4 participants
This PR resurrects #72 by applying @jrraymond's changes to the recent (
0.6.5)masterbranch with only minor code style changes. This also addresses a recent issue #620.The added algorithm enumerates maximal cliques in a graph by using Bron-Kerbosch algorithm with pivoting.
Specifically, my added changes include:
I did not apply the suggestion to use
FixedBitSetinstead ofHashMapfrom the original PR as I don't know how to approach it for the generic graph.