`      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_Graphalyze Types and Classes Ivan.Miljenovic@gmail.com :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. 'The cluster the node label belongs in. &The printed form of the actual label. A grouping of a s. A grouping of b s. ,We use a basic tree-based graph by default. 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. )We use a graph type with no edge labels. !The expected roots in the graph. c   Utility functions Ivan.Miljenovic@gmail.com"Extracting data from graphs. The node number of an a . The label of an a   Extract the d  from the e . The label of an e   Obtain the labels for a list of b s.  It is assumed that each b ' 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 a  s from an f . 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. (Spatial positioning of graphs. Use the g  function in   Data.GraphViz' to determine potential graph layouts. Pass the plain graph through g . This is an IO action,  however since the state doesn' t change it's safe to use h  ) to convert this to a normal function. EConvert the graph into one with positions stored in the node labels. JReturns the positions of the nodes in the graph, as found using Graphviz. Cluster utility functions. Create a cluster-lookup i. !0Used when the clusters are assigned in a lookup i instance. "A function to convert an a  to the required j   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. %-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 a list of elements into a square format - in as much of a square shape as possible. kDUsing the given line length and allowed error, take the elements of  the next line. lBRecursively build the rest of the line with given maximum length. )Shuffle 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. *Statistics functions. ;An efficient mean function by Don Stewart, available from:   5http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast +ACalculate the mean and standard deviation of a list of elements. ,7Calculate the mean and standard deviation of a list of m values. -Other utility functions. AFind the fixed point of a function with the given initial value. .AFind the fixed point of a function with the given initial value, & using the given equality function. /9Find the fixed point of a graph transformation function. 0Squaring a number. 1Shorthand for n  "op !"#$%&'()*+,-./01  !"#$%&'()*+,-/.01Graphviz wrapper functions Ivan.Miljenovic@gmail.com2Turns the graph into q r  format with the given title. ! Nodes are labelled, edges aren't. 3Turns the graph into q r  format with the given title. & Cluster the nodes based upon their  clusters. . Nodes and clusters are labelled, edges aren't. 2323 Algorithms for all graph types. Ivan.Miljenovic@gmail.com4*Find all connected components of a graph. s9Find the next component and split it off from the graph. t8Extract the given node and all nodes it is transitively  connected to from the graph. uHelper function for t above. 5>Find all possible paths from this given node, avoiding loops,  cycles, etc. vRemove all outgoing edges 6HFinds all cliques (i.e. maximal complete subgraphs) in the given graph. 7:Finds all cliques in the graph, without including labels. w9Determine if the given list of nodes is indeed a clique, + and not a smaller subgraph of a clique. 8/Find all regular subgraphs of the given graph. x.Extract the next regular subgraph of a graph. y;Returns all regular subgraphs that include the given node. z=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). 9?Determines if the list of nodes represents a regular subgraph. :$Find all cycles in the given graph. ;>Find all cycles in the given graph, returning just the nodes. <KFind all cycles in the given graph, excluding those that are also cliques. =KFind all cycles in the given graph, excluding those that are also cliques. |*Find all cycles containing a chosen node. }$Find all cycles for the given node. >$Find all chains in the given graph. ?$Find all chains in the given graph. ~'Find the chain starting with the given b . !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. CDetermines if this node matches the successor criteria for chains. EDetermines if this node matches the predecessor criteria for chains. 456789:;<=>? 456789:;<=>? Algorithms for directed graphs. Ivan.Miljenovic@gmail.com@Determine if this a  is an ending node. ADetermine if this b  is an ending node. B Find all a !s that meet the ending criteria. C Find all b "s that match the ending criteria. DFind all roots of the graph. EFind all roots of the graph. FReturns True if this a  is a root. GReturns True if this b  is a root. HFind all leaves of the graph. IFind all leaves of the graph. JReturns True if this a  is a leaf. KReturns True if this b  is a leaf. L"Find all singletons of the graph. M"Find all singletons of the graph. NReturns True if this a  is a singleton. OReturns True if this b  is a singleton. PThe 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. @ABCDEFGHIJKLMNOP@ABCDEFGHIJKLMNOP$Clustering and grouping algorithms. Ivan.Miljenovic@gmail.comQ>A collapsed node contains a list of nodes that it represents. SAn instance of * used for the Chinese Whispers algorithm. The original label. %The current cluster this node is in. The node' s weighting. T'The actual Chinese Whispers algorithm. #Choose a new cluster for the given b . Note that this updates 6 the graph each time a new cluster value is chosen. #Choose a new cluster for the given Context. CChoose 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. UEThe renamed CLUSTER algorithm. Attempts to cluster a graph by using + the spatial locations used by Graphviz. !The Euclidian distance function. ,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. ,Collapse all results of the given function. QRSTUVSTUQRVGraph analysis algorithms Ivan.Miljenovic@gmail.comW/Apply an algorithm to the data to be analysed. $456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWW$A Graph-Theoretic Analysis Library. Ivan.Miljenovic@gmail.comX$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. ZThe 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). ^Default values for X&, 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  X that aren'(t listed in the data points, then those 2 edges are ignored. Thus, no sanitation of the [ in   ImportParams is necessary. cbadefop  !"#$%&'()*+,-./01456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_XYZ[\]^_ !"#$$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrst uv w x yz { | } ~                    Graphalyze-0.1Data.Graph.Analysis.TypesData.Graph.Analysis.Utils!Data.Graph.Analysis.Visualisation%Data.Graph.Analysis.Algorithms.Common'Data.Graph.Analysis.Algorithms.Directed)Data.Graph.Analysis.Algorithms.ClusteringData.Graph.Analysis.AlgorithmsData.Graph.AnalysisbaseData.Ord fgl-5.4.2.2Data.Graph.Inductive.Graphgraphviz-2008.9.20 Data.GraphVizSystem.IO.Unsafecontainers-0.2.0.0 Data.IntMapghc-prim GHC.TypesPreludeGHC.BoolPosLabelPLabelxPosyPospnodeplabel GenClusterGC ClusterLabelcluster nodelabelLNGroupNGroupAGr GraphDatagraph wantedRootsnodelabeledgeeLabel addLabels filterNodes filterNodes' pathValuesundironeWaynlmap dotizeGraph toPosGraph getPositions createLookup setCluster assignClustersingle longerThanlongest groupElems sortMinMax blockPrintshufflemean statistics statistics'fixPoint fixPointByfixPointGraphssqfIgraphvizgraphvizClusters componentsOfpathTree cliquesIn cliquesIn' findRegular isRegularcyclesIn cyclesIn' uniqueCycles uniqueCycles'chainsIn chainsIn'endNodeendNode'endByendBy'rootsOfrootsOf'isRootisRoot'leavesOf leavesOf'isLeafisLeaf' singletonsOf singletonsOf' isSingleton isSingleton'coreOfCNodesCN WhisperingchineseWhispersrelativeNeighbourhood collapseGraphapplyAlg ImportParamsParams dataPoints relationshipsrootsdirected defaultParams importData GHC.ClassesOrdLNodeNodeData.Graph.Inductive.TreeGrEdgeLEdgeLPath graphToGraph GHC.IOBaseunsafePerformIOIntMap NodeClustertakeLentakeLineIntGHC.Real fromIntegral AttributeNode AttributeEdgeDotGraphsplitComponent extractNode nodeExtractormakeLeafisClique findRegularOf regularOf alsoRegular corecursive findCycles cyclesForgetChain chainLink isChainStart chainFind chainNexthasNexthasPrevnamewhispcoeff whisperNodewhisper chooseWhisper addWhispers euclidianmakeRNG areRelative nbrClustermakeCollapsiblecollapse collapseAll collapseAllByFalseequaldeg'indeg'outdeg'inn'out'lpre'lsuc'pre'suc' neighbors'labNode'lab'node'degindegoutdeginnoutlprelsucpresuc neighborslabcontextmkUGraphbuildGrdelEdgesdelNodesinsEdgesinsNodesdelLEdgedelEdgedelNodeinsEdgeinsNodegelemnewNodesedgesnodesemapnmapgmapufoldUNodeUEdgePathLPUPathAdjContextMContextDecompGDecompUContextUDecomplabEdges nodeRangenoNodesmatchAnylabNodesmkGraphmatchisEmptyemptyGraph&DynGraph