UMinho Haskell Libraries (1.0) Contents Index

Data.Relation.SetOfPairs Portability portable Stability experimental Maintainer joost.visser@di.uminho.pt

Contents Representation Building relations Basic operations Closures Reductions Basic graph queries Selections (project, slice, chop) Partitions Integration Structure metrics

Description

An implementation of relations as sets of pairs.

Synopsis

type Rel a b = Set (a, b) type Gph a = Rel a a type Graph a = (Set a, Gph a) emptyRel :: Rel a b mkRel :: (Ord a, Ord b) => [(a, b)] -> Rel a b mkRelNeighbors :: (Ord a, Ord b) => a -> [b] -> Rel a b identityRel :: Ord a => Set a -> Rel a a totalRel :: Ord a => Set a -> Rel a a chainRel :: (Enum n, Num n, Ord n) => n -> Rel n n dom :: Ord a => Rel a b -> Set a rng :: Ord b => Rel a b -> Set b ent :: Ord a => Rel a a -> Set a pairs :: (Ord a, Ord b) => Rel a b -> [(a, b)] inv :: (Ord a, Ord b) => Rel a b -> Rel b a comp :: (Ord a, Eq b, Ord c) => Rel b c -> Rel a b -> Rel a c reflClose :: Ord a => Rel a a -> Rel a a symmClose :: Ord a => Rel a a -> Rel a a transClose :: Ord a => Rel a a -> Rel a a reflTransClose :: Ord a => Rel a a -> Rel a a equiv :: Ord b => Rel b b -> Rel b b reflReduc :: Ord a => Gph a -> Gph a topNodes :: Ord a => Gph a -> Set a bottomNodes :: Ord a => Gph a -> Set a internalNodes :: Ord a => Gph a -> Set a domWith :: (Ord a, Ord b) => Set b -> Rel a b -> Set a rngWith :: (Ord a, Ord b) => Set a -> Rel a b -> Set b entWith :: Ord a => Set a -> Rel a a -> Set a removeSelfEdges :: Ord a => Gph a -> Gph a projectWith :: (Ord a, Ord b) => (a -> b -> Bool) -> Rel a b -> Rel a b project :: (Ord a, Ord b) => Set a -> Rel a b -> Rel a b projectBackward :: (Ord a, Ord b) => Set b -> Rel a b -> Rel a b slice :: Ord a => Set a -> Rel a a -> Rel a a sliceUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a sliceBackward :: Ord a => Set a -> Rel a a -> Rel a a chop :: Ord a => Set a -> Set a -> Rel a a -> Rel a a slicesUnion :: Ord a => Set a -> Set a -> Rel a a -> Rel a a slicesIntersect :: Ord a => Set a -> Set a -> Rel a a -> Rel a a slicesWith :: Ord a => (Rel a a -> Rel a a -> Rel a a) -> Set a -> Set a -> Rel a a -> Rel a a sliceOrChopWith :: Ord a => (Rel a a -> Rel a a -> Rel a a) -> [a] -> [a] -> Rel a a -> Rel a a gobbleUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a weakComponents :: Ord a => Gph a -> [Gph a] strongComponent :: Ord a => a -> Gph a -> Set a strongComponentSet :: (Ord a, Ord (Set a)) => Gph a -> Set (Set a) type Component a = Graph a strongComponent' :: Ord a => a -> Rel a a -> Component a strongComponentRel :: (Ord a, Ord (Set a)) => Gph a -> Gph (Set a) strongComponentGraph :: (Ord a, Ord (Set a)) => Gph a -> Graph (Set a) strongComponentRel' :: (Ord a, Ord (Set a)) => Gph a -> Gph (Component a) strongNonSingletonComponentSet :: (Ord a, Ord (Set a)) => Gph a -> Set (Set a) integrate :: Ord a => Rel a a -> Rel a a -> Rel a a -> (Rel a a, Bool) affectedPoints :: Ord a => Rel a a -> Rel a a -> Set a preservedPoints :: Ord a => Rel a a -> Rel a a -> Rel a a -> Set a treeImpurity :: Ord a => Gph a -> Float data StrongComponentMetrics = StrongComponentMetrics { componentCount :: Int componentCountNormalized :: Float nonSingletonComponentCount :: Int componentSizeMax :: Int heightOfComponentGraph :: Int } calculateStrongComponentMetrics :: Ord a => Gph a -> StrongComponentMetrics countOfLevels :: Ord a => Gph a -> Int normalizedCountOfLevels :: Ord a => Gph a -> Float numberOfNonSingletonLevels :: Ord a => Gph a -> Int sizeOfLargestLevel :: Ord a => Gph a -> Int height :: Ord a => Gph a -> Int heightDag :: Ord a => Gph a -> Int heightFrom :: Ord a => Gph a -> Set a -> Set a -> Int fanInOut :: Ord a => Gph a -> (Bag a, Bag a) asPercentageOf :: Int -> Int -> Float

