{- |
Description: Connected components
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

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

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

-- | Write a function that splits a graph into its connected components.
connectedComponents :: G -> [[Vertex]]
connectedComponents :: G -> [[Vertex]]
connectedComponents G
g = G -> Set Vertex -> [[Vertex]] -> [[Vertex]]
getComponents G
g (G -> Set Vertex
forall g. Graph g => g -> Set Vertex
vertexes G
g) []

getComponents :: G -> Set Vertex -> [[Vertex]] -> [[Vertex]]
getComponents :: G -> Set Vertex -> [[Vertex]] -> [[Vertex]]
getComponents G
g Set Vertex
vs [[Vertex]]
cs
  | Set Vertex -> Bool
forall a. Set a -> Bool
Set.null Set Vertex
vs = [[Vertex]]
cs
  | Bool
otherwise   = G -> Set Vertex -> [[Vertex]] -> [[Vertex]]
getComponents G
g Set Vertex
vs' ([Vertex]
c[Vertex] -> [[Vertex]] -> [[Vertex]]
forall a. a -> [a] -> [a]
:[[Vertex]]
cs)
  where v :: Vertex
v = Set Vertex -> Vertex
forall a. Set a -> a
Set.findMin Set Vertex
vs  -- chosen arbitrarily
        c :: [Vertex]
c = G -> Vertex -> [Vertex]
depthFirst G
g Vertex
v
        vs' :: Set Vertex
vs' = Set Vertex -> Set Vertex -> Set Vertex
forall a. Ord a => Set a -> Set a -> Set a
Set.difference Set Vertex
vs (Set Vertex -> Set Vertex) -> Set Vertex -> Set Vertex
forall a b. (a -> b) -> a -> b
$ [Vertex] -> Set Vertex
forall a. Ord a => [a] -> Set a
Set.fromList [Vertex]
c