Analysis.hs

{- |
   Module      : Data.Graph.Analysis
   Description : A Graph-Theoretic Analysis Library.
   Copyright   : (c) Ivan Lazar Miljenovic 2008
   License     : 2-Clause BSD
   Maintainer  : Ivan.Miljenovic@gmail.com

   This is the root module of the /Graphalyze/ library, which aims to
   provide a way of analysing the relationships inherent in discrete
   data as a graph.

   This was written as part of my mathematics honours thesis,
   /Graph-Theoretic Analysis of the Relationships in Discrete Data/.
 -}
module Data.Graph.Analysis
    ( version,
      -- * Re-exporting other modules
      module Data.Graph.Analysis.Types,
      module Data.Graph.Analysis.Utils,
      module Data.Graph.Analysis.Algorithms,
      module Data.Graph.Analysis.Reporting,
      module Data.Graph.Inductive.Graph,
      -- * Importing data
      ImportParams(..),
      defaultParams,
      importData,
      -- * Result analysis
      -- $analfuncts
      lengthAnalysis,
      classifyRoots
    ) where

import Data.Graph.Analysis.Utils
import Data.Graph.Analysis.Types
import Data.Graph.Analysis.Algorithms
import Data.Graph.Analysis.Reporting

import Data.Graph.Inductive.Graph
import Data.List
import Data.Maybe
import qualified Data.Map as M

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

-- | The library version.
version :: String
version = "0.2"

{- |
   This represents the information that's being passed in that we want
   to analyse.  If the graph is undirected, it is better to list each
   edge once rather than both directions.
 -}
data ImportParams a = Params { -- | The discrete points.
                               dataPoints :: [a],
                               -- | The relationships between the points.
                               relationships :: [(a,a)],
                               -- | The expected roots of the graph.
                               --   If @'directed' = 'False'@, then this is ignored.
                               roots :: [a],
                               -- | 'False' if relationships are symmetric
                               --   (i.e. an undirected graph).
                               directed :: Bool
                             }

-- | Default values for 'ImportParams', with no roots and a directed graph.
defaultParams :: ImportParams a
defaultParams = Params { dataPoints = [],
                         relationships = [],
                         roots = [],
                         directed = True
                       }

{- |
   Import data into a format suitable for analysis.  This function is
   /edge-safe/: if any datums are listed in the edges of
   'ImportParams' that aren't listed in the data points, then those
   edges are ignored.  Thus, no sanitation of the 'relationships' in
   @ImportParams@ is necessary.
 -}
importData        :: (Ord a) => ImportParams a -> GraphData a
importData params = GraphData { graph = dGraph, wantedRoots = rootNodes }
    where
      -- Adding Node values to each of the data points.
      lNodes = zip [1..] (dataPoints params)
      -- Creating a lookup map from the label to the @Node@ value.
      nodeMap = M.fromList $ map (uncurry (flip (,))) lNodes
      -- Find the Node value for the given data point.
      findNode n = M.lookup n nodeMap
      -- Validate a edge after looking its values up.
      validEdge (v1,v2) = case (findNode v1, findNode v2) of
                            (Just x, Just y) -> Just $ addLabel (x,y)
                            _                -> Nothing
      -- Add an empty edge label.
      addLabel (x,y) = (x,y,())
      -- The valid edges in the graph.
      graphEdges = catMaybes $ map validEdge (relationships params)
      -- Validate an edge
      validNode l = case (findNode l) of
                      (Just n) -> Just (n,l)
                      _        -> Nothing
      -- Construct the root nodes
      rootNodes = if (directed params)
                  then catMaybes $ map validNode (roots params)
                  else []
      -- Make the graph undirected if necessary.
      setDirection = if (directed params) then id else undir
      -- Construct the graph.
      dGraph = setDirection $ mkGraph lNodes graphEdges

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

{- $analfuncts
   Extra functions for data analysis.
 -}

-- | Returns the mean and standard deviations of the lengths of the sublists,
--   as well all those lists more than one standard deviation longer than
--   the mean.
lengthAnalysis    :: [[a]] -> (Int,Int,[(Int,[a])])
lengthAnalysis as = (av,stdDev,as'')
    where
      as' = addLengths as
      ls = map fst as'
      (av,stdDev) = statistics' ls
      as'' = filter (\(l,_) -> l > (av+stdDev)) as'

{- |
   Compare the actual roots in the graph with those that are expected
   (i.e. those in 'wantedRoots').  Returns (in order):

   * Those roots that are expected (i.e. elements of 'wantedRoots'
     that are roots).

   * Those roots that are expected but not present (i.e. elements of
     'wantedRoots' that /aren't/ roots.

   * Unexpected roots (i.e. those roots that aren't present in
     'wantedRoots').
 -}
classifyRoots    :: (Eq a) => GraphData a -> ([LNode a], [LNode a], [LNode a])
classifyRoots gd = (areWanted, notRoots, notWanted)
    where
      g = graph gd
      wntd = wantedRoots gd
      rts = rootsOf g
      areWanted = intersect wntd rts
      notRoots = wntd \\ rts
      notWanted = rts \\ wntd