-- Vicotoria Lam
-- COMP 554 Spring 2018
-- Interesting Haskell solution to this problem
import Data.Set (fromList,union,empty,isSubsetOf,member,Set)
import Data.List (sortOn,delete)
main :: IO ()
main = return ()
-- ghcid gets mad if this isn't here.
graph2 :: [[Double]]
graph2 = [ [ 0, 2, 1]
, [ 2, 0, 7]
, [ 1, 7, 0] ]
graph4 :: [[Double]]
graph4 = [ [ 0,10, 5, 7]
, [10, 0, 9, 6]
, [ 5, 9, 0, 8]
, [ 7, 6, 8, 0] ]
graph6 :: [[Double]]
graph6 = [ [ 0,10,12,11, 3, 5]
, [10, 0, 9,12, 2, 4]
, [12, 9, 0, 8, 0, 0]
, [11,12, 8, 0, 7, 0]
, [ 3, 2, 0, 7, 0, 6]
, [ 5, 4, 0, 0, 6, 0] ]
-- Part I.
v :: [[Double]] -> Set Int
v g = fromList [0..(length (g)-1) ]
scan :: [[Double]] -> [(Double, Int, Int)]
scan g = helpList
where
helpList = [ foo i j | j <- [0..(n-1)], i <- [j..(n-1)], keep i j ]
n = length g
keep :: Int -> Int -> Bool
keep i j = g !! i !! j /= 0
foo :: Int -> Int -> (Double, Int, Int)
foo i j = (g !! i !! j, i, j)
sort_ :: [[Double]] -> [(Int, Int)]
sort_ g = fmap getEdge (sortOn getCost (scan g))
where
getEdge :: (Double, Int, Int) -> (Int, Int)
getEdge (cost, v1, v2) = (v1, v2)
getCost :: (Double, Int, Int) -> Double
getCost (cost, v1, v2) = cost
-- note: sortOn function list
-- Part II.
type Tree = Set (Int, Int)
extract :: (Int, Int) -> Set Int
extract (a, b) =
fromList [a,b]
loop :: Set Int -> (Tree, Set Int, [(Int, Int)] ) -> Tree
loop v (tspan, included, sorted) = if included == v
then tspan
else loop v (step (tspan, included, sorted))
step :: (Tree, Set Int, [(Int, Int)] )
-> (Tree, Set Int, [(Int, Int)] )
step (tspan, included, sorted) = (tspan', included', sorted')
where
check (i, j) = (member i included || member j included) && not (isSubsetOf (fromList [i,j]) included)
viable = filter check sorted
tspan' = union tspan (fromList [head viable])
included' = union included (extract (head viable))
sorted' = delete (head viable) sorted
function :: [[Double]] -> Tree
function g = loop (v g) (tspan, included, sorted)
where
tspan = empty
included = fromList [0]
sorted = sort_ g