1-- (c) 2000 - 2002 by Martin Erwig [see file COPYRIGHT] 2-- | Maximum Independent Node Sets 3module Data.Graph.Inductive.Query.Indep ( 4 indep 5 , indepSize 6 ) where 7 8import Data.Graph.Inductive.Graph 9 10import Control.Arrow ((***)) 11import Data.Function (on) 12import Data.List (maximumBy) 13 14-- ----------------------------------------------------------------------------- 15 16-- | Calculate the maximum independent node set of the specified 17-- graph. 18indep :: (DynGraph gr) => gr a b -> [Node] 19indep = fst . indepSize 20 21-- | The maximum independent node set along with its size. 22indepSize :: (DynGraph gr) => gr a b -> ([Node], Int) 23indepSize g 24 | isEmpty g = ([], 0) 25 | l1 > l2 = il1 26 | otherwise = il2 27 where 28 vs = nodes g 29 v = snd . maximumBy (compare `on` fst) 30 . map ((,) =<< deg g) $ vs 31 (Just c,g') = match v g 32 il1@(_,l1) = indepSize g' 33 il2@(_,l2) = ((v:) *** (+1)) $ indepSize (delNodes (neighbors' c) g') 34