Copyright | (c) Andrey Mokhov 2016-2017 |
---|---|

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.