    -- (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 = ([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 :: forall (gr :: * -> * -> *) a b.
    DynGraph gr =>
    gr a b -> ([Node], Node)
    indepSize gr a b
    g
      | gr a b -> Bool
    forall a b. 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 -> (MContext a b, gr a b)
    forall a b. Node -> gr a b -> Decomp 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 b c b' c'. (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
    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')