-- 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.7.0.0


-- | This module defines the report framework used.
module Data.Graph.Analysis.Reporting

-- | Representation of a document. The document is to be stored in the
--   directory <a>rootDirectory</a>, and the main file is to have a
--   filename of <tt><a>fileFront</a> <a>&lt;.&gt;</a> (<a>docExtension</a>
--   dg)</tt>, where <tt>dg</tt> is an instance of
--   <a>DocumentGenerator</a>.
data Document
Doc :: FilePath -> String -> FilePath -> DocInline -> String -> String -> [DocElement] -> Document

-- | Document location
rootDirectory :: Document -> FilePath
fileFront :: Document -> String

-- | The sub-directory of <a>rootDirectory</a>, where graphs are to be
--   created.
graphDirectory :: Document -> FilePath

-- | Pre-matter
title :: Document -> DocInline
author :: Document -> String
date :: Document -> String

-- | Main-matter
content :: Document -> [DocElement]

-- | Represents the class of document generators.
class DocumentGenerator dg
createDocument :: (DocumentGenerator dg) => dg -> Document -> IO (Maybe FilePath)
docExtension :: (DocumentGenerator dg) => dg -> String

-- | Representation of a location, either on the internet or locally.
data Location
Web :: String -> Location
File :: FilePath -> Location

-- | Elements of a document.
data DocElement
Section :: DocInline -> [DocElement] -> DocElement
Paragraph :: [DocInline] -> DocElement
Enumeration :: [DocElement] -> DocElement
Itemized :: [DocElement] -> DocElement
Definition :: DocInline -> DocElement -> DocElement
GraphImage :: DocGraph -> DocElement

-- | Inline elements of a document.
data DocInline
Text :: String -> DocInline
BlankSpace :: DocInline
Grouping :: [DocInline] -> DocInline
Bold :: DocInline -> DocInline
Emphasis :: DocInline -> DocInline
DocLink :: DocInline -> Location -> DocInline
DocImage :: DocInline -> Location -> DocInline

-- | Specify the size the <a>DotGraph</a> should be at.
data GraphSize

-- | Specify the size to use.
GivenSize :: Point -> GraphSize

-- | Let GraphViz choose an appropriate size.
DefaultSize :: GraphSize

-- | Specify the <a>DotGraph</a> to turn into an image, its filename (sans
--   extension) and its caption. The <a>DotGraph</a> should not have a
--   <a>Size</a> set.
type DocGraph = (FilePath, DocInline, DotGraph Node)

-- | Return today's date as a string, e.g. "Monday 1 January, 2000". This
--   arbitrary format is chosen as there doesn't seem to be a way of
--   determining the correct format as per the user's locale settings.
today :: IO String

-- | Attempts to create the specified directly, returning <tt>True</tt> if
--   successful (or if the directory already exists), <tt>False</tt> if an
--   error occurred.
tryCreateDirectory :: FilePath -> IO Bool

-- | Attempts to creates a png file (with the given filename in the given
--   directory) from the graph using the given attributes. If the second
--   set of attributes is not <a>Nothing</a>, then the first image links to
--   the second. The whole result is wrapped in a <a>Paragraph</a>.
createGraph :: FilePath -> FilePath -> GraphSize -> Maybe GraphSize -> DocGraph -> IO (Maybe DocElement)

-- | Using a 6:4 ratio, create the given <a>Point</a> representing
--   width,height from the width.
createSize :: Double -> GraphSize

-- | Replace all <tt>.</tt> with <tt>-</tt> in the given <a>FilePath</a>,
--   since some output formats (e.g. LaTeX) don't like extraneous
--   <tt>.</tt>'s in the filename.
unDotPath :: FilePath -> FilePath
instance Show Location


-- | This module uses <i>Pandoc</i> to generate documents:
--   <a>http://johnmacfarlane.net/pandoc/</a>
--   
--   Note that Pandoc is released under GPL-2 or later, however according
--   to the Free Software Foundation, I am indeed allowed to use it:
--   <a>http://www.fsf.org/licensing/licenses/gpl-faq.html#IfLibraryIsGPL</a>
--   since the 2-Clause BSD license that I'm using is GPL-compatible:
--   <a>http://www.fsf.org/licensing/licenses/index_html#GPLCompatibleLicenses</a>
--   (search for <i>FreeBSD License</i>, which is another name for it).
module Data.Graph.Analysis.Reporting.Pandoc

