Copyright | (c) Andrey Mokhov 2016-2018 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
An abstract implementation of transitive binary relations. Use Algebra.Graph.Class for polymorphic construction and manipulation.
- data TransitiveRelation a
- fromRelation :: Relation a -> TransitiveRelation a
- toRelation :: Ord a => TransitiveRelation a -> Relation a
Data structure
data TransitiveRelation a Source #
The TransitiveRelation
data type represents a transitive binary relation
over a set of elements. Transitive relations satisfy all laws of the
Transitive
type class and, in particular, the closure axiom:
y /= empty
==> x * y + x * z + y * z == x * y + y * z
For example, the following holds:
path
xs == (clique
xs :: TransitiveRelation Int)
The Show
instance produces transitively closed expressions:
show (1 * 2 :: TransitiveRelation Int) == "edge 1 2" show (1 * 2 + 2 * 3 :: TransitiveRelation Int) == "edges [(1,2),(1,3),(2,3)]"
Ord a => Eq (TransitiveRelation a) Source # | |
(Num a, Ord a) => Num (TransitiveRelation a) Source # | |
(Ord a, Show a) => Show (TransitiveRelation a) Source # | |
Ord a => Transitive (TransitiveRelation a) Source # | |
Ord a => Graph (TransitiveRelation a) Source # | |
type Vertex (TransitiveRelation a) Source # | |
fromRelation :: Relation a -> TransitiveRelation a Source #
Construct a transitive relation from a Relation
.
Complexity: O(1) time.
toRelation :: Ord a => TransitiveRelation a -> Relation a Source #
Extract the underlying relation. Complexity: O(n * m * log(m)) time.