-- |
-- 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 <size> <ringType, 0 - ringSimple, 1 - ring, 2 - ringRD> <..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

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