{- |
Description: Cycles with a given vertex
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

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

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

-- | Finds all cycles in the graph which include the given vertex.
cycles :: Vertex -> G -> [[Vertex]]
cycles :: Vertex -> G -> [[Vertex]]
cycles Vertex
v 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 -> G -> [[Vertex]]
start Vertex
v G
g

-- | Start building up cycle from the first vertex.
start :: Vertex -> G -> [[Vertex]]
start :: Vertex -> G -> [[Vertex]]
start Vertex
v G
g = 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
-> G -> (Vertex, [Vertex], Set Vertex, Set Edge) -> [[Vertex]]
spread Vertex
v G
g (Vertex
v', [Vertex
v], Vertex -> Set Vertex
forall a. a -> Set a
Set.singleton Vertex
v, Set Edge
forall a. Set a
Set.empty)) (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
v G
g

-- | Build up cycles one vertex at a time.
spread :: Vertex -> G -> (Vertex, [Vertex], Set Vertex, Set Edge) -> [[Vertex]]
spread :: Vertex
-> G -> (Vertex, [Vertex], Set Vertex, Set Edge) -> [[Vertex]]
spread Vertex
_ G
_ (Vertex
_, [], Set Vertex
_, Set Edge
_) = []
spread Vertex
target G
graph (Vertex
v, path :: [Vertex]
path@(Vertex
u:[Vertex]
_), Set Vertex
visited, Set Edge
passed)
  | Edge -> Set Edge -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member Edge
e Set Edge
passed = []
  | Vertex
v Vertex -> Vertex -> Bool
forall a. Eq a => a -> a -> Bool
== Vertex
target = [[Vertex]
path]
  | Vertex -> Set Vertex -> Bool
forall a. Ord a => a -> Set a -> Bool
Set.member Vertex
v 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 -> [[Vertex]]
continue (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
v G
graph
  where e :: Edge
e = (Vertex, Vertex) -> Edge
Edge (Vertex
v, Vertex
u)
        continue :: Vertex -> [[Vertex]]
continue Vertex
v' = Vertex
-> G -> (Vertex, [Vertex], Set Vertex, Set Edge) -> [[Vertex]]
spread Vertex
target G
graph (Vertex
v', [Vertex]
path', Set Vertex
visited', Set Edge
passed')
        path' :: [Vertex]
path' = Vertex
v Vertex -> [Vertex] -> [Vertex]
forall a. a -> [a] -> [a]
: [Vertex]
path
        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
        passed' :: Set Edge
passed' = Edge -> Set Edge -> Set Edge
forall a. Ord a => a -> Set a -> Set a
Set.insert Edge
e Set Edge
passed