Copyright	(c) Andrey Mokhov 2016-2022
License	MIT (see the file LICENSE)
Maintainer	andrey.mokhov@gmail.com
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Algebra.Graph.Relation.Transitive

Contents

Data structure

Description

An abstract implementation of transitive binary relations. Use Algebra.Graph.Class for polymorphic construction and manipulation.

Synopsis

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)]"

Instances

Instances details

Ord a => Eq ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Methods (==) :: TransitiveRelation a -> TransitiveRelation a -> Bool Source # (/=) :: TransitiveRelation a -> TransitiveRelation a -> Bool Source #
( Ord a, Num a) => Num ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Methods (+) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source # (-) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source # (*) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source # negate :: TransitiveRelation a -> TransitiveRelation a Source # abs :: TransitiveRelation a -> TransitiveRelation a Source # signum :: TransitiveRelation a -> TransitiveRelation a Source # fromInteger :: Integer -> TransitiveRelation a Source #
Ord a => Ord ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Methods compare :: TransitiveRelation a -> TransitiveRelation a -> Ordering Source # (<) :: TransitiveRelation a -> TransitiveRelation a -> Bool Source # (<=) :: TransitiveRelation a -> TransitiveRelation a -> Bool Source # (>) :: TransitiveRelation a -> TransitiveRelation a -> Bool Source # (>=) :: TransitiveRelation a -> TransitiveRelation a -> Bool Source # max :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source # min :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source #
( Ord a, Show a) => Show ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Methods showsPrec :: Int -> TransitiveRelation a -> ShowS Source # show :: TransitiveRelation a -> String Source # showList :: [ TransitiveRelation a] -> ShowS Source #
IsString a => IsString ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Methods fromString :: String -> TransitiveRelation a Source #
NFData a => NFData ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Methods rnf :: TransitiveRelation a -> () Source #
Ord a => Transitive ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive
Ord a => Graph ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Associated Types type Vertex ( TransitiveRelation a) Source # Methods empty :: TransitiveRelation a Source # vertex :: Vertex ( TransitiveRelation a) -> TransitiveRelation a Source # overlay :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source # connect :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source #
type Vertex ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive type Vertex ( TransitiveRelation a) = a

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.