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