-- 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.11.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> <tt>&lt;.&gt;</tt>
--   (<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 -> [(Either DocGraph DocInline, DocInline)] -> [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
legend :: Document -> [(Either DocGraph DocInline, DocInline)]
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
Definitions :: [(DocInline, DocInline)] -> 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.
data DocGraph
DG :: FilePath -> DocInline -> DotGraph Node -> DocGraph

-- | What name to provide the image file (without an extension).
imageFile :: DocGraph -> FilePath
description :: DocGraph -> DocInline
dotGraph :: DocGraph -> DotGraph Node

-- | Defines the parameters used for creating visualisations of graphs.
data VisParams
VParams :: FilePath -> FilePath -> VisProperties -> Maybe VisProperties -> Bool -> VisParams

-- | Root directory of the document.
rootDir :: VisParams -> FilePath

-- | Image sub-directory.
graphDir :: VisParams -> FilePath

-- | The default visualisation.
defaultImage :: VisParams -> VisProperties

-- | If <tt><a>Just</a> vp'</tt>, then a larger visualisation is linked to
--   from the default one.
largeImage :: VisParams -> Maybe VisProperties

-- | Should the Dot source code be saved as well?
saveDot :: VisParams -> Bool

-- | A specification on how to visualise a <a>DocGraph</a>.
data VisProperties
VProps :: GraphSize -> GraphvizOutput -> VisProperties
size :: VisProperties -> GraphSize
format :: VisProperties -> GraphvizOutput

-- | Create the legend section and add it to the document proper.
addLegend :: FilePath -> FilePath -> VisProperties -> Document -> IO Document

-- | 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 create image files (with the given filename in the given
--   directory) from the graph. If the second <a>VisProperties</a> not
--   <a>Nothing</a>, then the first image links to the second. The whole
--   result is wrapped in a <a>Paragraph</a>. <a>unDotPath</a> is applied
--   to the filename in the <a>DocGraph</a>.
createGraph :: VisParams -> DocGraph -> IO 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 Eq GraphSize
instance Ord GraphSize
instance Show GraphSize
instance Read GraphSize
instance Eq VisProperties
instance Ord VisProperties
instance Show VisProperties
instance Read VisProperties
instance Eq VisParams
instance Ord VisParams
instance Show VisParams
instance Read VisParams
instance Eq DocGraph
instance Ord DocGraph
instance Show DocGraph
instance Read DocGraph
instance Eq DocInline
instance Ord DocInline
instance Show DocInline
instance Read DocInline
instance Eq DocElement
instance Ord DocElement
instance Show DocElement
instance Read DocElement
instance Eq Location
instance Ord Location
instance Show Location
instance Read Location
instance Eq Document
instance Ord Document
instance Show Document
instance Read Document


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

-- | Also save the generated Dot code to file when creating visualisations.
alsoSaveDot :: PandocDocument -> PandocDocument
instance Eq PandocProcess
instance Ord PandocProcess
instance Show PandocProcess
instance Read PandocProcess
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

-- | Add extra expected root nodes. No checks are made that these are valid
--   <a>Node</a> values.
addRoots :: GraphData n e -> NGroup -> GraphData n e

-- | Use a filtering function to find extra root nodes to add.
addRootsBy :: (LNode n -> Bool) -> GraphData n e -> GraphData n e

-- | 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
clustID :: ClusterType c => c -> Maybe GraphID

-- | A polymorphic type that covers all possible ID values allowed by Dot
--   syntax. Note that whilst the <a>ParseDot</a> and <a>PrintDot</a>
--   instances for <a>String</a> will properly take care of the special
--   cases for numbers, they are treated differently here.
data GraphID :: *
Str :: String -> GraphID
Int :: Int -> GraphID
Dbl :: Double -> 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]

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

-- | 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.
getLabels :: Graph g => g a b -> [Node] -> [a]

-- | 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.
getLabels' :: (Ord a, Graph g) => g a b -> Set Node -> Set 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
--   <tt>Data.Graph.Inductive.Basic.undir</tt> 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.
graphviz :: Ord cl => GraphvizParams nl el cl l -> GraphData nl el -> DotGraph Node

-- | Convert the clustered <a>GraphData</a> into <a>DotGraph</a> format.
--   Cluster the nodes based upon their <a>ClusterLabel</a> clusters.
graphvizClusters :: ClusterLabel nl => GraphvizParams nl el (Cluster nl) (NodeLabel nl) -> GraphData nl el -> DotGraph Node

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

-- | A cross between <a>applyDirAlg</a> and <a>setDirectedness</a>.
setDir :: (GraphvizParams nl el cl l -> AGr nl el -> a) -> GraphvizParams nl el cl l -> GraphData nl el -> a

-- | 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>minLevel</a>,
--   nodes in level "n" (with <tt>n &gt; minLevel</tt>) are at least
--   <i>n</i> edges away from a root node.
levelGraph :: (Ord a, DynGraph g) => g a b -> g (GenCluster a) b

-- | As with <a>levelGraph</a> but provide a custom grouping of
--   <a>Node</a>s to consider as the "roots".
levelGraphFrom :: (Ord a, DynGraph g) => NGroup -> g a b -> g (GenCluster a) b

-- | The level of the nodes in the <a>NGroup</a> provided to
--   <a>levelGraphFrom</a> (or the root nodes for <a>levelGraph</a>). A
--   level less than this indicates that the node is not accessible.
minLevel :: Int

-- | Find all <a>Node</a>s that can be reached from the provided
--   <a>Node</a>s.
accessibleFrom :: Graph g => g a b -> [Node] -> [Node]

-- | Find all <a>Node</a>s that can be reached from the provided nodes
--   using <a>Set</a>s rather than lists.
accessibleFrom' :: Graph g => g a b -> Set Node -> Set Node

-- | Find those <a>Node</a>s that are reachable only from the provided
--   <a>Node</a>s.
accessibleOnlyFrom :: Graph g => g a b -> [Node] -> [Node]

-- | Find those <a>Node</a>s that are reachable only from the provided
--   <a>Node</a>s, using <a>Set</a>s rather than lists.
accessibleOnlyFrom' :: Graph g => g a b -> Set Node -> Set Node

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

-- | 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 -> [NGroup]


-- | Clustering and grouping algorithms that are graph-invariant and
--   require no user intervention.
--   
--   For a clustering algorithm that works only on directed graphs, see
--   <tt>levelGraph</tt> in <a>Data.Graph.Analysis.Algorithms.Directed</a>.
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.
collapseAndReplace :: DynGraph gr => [gr a b -> [(NGroup, a)]] -> gr a b -> gr a b

-- | As with <a>collapseAndReplace</a>, but also return the
--   <tt>(<a>NGroup</a>, a)</tt>'s calculated with the functions provided.
collapseAndReplace' :: DynGraph gr => [gr a b -> [(NGroup, a)]] -> gr a b -> (gr a b, [(NGroup, a)])

-- | 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
ImpParams :: [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>wantedRootNodes</a>). Returns (in order):
--   
--   <ul>
--   <li>Those roots that are expected (i.e. elements of
--   <a>wantedRootNodes</a> that are roots).</li>
--   <li>Those roots that are expected but not present (i.e. elements of
--   <a>wantedRootNodes</a> that <i>aren't</i> roots.</li>
--   <li>Unexpected roots (i.e. those roots that aren't present in
--   <a>wantedRootNodes</a>).</li>
--   </ul>
classifyRoots :: GraphData n e -> (Set Node, Set Node, Set Node)

-- | Find the nodes that are not reachable from the expected roots (i.e.
--   those in <a>wantedRootNodes</a>).
inaccessibleNodes :: GraphData n e -> Set Node

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

-- | As with <a>collapseAndReplace</a>, but also update the
--   <a>wantedRootNodes</a> to contain the possibly compressed nodes. Since
--   the datums they refer to may no longer exist (as they are compressed),
--   <a>unusedRelationships</a> is set to <tt>[]</tt>.
collapseAndUpdate :: Ord n => [AGr n e -> [(NGroup, n)]] -> GraphData n e -> GraphData n e

-- | As with <a>collapseAndUpdate</a>, but also includes a lookup
--   <a>Map</a> from the old label to the new.
collapseAndUpdate' :: Ord n => [AGr n e -> [(NGroup, n)]] -> GraphData n e -> (GraphData n e, Map n n)

-- | As with <a>levelGraph</a>, but use the expected roots rather than the
--   actual roots.
levelGraphFromRoot :: Ord n => GraphData n e -> GraphData (GenCluster n) e