{- | 
   Implement the power method for calculating the first eigenvalue/vector 
   of a (sparse) matrix.  This is what Google Page Rank does.

   It's probably a good idea that each node links to itself, 
   but this is not required by the algorithm.

   Copyright: Ketil Malde, Licencse: GPL 2 or BSD
-}

module PowerMethod where

import Data.Map (Map)
import qualified Data.Map as M

type ScoredNodes node = Map node Double
type Links node       = Map node [node]

-- | calcualte the graph flow (i.e. a matrix-vector multiply of the
--   link matrix x score vector)
flow :: Ord node => Links node -> ScoredNodes node -> ScoredNodes node
flow links = M.unionsWith (+) . map (distribute links) . M.toList 
    
distribute links (k,s) = 
    M.fromList [(n,s/fromIntegral (length edges)) | n <- edges]
    where edges = maybe [] id (M.lookup k links)

-- | normalize a vector
normalize :: Ord node => ScoredNodes node -> ScoredNodes node
normalize ns = let divisor = sqrt . sum . map (^(2::Int)) $ M.elems ns
               in M.map (/divisor) ns

-- | Given the size of the vector and a set of links, iterate to calculate a
--   convergence towards the primary eigenvector
eigenvector1 :: Ord node => Links node -> [ScoredNodes node]
eigenvector1 links = 
    let initial = M.fromList [(n,1.0/fromIntegral (M.size links)) | n <- M.keys links]
    in iterate (normalize . flow links) initial