Data.Graph.Analysis

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.

The original version of this library was written as part of my mathematics honours thesis, Graph-Theoretic Analysis of the Relationships in Discrete Data.

Documentation

version :: String

The library version.

Re-exporting other modules

module Data.Graph.Analysis.Types

module Data.Graph.Analysis.Utils

module Data.Graph.Analysis.Algorithms

module Data.Graph.Analysis.Visualisation

module Data.Graph.Analysis.Reporting

module Data.Graph.Inductive.Graph

Importing data

data ImportParams n e

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.

Constructors

ImpParams

Fields

dataPoints :: [n]

The discrete points.

relationships :: [Rel n e]

The relationships between the points.

roots :: [n]

The expected roots of the graph. If directed = False, then this is ignored.

directed :: Bool

False if relationships are symmetric (i.e. an undirected graph).

importData :: (Ord n, Ord e) => ImportParams n e -> GraphData n e

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. The unused relations are stored in unusedRelationships. Note that it is assumed that all datums in roots are also contained within dataPoints.

Result analysis

Extra functions for data analysis.

lengthAnalysis :: [[a]] -> (Int, Int, [(Int, [a])])

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.

classifyRoots :: GraphData n e -> (Set Node, Set Node, Set Node)

Compare the actual roots in the graph with those that are expected (i.e. those in wantedRootNodes). Returns (in order):

• Those roots that are expected (i.e. elements of wantedRootNodes that are roots).
• Those roots that are expected but not present (i.e. elements of wantedRootNodes that aren't roots.
• Unexpected roots (i.e. those roots that aren't present in wantedRootNodes).

inaccessibleNodes :: GraphData n e -> Set Node

Find the nodes that are not reachable from the expected roots (i.e. those in wantedRootNodes).

interiorChains :: (Eq n, Eq e) => GraphData n e -> [LNGroup n]

Only return those chains (see chainsIn) where the non-initial nodes are not expected roots.

collapseAndUpdate :: Ord n => [AGr n e -> [(NGroup, n)]] -> GraphData n e -> GraphData n e

As with collapseAndReplace, but also update the wantedRootNodes to contain the possibly compressed nodes. Since the datums they refer to may no longer exist (as they are compressed), unusedRelationships is set to [].

collapseAndUpdate' :: Ord n => [AGr n e -> [(NGroup, n)]] -> GraphData n e -> (GraphData n e, Map n n)

As with collapseAndUpdate, but also includes a lookup Map from the old label to the new.

levelGraphFromRoot :: Ord n => GraphData n e -> GraphData (GenCluster n) e

As with levelGraph, but use the expected roots rather than the actual roots.