Algebra.Graph.Relation.Preorder

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

Data structure

data PreorderRelation a

The PreorderRelation data type represents a binary relation that is both reflexive and transitive. Preorders satisfy all laws of the Preorder type class and, in particular, the self-loop axiom:

vertex x == vertex x * vertex x

and the closure axiom:

y /= empty ==> x * y + x * z + y * z == x * y + y * z

For example, the following holds:

path xs == (clique xs :: PreorderRelation Int)

The Show instance produces reflexively and transitively closed expressions:

show (1             :: PreorderRelation Int) == "edge 1 1"
show (1 * 2         :: PreorderRelation Int) == "edges [(1,1),(1,2),(2,2)]"
show (1 * 2 + 2 * 3 :: PreorderRelation Int) == "edges [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"

Instances

Ord a => Eq (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Methods

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

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

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

Defined in Algebra.Graph.Relation.Preorder

Methods

(+) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

(-) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

(*) :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

negate :: PreorderRelation a -> PreorderRelation a

abs :: PreorderRelation a -> PreorderRelation a

signum :: PreorderRelation a -> PreorderRelation a

fromInteger :: Integer -> PreorderRelation a

Ord a => Ord (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Methods

compare :: PreorderRelation a -> PreorderRelation a -> Ordering

(<) :: PreorderRelation a -> PreorderRelation a -> Bool

(<=) :: PreorderRelation a -> PreorderRelation a -> Bool

(>) :: PreorderRelation a -> PreorderRelation a -> Bool

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

max :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

min :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

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

Defined in Algebra.Graph.Relation.Preorder

Methods

showsPrec :: Int -> PreorderRelation a -> ShowS

show :: PreorderRelation a -> String

showList :: [PreorderRelation a] -> ShowS

IsString a => IsString (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Methods

fromString :: String -> PreorderRelation a

NFData a => NFData (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Methods

rnf :: PreorderRelation a -> ()

Ord a => Preorder (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Ord a => Transitive (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Ord a => Reflexive (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Ord a => Graph (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

Associated Types

type Vertex (PreorderRelation a)

Methods

empty :: PreorderRelation a

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

overlay :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

connect :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a

type Vertex (PreorderRelation a)

Defined in Algebra.Graph.Relation.Preorder

type Vertex (PreorderRelation a) = a

fromRelation :: Relation a -> PreorderRelation a

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

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

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