g      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ $A Graph-Theoretic Analysis Library. Ivan.Miljenovic@gmail.com $This represents the information that's being passed in that we want F to analyse. If the graph is undirected, it is better to list each * edge once rather than both directions. The library version. Default values for  &, with no roots and a directed graph. CImport data into a format suitable for analysis. This function is   edge-safe+: if any datums are listed in the edges of    that aren'(t listed in the data points, then those 2 edges are ignored. Thus, no sanitation of the   in   ImportParams is necessary. 0Apply a function to the nodes after processing. ; This might be useful in circumstances where you want to 4 reduce the data type used to a simpler one, etc. IReturns the mean and standard deviations of the lengths of the sublists, H as well all those lists more than one standard deviation longer than  the mean. CCompare the actual roots in the graph with those that are expected  (i.e. those in ). Returns (in order): 1 Those roots that are expected (i.e. elements of   that are roots). A Those roots that are expected but not present (i.e. elements of   that aren't roots. - Unexpected roots (i.e. those roots that aren' t present in  ). The discrete points. &The relationships between the points. !The expected roots of the graph.  If   =  , then this is ignored.   if relationships are symmetric  (i.e. an undirected graph).         !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ Graphalyze Types and Classes Ivan.Miljenovic@gmail.com HBy default, the Graphalyze library works on graphs with no edge labels. J As such, these types provide useful aliases for the default FGL types. C Most of the algorithms, however, work on arbitrary graph types. 7Represents information about the graph being analysed. :Label type for storing node positions. Note that this isn't an instance of   since there'.s no clear indication on which cluster a node  belongs to at this stage. A generic cluster-label type. 6These types and classes represent useful label types. 0The class of outputs of a clustering algorithm. 9 This class is mainly used for visualization purposes,  with the  ! instance required for grouping. 3 Instances of this class are intended for use as  the label type of graphs. A grouping of s. ,We use a basic tree-based graph by default. 'The cluster the node label belongs in. &The printed form of the actual label. A grouping of s. )We use a graph type with no edge labels. !The expected roots in the graph.    Utility functions Ivan.Miljenovic@gmail.com(Squaring a number. AFind the fixed point of a function with the given initial value, & using the given equality function. 2Attempt to convert the combined form of a list of Strings ? into as much of a square shape as possible, using the given 7 separation string between elements in the same row. EConvert the graph into one with positions stored in the node labels. (Spatial positioning of graphs. Use the  function in   Data.GraphViz' to determine potential graph layouts. Pass the plain graph through . This is an IO action,  however since the state doesn' t change it's safe to use   ) to convert this to a normal function. Extracting data from graphs. The node number of an . The label of an   Extract the  from the . The label of an   Obtain the labels for a list of s.  It is assumed that each ' is indeed present in the given graph. IFind all the labelled nodes in the graph that match the given predicate. @Find all the nodes in the graph that match the given predicate. Manipulating graphs. Extract the actual  s from an . BMake the graph undirected, i.e. for every edge from A to B, there 6 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 G exist between two nodes with different edge labels, then both edges  will be duplicated. This is a pseudo-inverse of $: any edges that are both successor 0 and predecessor become successor edges only. !AMap over the labels on the nodes, using the node values as well. "JReturns the positions of the nodes in the graph, as found using Graphviz. #Cluster utility functions. Create a cluster-lookup . $0Used when the clusters are assigned in a lookup  instance. %A function to convert an  to the required   for use with the Graphviz library. &List utility functions. ?Return true if and only if the list contains a single element. '7If we need to only tell if the list contains more than n elements,  there's no need to find its length. ( Add the length of each sublist. )-Returns the longest list in a list of lists. */Group elements by the given grouping function. +<Returns the unique elements of the list in ascending order, 0 as well as the minimum and maximum elements. ,Attempt to convert the String form of a list into 9 as much of a square shape as possible, using a single ! space as a separation string. -Attempt to convert a list of Strings into a single String @ that is roughly a square shape, with a single space as a row  separator. .Attempt to convert the String form of a list into < as much of a square shape as possible, separating values  with commas. /Attempt to combine a list of Strings into as much of a < square shape as possible, separating values with commas. 0Attempt to convert the String form of a list into : as much of a square shape as possible, using the given 7 separation string between elements in the same row. 1Shuffle a list of elements.  This isn'@t the most efficient version, but should serve for small lists.  Adapted from:   0http://www.cse.unsw.edu.au/~tsewell/shuffle.html D The adaptation mainly involved altering the code so that the new ! random seed is also returned. 2Statistics functions. ;An efficient mean function by Don Stewart, available from:   5http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast 3ACalculate the mean and standard deviation of a list of elements. 47Calculate the mean and standard deviation of a list of   values. 5Other utility functions. AFind the fixed point of a function with the given initial value. 69Find the fixed point of a graph transformation function. 7Shorthand for   DUsing the given line length and allowed error, take the elements of  the next line. BRecursively build the rest of the line with given maximum length. ( !"#$%&'()*+,-./01234567& !"#$%&'()*+,-./01234567Graphviz wrapper functions Ivan.Miljenovic@gmail.com dPrint a path, with "->" between each element. e!The available Graphviz commands. f3The possible Graphviz outputs, obtained by running  dot -Txxx. C Note that it is not possible to choose between output variants, > and that not all of these may be available on your system. gTurns the graph into  format with the given title. ! Nodes are labelled, edges aren't. hTurns the graph into  format with the given title. & Cluster the nodes based upon their  clusters. . Nodes and clusters are labelled, edges aren't. iFRun the recommended Graphviz command on this graph, saving the result 3 to the file provided (note: file extensions are not checked). jARun the chosen Graphviz command on this graph, saving the result 3 to the file provided (note: file extensions are not checked). k=Print a cycle: copies the first node to the end of the list,  and then calls d. l2Show a group of nodes, with no implicit ordering. This command should not& be available outside this module, as  it isn'=t safe: running an arbitrary command will crash the program.  This function is taken from the mohws project, available under a = 3-Clause BSD license. The actual function is taken from:   )http://code.haskell.org/mohws/src/Util.hs > It provides an efficient way of transferring data from one    to another. 9Internal command to run Graphviz and process the output.  This is not+ to be made available outside this module. 589:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijkl5ghf=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abce89:;<ijdkl Graph analysis algorithms Ivan.Miljenovic@gmail.com/Apply an algorithm to the data to be analysed. $ Algorithms for all graph types. Ivan.Miljenovic@gmail.com$Find all chains in the given graph. ?Determines if the list of nodes represents a regular subgraph. KFind all cycles in the given graph, excluding those that are also cliques. >Find all cycles in the given graph, returning just the nodes.  8Extract the given node and all nodes it is transitively  connected to from the graph. *Find all connected components of a graph. >Find all possible paths from this given node, avoiding loops,  cycles, etc. HFinds all cliques (i.e. maximal complete subgraphs) in the given graph. :Finds all cliques in the graph, without including labels. /Find all regular subgraphs of the given graph. $Find all cycles in the given graph. KFind all cycles in the given graph, excluding those that are also cliques. $Find all chains in the given graph. !9Find the next component and split it off from the graph. "Helper function for   above. #Remove all outgoing edges $9Determine if the given list of nodes is indeed a clique, + and not a smaller subgraph of a clique. %.Extract the next regular subgraph of a graph. &;Returns all regular subgraphs that include the given node. '=Recursively find all regular subgraphs only containing nodes  in the given list. (;Return all nodes that are co-recursive with the given node  (i.e. for n, find all n' such that n->n' and n'->n). )*Find all cycles containing a chosen node. *$Find all cycles for the given node. +'Find the chain starting with the given . ,!Find the next link in the chain. -6Determines if the given node is the start of a chain. .DDetermine if the given node matches the chain criteria in the given A direction, and if so what the next node in that direction is. /!Find the next node in the chain. 0CDetermines if this node matches the successor criteria for chains. 1EDetermines if this node matches the predecessor criteria for chains.  Algorithms for directed graphs. Ivan.Miljenovic@gmail.comDetermine if this  is an ending node. Determine if this  is an ending node.  Find all !s that meet the ending criteria.  Find all "s that match the ending criteria. Find all roots of the graph. Find all roots of the graph. Returns True if this  is a root. Returns True if this  is a root. Find all leaves of the graph. Find all leaves of the graph. Returns True if this  is a leaf. Returns True if this  is a leaf. "Find all singletons of the graph. "Find all singletons of the graph. Returns True if this  is a singleton. Returns True if this  is a singleton. The core: of the graph is the part of the graph containing all the F cycles, etc. Depending on the context, it could be interpreted as ' the part of the graph where all the work is done. $Clustering and grouping algorithms. Ivan.Miljenovic@gmail.com2The original label. 3%The current cluster this node is in. 4EWe take the ceiling of the Euclidian distance function to use as our  metric function. !The Euclidian distance function. >A collapsed node contains a list of nodes that it represents. An instance of * used for the Chinese Whispers algorithm. 'The actual Chinese Whispers algorithm. EThe renamed CLUSTER algorithm. Attempts to cluster a graph by using + the spatial locations used by Graphviz. This definition of 5 , is written so as to make the shapes of the E nodes in Graphviz roughly circular, rather than one long ellipse. 6The node' s weighting. 7#Choose a new cluster for the given . Note that this updates 6 the graph each time a new cluster value is chosen. 8#Choose a new cluster for the given Context. 9CChoose which cluster to pick by taking the one with maximum sum of B weightings. If more than one has the same maximum, choose one  randomly. :KConvert the graph into a form suitable for the Chinese Whispers algorithm. ;,Converts the positional labels into an RNG. <BDetermines if the two given nodes should be connected in the RNG. K Nodes are connected if there is no node that is closer to both of them. =5Performs the actual clustering algorithm on the RNG. >!Allow the graph to be collapsed. ?,Collapse the two given nodes into one node. @-Collapse the list of nodes down to one node. A,Collapse all results of the given function. Graphalyze Types and Classes Ivan.Miljenovic@gmail.com o?Representation of a document. The document is to be stored in  the directory !, and the main file is to have a  filename of  B ( dg), where dg is an  instance of . pARepresentation of a location, either on the internet or locally. rElements of a document. t Return today's date as a string, e.g. "Monday 1 January, 2000". 1 This arbitrary format is chosen as there doesn't seem to be a way 4 of determining the correct format as per the user's locale settings. u5Attempts to create the specified directly, returning True 7 if successful (or if the directory already exists), False  if an error occurred. v?Attempts to creates a png file (with the given filename in the 4 given directory) and - if successful - returns a  link. -Represents the class of document generators. Convert idealised o values into actual documents, ( returning the document file created. >The extension of all document-style files created. Note that  this doesn'5t preclude the creation of other files, e.g. images. Document location  Pre-matter  Main-matter !mnopqrstuvwxyz{|}~!opmnr~}q|{zyxwstuvGraphalyze Types and Classes Ivan.Miljenovic@gmail.com C-Used when traversing the document structure. D Define the EF used. GStart with a level 1 heading. HCreate the document. IThe meta information JHtml output doesn'2t show the author and date; use this to print it. KLink conversion L&Conversion of simple inline elements. M3Conversion of complex elements. The only reason it's in the IO monad is : for GraphImage, as it requires IO to create the image. 1If any one of the conversions fail (i.e. returns N ), the entire  process fails. DIn future, may extend this to creating multiple files for top-level E sections, in which case the IO monad will be required for that as  well. O,Concatenate the result of multiple calls to M. PAs for O , but don't concat the resulting Qs. R !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~         !"#$%&'()*+,-./ 01 2345 6 789:;;<= 2>?@ABCDEFGHIJKLMNOPQRST UVWXYZ[\]^_`abcdefgfghijklmn opqrsGraphalyze-0.3Data.Graph.Analysis.TypesData.Graph.Analysis.Utils!Data.Graph.Analysis.VisualisationData.Graph.Analysis.Reporting$Data.Graph.Analysis.Reporting.Pandoc%Data.Graph.Analysis.Algorithms.Common'Data.Graph.Analysis.Algorithms.Directed)Data.Graph.Analysis.Algorithms.ClusteringData.Graph.Analysis.AlgorithmsData.Graph.Analysisbase Data.BoolData.Ord fgl-5.4.1.1Data.Graph.Inductive.Graphgraphviz-2008.9.20 Data.GraphVizForeigncontainers-0.1.0.1 Data.IntMapGHC.ExtsPrelude System.IOfilepath-1.1.0.0System.FilePath.Posixpandoc-1.0.0.1 Text.Pandoc Data.MaybeText.Pandoc.Definition GraphDataPLabelPosLabelGC GenCluster ClusterLabelLNGroupAGrxPosyPospnodeplabelcluster nodelabelNGroupgraph wantedRootssq fixPointByblockPrintWith' toPosGraph dotizeGraphnodelabeledgeeLabel addLabels filterNodes filterNodes' pathValuesundironeWaynlmap getPositions createLookup setCluster assignClustersingle longerThan addLengthslongest groupElems sortMinMax blockPrint blockPrint'blockPrintListblockPrintList'blockPrintWithshufflemean statistics statistics'fixPointfixPointGraphsfIFdpCircoTwoPiNeatoDotCmdXlibXdotWbmpVtxVrmlVmlzVmlTkSvgzSvgPs2PsPngPlainExtPlainPicPdfPclMpMifJpgJpegJpeIsmapImap_npImapHpglGtkGifGd2GdFigEps DotOutputDiaCmapx_npCmapxCmapCanonshowPathGraphvizCommandGraphvizOutputgraphvizgraphvizClusters runGraphvizrunGraphvizCommand showCycle showNodesFileURLDocumentLocation DocInline DocElementDocGraphtodaytryCreateDirectory createGraphText BlankSpaceGroupingBoldEmphasisDocLinkSection Paragraph EnumerationItemized DefinitionDocImage GraphImageDocumentGeneratorcreateDocument docExtension rootDirectory fileFronttitleauthordatecontentDocPandocDocument pandocHtml pandocLaTeX pandocRtfpandocMarkdown chainsIn' isRegular uniqueCycles' cyclesIn' componentsOfpathTree cliquesIn cliquesIn' findRegularcyclesIn uniqueCycleschainsInendNodeendNode'endByendBy'rootsOfrootsOf'isRootisRoot'leavesOf leavesOf'isLeafisLeaf' singletonsOf singletonsOf' isSingleton isSingleton'coreOfCNCNodes WhisperingchineseWhispersrelativeNeighbourhood collapseGraphapplyAlg ImportParamsversion defaultParams importDatamanipulateNodeslengthAnalysis classifyRoots dataPoints relationshipsrootsdirectedParamsGHC.BaseFalseData.Graph.Inductive.TreeGrUEdgePathLPUPathUDecomplabEdges nodeRangenoNodesmatchAnylabNodesmkGraphmatchisEmptyempty&equaldeg'indeg'outdeg'inn'out'lpre'lsuc'pre'suc' neighbors'labNode'lab'node'degindegoutdeginnoutlprelsucpresuc neighborslabcontextmkUGraphbuildGrdelEdgesinsEdgesinsNodesdelLEdgedelEdgedelNodeinsEdgeinsNodegelemnewNodesedgesnodesemapnmapgmapufoldGraphContextDynGraphNodeEdgeLNodeLEdgedelNodesAdjDecompGDecompUContextMContextUNodeLPath AttributeNode AttributeEdgeOrd graphToGraph GHC.IOBaseunsafePerformIOIntMap NodeClusterIntGHC.Real fromIntegraltakeLentakeLineDotGraphrunGraphvizInternalsquirtHandlegraphvizWithHandle extractNodesplitComponent nodeExtractormakeLeafisClique findRegularOf regularOf alsoRegular corecursive findCycles cyclesForgetChain chainLink isChainStart chainFind chainNexthasNexthasPrevnamewhisp euclidianGHC.Showshowcoeff whisperNodewhisper chooseWhisper addWhispersmakeRNG areRelative nbrClustermakeCollapsiblecollapse collapseAll collapseAllBy<.> PandocProcess writerOptionsText.Pandoc.Shared WriterOptionsdefaultProcess createPandocmakeMetahtmlInfo loc2targetinlineselementsNothing multiElems multiElems'Block