packages feed

graph-utils (empty) → 0.3.5

raw patch · 5 files changed

+153/−0 lines, 5 filesdep +basedep +containersdep +fglsetup-changed

Dependencies added: base, containers, fgl, mtl, parsec, template-haskell

Files

+ Data/Graph/EasyGrapher.hs view
@@ -0,0 +1,5 @@+module Data.Graph.EasyGrapher (+    gr, buildGraph, EGGraph(..), EGTerm(..), fromGr+  ) where+import Data.Graph.EasyGrapher.EasyGrapher+import Data.Graph.EasyGrapher.Quote
+ Data/Graph/PageRank.hs view
@@ -0,0 +1,60 @@+module Data.Graph.PageRank (pageRanks, RankDic(..)) where+import Control.Monad.RWS+import Data.Graph.Inductive+import Prelude hiding (map, lookup)+import Data.Map hiding (map)+import Data.Maybe (fromJust)+import Control.Monad++map :: (Functor f) => (a -> b) -> f a -> f b+map = fmap++data Env = Env {node :: [Node], from :: Map Node [Node], outdegrees :: Map Node Int}++-- |'RankDic' is the Map for holding PageRank data.+type RankDic = Map Node Double +type PRMachine = RWS Env () RankDic++lookupEnv :: (Ord a) => (Env -> Map a b) -> a -> PRMachine b+lookupEnv f a = do{ dic<-asks f; return $ fromJust $ lookup a dic}++outdegree :: Node -> PRMachine Int+outdegree = lookupEnv outdegrees++froms :: Node -> PRMachine [Node]+froms = lookupEnv from++currentRank :: Node -> PRMachine Double+currentRank nd = gets (fromJust.lookup nd)++-- |'pageRanks' calculate the PageRank for each node in the Graph 'gr'+pageRanks :: (Graph gr) => gr a b -> Double -> Double -> RankDic+pageRanks gr epsilon error = fst $ execRWS steps Env{node=nds, from=froms, outdegrees=outdegs} initRanks+    where nds = nodes gr+          count :: (Num a) => a+          count = fromIntegral $ noNodes gr+          froms = fromList $ zip nds $ map (pre gr) nds+          outdegs = fromList $ zip nds $ map (outdeg gr) nds+          initRanks = fromList $ zip nds $ replicate count (1/count)+          steps = do+            old <- get+            new <- calcPageRank epsilon+            let cond = foldWithKey (\k a b -> b && ((findWithDefault (1/0) k new)-a < error)) True old+            if cond then return new else steps+            +            ++calcPageRank :: Double -> PRMachine RankDic+calcPageRank epsilon = do+  nds <- asks node+  dic <- forM nds $ \n -> do+                 frms <- froms n+                 ranks <- forM frms $ \m -> do+                            deg <- outdegree m+                            rank <- currentRank m+                            return (rank/fromIntegral deg)+                 count <- liftM (fromIntegral.length) $ asks node+                 return (n, epsilon/count + (1-epsilon)*(sum ranks))+  let rdic = fromList dic+  put rdic+  return rdic
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright (c)2010, Hiromi ISHII++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Hiromi ISHII nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ graph-utils.cabal view
@@ -0,0 +1,56 @@+Name:                graph-utils++Version:             0.3.5++-- A short (one-line) description of the package.+Synopsis:            A simple wapper & quasi quoter for fgl.++-- A longer description of the package.+Description:+  Simple Wrapper for generating Graph provided by Data.Graph.Inductive.+  It also contains PageRank calculator.++-- URL for the project homepage or repository.+Homepage:            http://github.com/konn/graph-utils/++-- The license under which the package is released.+License:             BSD3++-- The file containing the license text.+License-file:        LICENSE++-- The package author(s).+Author:              Hiromi ISHII++-- An email address to which users can send suggestions, bug reports,+-- and patches.+Maintainer: Hiromi Ishii <mr_konn _at_ jcom.home.ne.jp>++-- A copyright notice.+Copyright: (C) 2010 Hiromi Ishii++Category:            Data, Graphs, Data Structures++Build-type:          Simple++-- Extra files to be distributed with the package, such as examples or+-- a README.+-- Extra-source-files:  ++-- Constraint on the version of Cabal needed to build this package.+Cabal-version:       >=1.2+++Library+  -- Modules exported by the library.+  Exposed-modules:  Data.Graph.EasyGrapher, Data.Graph.PageRank+  +  -- Packages needed in order to build this package.+  Build-depends: base >=2 && < 4 , fgl, mtl, containers, template-haskell, parsec>=3.0+  +  -- Modules not exported by this package.+  -- Other-modules:       +  +  -- Extra tools (e.g. alex, hsc2hs, ...) needed to build the source.+  -- Build-tools:         +