Copyright | (c) Ivan Lazar Miljenovic 2009 |
---|---|

License | 2-Clause BSD |

Maintainer | Ivan.Miljenovic@gmail.com |

Safe Haskell | None |

Language | Haskell98 |

This module defines various utility functions used throughout.

- node :: LNode a -> Node
- label :: LNode a -> a
- labels :: Graph g => g a b -> [a]
- edge :: LEdge b -> Edge
- eLabel :: LEdge b -> b
- addLabels :: Graph g => g a b -> [Node] -> [LNode a]
- addLabels' :: (Ord a, Graph g) => g a b -> Set Node -> Set (LNode a)
- getLabels :: Graph g => g a b -> [Node] -> [a]
- getLabels' :: (Ord a, Graph g) => g a b -> Set Node -> Set a
- filterNodes :: Graph g => (g a b -> LNode a -> Bool) -> g a b -> [LNode a]
- filterNodes' :: Graph g => (g a b -> Node -> Bool) -> g a b -> [Node]
- pathValues :: LPath a -> [LNode a]
- undir :: (Eq b, DynGraph gr) => gr a b -> gr a b
- oneWay :: (DynGraph g, Eq b) => g a b -> g a b
- mkSimple :: DynGraph gr => gr a b -> gr a b
- compact :: DynGraph gr => gr a b -> gr a [b]
- compact' :: DynGraph gr => gr a b -> gr a Int
- compactSame :: (Ord b, DynGraph gr) => gr a b -> gr a (Int, b)
- nlmap :: DynGraph gr => (LNode a -> c) -> gr a b -> gr c b
- delLNodes :: DynGraph gr => LNGroup a -> gr a b -> gr a b
- toPosGraph :: (DynGraph gr, Ord b) => Bool -> gr a b -> gr (PosLabel a) b
- getPositions :: (DynGraph gr, Ord b) => Bool -> gr a b -> [PosLabel a]
- createLookup :: [[Node]] -> IntMap Int
- setCluster :: DynGraph gr => IntMap Int -> gr a b -> gr (GenCluster a) b
- reCluster :: DynGraph g => g (GenCluster a) b -> g (GenCluster a) b
- reClusterBy :: DynGraph g => IntMap Int -> g (GenCluster a) b -> g (GenCluster a) b
- clusterCount :: Graph g => g (GenCluster a) b -> IntMap Int
- single :: [a] -> Bool
- longerThan :: Int -> [a] -> Bool
- addLengths :: [[a]] -> [(Int, [a])]
- longest :: [[a]] -> [a]
- lengthSort :: [[a]] -> [[a]]
- groupElems :: Ord b => (a -> b) -> [a] -> [(b, [a])]
- sortMinMax :: Ord a => [a] -> ([a], a, a)
- shuffle :: RandomGen g => g -> [a] -> ([a], g)
- mean :: [Double] -> Double
- statistics :: [Double] -> (Double, Double)
- statistics' :: [Int] -> (Int, Int)
- fixPoint :: Eq a => (a -> a) -> a -> a
- fixPointGraphs :: (Eq a, Eq b, Graph g) => (g a b -> g a b) -> g a b -> g a b
- fixPointBy :: (a -> a -> Bool) -> (a -> a) -> a -> a

# Graph functions

## Data extraction

Extracting data from graphs.

filterNodes :: Graph g => (g a b -> LNode a -> Bool) -> g a b -> [LNode a] Source #

Find all the labelled nodes in the graph that match the given predicate.

filterNodes' :: Graph g => (g a b -> Node -> Bool) -> g a b -> [Node] Source #

Find all the nodes in the graph that match the given predicate.

## Graph manipulation

undir :: (Eq b, DynGraph gr) => gr a b -> gr a b Source #

Make the graph undirected, i.e. for every edge from A to B, there
exists an edge from B to A. The provided function
`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.

oneWay :: (DynGraph g, Eq b) => g a b -> g a b Source #

This is a pseudo-inverse of `undir`

: any edges that are both successor
and predecessor become successor edges only.

mkSimple :: DynGraph gr => gr a b -> gr a b Source #

Makes the graph a simple one, by removing all duplicate edges and loops. The edges removed if duplicates exist are arbitrary.

compact :: DynGraph gr => gr a b -> gr a [b] Source #

Adjoin duplicate edges by grouping the labels together.

compact' :: DynGraph gr => gr a b -> gr a Int Source #

Compact the graph by counting how many multiple edges there are (considering only the two nodes and not the labels).

compactSame :: (Ord b, DynGraph gr) => gr a b -> gr a (Int, b) Source #

Compact the graph by adjoining identical duplicate edges.

nlmap :: DynGraph gr => (LNode a -> c) -> gr a b -> gr c b Source #

Map over the labels on the nodes, using the node values as well.

delLNodes :: DynGraph gr => LNGroup a -> gr a b -> gr a b Source #

Delete these labelled nodes from the graph.

## Graph layout

Spatial positioning of graphs. Use the `dotizeGraph`

function in
Data.GraphViz to determine potential graph layouts.

toPosGraph :: (DynGraph gr, Ord b) => Bool -> gr a b -> gr (PosLabel a) b Source #

Convert the graph into one with positions stored in the node
labels. The `Bool`

parameter denotes if the graph is directed or
not.

getPositions :: (DynGraph gr, Ord b) => Bool -> gr a b -> [PosLabel a] Source #

Returns the positions of the nodes in the graph, as found using
Graphviz. The `Bool`

parameter denotes if the graph is directed
or not.

## Cluster functions

Cluster utility functions.

setCluster :: DynGraph gr => IntMap Int -> gr a b -> gr (GenCluster a) b Source #

Used when the clusters are assigned in a lookup `IntMap`

instance.

reCluster :: DynGraph g => g (GenCluster a) b -> g (GenCluster a) b Source #

Change the cluster values in the graph by having the largest cluster have the smallest cluster label.

reClusterBy :: DynGraph g => IntMap Int -> g (GenCluster a) b -> g (GenCluster a) b Source #

Change the cluster values using the given lookup `IntMap`

.

clusterCount :: Graph g => g (GenCluster a) b -> IntMap Int Source #

Create an `IntMap`

of the size of each cluster.

# List functions

List utility functions.

longerThan :: Int -> [a] -> Bool Source #

If we need to only tell if the list contains more than `n`

elements,
there's no need to find its length.

addLengths :: [[a]] -> [(Int, [a])] Source #

Add the length of each sublist.

lengthSort :: [[a]] -> [[a]] Source #

groupElems :: Ord b => (a -> b) -> [a] -> [(b, [a])] Source #

Group elements by the given grouping function.

sortMinMax :: Ord a => [a] -> ([a], a, a) Source #

Returns the unique elements of the list in ascending order, as well as the minimum and maximum elements.

shuffle :: RandomGen g => g -> [a] -> ([a], g) Source #

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

# Statistics functions

mean :: [Double] -> Double Source #

An efficient mean function by Don Stewart, available from: http://cgi.cse.unsw.edu.au/~dons/blog/2008/05/16#fast

Calculate the mean and standard deviation of a list of elements.

Calculate the mean and standard deviation of a list of `Int`

values.

# Other functions

fixPoint :: Eq a => (a -> a) -> a -> a Source #

Find the fixed point of a function with the given initial value.

fixPointGraphs :: (Eq a, Eq b, Graph g) => (g a b -> g a b) -> g a b -> g a b Source #

Find the fixed point of a graph transformation function.

fixPointBy :: (a -> a -> Bool) -> (a -> a) -> a -> a Source #

Find the fixed point of a function with the given initial value, using the given equality function.