{-# OPTIONS_GHC -Wno-name-shadowing #-}
module Darcs.Util.Graph
( Graph
, Vertex
, VertexSet
, Component(..)
, ltmis
, bkmis
, components
, genGraphs
, genComponents
, 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 Safe ( tailErr )
import Darcs.Prelude
type Vertex = Int
type VertexSet = [Vertex]
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
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)]
gsize :: Graph -> Int
gsize :: Graph -> Vertex
gsize Graph
v = Graph -> Vertex
forall a. Vector a -> Vertex
V.length Graph
v
type Helper = U.Vector Bool
ltmis :: (Bool,Bool) -> Component -> [VertexSet]
ltmis :: (Bool, Bool) -> Component -> [[Vertex]]
ltmis (Bool
bt1,Bool
bt2) (Component Graph
g [Vertex]
comp) =
([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)
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)
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
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
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)
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
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)
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 :: 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
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
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
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
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
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
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)
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
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
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
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. Partial => [a] -> [a]
tailErr ([[Vertex]] -> [[Vertex]])
-> ([Vertex] -> [[Vertex]]) -> [Vertex] -> [[Vertex]]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Vertex] -> [[Vertex]]
powerset
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
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])