-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Enumerate all maximal cliques of a graph.
--   
--   Enumerate all maximal cliques of a 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.
@package maximal-cliques
@version 0.1.1


-- | 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:
--   <a>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.705</a>.
--   Patches providing improved implementations are more than welcome.
module Data.Algorithm.MaximalCliques

-- | 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.
getMaximalCliques :: (a -> a -> Bool) -> [a] -> [[a]]

-- | The Bron-Kerbosch algorithm for finding all maximal cliques in an
--   undirected graph.
--   <a>http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm</a>.
--   Works on nodes represented as <a>Int</a>s.
maximalCliques :: (IntSet -> IntSet -> Int) -> (Int -> IntSet) -> IntSet -> [IntSet]