-- | Definition of a Pandoc Document. Size measurements are in inches, and
--   a 6:4 ratio is used for width:length.
data PandocDocument
pandocHtml :: PandocDocument
pandocLaTeX :: PandocDocument
pandocRtf :: PandocDocument
pandocMarkdown :: PandocDocument
instance DocumentGenerator PandocDocument


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

-- | Represents information about the graph being analysed.
data GraphData n e
GraphData :: AGr n e -> NGroup -> Bool -> [Rel n e] -> GraphData n e

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

-- | The expected root nodes in the graph.
wantedRootNodes :: GraphData n e -> NGroup

-- | Is the data this graph represents directed in nature?
directedData :: GraphData n e -> Bool

-- | Unused relationships (i.e. not in the actual graph). These are the
--   edges containing nodes not in the graph.
unusedRelationships :: GraphData n e -> [Rel n e]

-- | An alias for the type of graph being used by default.
type AGr n e = Gr n e

-- | A relationship between two nodes with a label.
type Rel n e = (n, n, e)

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

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

-- | The expected roots in the data to be analysed.
wantedRoots :: GraphData n e -> LNGroup n

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

-- | Apply an algorithm that requires knowledge about whether the graph is
--   directed (<a>True</a>) or undirected (<a>False</a>) to the data to be
--   analysed.
applyDirAlg :: (Bool -> AGr n e -> a) -> GraphData n e -> a

-- | Merge the <a>unusedRelationships</a> into the graph by adding the
--   appropriate nodes.
mergeUnused :: (Ord n, Ord e) => GraphData n e -> GraphData n e

-- | Used to set <tt><a>unusedRelationships</a> = []</tt>. This is of use
--   when they are unneeded or because there is no sensible mapping
--   function to use when applying a mapping function to the nodes in the
--   graph.
removeUnused :: GraphData n e -> GraphData n e

-- | Replace the current graph by applying a function to it. To ensure type
--   safety, <a>removeUnused</a> is applied.
updateGraph :: (AGr a b -> AGr c d) -> GraphData a b -> GraphData c d

-- | Replace the current graph by applying a function to it, where the
--   function depends on whether the graph is directed (<a>True</a>) or
--   undirected (<a>False</a>). To ensure type safety, <a>removeUnused</a>
--   is applied.
updateGraph' :: (Bool -> AGr a b -> AGr c d) -> GraphData a b -> GraphData c d

-- | Apply a function to all the data points. This might be useful in
--   circumstances where you want to reduce the data type used to a simpler
--   one, etc. The function is also applied to the datums in
--   <a>unusedRelationships</a>.
mapAllNodes :: (Ord a, Ord e, Ord b) => (a -> b) -> GraphData a e -> GraphData b e

-- | Apply the first function to nodes in the graph, and the second
--   function to those unknown datums in <a>unusedRelationships</a>. As a
--   sample reason for this function, it can be used to apply a two-part
--   constructor (e.g. <a>Left</a> and <a>Right</a> from <a>Either</a>) to
--   the nodes such that the wanted and unwanted datums can be
--   differentiated before calling <a>mergeUnused</a>.
mapNodeType :: (Ord a, Ord b, Ord e) => (a -> b) -> (a -> b) -> GraphData a e -> GraphData b e

-- | 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 (ClusterType (Cluster cl)) => ClusterLabel cl where { type family Cluster cl; type family NodeLabel cl; }
cluster :: (ClusterLabel cl) => cl -> Cluster cl
nodeLabel :: (ClusterLabel cl) => cl -> NodeLabel cl

-- | A class used to define which types are valid for clusters.
class (Ord c) => ClusterType c
clusterID :: (ClusterType c) => c -> Maybe GraphID

-- | A generic cluster-label type.
data GenCluster a
GC :: Int -> a -> GenCluster a
clust :: GenCluster a -> Int
nLbl :: GenCluster a -> 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 (Eq a) => Eq (GenCluster a)
instance (Show a) => Show (GenCluster a)
instance ClusterLabel (GenCluster a)
instance ClusterType String
instance ClusterType Int


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

-- | The node number of an <a>LNode</a>.
node :: LNode a -> Node

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

-- | The labels of all nodes in a tree.
labels :: (Graph g) => g a b -> [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]

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

-- | Makes the graph a simple one, by removing all duplicate edges and
--   loops. The edges removed if duplicates exist are arbitrary.
mkSimple :: (DynGraph gr) => gr a b -> gr a b

