{- |
Description: Construct minimum spanning tree
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.P84".
-}
module Problems.P84 (minimumSpanningTree, weights84) where

import           Data.Map.Lazy   (Map)
import qualified Data.Map.Lazy   as Map
import           Problems.Graphs
import qualified Solutions.P84   as Solution

-- $setup
-- >>> import Data.Map ((!))
-- >>> import qualified Data.Set as Set
-- >>> import Problems.Graphs
-- >>> import Problems.P83

-- | Write a function which constructs the minimum spanning tree of a given weighted graph.
-- While the weight of an edge could be encoded in the graph represention itself,
-- here we will specify the weight of each edge in a separate map.
--
-- === Examples
--
-- >>> let t = minimumSpanningTree graph83 weights84
-- >>> Set.foldr (\e w -> w + weights84 ! e) 0 $ edges t
-- 33
--
-- === __Hint__
--
-- The minimum spanning tree of a graph can be constructed
-- using [Prim's algorithm](https://en.wikipedia.org/wiki/Prim%27s_algorithm)
-- or [Kruskal's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm).
minimumSpanningTree :: G -> Map Edge Int -> G
minimumSpanningTree :: G -> Map Edge Int -> G
minimumSpanningTree = G -> Map Edge Int -> G
Solution.minimumSpanningTree

-- | Edge to weight map for use with 'Problem.graph83' as an example for 'minimumSpanningTree'.
weights84 :: Map Edge Int
weights84 :: Map Edge Int
weights84 = [(Edge, Int)] -> Map Edge Int
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [ ((Int, Int) -> Edge
Edge (Int
1, Int
2), Int
4)
                         , ((Int, Int) -> Edge
Edge (Int
1, Int
3), Int
1)
                         , ((Int, Int) -> Edge
Edge (Int
1, Int
5), Int
2)
                         , ((Int, Int) -> Edge
Edge (Int
2, Int
4), Int
8)
                         , ((Int, Int) -> Edge
Edge (Int
2, Int
8), Int
6)
                         , ((Int, Int) -> Edge
Edge (Int
3, Int
4), Int
10)
                         , ((Int, Int) -> Edge
Edge (Int
4, Int
5), Int
5)
                         , ((Int, Int) -> Edge
Edge (Int
4, Int
6), Int
5)
                         , ((Int, Int) -> Edge
Edge (Int
5, Int
6), Int
3)
                         , ((Int, Int) -> Edge
Edge (Int
5, Int
10), Int
4)
                         , ((Int, Int) -> Edge
Edge (Int
6, Int
7), Int
1)
                         , ((Int, Int) -> Edge
Edge (Int
7, Int
8), Int
2)
                         , ((Int, Int) -> Edge
Edge (Int
7, Int
9), Int
7)
                         , ((Int, Int) -> Edge
Edge (Int
7, Int
10), Int
11)]