-- (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 :: gr a b -> [Node]
indep = ([Node], Node) -> [Node]
forall a b. (a, b) -> a
fst (([Node], Node) -> [Node])
-> (gr a b -> ([Node], Node)) -> gr a b -> [Node]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. gr a b -> ([Node], Node)
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 :: gr a b -> ([Node], Node)
indepSize gr a b
g
  | gr a b -> Bool
forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> Bool
isEmpty gr a b
g = ([], Node
0)
  | Node
l1 Node -> Node -> Bool
forall a. Ord a => a -> a -> Bool
> Node
l2   = ([Node], Node)
il1
  | Bool
otherwise = ([Node], Node)
il2
  where
    vs :: [Node]
vs          = gr a b -> [Node]
forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> [Node]
nodes gr a b
g
    v :: Node
v           = (Node, Node) -> Node
forall a b. (a, b) -> b
snd ((Node, Node) -> Node)
-> ([Node] -> (Node, Node)) -> [Node] -> Node
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Node, Node) -> (Node, Node) -> Ordering)
-> [(Node, Node)] -> (Node, Node)
forall (t :: * -> *) a.
Foldable t =>
(a -> a -> Ordering) -> t a -> a
maximumBy (Node -> Node -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Node -> Node -> Ordering)
-> ((Node, Node) -> Node)
-> (Node, Node)
-> (Node, Node)
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (Node, Node) -> Node
forall a b. (a, b) -> a
fst)
                  ([(Node, Node)] -> (Node, Node))
-> ([Node] -> [(Node, Node)]) -> [Node] -> (Node, Node)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Node -> (Node, Node)) -> [Node] -> [(Node, Node)]
forall a b. (a -> b) -> [a] -> [b]
map ((,) (Node -> Node -> (Node, Node))
-> (Node -> Node) -> Node -> (Node, Node)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< gr a b -> Node -> Node
forall (gr :: * -> * -> *) a b. Graph gr => gr a b -> Node -> Node
deg gr a b
g) ([Node] -> Node) -> [Node] -> Node
forall a b. (a -> b) -> a -> b
$ [Node]
vs
    (Just Context a b
c,gr a b
g') = Node -> gr a b -> (Maybe (Context a b), gr a b)
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)  = gr a b -> ([Node], Node)
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
gr a b -> ([Node], Node)
indepSize gr a b
g'
    il2 :: ([Node], Node)
il2@([Node]
_,Node
l2)  = ((Node
vNode -> [Node] -> [Node]
forall a. a -> [a] -> [a]
:) ([Node] -> [Node])
-> (Node -> Node) -> ([Node], Node) -> ([Node], Node)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** (Node -> Node -> Node
forall a. Num a => a -> a -> a
+Node
1)) (([Node], Node) -> ([Node], Node))
-> ([Node], Node) -> ([Node], Node)
forall a b. (a -> b) -> a -> b
$ gr a b -> ([Node], Node)
forall (gr :: * -> * -> *) a b.
DynGraph gr =>
gr a b -> ([Node], Node)
indepSize ([Node] -> gr a b -> gr a b
forall (gr :: * -> * -> *) a b.
Graph gr =>
[Node] -> gr a b -> gr a b
delNodes (Context a b -> [Node]
forall a b. Context a b -> [Node]
neighbors' Context a b
c) gr a b
g')