Graphalyze-0.13.0.0: Graph-Theoretic Analysis library.

Maintainer Ivan.Miljenovic@gmail.com Safe-Infered

Data.Graph.Analysis

Description

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.

Synopsis

# Documentation

The library version.

# Importing data

data ImportParams n e Source

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 FieldsdataPoints :: [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 eSource

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])])Source

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)Source

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`).

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]Source

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 eSource

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)Source

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) eSource

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