|
Data.Relation.MapFromPairs | Portability | portable | Stability | experimental | Maintainer | joost.visser@di.uminho.pt |
|
|
|
|
|
Description |
An implementation of labeled relations as map from pairs to values.
|
|
Synopsis |
|
type LRel a b c = FiniteMap (a, b) c | | rel :: (Ord a, Ord b) => (c -> Bool) -> LRel a b c -> Rel a b | | lrel :: (Ord a, Ord b) => c -> Rel a b -> LRel a b c | | entities :: Ord a => LRel a a c -> Set a | | labels :: (Ord a, Ord b, Ord c) => LRel a b c -> Set c | | extremal :: Ord a => b -> (b -> b -> b) -> (b -> b -> b) -> LRel a a b -> LRel a a b | | reach :: Ord a => LRel a a Bool -> LRel a a Bool | | leastcost :: (Num cost, Ord cost, Ord a) => cost -> LRel a a cost -> LRel a a cost | | worstcost :: (Ord a, Num cost, Ord cost) => cost -> LRel a a cost -> LRel a a cost | | bottleneck :: (Ord height, Num height, Ord a) => LRel a a height -> LRel a a height | | leastcost' :: (Num cost, Ord cost, Bounded cost, Ord a) => LRel a a cost -> LRel a a cost | | depth :: Ord a => Gph a -> Int |
|
|
|
Representation |
|
type LRel a b c = FiniteMap (a, b) c |
The type of labeled releations. |
|
rel |
:: (Ord a, Ord b) | | => (c -> Bool) | Predicate on labels. | -> LRel a b c | | -> Rel a b | | Convert labeled relation to one without labels. The first argument
is a predicate that determines, based on the label, which pairs are
to be included in the result relation. |
|
|
lrel |
:: (Ord a, Ord b) | | => c | Initialization label | -> Rel a b | | -> LRel a b c | | Convert relation to a labeled one. The first argument is the
label with which all pairs in the result relation will be labeled. |
|
|
entities :: Ord a => LRel a a c -> Set a |
Carrier set. |
|
labels :: (Ord a, Ord b, Ord c) => LRel a b c -> Set c |
Label set. |
|
Extremal paths. |
|
extremal |
:: Ord a | | => b | Zero of multiplication. | -> (b -> b -> b) | Multiplication. | -> (b -> b -> b) | Addition. | -> LRel a a b | | -> LRel a a b | | Generic extremal path algorithm, based on Roland Backhouse's
lecture notes, page 192 (draft version). |
|
|
reach :: Ord a => LRel a a Bool -> LRel a a Bool |
Reachability. This is transitive closure following Roy-Warshall. |
|
leastcost |
:: (Num cost, Ord cost, Ord a) | | => cost | Maximum bound. | -> LRel a a cost | Cost labels must be non-negative. | -> LRel a a cost | | Least cost, or shortest path. |
|
|
worstcost :: (Ord a, Num cost, Ord cost) => cost -> LRel a a cost -> LRel a a cost |
Worst cost, or longest path. UNTESTED. |
|
bottleneck |
:: (Ord height, Num height, Ord a) | | => LRel a a height | Height labels must be non-negative. | -> LRel a a height | | Bottle neck. |
|
|
leastcost' :: (Num cost, Ord cost, Bounded cost, Ord a) => LRel a a cost -> LRel a a cost |
Least cost, or shortest path. DOES NOT WORK, because it relies on
maxBound from the Bounded class, leading to erroneous arithmetic. |
|
Costs with infinity |
|
depth :: Ord a => Gph a -> Int |
Compute depth of a graph. |
|
Produced by Haddock version 0.6 |