Representation

type Rel a b = Set (a, b)

Type of relations

type Gph a = Rel a a

Type of graphs: relations with domain and range of the same type.

type Graph a = (Set a, Gph a)

Type of graphs, with explicit entity set.

Building relations

emptyRel :: Rel a b

Build an empty relation.

mkRel :: (Ord a, Ord b) => [(a, b)] -> Rel a b

Build a relation from a list of pairs.

mkRelNeighbors :: (Ord a, Ord b) => a -> [b] -> Rel a b

Build a relation from distributing an element to a set of elements

identityRel :: Ord a => Set a -> Rel a a

Build identity relation, which contains an edge from each node to itself.

totalRel :: Ord a => Set a -> Rel a a

Build total relation, which contains an edge from each node to each other node and to itself.

chainRel :: (Enum n, Num n, Ord n) => n -> Rel n n

Build a chain relation of given number of numerals.

Basic operations

dom :: Ord a => Rel a b -> Set a

Obtain the domain of a relation

rng :: Ord b => Rel a b -> Set b

Obtain the range of a relation

ent :: Ord a => Rel a a -> Set a

Obtain all entities in a relation (union of domain and range)

pairs :: (Ord a, Ord b) => Rel a b -> [(a, b)]

Convert relation to a list of pairs.

inv :: (Ord a, Ord b) => Rel a b -> Rel b a

Take the inverse of a relation

comp :: (Ord a, Eq b, Ord c) => Rel b c -> Rel a b -> Rel a c

Compose two relations

Closures

reflClose :: Ord a => Rel a a -> Rel a a

Compute the reflective closure

symmClose :: Ord a => Rel a a -> Rel a a

Compute the symmetric closure

transClose :: Ord a => Rel a a -> Rel a a

Compute the transitive closure

reflTransClose :: Ord a => Rel a a -> Rel a a

Compute the reflexive, transitive closure

equiv :: Ord b => Rel b b -> Rel b b

Compute the reflexive, transitive, symmetric closure, i.e. the induced equivalence relation.

Reductions

reflReduc :: Ord a => Gph a -> Gph a

Reflexive reduction, i.e remove self-edges.

Basic graph queries

topNodes :: Ord a => Gph a -> Set a

Find top nodes of a graph. Those nodes that have outgoing but no incoming edges.

bottomNodes :: Ord a => Gph a -> Set a

Find bottom nodes of a graph. Those nodes that have incoming but no outgoing edges.

internalNodes :: Ord a => Gph a -> Set a

Find internal nodes of a graph. Those nodes that have both incoming and outgoing edges.

Selections (project, slice, chop)

domWith :: (Ord a, Ord b) => Set b -> Rel a b -> Set a

Obtain the subdomain of a relation given a subrange.

rngWith :: (Ord a, Ord b) => Set a -> Rel a b -> Set b

Obtain the subrange of a relation given a subdomain.

entWith :: Ord a => Set a -> Rel a a -> Set a

Obtain the subrange and subdomain of a relation given a subdomain.

removeSelfEdges :: Ord a => Gph a -> Gph a

Remove all edges of the form (x,x).

projectWith :: (Ord a, Ord b) => (a -> b -> Bool) -> Rel a b -> Rel a b

Retrieve a subrelation given predicates on domain and range.

project :: (Ord a, Ord b) => Set a -> Rel a b -> Rel a b

Projection of set through relation

projectBackward :: (Ord a, Ord b) => Set b -> Rel a b -> Rel a b

Projection of set backward through relation

slice :: Ord a => Set a -> Rel a a -> Rel a a

Compute forward slice starting from seeds.

sliceUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a

Compute forward slice starting from seeds, stopping at stoppers.

sliceBackward :: Ord a => Set a -> Rel a a -> Rel a a

Compute backward slice starting from seeds.

chop :: Ord a => Set a -> Set a -> Rel a a -> Rel a a

Compute chop between seeds and sinks.

slicesUnion :: Ord a => Set a -> Set a -> Rel a a -> Rel a a

Compute union of backward and forward slice.

slicesIntersect :: Ord a => Set a -> Set a -> Rel a a -> Rel a a

