-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Graph-Theoretic Analysis library.
--   
--   A library to use graph theory to analyse the relationships inherent in
--   discrete data.
@package Graphalyze
@version 0.1


-- | This module defines the various types and classes utilised by the
--   Graphalyze library.
module Data.Graph.Analysis.Types

-- | By default, the Graphalyze library works on graphs with no edge
--   labels. As such, these types provide useful aliases for the default
--   FGL types. Most of the algorithms, however, work on arbitrary graph
--   types.
--   
--   Represents information about the graph being analysed.
data GraphData a
GraphData :: AGr a -> LNGroup a -> GraphData a

-- | We use a graph type with no edge labels.
graph :: GraphData a -> AGr a

-- | The expected roots in the graph.
wantedRoots :: GraphData a -> LNGroup a

-- | We use a basic tree-based graph by default.
type AGr a = Gr a ()

-- | A grouping of <a>Node</a>s.
type NGroup = [Node]

-- | A grouping of <a>LNode</a>s.
type LNGroup a = [LNode a]

-- | These types and classes represent useful label types.
--   
--   The class of outputs of a clustering algorithm. This class is mainly
--   used for visualization purposes, with the <a>Ord</a> instance required
--   for grouping. Instances of this class are intended for use as the
--   label type of graphs.
class (Ord c) => ClusterLabel a c | a -> c
cluster :: (ClusterLabel a c) => a -> c
nodelabel :: (ClusterLabel a c) => a -> String

-- | A generic cluster-label type.
data GenCluster a
GC :: Int -> a -> GenCluster a

-- | Label type for storing node positions. Note that this isn't an
--   instance of <a>ClusterLabel</a> since there's no clear indication on
--   which cluster a node belongs to at this stage.
data PosLabel a
PLabel :: Int -> Int -> Node -> a -> PosLabel a
xPos :: PosLabel a -> Int
yPos :: PosLabel a -> Int
pnode :: PosLabel a -> Node
plabel :: PosLabel a -> a
instance (Eq a) => Eq (PosLabel a)
instance (Show a) => Show (PosLabel a)
instance (Show a) => Show (GraphData a)
instance (Show a) => ClusterLabel (GenCluster a) Int


-- | This module defines various utility functions used throughout.
module Data.Graph.Analysis.Utils

-- | Extracting data from graphs.
--   
--   The node number of an <a>LNode</a>.
node :: LNode a -> Node

-- | The label of an <a>LNode</a>
label :: LNode a -> a

-- | Extract the <a>Edge</a> from the <a>LEdge</a>.
edge :: LEdge b -> Edge

-- | The label of an <a>LEdge</a>
eLabel :: LEdge b -> b

-- | Obtain the labels for a list of <a>Node</a>s. It is assumed that each
--   <a>Node</a> is indeed present in the given graph.
addLabels :: (Graph g) => g a b -> [Node] -> [LNode a]

-- | Find all the labelled nodes in the graph that match the given
--   predicate.
filterNodes :: (Graph g) => (g a b -> LNode a -> Bool) -> g a b -> [LNode a]

-- | Find all the nodes in the graph that match the given predicate.
filterNodes' :: (Graph g) => (g a b -> Node -> Bool) -> g a b -> [Node]

-- | Manipulating graphs.
--   
--   Extract the actual <a>LNode</a>s from an <a>LPath</a>.
pathValues :: LPath a -> [LNode a]

