[Haskell-cafe] Re: functional graphs

[Mirko Rahn]

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