Compute intersection of backward and forward slice. This is the same as the computing the chop between seeds and sinks.

slicesWith :: Ord a => (Rel a a -> Rel a a -> Rel a a) -> Set a -> Set a -> Rel a a -> Rel a a

Compute combination of backward and forward slice, where a binary operator is supplied to specify the kind of combination.

sliceOrChopWith

:: Ord a => (Rel a a -> Rel a a -> Rel a a) binary graph operation -> [a] sources -> [a] sinks -> Rel a a input relation -> Rel a a output relation Compute slice or chop, depending on whether the source or sink set or both are empty.

Partitions

gobbleUntil :: Ord a => Set a -> Set a -> Rel a a -> Rel a a

Compute subrelation connected to seeds, stopping at stoppers.

weakComponents :: Ord a => Gph a -> [Gph a]

Compute weakly connected components.

strongComponent :: Ord a => a -> Gph a -> Set a

Compute a single strong component (set of nodes).

strongComponentSet :: (Ord a, Ord (Set a)) => Gph a -> Set (Set a)

Compute the set of strong components (sets of nodes).

type Component a = Graph a

Type of components: node set tupled with subgraph.

strongComponent' :: Ord a => a -> Rel a a -> Component a

Compute a single strong component (node set tupled with subrelation).

strongComponentRel :: (Ord a, Ord (Set a)) => Gph a -> Gph (Set a)

Compute the graph of strong components (node sets). Note: strong components that have no relations to other components will not be present in the graph!

strongComponentGraph :: (Ord a, Ord (Set a)) => Gph a -> Graph (Set a)

Compute the graph of strong components (node sets).

strongComponentRel' :: (Ord a, Ord (Set a)) => Gph a -> Gph (Component a)

Compute the graph of stong components (node sets tupled with subrelations).

strongNonSingletonComponentSet :: (Ord a, Ord (Set a)) => Gph a -> Set (Set a)

Compute the set of strong components that have more than a single node

Integration

integrate :: Ord a => Rel a a -> Rel a a -> Rel a a -> (Rel a a, Bool)

Integrate two graphs with respect to a base graph into a new graph that contains the differences of each input graph with respect to the base graph. The boolean value indicates whether the graphs are interference-free, i.e. whether the integration is valid.

affectedPoints :: Ord a => Rel a a -> Rel a a -> Set a

Points in the first graph that are affected by changes with respect to the base graph.

preservedPoints :: Ord a => Rel a a -> Rel a a -> Rel a a -> Set a

Points in the base graph that are not affected by changes in either input graph.

Structure metrics

treeImpurity :: Ord a => Gph a -> Float

Tree impurity (TIMP): how much does the graph resemble a tree, expressed as a percentage. A tree has tree impurity of 0 percent. A fully connected graph has tree impurity of 100 percent. Fenton and Pfleeger only defined tree impurity for non-directed graphs without self-edges. This implementation therefore does not count self-edges, and counts 2 directed edges between the same nodes only once.

data StrongComponentMetrics

A record type to hold metrics about strong components. Constructors StrongComponentMetrics componentCount :: Int Count of strong components componentCountNormalized :: Float Normalized count of strong components nonSingletonComponentCount :: Int Count of non-singleton components componentSizeMax :: Int Size of largest component heightOfComponentGraph :: Int Height of component DAG

calculateStrongComponentMetrics :: Ord a => Gph a -> StrongComponentMetrics

Calculate the strong component metrics for a given graph.

countOfLevels :: Ord a => Gph a -> Int

Count of levels (LEV):

normalizedCountOfLevels :: Ord a => Gph a -> Float

Normalized count of levels (CLEV):

numberOfNonSingletonLevels :: Ord a => Gph a -> Int

Number of non-singleton levels (NSLEV)

sizeOfLargestLevel :: Ord a => Gph a -> Int

Size of largest level (DEP):

height :: Ord a => Gph a -> Int

Height (works also in the presence of cycles)

heightDag :: Ord a => Gph a -> Int

Height (does not work in the presence of cycles)

heightFrom

:: Ord a => Gph a Graph -> Set a Already visited nodes -> Set a Nodes still to visit -> Int Result Compute graph height starting from a given set of nodes.

fanInOut :: Ord a => Gph a -> (Bag a, Bag a)

Compute fan-in and fan-out of a given graph. Both are represented with a bags of nodes. The arity of each node in the bag is its fanout or fanin, repectively.

asPercentageOf :: Int -> Int -> Float

Helper for math.

Produced by Haddock version 0.6