-- | Make the graph undirected, i.e. for every edge from A to B, there
--   exists an edge from B to A. The provided function
--   Data.Graph.Inductive.Basic.undir duplicates loops as well, which isn't
--   wanted. It is assumed that no edges are already duplicates [i.e. if
--   there exists an edge (n1,n2), then there doesn't exist (n2,n1)]. This
--   function also preserves edge labels: if two edges exist between two
--   nodes with different edge labels, then both edges will be duplicated.
undir :: (Eq b, DynGraph gr) => gr a b -> gr a b

-- | This is a pseudo-inverse of <a>undir</a>: any edges that are both
--   successor and predecessor become successor edges only.
oneWay :: (DynGraph g, Eq b) => g a b -> g a b

-- | Map over the labels on the nodes, using the node values as well.
nlmap :: (DynGraph gr) => (LNode a -> c) -> gr a b -> gr c b

-- | Spatial positioning of graphs. Use the <a>graphToGraph</a> function in
--   <a>Data.GraphViz</a> to determine potential graph layouts.
--   
--   Pass the plain graph through <a>graphToGraph</a>. This is an IO
--   action, however since the state doesn't change it's safe to use
--   <a>unsafePerformIO</a> to convert this to a normal function.
dotizeGraph :: (DynGraph gr, Ord b) => gr a b -> gr (AttributeNode a) (AttributeEdge b)

-- | Convert the graph into one with positions stored in the node labels.
toPosGraph :: (DynGraph gr, Ord b) => gr a b -> gr (PosLabel a) b

-- | Returns the positions of the nodes in the graph, as found using
--   Graphviz.
getPositions :: (DynGraph gr, Ord b) => gr a b -> [PosLabel a]

-- | Cluster utility functions.
--   
--   Create a cluster-lookup <a>IntMap</a>.
createLookup :: [[Node]] -> IntMap Int

-- | Used when the clusters are assigned in a lookup <a>IntMap</a>
--   instance.
setCluster :: (DynGraph gr) => IntMap Int -> gr a b -> gr (GenCluster a) b

-- | A function to convert an <a>LNode</a> to the required
--   <a>NodeCluster</a> for use with the Graphviz library.
assignCluster :: (ClusterLabel a c) => LNode a -> NodeCluster c a

-- | List utility functions.
--   
--   Return true if and only if the list contains a single element.
single :: [a] -> Bool

-- | If we need to only tell if the list contains more than <tt>n</tt>
--   elements, there's no need to find its length.
longerThan :: Int -> [a] -> Bool

-- | Returns the longest list in a list of lists.
longest :: [[a]] -> [a]

-- | Group elements by the given grouping function.
groupElems :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]

-- | Returns the unique elements of the list in ascending order, as well as
--   the minimum and maximum elements.
sortMinMax :: (Ord a) => [a] -> ([a], a, a)

-- | Attempt to convert a list of elements into a square format in as much
--   of a square shape as possible.
blockPrint :: (Show a) => [a] -> String

-- | Shuffle a list of elements. This isn't the most efficient version, but
--   should serve for small lists. Adapted from:
--   <a>http://www.cse.unsw.edu.au/~tsewell/shuffle.html</a> The adaptation
--   mainly involved altering the code so that the new random seed is also
--   returned.
shuffle :: (RandomGen g) => g -> [a] -> ([a], g)

-- | Statistics functions.
--   
--   An efficient mean function by Don Stewart, available from:
--   <a>http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast</a>
mean :: [Double] -> Double

-- | Calculate the mean and standard deviation of a list of elements.
statistics :: [Double] -> (Double, Double)

-- | Calculate the mean and standard deviation of a list of <a>Int</a>
--   values.
statistics' :: [Int] -> (Int, Int)

-- | Other utility functions.
--   
--   Find the fixed point of a function with the given initial value.
fixPoint :: (Eq a) => (a -> a) -> a -> a

-- | Find the fixed point of a graph transformation function.
fixPointGraphs :: (Eq a, Eq b, Graph g) => (g a b -> g a b) -> g a b -> g a b

-- | Find the fixed point of a function with the given initial value, using
--   the given equality function.
fixPointBy :: (a -> a -> Bool) -> (a -> a) -> a -> a

-- | Squaring a number.
sq :: (Num a) => a -> a

-- | Shorthand for <a>fromIntegral</a>
fI :: (Num a) => Int -> a


