-- (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 :: forall (gr :: * -> * -> *) a b. DynGraph gr => gr a b -> [Node]
indep = forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (gr :: * -> * -> *) a b.
DynGraph gr =>
gr a b -> ([Node], Node)
indepSize

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