Algebra.Graph.Relation.Internal

This module exposes the implementation of the Relation data type. The API is unstable and unsafe, and is exposed only for documentation. You should use the non-internal module Algebra.Graph.Relation instead.

Binary relation implementation

data Relation a

The Relation data type represents a graph as a binary relation. We define a Num instance as a convenient notation for working with graphs:

0           == vertex 0
1 + 2       == overlay (vertex 1) (vertex 2)
1 * 2       == connect (vertex 1) (vertex 2)
1 + 2 * 3   == overlay (vertex 1) (connect (vertex 2) (vertex 3))
1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))

The Show instance is defined using basic graph construction primitives:

show (empty     :: Relation Int) == "empty"
show (1         :: Relation Int) == "vertex 1"
show (1 + 2     :: Relation Int) == "vertices [1,2]"
show (1 * 2     :: Relation Int) == "edge 1 2"
show (1 * 2 * 3 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"

The Eq instance satisfies all axioms of algebraic graphs:

• overlay is commutative and associative:

        x + y == y + x
  x + (y + z) == (x + y) + z

• connect is associative and has empty as the identity:

    x * empty == x
    empty * x == x
  x * (y * z) == (x * y) * z

• connect distributes over overlay:

  x * (y + z) == x * y + x * z
  (x + y) * z == x * z + y * z

• connect can be decomposed:

  x * y * z == x * y + x * z + y * z

The following useful theorems can be proved from the above set of axioms.

• overlay has empty as the identity and is idempotent:

    x + empty == x
    empty + x == x
        x + x == x

• Absorption and saturation of connect:

  x * y + x + y == x * y
      x * x * x == x * x

When specifying the time and memory complexity of graph algorithms, n and m will denote the number of vertices and edges in the graph, respectively.

Constructors

Relation

Fields

• domain :: Set a

  The domain of the relation.

• relation :: Set (a, a)

  The set of pairs of elements that are related. It is guaranteed that each element belongs to the domain.

Instances

Eq a => Eq (Relation a)

Methods

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

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

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

Methods

(+) :: Relation a -> Relation a -> Relation a

(-) :: Relation a -> Relation a -> Relation a

(*) :: Relation a -> Relation a -> Relation a

negate :: Relation a -> Relation a

abs :: Relation a -> Relation a

signum :: Relation a -> Relation a

fromInteger :: Integer -> Relation a

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

Methods

showsPrec :: Int -> Relation a -> ShowS

show :: Relation a -> String

showList :: [Relation a] -> ShowS

ToGraph (Relation a)

Associated Types

type ToVertex (Relation a) :: *

Methods

toGraph :: (Graph g, (* ~ Vertex g) (ToVertex (Relation a))) => Relation a -> g

foldg :: r -> (ToVertex (Relation a) -> r) -> (r -> r -> r) -> (r -> r -> r) -> Relation a -> r

Ord a => Graph (Relation a)

Associated Types

type Vertex (Relation a) :: *

Methods

empty :: Relation a

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

overlay :: Relation a -> Relation a -> Relation a

connect :: Relation a -> Relation a -> Relation a

type ToVertex (Relation a)

type ToVertex (Relation a) = a

type Vertex (Relation a)

type Vertex (Relation a) = a

consistent :: Ord a => Relation a -> Bool

Check if the internal representation of a relation is consistent, i.e. if all pairs of elements in the relation refer to existing elements in the domain. It should be impossible to create an inconsistent Relation, and we use this function in testing. Note: this function is for internal use only.

consistent empty                  == True
consistent (vertex x)             == True
consistent (overlay x y)          == True
consistent (connect x y)          == True
consistent (edge x y)             == True
consistent (edges xs)             == True
consistent (graph xs ys)          == True
consistent (fromAdjacencyList xs) == True

setProduct :: Set a -> Set b -> Set (a, b)

Compute the Cartesian product of two sets. Note: this function is for internal use only.

referredToVertexSet :: Ord a => Set (a, a) -> Set a

The set of elements that appear in a given set of pairs. Note: this function is for internal use only.