-- | A wrapper module around the Haskell <a>Data.GraphViz</a> library to
--   turn Graphs into basic graphs for processing by the Graphviz
--   application.
module Data.Graph.Analysis.Visualisation

-- | Turns the graph into <a>DotGraph</a> format with the given title.
--   Nodes are labelled, edges aren't.
graphviz :: (Graph g, Show a, Ord b) => String -> g a b -> DotGraph

-- | Turns the graph into <a>DotGraph</a> format with the given title.
--   Cluster the nodes based upon their <a>ClusterLabel</a> clusters. Nodes
--   and clusters are labelled, edges aren't.
graphvizClusters :: (Graph g, Show c, ClusterLabel a c, Ord b) => String -> g a b -> DotGraph


-- | Defines algorithms that work on both undirected and directed graphs.
module Data.Graph.Analysis.Algorithms.Common

-- | Find all connected components of a graph.
componentsOf :: (DynGraph g) => g a b -> [g a b]

-- | Find all possible paths from this given node, avoiding loops, cycles,
--   etc.
pathTree :: (DynGraph g) => Decomp g a b -> [NGroup]

-- | Finds all cliques (i.e. maximal complete subgraphs) in the given
--   graph.
cliquesIn :: (Graph g) => g a b -> [[LNode a]]

-- | Finds all cliques in the graph, without including labels.
cliquesIn' :: (Graph g) => g a b -> [NGroup]

-- | Find all regular subgraphs of the given graph.
findRegular :: (Graph g) => g a b -> [[Node]]

-- | Determines if the list of nodes represents a regular subgraph.
isRegular :: (Graph g) => g a b -> NGroup -> Bool

-- | Find all cycles in the given graph.
cyclesIn :: (DynGraph g) => g a b -> [LNGroup a]

-- | Find all cycles in the given graph, returning just the nodes.
cyclesIn' :: (DynGraph g) => g a b -> [NGroup]

-- | Find all cycles in the given graph, excluding those that are also
--   cliques.
uniqueCycles :: (DynGraph g) => g a b -> [LNGroup a]

-- | Find all cycles in the given graph, excluding those that are also
--   cliques.
uniqueCycles' :: (DynGraph g) => g a b -> [NGroup]

-- | Find all chains in the given graph.
chainsIn :: (DynGraph g, Eq b) => g a b -> [LNGroup a]

-- | Find all chains in the given graph.
chainsIn' :: (DynGraph g, Eq b) => g a b -> [NGroup]


-- | Defines algorithms that work on both directed graphs.
module Data.Graph.Analysis.Algorithms.Directed

-- | Determine if this <a>LNode</a> is an ending node.
endNode :: (Graph g) => (g a b -> Node -> NGroup) -> g a b -> LNode a -> Bool

-- | Determine if this <a>Node</a> is an ending node.
endNode' :: (Graph g) => (g a b -> Node -> NGroup) -> g a b -> Node -> Bool

-- | Find all <a>LNode</a>s that meet the ending criteria.
endBy :: (Graph g) => (g a b -> Node -> NGroup) -> g a b -> LNGroup a

-- | Find all <a>Node</a>s that match the ending criteria.
endBy' :: (Graph g) => (g a b -> Node -> NGroup) -> g a b -> NGroup

-- | Find all roots of the graph.
rootsOf :: (Graph g) => g a b -> LNGroup a

-- | Find all roots of the graph.
rootsOf' :: (Graph g) => g a b -> NGroup

-- | Returns <tt>True</tt> if this <a>LNode</a> is a root.
isRoot :: (Graph g) => g a b -> LNode a -> Bool

-- | Returns <tt>True</tt> if this <a>Node</a> is a root.
isRoot' :: (Graph g) => g a b -> Node -> Bool

-- | Find all leaves of the graph.
leavesOf :: (Graph g) => g a b -> LNGroup a

