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

Part of Ninety-Nine Haskell "Problems".  Some solutions are in "Solutions.P83".
-}
module Problems.P83 (spanningTrees, isTree, isConnected, graph83) where

import           Problems.Graphs
import           Problems.P80
import qualified Solutions.P83   as Solution

-- $setup
-- >>> import Problems.Graphs
-- >>> import Problems.P80

-- | Mathematically, a tree is a graph with exactly one path between any two vertexes.
-- A spanning tree of a graph is a tree which includes all vertexes of the graph.
--
-- Write a function to construct all spanning trees of a given graph.
--
-- You can use 'graph83' as an example graph to construct spanning trees from.
--
-- === Examples
--
-- >>> length $ spanningTrees graph83
-- 173
--
-- >>> toG (Paths [[1,2,4,5,6,7,8],[1,3],[5,10],[7,9]]) `elem` spanningTrees graph83
-- True
spanningTrees :: G -> [G]
spanningTrees :: G -> [G]
spanningTrees = G -> [G]
Solution.spanningTrees

-- | Write a function which returns whether a graph is a tree using 'spanningTrees'.
--
-- === Examples
--
-- >>> isTree graph83
-- False
--
-- >>> isTree $ toG $ Paths [[1,2,3],[1,4,5]]
-- True
isTree :: G -> Bool
isTree :: G -> Bool
isTree = G -> Bool
Solution.isTree

-- | Write a function which returns whether a graph is connected using 'spanningTrees'.
--
-- === Examples
--
-- >>> isConnected graph83
-- True
--
-- >>> isConnected $ toG $ Lists ([1,2,3], [])
-- False
isConnected :: G -> Bool
isConnected :: G -> Bool
isConnected = G -> Bool
Solution.isConnected

-- | Graph for use as an example for 'spanningTrees'.
--
-- ![Graph with path 1,2,4,5,6,7,8, path 1,3,4,5, path 2,8, and path 5,10,7,9](images/Graphs/Example-P83.svg)
graph83 :: G
graph83 :: G
graph83 = Paths -> G
forall g. ConvertibleGraph g => g -> G
toG (Paths -> G) -> Paths -> G
forall a b. (a -> b) -> a -> b
$ [[Vertex]] -> Paths
Paths [[Vertex
1,Vertex
2,Vertex
4,Vertex
5,Vertex
6,Vertex
7,Vertex
8],[Vertex
1,Vertex
3,Vertex
4,Vertex
6],[Vertex
2,Vertex
8],[Vertex
5,Vertex
10,Vertex
7,Vertex
9]]