| Copyright | (c) Gershom Bazerman 2010 |
|---|---|
| License | BSD 3 Clause |
| Maintainer | gershomb@gmail.com |
| Stability | experimental |
| Safe Haskell | None |
| Language | Haskell98 |
Data.Algorithm.MaximalCliques
Description
This library uses the Bron-Kerbosch algorithm to enumerate all maximal cliques in an undirected graph. A clique is a set of nodes such that there is an edge between every node and every other node in the set. A maximal clique is a clique such that no node may be added while preserving the clique property.
Maximal clique enumeration is ExpTime complete, and even finding the greatest single clique (the maximum clique) is NP-complete. The Bron-Kerbosch algorithm is known to run well in practice while maintaining a simple implementation. If more efficiency is desired, there are now better algorithms. See, for example, Makino and Uno: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.705. Patches providing improved implementations are more than welcome.
- getMaximalCliques :: (a -> a -> Bool) -> [a] -> [[a]]
- maximalCliques :: (IntSet -> IntSet -> Int) -> (Int -> IntSet) -> IntSet -> [IntSet]
Documentation
getMaximalCliques :: (a -> a -> Bool) -> [a] -> [[a]] #
Given a list of nodes, and a function that determines whether there is an edge between any two nodes, yields a list of maximal cliques -- sets of nodes such that every node is connected to every other, and such that no other node may be added while maintaining this property.
Arguments
| :: (IntSet -> IntSet -> Int) | A function that given two |
| -> (Int -> IntSet) | A function that given a node id, yields the set of its neighbors. |
| -> IntSet | The set of all nodes in the graph. |
| -> [IntSet] | An enumeration of all maximal cliques in the graph. |
The Bron-Kerbosch algorithm for finding all maximal cliques in an undirected graph.
http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm. Works on nodes represented as Ints.