{- |
Description: Depth-first graph traversal
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

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

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

-- | Write a function that generates a depth-first order graph traversal sequence.
-- The starting point should be specified,
-- and the output should be a list of nodes that are reachable from this starting point in depth-first order.
depthFirst :: G -> Vertex -> [Vertex]
depthFirst :: G -> Vertex -> [Vertex]
depthFirst G
g Vertex
v = [Vertex] -> [Vertex]
forall a. [a] -> [a]
reverse ([Vertex] -> [Vertex]) -> [Vertex] -> [Vertex]
forall a b. (a -> b) -> a -> b
$ (Set Vertex, [Vertex]) -> [Vertex]
forall a b. (a, b) -> b
snd ((Set Vertex, [Vertex]) -> [Vertex])
-> (Set Vertex, [Vertex]) -> [Vertex]
forall a b. (a -> b) -> a -> b
$ G -> Vertex -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseVertex G
g Vertex
v (Set Vertex
forall a. Set a
Set.empty, [])

traverseVertex :: G -> Vertex -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseVertex :: G -> Vertex -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseVertex G
g Vertex
v (Set Vertex
visited, [Vertex]
vs)
  | Vertex -> Set Vertex -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member Vertex
v Set Vertex
visited = (Set Vertex
visited, [Vertex]
vs)
  | Bool
otherwise            = G -> [Vertex] -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseNeighbors G
g [Vertex]
ns (Set Vertex
visited', [Vertex]
vs')
  where ns :: [Vertex]
ns = Set Vertex -> [Vertex]
forall a. Set a -> [a]
Set.toList (Set Vertex -> [Vertex]) -> Set Vertex -> [Vertex]
forall a b. (a -> b) -> a -> b
$ Vertex -> G -> Set Vertex
forall g. Graph g => Vertex -> g -> Set Vertex
neighbors Vertex
v G
g
        visited' :: Set Vertex
visited' = Vertex -> Set Vertex -> Set Vertex
forall a. Ord a => a -> Set a -> Set a
Set.insert Vertex
v Set Vertex
visited
        vs' :: [Vertex]
vs' = Vertex
v Vertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
: [Vertex]
vs

traverseNeighbors :: G -> [Vertex] -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseNeighbors :: G -> [Vertex] -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseNeighbors G
_ [] (Set Vertex, [Vertex])
r = (Set Vertex, [Vertex])
r
traverseNeighbors G
g (Vertex
v:[Vertex]
vs) (Set Vertex, [Vertex])
r = G -> [Vertex] -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseNeighbors G
g [Vertex]
vs (Set Vertex, [Vertex])
r'
  where r' :: (Set Vertex, [Vertex])
r' = G -> Vertex -> (Set Vertex, [Vertex]) -> (Set Vertex, [Vertex])
traverseVertex G
g Vertex
v (Set Vertex, [Vertex])
r