-- | -- Module : Warshall -- Copyright : (c) Philipps Universitaet Marburg 2009-2010 -- License : BSD-style (see the file LICENSE) -- -- Maintainer : eden@mathematik.uni-marburg.de -- Stability : beta -- Portability : not portable -- -- The following Haskell module implements Warshall's algorithm -- for computing shortest paths with Eden. -- -- Depends on the Eden Compiler. -- -- Eden Project {- Finding Shortest Paths in a Graph using the Warshall algorithm and a ring topology. author: Rita Loogen, Jost Berthold Philipps-Universität Marburg based on a concurrent Clean program in \cite{CleanBook} ------------------------------------------------- -} module Main(main) where import Data.List import System.Environment import Control.DeepSeq import Control.Parallel (pseq) import Control.Parallel.Eden import RingSkels import Control.Parallel.Eden.Auxiliary ------------------------------------------------------------------------------- usage :: String usage = "Usage:\n" ++ "\t #> warshall <..rest is ignored..>\n"++ "computes a matrix of shortest paths for a graph of given size." main = do args <- getArgs if length args < 2 then putStrLn usage else do let ~(size:ringnr:_) = args size0 = read size ringnr0 = read ringnr fct = [ringSimple,ring,ringRD] !! (ringnr0 - 1) res = if size0 == 6 then warshall fct noPe test6 else warshall fct noPe (m1 size0) -- print res rnf res `pseq` putStrLn "Done!" type Matrix a = [[a]] dim :: Matrix a -> Int dim = length -- warshall :: () -> Int -> Matrix Int -> Matrix Int warshall ringskel np mat = ringskel np split concat ringf (mat,0) -- ring type issue, 0 is dummy parameter where split :: Int -> (Matrix Int, Int) -> [ (Matrix Int, Int )] -- ring size all input [ (some rows ,no. of 1st row)] split n (mat,_) = let inputrows = splitIntoN n mat -- [[r1..rk],[r(k+1)..r(2k)]..[r(i*k)..r(dim mat)]] in zip inputrows (scanl (+) 1 (map length inputrows)) -- should be "(init (scanl (+)...)" ringf :: ((Matrix Int, Int), [[Int]] ) -> ( Matrix Int , [[Int]]) -- ((some rows,start),more rows) -> ( result rows , rows for ring) ringf ((rows,startrow), fromLeft) = create_procs (length \$ head rows) startrow rows fromLeft -- ring_iterate :: Int -> Int -> Int -> [Int] -> [[Int]] -> ([Int],[[Int]]) ring_iterate size k i rowk rows | i > size = (rowk, []) --iterations_finished | i == k = (solution, rowk:restoutput) -- start_sending_this_row | otherwise = (solution, rowi:restoutput) where rowi:xs = rows (solution, restoutput) = rnf nextrowk `pseq` ring_iterate size k (i+1) nextrowk xs nextrowk | i == k = rowk -- no update for own row | otherwise = updaterow rowk rowi distki distki = rowk!!(i-1) --updaterow :: updaterow [] rowi distij = [] updaterow (distjk:restrowj) (distik:restrowi) distji = min distjk (distji + distik):updaterow restrowj restrowi distji -- -- sequential version from Clean book seq_warshall :: Int -> Matrix Int -> Matrix Int seq_warshall _ mat = solution where (solution, output) = create_procs (length mat) 1 mat output create_procs :: Int -> Int -> Matrix Int -> [[Int]] -> ([[Int]],[[Int]]) create_procs size k [rowN] inputleft = ([rowNsolution], output) where (rowNsolution, output) = ring_iterate size k 1 rowN inputleft create_procs size k (rowk:restmat) inputleft = (rowksolution:restsolutions, outputN) where (rowksolution, outputk) = ring_iterate size k 1 rowk inputleft (restsolutions, outputN) = create_procs size (k+1) restmat outputk -- Test data --------------------------------------------------------------------------------- test6 :: Matrix Int test6 = [[ 0, 100, 100, 13, 100, 100], [100, 0, 100, 100, 4,9], [11, 100, 0, 100, 100, 100], [100, 3, 100, 0, 100, 7], [15, 5, 100, 1, 0, 100], [11, 100, 100, 14, 100, 0]] {- Adjacency Matrix Shortest Paths: - - To - - [[ 0 , 100, 100, 13, 100, 100], [[ 0,16,100,13,20,20], F [100 , 0, 100, 100, 4, 9], [19, 0,100, 5, 4, 9], r [ 11 , 100, 0, 100, 100, 100], [11,27, 0,24,31,31], o [100 , 3, 100, 0, 100, 7], [18, 3,100, 0, 7, 7], m [ 15 , 5, 100, 1, 0, 100], [15, 4,100, 1, 0, 8], [ 11 , 100, 100, 14, 100, 0]] [11,17,100,14,21, 0]] -} test3 :: [[Int]] test3 = [[0,1,100],[1,0,1],[100,1,0]] m1 size = replicate size [1..size] m2 size = listToListList size [1..size*size] mA size = if size <= 4000 then m1 size else listToListList size (concat (take 20 (repeat [1..(size*size `div` 20)]))) mB size = if size <= 4000 then m1 size else listToListList size (concat (take 20 (repeat [0,2.. ((size*size) `div` 20)-2]))) listToListList c m | length m <= c = [m] | otherwise = c1 : listToListList c resto where (c1,resto) = splitAt c m ---------------------------------------------------------------