Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

feat: Add Bron Kerbosch algorithm to find maximal cliques #658

Open
wants to merge 1 commit into
base: main
Choose a base branch
from

Conversation

TripleCamellya
Copy link
Contributor

References to other Issues or PRs or Relevant literature

Fixes #639

Bron–Kerbosch algorithm is an enumeration algorithm for finding all maximal cliques. It is widely used in application areas of graph algorithms such as computational chemistry.

More detail can see issue or wiki:

https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

Brief description of what is fixed or changed

  1. Implement a new API for maximal cliques problem.
  2. Add Bron-Kerbosch algorithm for maximal cliques problem.
  3. Add related doc for find_maximal_cliques.
  4. Add related tests.
  5. Fix some format inconsistency, like double white lines.

Other comments

Example usage:

from pydatastructs import Graph, AdjacencyListGraphNode
from pydatastructs import find_maximal_cliques
V1 = AdjacencyListGraphNode('V1')
V2 = AdjacencyListGraphNode('V2')
V3 = AdjacencyListGraphNode('V3')
V4 = AdjacencyListGraphNode('V4')
G = Graph(V1, V2, V3, V4)
G.add_edge('V1', 'V2')
G.add_edge('V2', 'V1')
G.add_edge('V2', 'V3')
G.add_edge('V3', 'V2')
G.add_edge('V1', 'V3')
G.add_edge('V3', 'V1')
G.add_edge('V1', 'V4')
G.add_edge('V4', 'V1')
find_maximal_cliques(G, 'bron_kerbosc')
[['V1', 'V2', 'V3'], ['V1', 'V4']]

API Changes:

I used to return like List[Set], but I found that the order of set is random. So I changed API to sorted list to pass the doc test and other test.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Add Bron Kerbosch algorithm to find maximal cliques
1 participant