pydatastructs
pydatastructs copied to clipboard
feat: Add Bron Kerbosch algorithm to find maximal cliques
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
- Implement a new API for maximal cliques problem.
- Add Bron-Kerbosch algorithm for maximal cliques problem.
- Add related doc for
find_maximal_cliques. - Add related tests.
- 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.