Hello,
It's a _complete_ graph, i.e. there is an edge between every two nodes.
I want to compute the minimum spanning tree. Eventually I want to have a
sub-optimal solution for the travelling salesman problem (TSP).
A direct solution for this problem would be:
-- | place a f-minimal element to the left, remember the minimal value
min_left :: Ord b => (a -> b) -> [a] -> ([a],b)
min_left _ [] = error "min_left: empty list"
min_left f (x:xs) = ms (x,f x) [] xs $ map f xs
where ms (y,v) nonmin (z:zs) (w:ws)
| w < v = ms (z,w) (y:nonmin) zs ws
| otherwise = ms (y,v) (z:nonmin) zs ws
ms (y,v) nonmin _ _ = (y:nonmin,v)
-- | the same for cross xs ys and a f with arity two
mins :: Ord c => (a -> b -> c) -> [a] -> [b] -> [(a, ([b],c))]
mins f xs ys =
fst $ min_left (snd . snd) [(x,min_left (f x) ys) | x <- xs]
-- | *complete* graph
data CGraph a b = CGraph [a] (a -> a -> b)
-- | give a list of edges with weight that form a minimal spanning tree
prim :: Ord b => CGraph a b -> [(a,a,b)]
prim (CGraph [] _) = []
prim (CGraph (x:xs) w) = build [x] xs
where build _ [] = []
build seen open =
let (f,(t:rest,v)):_ = mins w seen open
in (f,t,v) : build (t:seen) rest
-- | calculate the complete round trip and its (accumulated) weight
round_trip :: (Eq a, Ord b, Num b) => CGraph a b -> [(a,a,b,b)]
round_trip = rt 0 [] . prim
where
rt _ [] [] = []
rt s ((c,r,v):bs) [] = (c,r,v,s+v) : rt (s+v) bs []
rt s [] ((r,c,v):ys) = (r,c,v,s+v) : rt (s+v) [(c,r,v)] ys
rt s (b@(z,t,w):bs) ((r,c,v):ys)
| r == z = (r,c,v,s+v) : rt (s+v) ((c,r,v):b:bs) ys
| otherwise = (z,t,w,s+w) : rt (s+w) bs ((r,c,v):ys)
{-
*Main> round_trip $ CGraph [0..5] (\ x y -> mod (x+y) 4)
[(0,4,0,0),(4,5,1,1),(5,3,0,1),(3,1,0,1),(1,3,0,1),(3,2,1,2),(2,3,1,3),(3,5,0,3),(5,4,1,4),(4,0,0,4)]
-}
Have fun!
/BR, Mirko Rahn
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
