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

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

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

-- | Write a function that, given two vertexes @a@ and @b@ in a graph,
-- returns all the acyclic paths from @a@ to @b@.
paths :: Vertex -> Vertex -> G -> [[Vertex]]
paths :: Vertex -> Vertex -> G -> [[Vertex]]
paths Vertex
a Vertex
b G
g = ([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 -> G -> (Set Vertex, [Vertex]) -> [[Vertex]]
spread Vertex
a Vertex
b G
g (Set Vertex
forall a. Set a
Set.empty, [])

spread :: Vertex -> Vertex -> G -> (Set Vertex, [Vertex]) -> [[Vertex]]
spread :: Vertex -> Vertex -> G -> (Set Vertex, [Vertex]) -> [[Vertex]]
spread Vertex
a Vertex
b G
g (Set Vertex
visited, [Vertex]
path)
  | Vertex
a Vertex -> Vertex -> Bool
forall a. Eq a => a -> a -> Bool
== Vertex
b               = [Vertex
b Vertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
: [Vertex]
path]
  | Vertex -> Set Vertex -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member Vertex
a Set Vertex
visited = []
  | Bool
otherwise            = Set [[Vertex]] -> [[Vertex]]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat (Set [[Vertex]] -> [[Vertex]]) -> Set [[Vertex]] -> [[Vertex]]
forall a b. (a -> b) -> a -> b
$ (Vertex -> [[Vertex]]) -> Set Vertex -> Set [[Vertex]]
forall b a. Ord b => (a -> b) -> Set a -> Set b
Set.map (\Vertex
v -> Vertex -> Vertex -> G -> (Set Vertex, [Vertex]) -> [[Vertex]]
spread Vertex
v Vertex
b G
g (Set Vertex
visited', [Vertex]
path')) (Set Vertex -> Set [[Vertex]]) -> Set Vertex -> Set [[Vertex]]
forall a b. (a -> b) -> a -> b
$ Vertex -> G -> Set Vertex
forall g. Graph g => Vertex -> g -> Set Vertex
neighbors Vertex
a G
g
  where visited' :: Set Vertex
visited' = Vertex -> Set Vertex -> Set Vertex
forall a. Ord a => a -> Set a -> Set a
Set.insert Vertex
a Set Vertex
visited
        path' :: [Vertex]
path' = Vertex
a Vertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
: [Vertex]
path