{- |
Description: Bipartite graphs
Copyright: Copyright (C) 2023 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P89" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P89 (bipartite) where

import           Data.Set        (Set)
import qualified Data.Set        as Set
import           Problems.Graphs

-- | Write a function that finds out whether a given graph is bipartite.
bipartite :: G -> Bool
bipartite :: G -> Bool
bipartite G
g = G -> (Set Vertex, Set Vertex, Set Vertex, Set Vertex) -> Bool
partition G
g (G -> Set Vertex
forall g. Graph g => g -> Set Vertex
vertexes G
g, Set Vertex
forall a. Set a
Set.empty, Set Vertex
forall a. Set a
Set.empty, Set Vertex
forall a. Set a
Set.empty)

partition :: G -> (Set Vertex, Set Vertex, Set Vertex, Set Vertex) -> Bool
partition :: G -> (Set Vertex, Set Vertex, Set Vertex, Set Vertex) -> Bool
partition G
g (Set Vertex
remaining, Set Vertex
boundary, Set Vertex
us, Set Vertex
vs)
  -- Went through all vertexes without encountering a contradiction with bipartiteness.
  | Set Vertex -> Bool
forall a. Set a -> Bool
Set.null Set Vertex
boundary Bool -> Bool -> Bool
&& Set Vertex -> Bool
forall a. Set a -> Bool
Set.null Set Vertex
remaining = Bool
True
  -- Start again with disconnected component.
  | Set Vertex -> Bool
forall a. Set a -> Bool
Set.null Set Vertex
boundary = let (Vertex
v', Set Vertex
r') = Set Vertex -> (Vertex, Set Vertex)
forall a. Set a -> (a, Set a)
Set.deleteFindMin Set Vertex
remaining
                        in G -> (Set Vertex, Set Vertex, Set Vertex, Set Vertex) -> Bool
partition G
g (Set Vertex
r', Vertex -> Set Vertex
forall a. a -> Set a
Set.singleton Vertex
v', Set Vertex
us, Set Vertex
vs)
  -- If bipartite, then boundary' must necessarily end up the same set which will include vs.
  -- If any vertex in boundary' is also in us,
  -- then the set including us cannot be disjoint with that for vs.
  | Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ Set Vertex -> Set Vertex -> Bool
forall a. Ord a => Set a -> Set a -> Bool
Set.disjoint Set Vertex
boundary' Set Vertex
us = Bool
False
  | Bool
otherwise = G -> (Set Vertex, Set Vertex, Set Vertex, Set Vertex) -> Bool
partition G
g (Set Vertex
remaining', Set Vertex
boundary', Set Vertex
us', Set Vertex
vs')
  where
    -- The neighbors of vertexes that are slated to be added to us.
    -- These neighbors will be added to the set which includes vs;
    -- don't revisit those already visited.
    boundary' :: Set Vertex
boundary' = Set Vertex -> Set Vertex -> Set Vertex
forall a. Ord a => Set a -> Set a -> Set a
Set.difference (Set (Set Vertex) -> Set Vertex
forall (f :: * -> *) a. (Foldable f, Ord a) => f (Set a) -> Set a
Set.unions (Set (Set Vertex) -> Set Vertex) -> Set (Set Vertex) -> Set Vertex
forall a b. (a -> b) -> a -> b
$ (Vertex -> Set Vertex) -> Set Vertex -> Set (Set Vertex)
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map (Vertex -> G -> Set Vertex
forall g. Graph g => Vertex -> g -> Set Vertex
`neighbors` G
g) Set Vertex
boundary) Set Vertex
vs
    -- The remaining vertexes that are neither in us' or vs' yet.
    remaining' :: Set Vertex
remaining' = Set Vertex -> Set Vertex -> Set Vertex
forall a. Ord a => Set a -> Set a -> Set a
Set.difference Set Vertex
remaining Set Vertex
boundary
    -- Switch roles between us and vs.
    us' :: Set Vertex
us' = Set Vertex
vs
    -- Add the boundary vertexes to the set including us; switch roles between us and vs.
    vs' :: Set Vertex
vs' = Set Vertex -> Set Vertex -> Set Vertex
forall a. Ord a => Set a -> Set a -> Set a
Set.union Set Vertex
us Set Vertex
boundary