Algebra.Graph.Relation.Transitive

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

Data structure

data TransitiveRelation a

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

Ord a => Eq (TransitiveRelation a)

Methods

(==) :: TransitiveRelation a -> TransitiveRelation a -> Bool

(/=) :: TransitiveRelation a -> TransitiveRelation a -> Bool

(Num a, Ord a) => Num (TransitiveRelation a)

Methods

(+) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

(-) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

(*) :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

negate :: TransitiveRelation a -> TransitiveRelation a

abs :: TransitiveRelation a -> TransitiveRelation a

signum :: TransitiveRelation a -> TransitiveRelation a

fromInteger :: Integer -> TransitiveRelation a

(Ord a, Show a) => Show (TransitiveRelation a)

Methods

showsPrec :: Int -> TransitiveRelation a -> ShowS

show :: TransitiveRelation a -> String

showList :: [TransitiveRelation a] -> ShowS

Ord a => Transitive (TransitiveRelation a)

Ord a => Graph (TransitiveRelation a)

Associated Types

type Vertex (TransitiveRelation a) :: *

Methods

empty :: TransitiveRelation a

vertex :: Vertex (TransitiveRelation a) -> TransitiveRelation a

overlay :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

connect :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a

type Vertex (TransitiveRelation a)

type Vertex (TransitiveRelation a) = a

fromRelation :: Relation a -> TransitiveRelation a

Construct a transitive relation from a Relation. Complexity: O(1) time.

toRelation :: Ord a => TransitiveRelation a -> Relation a

Extract the underlying relation. Complexity: O(n * m * log(m)) time.