{- The idea of the ltmis algorithm is based on this paper:

Loukakis, E & Tsouros, Constantin. (1981). A depth first search algorithm to
generate the family of maximal independent sets of a graph
lexicographically. Computing. 27. 349-366. 10.1007/BF02277184.

This is basically the same as Bron-Kerbosch but with two special
optimizations, one to avoid needless backtracking and one to avoid needless
branching. For large graphs the gains in efficiency are significant. On my
computer generating all MIS for the first 100000 graphs of size 12 takes
0.757 seconds with ltmis (True,True) and over 10 seconds with bkmis.

-}

{-# OPTIONS_GHC -Wno-name-shadowing #-}
module Darcs.Util.Graph
  ( Graph
  , Vertex
  , VertexSet
  , Component(..)
  -- * Algorithms
  , ltmis
  , bkmis
  , components
  -- * Generating graphs
  , genGraphs
  , genComponents
  -- * Properties
  , prop_ltmis_eq_bkmis
  , prop_ltmis_maximal_independent_sets
  , prop_ltmis_all_maximal_independent_sets
  , prop_components
  ) where

import Control.Monad ( filterM )
import Control.Monad.ST ( runST, ST )

import Data.List ( sort )
import qualified Data.Set as S

import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as MU

import Darcs.Prelude

-- | Vertices are represented as 'Int'.
type Vertex = Int

-- | Set of vertices, represented as a list for efficiency (yes, indeed).
type VertexSet = [Vertex]

-- | Undirected graph represented as a 'V.Vector' of adjacency 'VertexSet's.
type Graph = V.Vector VertexSet

data Component = Component Graph VertexSet deriving Vertex -> Component -> ShowS
[Component] -> ShowS
Component -> String
(Vertex -> Component -> ShowS)
-> (Component -> String)
-> ([Component] -> ShowS)
-> Show Component
forall a.
(Vertex -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Vertex -> Component -> ShowS
showsPrec :: Vertex -> Component -> ShowS
$cshow :: Component -> String
show :: Component -> String
$cshowList :: [Component] -> ShowS
showList :: [Component] -> ShowS
Show

-- | The neighbors of a 'Vertex' in a 'Graph'.
neighbours :: Graph -> Vertex -> VertexSet
neighbours :: Graph -> Vertex -> [Vertex]
neighbours Graph
g Vertex
v = Graph
g Graph -> Vertex -> [Vertex]
forall a. Vector a -> Vertex -> a
V.! Vertex
v

has_edge :: Graph -> Vertex -> Vertex -> Bool
has_edge :: Graph -> Vertex -> Vertex -> Bool
has_edge Graph
g Vertex
u Vertex
v = Vertex
u Vertex -> [Vertex] -> Bool
forall a. Eq a => a -> [a] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` Graph -> Vertex -> [Vertex]
neighbours Graph
g Vertex
v

has_any_edge :: Graph -> VertexSet -> Vertex -> Bool
has_any_edge :: Graph -> [Vertex] -> Vertex -> Bool
has_any_edge Graph
g [Vertex]
vs Vertex
u = (Vertex -> Bool) -> [Vertex] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Graph -> Vertex -> Vertex -> Bool
has_edge Graph
g Vertex
u) [Vertex]
vs

all_vertices :: Graph -> VertexSet
all_vertices :: Graph -> [Vertex]
all_vertices Graph
g = [Vertex
0..(Graph -> Vertex
gsize Graph
g Vertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
- Vertex
1)]

-- | The number of vertices in a 'Graph'.
gsize :: Graph -> Int
gsize :: Graph -> Vertex
gsize Graph
v = Graph -> Vertex
forall a. Vector a -> Vertex
V.length Graph
v

-- * Maximal independent sets

-- | Simple helper type used in the 'ltmis' and 'components' algorithms.
type Helper = U.Vector Bool

-- | Determine the maximal independent sets in a 'Component' of a 'Graph'.
ltmis :: (Bool,Bool) -> Component -> [VertexSet]
ltmis :: (Bool, Bool) -> Component -> [[Vertex]]
ltmis (Bool
bt1,Bool
bt2) (Component Graph
g [Vertex]
comp) =
    -- the map reverse is because we use (:) to add vertices to r
    -- when branching
    ([Vertex] -> [Vertex]) -> [[Vertex]] -> [[Vertex]]
forall a b. (a -> b) -> [a] -> [b]
map [Vertex] -> [Vertex]
forall a. [a] -> [a]
reverse ([[Vertex]] -> [[Vertex]]) -> [[Vertex]] -> [[Vertex]]
forall a b. (a -> b) -> a -> b
$ [Vertex] -> Vertex -> Helper -> [[Vertex]]
go [] Vertex
0 Helper
init_h
  where
    size :: Vertex
size = Graph -> Vertex
gsize Graph
g
    init_h :: Helper
init_h = Vertex -> Bool -> Helper
forall a. Unbox a => Vertex -> a -> Vector a
U.replicate (Graph -> Vertex
gsize Graph
g) Bool
True Helper -> [(Vertex, Bool)] -> Helper
forall a. Unbox a => Vector a -> [(Vertex, a)] -> Vector a
U.// [Vertex] -> [Bool] -> [(Vertex, Bool)]
forall a b. [a] -> [b] -> [(a, b)]
zip [Vertex]
comp (Bool -> [Bool]
forall a. a -> [a]
repeat Bool
False)
    -- h[v] = neighbours g v `intersectsWith` r || v `elem` r || v `notElem` comp
    go :: VertexSet -> Vertex -> Helper -> [VertexSet]
    go :: [Vertex] -> Vertex -> Helper -> [[Vertex]]
go [Vertex]
r !Vertex
sep Helper
h =
      case Vertex -> Helper -> [Vertex]
candidates Vertex
sep Helper
h of
        [] -> [[Vertex]
r]
        Vertex
br:[Vertex]
_ ->
          (if Bool
bt1 Bool -> Bool -> Bool
&& Vertex -> Helper -> Bool
done_branching Vertex
sep' Helper
h' then [] else [Vertex] -> Vertex -> Helper -> [[Vertex]]
go (Vertex
brVertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
:[Vertex]
r) Vertex
sep' Helper
h')
          [[Vertex]] -> [[Vertex]] -> [[Vertex]]
forall a. [a] -> [a] -> [a]
++
          (if Bool
bt2 Bool -> Bool -> Bool
&& Vertex -> Helper -> Vertex -> Bool
done_backtracking Vertex
sep' Helper
h Vertex
br then [] else [Vertex] -> Vertex -> Helper -> [[Vertex]]
go [Vertex]
r Vertex
sep' Helper
h)
          where
            h' :: Helper
h' = Helper
h Helper -> [(Vertex, Bool)] -> Helper
forall a. Unbox a => Vector a -> [(Vertex, a)] -> Vector a
U.// [Vertex] -> [Bool] -> [(Vertex, Bool)]
forall a b. [a] -> [b] -> [(a, b)]
zip (Vertex
br Vertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
: Graph -> Vertex -> [Vertex]
neighbours Graph
g Vertex
br) (Bool -> [Bool]
forall a. a -> [a]
repeat Bool
True)
            sep' :: Vertex
sep' = Vertex
br Vertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
+ Vertex
1

    candidates :: Vertex -> Helper -> VertexSet
    candidates :: Vertex -> Helper -> [Vertex]
candidates Vertex
sep Helper
h = (Vertex -> Bool) -> [Vertex] -> [Vertex]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Vertex -> Bool) -> Vertex -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Helper
h Helper -> Vertex -> Bool
forall a. Unbox a => Vector a -> Vertex -> a
U.!)) ([Vertex] -> [Vertex]) -> [Vertex] -> [Vertex]
forall a b. (a -> b) -> a -> b
$ [Vertex
sep..(Vertex
sizeVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
-Vertex
1)]

    excludes :: Vertex -> Helper -> [Vertex]
    excludes :: Vertex -> Helper -> [Vertex]
excludes Vertex
sep Helper
h = (Vertex -> Bool) -> [Vertex] -> [Vertex]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Vertex -> Bool) -> Vertex -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Helper
h Helper -> Vertex -> Bool
forall a. Unbox a => Vector a -> Vertex -> a
U.!)) [Vertex
0 .. (Vertex
sepVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
-Vertex
1)]

    is_candidate :: Vertex -> Helper -> Vertex -> Bool
    is_candidate :: Vertex -> Helper -> Vertex -> Bool
is_candidate Vertex
sep Helper
h Vertex
v = Vertex
v Vertex -> Vertex -> Bool
forall a. Ord a => a -> a -> Bool
>= Vertex
sep Bool -> Bool -> Bool
&& Bool -> Bool
not ((Helper
h Helper -> Vertex -> Bool
forall a. Unbox a => Vector a -> Vertex -> a
U.!) Vertex
v)

    intersects_candidates :: Vertex -> Helper -> VertexSet -> Bool
    intersects_candidates :: Vertex -> Helper -> [Vertex] -> Bool
intersects_candidates Vertex
sep Helper
h = (Vertex -> Bool) -> [Vertex] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Vertex -> Helper -> Vertex -> Bool
is_candidate Vertex
sep Helper
h)

    -- for some x in X, N(x) does not intersect C
    -- means whatever candidate we add we won't get an MIS
    -- so can stop branching
    done_branching :: Vertex -> Helper -> Bool
    done_branching :: Vertex -> Helper -> Bool
done_branching Vertex
sep Helper
h =
      ([Vertex] -> Bool) -> [[Vertex]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Bool -> Bool
not (Bool -> Bool) -> ([Vertex] -> Bool) -> [Vertex] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vertex -> Helper -> [Vertex] -> Bool
intersects_candidates Vertex
sep Helper
h) ([[Vertex]] -> Bool) -> [[Vertex]] -> Bool
forall a b. (a -> b) -> a -> b
$ (Vertex -> [Vertex]) -> [Vertex] -> [[Vertex]]
forall a b. (a -> b) -> [a] -> [b]
map (Graph -> Vertex -> [Vertex]
neighbours Graph
g) ([Vertex] -> [[Vertex]]) -> [Vertex] -> [[Vertex]]
forall a b. (a -> b) -> a -> b
$ Vertex -> Helper -> [Vertex]
excludes Vertex
sep Helper
h

    -- if done_backtracking (neighbours g v), then v must
    -- be a member of any MIS containing R
    done_backtracking :: Vertex -> Helper -> Vertex -> Bool
    done_backtracking :: Vertex -> Helper -> Vertex -> Bool
done_backtracking Vertex
sep Helper
h Vertex
v = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ Vertex -> Helper -> [Vertex] -> Bool
intersects_candidates Vertex
sep Helper
h ([Vertex] -> Bool) -> [Vertex] -> Bool
forall a b. (a -> b) -> a -> b
$ Graph -> Vertex -> [Vertex]
neighbours Graph
g Vertex
v

-- | The classic Bron-Kerbosch algorithm for determining the maximal
-- independent sets in a 'Graph'.
bkmis :: Graph -> [VertexSet]
bkmis :: Graph -> [[Vertex]]
bkmis Graph
g = [[Vertex]] -> [[Vertex]]
forall a. [a] -> [a]
reverse ([[Vertex]] -> [[Vertex]]) -> [[Vertex]] -> [[Vertex]]
forall a b. (a -> b) -> a -> b
$ ([Vertex] -> [Vertex]) -> [[Vertex]] -> [[Vertex]]
forall a b. (a -> b) -> [a] -> [b]
map [Vertex] -> [Vertex]
forall a. [a] -> [a]
reverse ([[Vertex]] -> [[Vertex]]) -> [[Vertex]] -> [[Vertex]]
forall a b. (a -> b) -> a -> b
$ [Vertex] -> [Vertex] -> [Vertex] -> [[Vertex]]
go [] [] (Graph -> [Vertex]
all_vertices Graph
g) where
  go :: [Vertex] -> [Vertex] -> [Vertex] -> [[Vertex]]
go [Vertex]
r [] [] = [[Vertex]
r]
  go [Vertex]
r [Vertex]
xs [Vertex]
cs = [Vertex] -> [Vertex] -> [[Vertex]]
loop [Vertex]
xs [Vertex]
cs where
    loop :: [Vertex] -> [Vertex] -> [[Vertex]]
loop [Vertex]
_ [] = []
    loop [Vertex]
xs (Vertex
c:[Vertex]
cs) = [Vertex] -> [Vertex] -> [[Vertex]]
loop (Vertex
cVertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
:[Vertex]
xs) [Vertex]
cs [[Vertex]] -> [[Vertex]] -> [[Vertex]]
forall a. [a] -> [a] -> [a]
++ [Vertex] -> [Vertex] -> [Vertex] -> [[Vertex]]
go (Vertex
cVertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
:[Vertex]
r) (Vertex -> [Vertex] -> [Vertex]
res Vertex
c [Vertex]
xs) (Vertex -> [Vertex] -> [Vertex]
res Vertex
c [Vertex]
cs)
    res :: Vertex -> [Vertex] -> [Vertex]
res Vertex
v = (Vertex -> Bool) -> [Vertex] -> [Vertex]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Vertex -> Bool) -> Vertex -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph -> Vertex -> Vertex -> Bool
has_edge Graph
g Vertex
v)

-- * Generating graphs

genGraph :: Monad m => (Int -> Int -> m VertexSet) -> Int -> m Graph
genGraph :: forall (m :: * -> *).
Monad m =>
(Vertex -> Vertex -> m [Vertex]) -> Vertex -> m Graph
genGraph Vertex -> Vertex -> m [Vertex]
genSubset = Vertex -> Vertex -> m Graph
go Vertex
0 where
  go :: Vertex -> Vertex -> m Graph
go Vertex
_ Vertex
0 = Graph -> m Graph
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Graph
forall a. Vector a
V.empty
  go Vertex
s Vertex
n = do -- list monad
    Graph
g <- Vertex -> Vertex -> m Graph
go (Vertex
sVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
+Vertex
1) (Vertex
nVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
-Vertex
1)
    [Vertex]
vs <- Vertex -> Vertex -> m [Vertex]
genSubset (Vertex
sVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
+Vertex
1) (Vertex
nVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
-Vertex
1)
    Graph -> m Graph
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Graph -> m Graph) -> Graph -> m Graph
forall a b. (a -> b) -> a -> b
$ (forall s. MVector s [Vertex] -> ST s ()) -> Graph -> Graph
forall a.
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
V.modify (\MVector s [Vertex]
h -> (Vertex -> ST s ()) -> [Vertex] -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (MVector (PrimState (ST s)) [Vertex] -> Vertex -> ST s ()
forall {m :: * -> *}.
PrimMonad m =>
MVector (PrimState m) [Vertex] -> Vertex -> m ()
adjust MVector s [Vertex]
MVector (PrimState (ST s)) [Vertex]
h) [Vertex]
vs) ([Vertex] -> Graph -> Graph
forall a. a -> Vector a -> Vector a
V.cons [Vertex]
vs Graph
g)
    where
      adjust :: MVector (PrimState m) [Vertex] -> Vertex -> m ()
adjust MVector (PrimState m) [Vertex]
g Vertex
i = do
        [Vertex]
vs <- MVector (PrimState m) [Vertex] -> Vertex -> m [Vertex]
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Vertex -> m a
MV.read MVector (PrimState m) [Vertex]
g (Vertex
iVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
-Vertex
s)
        MVector (PrimState m) [Vertex] -> Vertex -> [Vertex] -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Vertex -> a -> m ()
MV.write MVector (PrimState m) [Vertex]
g (Vertex
iVertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
-Vertex
s) (Vertex
sVertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
:[Vertex]
vs)

-- | Enumerate all (simple) graphs of a given size (number of vertices).
genGraphs :: Int -> [Graph]
genGraphs :: Vertex -> [Graph]
genGraphs = (Vertex -> Vertex -> [[Vertex]]) -> Vertex -> [Graph]
forall (m :: * -> *).
Monad m =>
(Vertex -> Vertex -> m [Vertex]) -> Vertex -> m Graph
genGraph Vertex -> Vertex -> [[Vertex]]
forall {t} {a}. (Eq t, Num t, Num a) => a -> t -> [[a]]
subsets where
  -- Subsets of the n elements [s..(s+n-1)] (each subset is ordered)
  subsets :: a -> t -> [[a]]
subsets a
_ t
0 = [a] -> [[a]]
forall a. a -> [a]
forall (m :: * -> *) a. Monad m => a -> m a
return []
  subsets a
s t
n = do
    [a]
vs <- a -> t -> [[a]]
subsets (a
sa -> a -> a
forall a. Num a => a -> a -> a
+a
1) (t
nt -> t -> t
forall a. Num a => a -> a -> a
-t
1)
    [[a]
vs,a
sa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
vs]

genComponents :: Int -> [Component]
genComponents :: Vertex -> [Component]
genComponents Vertex
n = do
  Graph
g <- Vertex -> [Graph]
genGraphs Vertex
n
  Graph -> [Component]
components Graph
g

-- * Connected components

-- | Split a 'Graph' into connected components. For efficiency we don't
-- represent the result as a list of Graphs, but rather of 'VertexSet's.
components :: Graph -> [Component]
components :: Graph -> [Component]
components Graph
g = [Component] -> [Component]
forall a. [a] -> [a]
reverse ([Component] -> [Component]) -> [Component] -> [Component]
forall a b. (a -> b) -> a -> b
$ ([Vertex] -> Component) -> [[Vertex]] -> [Component]
forall a b. (a -> b) -> [a] -> [b]
map (Graph -> [Vertex] -> Component
Component Graph
g) ([[Vertex]] -> [Component]) -> [[Vertex]] -> [Component]
forall a b. (a -> b) -> a -> b
$ (forall s. ST s [[Vertex]]) -> [[Vertex]]
forall a. (forall s. ST s a) -> a
runST ST s [[Vertex]]
forall s. ST s [[Vertex]]
go where
  size :: Vertex
size = Graph -> Vertex
gsize Graph
g
  go :: ST s [VertexSet]
  go :: forall s. ST s [[Vertex]]
go = do
    MVector s Bool
mh <- Vertex -> Bool -> ST s (MVector (PrimState (ST s)) Bool)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Vertex -> a -> m (MVector (PrimState m) a)
MU.replicate Vertex
size Bool
False
    Vertex
-> MVector (PrimState (ST s)) Bool -> [[Vertex]] -> ST s [[Vertex]]
forall {m :: * -> *}.
PrimMonad m =>
Vertex -> MVector (PrimState m) Bool -> [[Vertex]] -> m [[Vertex]]
loop Vertex
0 MVector s Bool
MVector (PrimState (ST s)) Bool
mh []
  loop :: Vertex -> MVector (PrimState m) Bool -> [[Vertex]] -> m [[Vertex]]
loop Vertex
v MVector (PrimState m) Bool
mh [[Vertex]]
r
    | Vertex
v Vertex -> Vertex -> Bool
forall a. Eq a => a -> a -> Bool
== Vertex
size = [[Vertex]] -> m [[Vertex]]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return [[Vertex]]
r
    | Bool
otherwise = do
      [Vertex]
c <- Vertex -> m [Vertex]
new_component Vertex
v
      if [Vertex] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Vertex]
c
        then Vertex -> MVector (PrimState m) Bool -> [[Vertex]] -> m [[Vertex]]
loop (Vertex
v Vertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
+ Vertex
1) MVector (PrimState m) Bool
mh [[Vertex]]
r
        else Vertex -> MVector (PrimState m) Bool -> [[Vertex]] -> m [[Vertex]]
loop (Vertex
v Vertex -> Vertex -> Vertex
forall a. Num a => a -> a -> a
+ Vertex
1) MVector (PrimState m) Bool
mh ([Vertex]
c [Vertex] -> [[Vertex]] -> [[Vertex]]
forall a. a -> [a] -> [a]
: [[Vertex]]
r)
    where
      new_component :: Vertex -> m [Vertex]
new_component Vertex
v = do
        Bool
visited <- MVector (PrimState m) Bool -> Vertex -> m Bool
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Vertex -> m a
MU.read MVector (PrimState m) Bool
mh Vertex
v
        if Bool
visited
          then [Vertex] -> m [Vertex]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return []
          else do
            -- mark v as visited
            MVector (PrimState m) Bool -> Vertex -> Bool -> m ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Vertex -> a -> m ()
MU.write MVector (PrimState m) Bool
mh Vertex
v Bool
True
            [[Vertex]]
cs <- (Vertex -> m [Vertex]) -> [Vertex] -> m [[Vertex]]
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> [a] -> m [b]
mapM Vertex -> m [Vertex]
new_component (Graph -> Vertex -> [Vertex]
neighbours Graph
g Vertex
v)
            [Vertex] -> m [Vertex]
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ([Vertex] -> m [Vertex]) -> [Vertex] -> m [Vertex]
forall a b. (a -> b) -> a -> b
$ Vertex
v Vertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
: [[Vertex]] -> [Vertex]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[Vertex]]
cs

-- * Properties

-- | Whether a 'VertexSet' is independent i.e. no edge exists between any
-- two of its vertices.
prop_is_independent_set :: Graph -> VertexSet -> Bool
prop_is_independent_set :: Graph -> [Vertex] -> Bool
prop_is_independent_set Graph
g [Vertex]
vs = (Vertex -> Bool) -> [Vertex] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Bool -> Bool
not (Bool -> Bool) -> (Vertex -> Bool) -> Vertex -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph -> [Vertex] -> Vertex -> Bool
has_any_edge Graph
g [Vertex]
vs) [Vertex]
vs

-- | Whether a 'VertexSet' is maximally independent i.e. it is independent
-- and no longer independent if we add any other vertex.
prop_is_maximal_independent_set :: Component -> VertexSet -> Bool
prop_is_maximal_independent_set :: Component -> [Vertex] -> Bool
prop_is_maximal_independent_set (Component Graph
g [Vertex]
c) [Vertex]
vs =
    Graph -> [Vertex] -> Bool
prop_is_independent_set Graph
g [Vertex]
vs Bool -> Bool -> Bool
&&
    (Vertex -> Bool) -> [Vertex] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Graph -> [Vertex] -> Vertex -> Bool
has_any_edge Graph
g [Vertex]
vs) [Vertex]
other_vertices
  where
    other_vertices :: [Vertex]
other_vertices = (Vertex -> Bool) -> [Vertex] -> [Vertex]
forall a. (a -> Bool) -> [a] -> [a]
filter (Vertex -> [Vertex] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [Vertex]
vs) [Vertex]
c

-- | Whether 'ltmis' is equivalent to 'bkmis'.
prop_ltmis_eq_bkmis :: Graph -> Bool
prop_ltmis_eq_bkmis :: Graph -> Bool
prop_ltmis_eq_bkmis Graph
g =
  (Bool, Bool) -> Component -> [[Vertex]]
ltmis (Bool
True, Bool
True) (Graph -> [Vertex] -> Component
Component Graph
g (Graph -> [Vertex]
all_vertices Graph
g)) [[Vertex]] -> [[Vertex]] -> Bool
forall a. Eq a => a -> a -> Bool
== Graph -> [[Vertex]]
bkmis Graph
g

-- | Whether 'ltmis' generates only maximal independent sets.
prop_ltmis_maximal_independent_sets :: Component -> Bool
prop_ltmis_maximal_independent_sets :: Component -> Bool
prop_ltmis_maximal_independent_sets Component
sg =
  ([Vertex] -> Bool) -> [[Vertex]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Component -> [Vertex] -> Bool
prop_is_maximal_independent_set Component
sg) ((Bool, Bool) -> Component -> [[Vertex]]
ltmis (Bool
True, Bool
True) Component
sg)

-- | Whether 'ltmis' generates /all/ maximal independent sets.
prop_ltmis_all_maximal_independent_sets :: Component -> Bool
prop_ltmis_all_maximal_independent_sets :: Component -> Bool
prop_ltmis_all_maximal_independent_sets sg :: Component
sg@(Component Graph
_ [Vertex]
c) =
    ([Vertex] -> Bool) -> [[Vertex]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Bool -> Bool
not (Bool -> Bool) -> ([Vertex] -> Bool) -> [Vertex] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Component -> [Vertex] -> Bool
prop_is_maximal_independent_set Component
sg) [[Vertex]]
other_subsets
  where
    mis :: [[Vertex]]
mis = (Bool, Bool) -> Component -> [[Vertex]]
ltmis (Bool
True, Bool
True) Component
sg
    all_subsets :: [[Vertex]]
all_subsets = [Vertex] -> [[Vertex]]
powerset [Vertex]
c
    other_subsets :: [[Vertex]]
other_subsets = ([Vertex] -> Bool) -> [[Vertex]] -> [[Vertex]]
forall a. (a -> Bool) -> [a] -> [a]
filter ([Vertex] -> [[Vertex]] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`notElem` [[Vertex]]
mis) [[Vertex]]
all_subsets

-- | Whether a list of 'VertexSet's of a 'Graph' is a partition of
-- the set of all its vertices.
prop_is_partition :: Graph -> [VertexSet] -> Bool
prop_is_partition :: Graph -> [[Vertex]] -> Bool
prop_is_partition Graph
g [[Vertex]]
cs = [Vertex] -> [Vertex]
forall a. Ord a => [a] -> [a]
sort ([[Vertex]] -> [Vertex]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[Vertex]]
cs) [Vertex] -> [Vertex] -> Bool
forall a. Eq a => a -> a -> Bool
== Graph -> [Vertex]
all_vertices Graph
g

-- | Whether there is no edge between a 'VertexSet' of a 'Graph' and the rest
-- of the 'Graph'.
prop_self_contained :: Graph -> VertexSet -> Bool
prop_self_contained :: Graph -> [Vertex] -> Bool
prop_self_contained Graph
g [Vertex]
c =
  [Set Vertex] -> Set Vertex
forall (f :: * -> *) a. (Foldable f, Ord a) => f (Set a) -> Set a
S.unions ((Vertex -> Set Vertex) -> [Vertex] -> [Set Vertex]
forall a b. (a -> b) -> [a] -> [b]
map ([Vertex] -> Set Vertex
forall a. Ord a => [a] -> Set a
S.fromList ([Vertex] -> Set Vertex)
-> (Vertex -> [Vertex]) -> Vertex -> Set Vertex
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Graph -> Vertex -> [Vertex]
neighbours Graph
g) [Vertex]
c) Set Vertex -> Set Vertex -> Bool
forall a. Ord a => Set a -> Set a -> Bool
`S.isSubsetOf` [Vertex] -> Set Vertex
forall a. Ord a => [a] -> Set a
S.fromList [Vertex]
c

-- | Whether a 'VertexSet' of a 'Graph' is connected.
prop_connected :: Graph -> VertexSet -> Bool
prop_connected :: Graph -> [Vertex] -> Bool
prop_connected Graph
g = Bool -> Bool
not (Bool -> Bool) -> ([Vertex] -> Bool) -> [Vertex] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([Vertex] -> Bool) -> [[Vertex]] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Graph -> [Vertex] -> Bool
prop_self_contained Graph
g) ([[Vertex]] -> Bool)
-> ([Vertex] -> [[Vertex]]) -> [Vertex] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Vertex] -> [[Vertex]]
proper_non_empty_subsets
  where
    proper_non_empty_subsets :: [Vertex] -> [[Vertex]]
proper_non_empty_subsets = ([Vertex] -> Bool) -> [[Vertex]] -> [[Vertex]]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> ([Vertex] -> Bool) -> [Vertex] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Vertex] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null) ([[Vertex]] -> [[Vertex]])
-> ([Vertex] -> [[Vertex]]) -> [Vertex] -> [[Vertex]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [[Vertex]] -> [[Vertex]]
forall a. HasCallStack => [a] -> [a]
tail ([[Vertex]] -> [[Vertex]])
-> ([Vertex] -> [[Vertex]]) -> [Vertex] -> [[Vertex]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Vertex] -> [[Vertex]]
powerset

-- | Whether a 'VertexSet' is a connected component of the 'Graph'.
prop_connected_component :: Component -> Bool
prop_connected_component :: Component -> Bool
prop_connected_component (Component Graph
g [Vertex]
vs) =
  Graph -> [Vertex] -> Bool
prop_self_contained Graph
g [Vertex]
vs Bool -> Bool -> Bool
&& Graph -> [Vertex] -> Bool
prop_connected Graph
g [Vertex]
vs

-- | Complete specification of the 'components' function.
prop_components :: Graph -> Bool
prop_components :: Graph -> Bool
prop_components Graph
g =
    (Component -> Bool) -> [Component] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Component -> Bool
prop_connected_component [Component]
cs Bool -> Bool -> Bool
&&
      Graph -> [[Vertex]] -> Bool
prop_is_partition Graph
g ((Component -> [Vertex]) -> [Component] -> [[Vertex]]
forall a b. (a -> b) -> [a] -> [b]
map Component -> [Vertex]
vertices [Component]
cs) Bool -> Bool -> Bool
&& (Graph -> Bool) -> [Graph] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Graph -> Graph -> Bool
forall a. Eq a => a -> a -> Bool
== Graph
g) ((Component -> Graph) -> [Component] -> [Graph]
forall a b. (a -> b) -> [a] -> [b]
map Component -> Graph
graph [Component]
cs)
  where
    vertices :: Component -> [Vertex]
vertices (Component Graph
_ [Vertex]
vs) = [Vertex]
vs
    graph :: Component -> Graph
graph (Component Graph
g [Vertex]
_) = Graph
g
    cs :: [Component]
cs = Graph -> [Component]
components Graph
g

powerset :: VertexSet -> [VertexSet]
powerset :: [Vertex] -> [[Vertex]]
powerset = ([Vertex] -> [Vertex]) -> [[Vertex]] -> [[Vertex]]
forall a b. (a -> b) -> [a] -> [b]
map [Vertex] -> [Vertex]
forall a. Ord a => [a] -> [a]
sort ([[Vertex]] -> [[Vertex]])
-> ([Vertex] -> [[Vertex]]) -> [Vertex] -> [[Vertex]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Vertex -> [Bool]) -> [Vertex] -> [[Vertex]]
forall (m :: * -> *) a.
Applicative m =>
(a -> m Bool) -> [a] -> m [a]
filterM ([Bool] -> Vertex -> [Bool]
forall a b. a -> b -> a
const [Bool
True, Bool
False])