module S9_5 where -- to get access to the imported modules in Hugs do -- :set -P../Chapter7:../Chapter5:{Hugs}/lib:{Hugs}/lib/hugs:{Hugs}/lib/exts import Dynamic import Graph type AspCoord = (Int,Int,Int) type AspEntry = (Int,[Int]) compAsp :: (Graph Int Int) -> Table AspEntry AspCoord -> AspCoord -> AspEntry compAsp g c (i,j,k) | k==0 = (weight i j g , if i==j then [i] else [i,j]) | otherwise = let (v1,p) = findTable c (i,j,k-1) (a,p1) = findTable c (i,k,k-1) (b,_:p2) = findTable c (k,j,k-1) v2 = a+b in if v1<=v2 then (v1,p) else (v2,p1++p2) bndsAsp :: Int -> ((Int,Int,Int),(Int,Int,Int)) bndsAsp n = ((1,1,0),(n,n,n)) asp :: (Graph Int Int) -> [ ((Int,Int) , AspEntry) ] asp g = [ ((i,j) , findTable t (i,j,n)) | i<-[1..n], j<-[i+1..n]] where n = length (nodes g) t = dynamic (compAsp g) (bndsAsp n) graphEx ::Graph Int Int graphEx = mkGraph True (1,6) [(i,j,(v!!(i-1))!!(j-1)) |i<-[1..6],j<-[1..6]] v::[[Int]] v = [[ 0, 4, 1, 6,100,100], [ 4, 0, 1,100, 5,100], [ 1, 1, 0,100, 8, 2], [ 6,100,100, 0,100, 2], [100, 5, 8,100, 0, 5], [100,100, 2, 2, 5, 0]] baaseP245 :: Graph Int Int baaseP245 = mkGraph True (1,6) [(i,j,(v'!!(i-1))!!(j-1)) |i<-[1..6],j<-[1..6]] v'::[[Int]] v' =[[ 0, 4,100,100,100, 2], [ 1, 0, 3, 4,100,100], [ 6, 3, 0, 7,100,100], [ 6,100,100, 0, 2,100], [100,100,100, 5, 0,100], [100,100,100, 2, 3, 0]] {- Examples of evaluations and results ? asp graphEx [((1, 2), (2, [1, 3, 2])), ((1, 3), (1, [1, 3])), ((1, 4), (5, [1, 3, 6, 4])), ((1, 5), (7, [1, 3, 2, 5])), ((1, 6), (3, [1, 3, 6])), ((2, 3), (1, [2, 3])), ((2, 4), (5, [2, 3, 6, 4])), ((2, 5), (5, [2, 5])), ((2, 6), (3, [2, 3, 6])), ((3, 4), (4, [3, 6, 4])), ((3, 5), (6, [3, 2, 5])), ((3, 6), (2, [3, 6])), ((4, 5), (7, [4, 6, 5])), ((4, 6), (2, [4, 6])), ((5, 6), (5, [5, 6]))] ? asp baaseP245 [((1, 2), (4, [1, 2])), ((1, 3), (7, [1, 2, 3])), ((1, 4), (4, [1, 6, 4])), ((1, 5), (5, [1, 6, 5])), ((1, 6), (2, [1, 6])), ((2, 3), (3, [2, 3])), ((2, 4), (4, [2, 4])), ((2, 5), (6, [2, 4, 5])), ((2, 6), (3, [2, 1, 6])), ((3, 4), (7, [3, 4])), ((3, 5), (9, [3, 4, 5])), ((3, 6), (6, [3, 2, 1, 6])), ((4, 5), (2, [4, 5])), ((4, 6), (8, [4, 1, 6])), ((5, 6), (13, [5, 4, 1, 6]))] -}