pydatastructs icon indicating copy to clipboard operation
pydatastructs copied to clipboard

feat: Add Bron Kerbosch algorithm to find maximal cliques

Open TripleCamellya opened this issue 9 months ago • 0 comments

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.

TripleCamellya avatar Mar 19 '25 07:03 TripleCamellya