-- | Find all leaves of the graph.
leavesOf' :: (Graph g) => g a b -> NGroup

-- | Returns <tt>True</tt> if this <a>LNode</a> is a leaf.
isLeaf :: (Graph g) => g a b -> LNode a -> Bool

-- | Returns <tt>True</tt> if this <a>Node</a> is a leaf.
isLeaf' :: (Graph g) => g a b -> Node -> Bool

-- | Find all singletons of the graph.
singletonsOf :: (Graph g) => g a b -> LNGroup a

-- | Find all singletons of the graph.
singletonsOf' :: (Graph g) => g a b -> NGroup

-- | Returns <tt>True</tt> if this <a>LNode</a> is a singleton.
isSingleton :: (Graph g) => g a b -> LNode a -> Bool

-- | Returns <tt>True</tt> if this <a>Node</a> is a singleton.
isSingleton' :: (Graph g) => g a b -> Node -> Bool

-- | The <i>core</i> of the graph is the part of the graph containing all
--   the cycles, etc. Depending on the context, it could be interpreted as
--   the part of the graph where all the <a>work</a> is done.
coreOf :: (DynGraph g, Eq a, Eq b) => g a b -> [g a b]


-- | Clustering and grouping algorithms that are graph-invariant and
--   require no user intervention.
module Data.Graph.Analysis.Algorithms.Clustering

-- | An instance of <a>ClusterLabel</a> used for the Chinese Whispers
--   algorithm.
data Whispering a

-- | The actual Chinese Whispers algorithm.
chineseWhispers :: (RandomGen g, Eq a, Eq b, DynGraph gr) => g -> gr a b -> gr (Whispering a) b

-- | The renamed CLUSTER algorithm. Attempts to cluster a graph by using
--   the spatial locations used by Graphviz.
relativeNeighbourhood :: (DynGraph gr, Eq a, Ord b) => gr a b -> gr (GenCluster a) b

-- | A collapsed node contains a list of nodes that it represents.
data CNodes a
CN :: [LNode a] -> CNodes a
collapseGraph :: (DynGraph gr, Eq b) => gr a b -> gr (CNodes a) b
instance (Show a) => Show (Whispering a)
instance (Eq a) => Eq (Whispering a)
instance (Show a) => Show (CNodes a)
instance (Eq a) => Metric (PosLabel a)
instance (Show a) => ClusterLabel (Whispering a) Int


-- | This module exports all the algorithms found in the
--   <tt>Data.Graph.Analysis.Algorithms.*</tt> modules.
module Data.Graph.Analysis.Algorithms

-- | Apply an algorithm to the data to be analysed.
applyAlg :: (AGr a -> b) -> GraphData a -> b


-- | This is the root module of the <i>Graphalyze</i> 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,
--   <i>Graph-Theoretic Analysis of the Relationships in Discrete Data</i>.
module Data.Graph.Analysis

-- | 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 :: [a] -> [(a, a)] -> [a] -> Bool -> ImportParams a

-- | The discrete points.
dataPoints :: ImportParams a -> [a]

-- | The relationships between the points.
relationships :: ImportParams a -> [(a, a)]

-- | The expected roots of the graph. If <tt><a>directed</a> =
--   <a>False</a></tt>, then this is ignored.
roots :: ImportParams a -> [a]

-- | <a>False</a> if relationships are symmetric (i.e. an undirected
--   graph).
directed :: ImportParams a -> Bool

-- | Default values for <a>ImportParams</a>, with no roots and a directed
--   graph.
defaultParams :: ImportParams a

-- | Import data into a format suitable for analysis. This function is
--   <i>edge-safe</i>: if any datums are listed in the edges of
--   <a>ImportParams</a> that aren't listed in the data points, then those
--   edges are ignored. Thus, no sanitation of the <a>relationships</a> in
--   <tt>ImportParams</tt> is necessary.
importData :: (Ord a) => ImportParams a -> GraphData a