-- (c) 2000 - 2002 by Martin Erwig [see file COPYRIGHT]
-- | Maximum Independent Node Sets
module Data.Graph.Inductive.Query.Indep (
    indep
  , indepSize
  ) where

import Data.Graph.Inductive.Graph

import Control.Arrow ((***))
import Data.Function (on)
import Data.List     (maximumBy)

-- -----------------------------------------------------------------------------

-- | Calculate the maximum independent node set of the specified
--   graph.
indep :: (DynGraph gr) => gr a b -> [Node]
indep = fst . indepSize

-- | The maximum independent node set along with its size.
indepSize :: (DynGraph gr) => gr a b -> ([Node], Int)
indepSize g
  | isEmpty g = ([], 0)
  | l1 > l2   = il1
  | otherwise = il2
  where
    vs          = nodes g
    v           = snd . maximumBy (compare `on` fst)
                  . map ((,) =<< deg g) $ vs
    (Just c,g') = match v g
    il1@(_,l1)  = indepSize g'
    il2@(_,l2)  = ((v:) *** (+1)) $ indepSize (delNodes (neighbors' c) g')