{- |
   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
    ( -- * Re-exporting other modules
      module Data.Graph.Analysis.Types,
      module Data.Graph.Analysis.Utils,
      module Data.Graph.Analysis.Algorithms,
      module Data.Graph.Inductive.Graph,
      -- * Importing data
    ) where

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

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

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

{- |
   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 }
      -- 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