-- (c) 2000 - 2002 by Martin Erwig [see file COPYRIGHT]
-- | Maximum Independent Node Sets

module Data.Graph.Inductive.Query.Indep (
    indep
) where


import Data.Graph.Inductive.Graph


first :: (a -> Bool) -> [a] -> a
first p = head . filter p

indep :: DynGraph gr => gr a b -> [Node]
indep g | isEmpty g = []
indep g = if length i1>length i2 then i1 else i2
          where vs          = nodes g 
                m           = maximum (map (deg g) vs) 
                v           = first (\v'->deg g v'==m) vs 
                (Just c,g') = match v g 
                i1          = indep g'
                i2          = v:indep (delNodes (neighbors' c) g')