maximal-cliques (empty) → 0.1

raw patch · 4 files changed

+134/−0 lines, 4 filesdep +basedep +containersdep +vectorsetup-changed

Dependencies added: base, containers, vector

Files

Data/Algorithm/MaximalCliques.hs +42/−0
LICENSE +30/−0
Setup.hs +2/−0
maximal-cliques.cabal +60/−0

+ Data/Algorithm/MaximalCliques.hs view

@@ -0,0 +1,42 @@+{- |+Module      :  Data.Algorithm.MaximalCliques+Copyright   :  (c) Gershom Bazerman, 2010+License     :  BSD 3 Clause+Maintainer  :  gershomb@gmail.com+Stability   :  experimental++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.++-}+module Data.Algorithm.MaximalCliques where++import Data.List (mapAccumL)+import qualified Data.IntSet as S+import qualified Data.Vector as V++-- | 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]]+getMaximalCliques tolFun xs = map (map (fst . (V.!) lv) . S.toList) $+                              maximalCliques pickpivot (snd . ((V.!) lv)) (S.fromList $ map fst lnodes)+    where lnodes = zip [0..] xs+          lnodes' = map (\(k,n) -> (n,S.fromList $ filter (/=k) $ map fst $ filter (tolFun n . snd) lnodes)) lnodes+          lv = V.fromList lnodes'+          pickpivot p x = head $ S.elems p ++ S.elems x++-- | 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 'Int's.+maximalCliques :: (S.IntSet -> S.IntSet -> Int) -- ^ A function that given two 'IntSet's, chooses a member of one as a pivot.+               -> (Int -> S.IntSet)  -- ^ A function that given a node id, yields the set of its neighbors.+               -> S.IntSet -- ^ The set of all nodes in the graph.+               -> [S.IntSet] -- ^ An enumeration of all maximal cliques in the graph.+maximalCliques pickpivot neighborsOf nodeset = go S.empty nodeset S.empty+    where go r p x+              | S.null p && S.null x = [r]+              | otherwise =+                  let pivot = pickpivot p x+                      step' (p',x') v =+                          let nv  = neighborsOf v+                          in ((S.delete v p', S.insert v x'), go (S.insert v r) (S.intersection nv p') (S.intersection nv x'))+                  in concat . snd $ mapAccumL step' (p,x) $ S.elems (p S.\\ neighborsOf pivot)

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright (c)2010, Gershom Bazerman++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Gershom Bazerman nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ maximal-cliques.cabal view

@@ -0,0 +1,60 @@+-- maximal-cliques.cabal auto-generated by cabal init. For additional+-- options, see+-- http://www.haskell.org/cabal/release/cabal-latest/doc/users-guide/authors.html#pkg-descr.+-- The name of the package.+Name:                maximal-cliques++-- The package version. See the Haskell package versioning policy+-- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for+-- standards guiding when and how versions should be incremented.+Version:             0.1++-- A short (one-line) description of the package.+Synopsis:            Enumerate all maximal cliques of a graph.++-- A longer description of the package.+Description:         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.++-- The license under which the package is released.+License:             BSD3++-- The file containing the license text.+License-file:        LICENSE++-- The package author(s).+Author:              Gershom Bazerman++-- An email address to which users can send suggestions, bug reports,+-- and patches.+Maintainer:          gershomb@gmail.com++-- A copyright notice.+-- Copyright:++Category:            Algorithms++Build-type:          Simple++-- Extra files to be distributed with the package, such as examples or+-- a README.+-- Extra-source-files:++-- Constraint on the version of Cabal needed to build this package.+Cabal-version:       >=1.2+++Library+  -- Modules exported by the library.+  Exposed-modules: Data.Algorithm.MaximalCliques++  -- Packages needed in order to build this package.+  Build-depends:   base > 3, base < 5, containers, vector++  ghc-options:     -Wall++  -- Modules not exported by this package.+  -- Other-modules:++  -- Extra tools (e.g. alex, hsc2hs, ...) needed to build the source.+  -- Build-tools:+