-----------------------------------

Lazy

Tue Nov 14, 2006 3:13 pm


[Haskell] Single Source All Paths

-----------------------------------

Hi all,

This is a little program I put together to practice Haskell. The specs can be found here: http://www.doc.ic.ac.uk/~ajf/Teaching/Haskell/sampleTest2.pdf, although I deviated a little from the assignment.

It's far from perfect. The instance declaration of Finite is incomplete, and I feel that some things can be done more elegantly. Time permiting, I'll try to rewrite it as a State monad, to carry around the graph.

All comments and advice are appreciated.

import List

type Id = Int
type Weight = Int
type Edge  = ( Id, Id )
type Graph = [ ( Edge, Weight ) ]

data Cost = Finite Weight | Infinity 
		deriving ( Eq, Show )


edge 	 = fst
cost     = snd
fromId = ( fst . fst )
toId   = ( snd . fst )


instance Num Cost where
	Infinity + _ = Infinity
	_ + Infinity = Infinity
	Finite a + Finite b = Finite ( a + b )
	
instance Ord Cost where
	Infinity  [ ( Edge, Cost ) ]
	solve' _ [] n = n
	solve' s c acc = solve' s c' acc' where
		 minp  = cheapest c
		 restp = delete minp c
		 c' = map ( \ x -> relax x minp graph ) restp
		 acc' = minp : acc 
 

allIds :: Graph -> [ Id ]
allIds graph = nub $ concat [ ( [ fromId g ] ++ [ toId g ] ) | g  Graph -> Cost 
lookUpCost edge graph = let found = lookup edge graph in
		  case found of
		  Nothing -> Infinity
		  Just a  -> Finite a

costs :: Id -> Graph -> [ ( Edge , Cost ) ]
costs s graph = [  ( ( s, x ), lookUpCost ( s, x ) graph ) | x  ( Edge, Cost )
cheapest n = minimumBy ( \ x y -> compare ( cost x ) ( cost y ) ) n

relax :: ( Edge, Cost ) -> ( Edge, Cost ) -> Graph -> ( Edge, Cost )
relax p minp graph = ( edge p, min ( cost p ) transit  ) where
	transit = lookUpCost (fromId p, toId minp) graph + lookUpCost (toId minp, toId p) graph

	              
-- test data

test :: Graph
test= [ ( ( 0, 1 ), 1 ),
	( ( 0, 2 ), 3 ),
	( ( 0, 4 ), 6 ),
	( ( 1, 2 ), 1 ),
	( ( 1, 3 ), 3 ),
	( ( 2, 0 ), 1 ),
	( ( 2, 1 ), 2 ),
	( ( 2, 3 ), 1 ),
	( ( 3, 0 ), 3 ),
	( ( 3, 4 ), 2 ),
	( ( 4, 3 ), 1 ),
	( ( 5, 2 ), 9 ) ]




-----------------------------------

Tyr_God_Of_War

Sun Apr 24, 2011 9:48 am


RE:[Haskell] Single Source All Paths

-----------------------------------

The pdf is gone, could you state the problem here?


-----------------------------------

apython1992

Sun Apr 24, 2011 3:26 pm


RE:[Haskell] Single Source All Paths

-----------------------------------

Um...that post is about five years old.