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

Add Bron Kerbosch algorithm to find maximal cliques #639

Open
TripleCamellya opened this issue Mar 12, 2025 · 1 comment · May be fixed by #658
Open

Add Bron Kerbosch algorithm to find maximal cliques #639

TripleCamellya opened this issue Mar 12, 2025 · 1 comment · May be fixed by #658

Comments

@TripleCamellya
Copy link
Contributor

A clique in an undirected graph is a subset of vertices where every two distinct vertices are adjacent. In other words, a clique is a complete subgraph where each vertex is connected to every other vertex within the subset.

A maximal clique is a clique that cannot be extended by including one more adjacent vertex. That is, a maximal clique is a clique that is not a subset of any other clique in the graph. It is the largest clique that can be formed starting from a given vertex or a given subset of vertices.

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.

Here is wiki:

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

Task:

  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.
@TripleCamellya
Copy link
Contributor Author

I have already completed the tasks mentioned above. I will submit a new PR after receiving a reply to my previous one.

Example:

>>> 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', 'V3', 'V2'}, {'V1', 'V4'}]

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 a pull request may close this issue.

1 participant