-- | Adjoin duplicate edges by grouping the labels together.
compact :: (DynGraph gr) => gr a b -> gr a [b]

-- | Compact the graph by counting how many multiple edges there are
--   (considering only the two nodes and not the labels).
compact' :: (DynGraph gr) => gr a b -> gr a Int

-- | Compact the graph by adjoining identical duplicate edges.
compactSame :: (Ord b) => (DynGraph gr) => gr a b -> gr a (Int, 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

-- | Delete these labelled nodes from the graph.
delLNodes :: (DynGraph gr) => LNGroup a -> gr a b -> gr a b

-- | Convert the graph into one with positions stored in the node labels.
--   The <a>Bool</a> parameter denotes if the graph is directed or not.
toPosGraph :: (DynGraph gr, Ord b) => Bool -> gr a b -> gr (PosLabel a) b

-- | Returns the positions of the nodes in the graph, as found using
--   Graphviz. The <a>Bool</a> parameter denotes if the graph is directed
--   or not.
getPositions :: (DynGraph gr, Ord b) => Bool -> gr a b -> [PosLabel a]

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

-- | Change the cluster values in the graph by having the largest cluster
--   have the smallest cluster label.
reCluster :: (DynGraph g) => g (GenCluster a) b -> g (GenCluster a) b

-- | Change the cluster values using the given lookup <a>IntMap</a>.
reClusterBy :: (DynGraph g) => IntMap Int -> g (GenCluster a) b -> g (GenCluster a) b

-- | Create an <a>IntMap</a> of the size of each cluster.
clusterCount :: (Graph g) => g (GenCluster a) b -> IntMap Int

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

-- | Add the length of each sublist.
addLengths :: [[a]] -> [(Int, [a])]

-- | Returns the longest list in a list of lists.
longest :: [[a]] -> [a]
lengthSort :: [[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)

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

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

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


-- | Functions to assist in visualising graphs and components of graphs.
module Data.Graph.Analysis.Visualisation

-- | Convert the <a>GraphData</a> into <a>DotGraph</a> format with the
--   given <a>Attribute</a>s.
graphviz :: GraphData n e -> [GlobalAttributes] -> (LNode n -> Attributes) -> (LEdge e -> Attributes) -> DotGraph Node

-- | Convert the clustered <a>GraphData</a> into <a>DotGraph</a> format
--   with the given <a>Attribute</a>s. Cluster the nodes based upon their
--   <a>ClusterLabel</a> clusters.
graphvizClusters :: (ClusterLabel cl) => GraphData cl e -> [GlobalAttributes] -> (Cluster cl -> [GlobalAttributes]) -> (LNode (NodeLabel cl) -> Attributes) -> (LEdge e -> Attributes) -> DotGraph Node

-- | Convert the <a>GraphData</a> into a clustered <a>DotGraph</a> format
--   using the given clustering function and with the given
--   <a>Attribute</a>s.
graphvizClusters' :: (Ord c) => GraphData n e -> [GlobalAttributes] -> (LNode n -> NodeCluster c l) -> (c -> Maybe GraphID) -> (c -> [GlobalAttributes]) -> (LNode l -> Attributes) -> (LEdge e -> Attributes) -> DotGraph Node

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

-- | Used to state that GraphViz should use the default <a>Attribute</a>s
--   for the given value.
noAttributes :: a -> Attributes

-- | Print a path, with "-&gt;" between each element.
showPath :: (Show a) => [a] -> String

-- | Print a path, with "-&gt;" between each element.
showPath' :: (a -> String) -> [a] -> String

-- | Print a cycle: copies the first node to the end of the list, and then
--   calls <a>showPath</a>.
showCycle :: (Show a) => [a] -> String

-- | Print a cycle: copies the first node to the end of the list, and then
--   calls <a>showPath'</a>.
showCycle' :: (a -> String) -> [a] -> String

-- | Show a group of nodes, with no implicit ordering.
showNodes :: (Show a) => [a] -> String

-- | Show a group of nodes, with no implicit ordering.
showNodes' :: (a -> String) -> [a] -> String

-- | Attempt to convert the <tt>String</tt> form of a list into as much of
--   a square shape as possible, using a single space as a separation
--   string.
blockPrint :: (Show a) => [a] -> String

-- | Attempt to convert a list of <tt>String</tt>s into a single
--   <tt>String</tt> that is roughly a square shape, with a single space as
--   a row separator.
blockPrint' :: [String] -> String

-- | Attempt to convert the <tt>String</tt> form of a list into as much of
--   a square shape as possible, separating values with commas.
blockPrintList :: (Show a) => [a] -> String

-- | Attempt to combine a list of <tt>String</tt>s into as much of a square
--   shape as possible, separating values with commas.
blockPrintList' :: [String] -> String

-- | Attempt to convert the <tt>String</tt> form of a list into as much of
--   a square shape as possible, using the given separation string between
--   elements in the same row.
blockPrintWith :: (Show a) => String -> [a] -> String

-- | Attempt to convert the combined form of a list of <tt>String</tt>s
--   into as much of a square shape as possible, using the given separation
--   string between elements in the same row.
blockPrintWith' :: String -> [String] -> String


-- | 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 :: (DynGraph g) => g a b -> [[LNode a]]

-- | Finds all cliques in the graph, without including labels.
cliquesIn' :: (DynGraph 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 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

-- | Cluster the nodes in the graph based upon how far away they are from a
--   root node. Root nodes are in the cluster labelled <a>0</a>, nodes in
--   level <a>n</a> are at least <i>n</i> edges away from a root node.
levelGraph :: (Ord a) => (DynGraph g) => g a b -> g (GenCluster a) b

-- | The shortest paths to each of the leaves in the graph (excluding
--   singletons). This can be used to obtain an indication of the overall
--   height/depth of the graph.
leafMinPaths :: (Graph g) => g a b -> [LNGroup a]


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

-- | The actual Chinese Whispers algorithm.
chineseWhispers :: (RandomGen g, Eq a, Eq b, DynGraph gr) => g -> gr a b -> gr (GenCluster 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) => Bool -> gr a b -> gr (GenCluster a) b

-- | A collapsed node contains a list of nodes that it represents.
type CNodes a = [a]

-- | Collapse the cliques, cycles and chains in the graph down. Note that
--   this doesn't work too well on undirected graphs, since every pair of
--   nodes forms a K_2 subgraph.
collapseGraph :: (DynGraph gr, Eq b) => gr a b -> gr (CNodes a) b

-- | Use the given functions to determine which nodes to collapse.
collapseGraphBy :: (DynGraph gr) => [gr (CNodes a) b -> [NGroup]] -> gr a b -> gr (CNodes a) b

-- | Use the given functions to determine which nodes to collapse, with a
--   new label to represent the collapsed nodes.
collapseGraphBy' :: (DynGraph gr) => [gr a b -> [(NGroup, a)]] -> gr a b -> gr a b

-- | Return <tt><a>True</a></tt> if the collapsed graph is either a
--   singleton node or else isomorphic to the original graph (i.e. not
--   collapsed at all).
trivialCollapse :: (Graph gr) => gr (CNodes a) b -> Bool
instance (Eq a) => Metric (PosLabel a)


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


-- | 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.
--   
--   The original version of this library was written as part of my
--   mathematics honours thesis, <i>Graph-Theoretic Analysis of the
--   Relationships in Discrete Data</i>.
module Data.Graph.Analysis

-- | The library version.
version :: String

-- | 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 n e
Params :: [n] -> [Rel n e] -> [n] -> Bool -> ImportParams n e

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

-- | The relationships between the points.
relationships :: ImportParams n e -> [Rel n e]

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

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

-- | 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. The unused relations are stored in
--   <a>unusedRelationships</a>. Note that it is assumed that all datums in
--   <a>roots</a> are also contained within <a>dataPoints</a>.
importData :: (Ord n, Ord e) => ImportParams n e -> GraphData n e

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

-- | Compare the actual roots in the graph with those that are expected
--   (i.e. those in <a>wantedRoots</a>). Returns (in order):
--   
--   <ul>
--   <li>Those roots that are expected (i.e. elements of <a>wantedRoots</a>
--   that are roots).</li>
--   <li>Those roots that are expected but not present (i.e. elements of
--   <a>wantedRoots</a> that <i>aren't</i> roots.</li>
--   <li>Unexpected roots (i.e. those roots that aren't present in
--   <a>wantedRoots</a>).</li>
--   </ul>
classifyRoots :: (Ord n) => GraphData n e -> ([LNode n], [LNode n], [LNode n])

-- | Only return those chains (see <a>chainsIn</a>) where the non-initial
--   nodes are <i>not</i> expected roots.
interiorChains :: (Eq n, Eq e) => GraphData n e -> [LNGroup n]