Algebra.Graph.Relation.Internal

This module exposes the implementation of binary relations. The API is unstable and unsafe. Where possible use non-internal modules Algebra.Graph.Relation, Algebra.Graph.Relation.Reflexive, Algebra.Graph.Relation.Symmetric, Algebra.Graph.Relation.Transitive and Algebra.Graph.Relation.Preorder instead.

Data structure

data Relation a

The Relation data type represents a graph as a binary relation. We define a law-abiding 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) == "graph [1,2,3] [(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

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 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.

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

Basic graph construction primitives

empty :: Relation a

Construct the empty graph. Complexity: O(1) time and memory.

isEmpty     empty == True
hasVertex x empty == False
vertexCount empty == 0
edgeCount   empty == 0

vertex :: a -> Relation a

Construct the graph comprising a single isolated vertex. Complexity: O(1) time and memory.

isEmpty     (vertex x) == False
hasVertex x (vertex x) == True
hasVertex 1 (vertex 2) == False
vertexCount (vertex x) == 1
edgeCount   (vertex x) == 0

overlay :: Ord a => Relation a -> Relation a -> Relation a

Overlay two graphs. This is an idempotent, commutative and associative operation with the identity empty. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

isEmpty     (overlay x y) == isEmpty   x   && isEmpty   y
hasVertex z (overlay x y) == hasVertex z x || hasVertex z y
vertexCount (overlay x y) >= vertexCount x
vertexCount (overlay x y) <= vertexCount x + vertexCount y
edgeCount   (overlay x y) >= edgeCount x
edgeCount   (overlay x y) <= edgeCount x   + edgeCount y
vertexCount (overlay 1 2) == 2
edgeCount   (overlay 1 2) == 0

connect :: Ord a => Relation a -> Relation a -> Relation a

Connect two graphs. This is an associative operation with the identity empty, which distributes over the overlay and obeys the decomposition axiom. Complexity: O((n + m) * log(n)) time and O(n + m) memory. Note that the number of edges in the resulting graph is quadratic with respect to the number of vertices of the arguments: m = O(m1 + m2 + n1 * n2).

isEmpty     (connect x y) == isEmpty   x   && isEmpty   y
hasVertex z (connect x y) == hasVertex z x || hasVertex z y
vertexCount (connect x y) >= vertexCount x
vertexCount (connect x y) <= vertexCount x + vertexCount y
edgeCount   (connect x y) >= edgeCount x
edgeCount   (connect x y) >= edgeCount y
edgeCount   (connect x y) >= vertexCount x * vertexCount y
edgeCount   (connect x y) <= vertexCount x * vertexCount y + edgeCount x + edgeCount y
vertexCount (connect 1 2) == 2
edgeCount   (connect 1 2) == 1

vertices :: Ord a => [a] -> Relation a

Construct the graph comprising a given list of isolated vertices. Complexity: O(L * log(L)) time and O(L) memory, where L is the length of the given list.

vertices []            == empty
vertices [x]           == vertex x
hasVertex x . vertices == elem x
vertexCount . vertices == length . nub
vertexSet   . vertices == Set.fromList

edges :: Ord a => [(a, a)] -> Relation a

Construct the graph from a list of edges. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

edges []          == empty
edges [(x,y)]     == edge x y
edgeCount . edges == length . nub

fromAdjacencyList :: Ord a => [(a, [a])] -> Relation a

Construct a graph from an adjacency list. Complexity: O((n + m) * log(n)) time and O(n + m) memory.

fromAdjacencyList []                                  == empty
fromAdjacencyList [(x, [])]                           == vertex x
fromAdjacencyList [(x, [y])]                          == edge x y
overlay (fromAdjacencyList xs) (fromAdjacencyList ys) == fromAdjacencyList (xs ++ ys)

Graph properties

edgeList :: Ord a => Relation a -> [(a, a)]

The sorted list of edges of a graph. Complexity: O(n + m) time and O(m) memory.

edgeList empty          == []
edgeList (vertex x)     == []
edgeList (edge x y)     == [(x,y)]
edgeList (star 2 [1,3]) == [(2,1), (2,3)]
edgeList . edges        == nub . sort

preset :: Ord a => a -> Relation a -> Set a

The preset of an element x is the set of elements that are related to it on the left, i.e. preset x == { a | aRx }. In the context of directed graphs, this corresponds to the set of direct predecessors of vertex x. Complexity: O(n + m) time and O(n) memory.

preset x empty      == Set.empty
preset x (vertex x) == Set.empty
preset 1 (edge 1 2) == Set.empty
preset y (edge x y) == Set.fromList [x]

postset :: Ord a => a -> Relation a -> Set a

The postset of an element x is the set of elements that are related to it on the right, i.e. postset x == { a | xRa }. In the context of directed graphs, this corresponds to the set of direct successors of vertex x. Complexity: O(n + m) time and O(n) memory.

postset x empty      == Set.empty
postset x (vertex x) == Set.empty
postset x (edge x y) == Set.fromList [y]
postset 2 (edge 1 2) == Set.empty

Graph transformation

removeVertex :: Ord a => a -> Relation a -> Relation a

Remove a vertex from a given graph. Complexity: O(n + m) time.

removeVertex x (vertex x)       == empty
removeVertex x . removeVertex x == removeVertex x

removeEdge :: Ord a => a -> a -> Relation a -> Relation a

Remove an edge from a given graph. Complexity: O(log(m)) time.

removeEdge x y (edge x y)       == vertices [x, y]
removeEdge x y . removeEdge x y == removeEdge x y
removeEdge x y . removeVertex x == removeVertex x
removeEdge 1 1 (1 * 1 * 2 * 2)  == 1 * 2 * 2
removeEdge 1 2 (1 * 1 * 2 * 2)  == 1 * 1 + 2 * 2

gmap :: (Ord a, Ord b) => (a -> b) -> Relation a -> Relation b

Transform a graph by applying a function to each of its vertices. This is similar to Functor's fmap but can be used with non-fully-parametric Relation. Complexity: O((n + m) * log(n)) time.

gmap f empty      == empty
gmap f (vertex x) == vertex (f x)
gmap f (edge x y) == edge (f x) (f y)
gmap id           == id
gmap f . gmap g   == gmap (f . g)

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

Construct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(m) time, assuming that the predicate takes O(1) to be evaluated.

induce (const True)  x      == x
induce (const False) x      == empty
induce (/= x)               == removeVertex x
induce p . induce q         == induce (\x -> p x && q x)
isSubgraphOf (induce p x) x == True

Operations on binary relations

reflexiveClosure :: Ord a => Relation a -> Relation a

Compute the reflexive closure of a Relation. Complexity: O(n*log(m)) time.

reflexiveClosure empty      == empty
reflexiveClosure (vertex x) == edge x x

symmetricClosure :: Ord a => Relation a -> Relation a

Compute the symmetric closure of a Relation. Complexity: O(m*log(m)) time.

symmetricClosure empty      == empty
symmetricClosure (vertex x) == vertex x
symmetricClosure (edge x y) == edges [(x, y), (y, x)]

transitiveClosure :: Ord a => Relation a -> Relation a

Compute the transitive closure of a Relation. Complexity: O(n * m * log(m)) time.

transitiveClosure empty           == empty
transitiveClosure (vertex x)      == vertex x
transitiveClosure (path $ nub xs) == clique (nub xs)

preorderClosure :: Ord a => Relation a -> Relation a

Compute the preorder closure of a Relation. Complexity: O(n * m * log(m)) time.

preorderClosure empty           == empty
preorderClosure (vertex x)      == edge x x
preorderClosure (path $ nub xs) == reflexiveClosure (clique $ nub xs)

Reflexive relations

newtype ReflexiveRelation a

The ReflexiveRelation data type represents a reflexive binary relation over a set of elements. Reflexive relations satisfy all laws of the Reflexive type class and, in particular, the self-loop axiom:

vertex x == vertex x * vertex x

The Show instance produces reflexively closed expressions:

show (1     :: ReflexiveRelation Int) == "edge 1 1"
show (1 * 2 :: ReflexiveRelation Int) == "edges [(1,1),(1,2),(2,2)]"

Constructors

ReflexiveRelation

Fields

• fromReflexive :: Relation a

Instances

Ord a => Eq (ReflexiveRelation a)

Methods

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

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

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

Methods

(+) :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

(-) :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

(*) :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

negate :: ReflexiveRelation a -> ReflexiveRelation a

abs :: ReflexiveRelation a -> ReflexiveRelation a

signum :: ReflexiveRelation a -> ReflexiveRelation a

fromInteger :: Integer -> ReflexiveRelation a

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

Methods

showsPrec :: Int -> ReflexiveRelation a -> ShowS

show :: ReflexiveRelation a -> String

showList :: [ReflexiveRelation a] -> ShowS

Ord a => Reflexive (ReflexiveRelation a)

Ord a => Graph (ReflexiveRelation a)

Associated Types

type Vertex (ReflexiveRelation a) :: *

Methods

empty :: ReflexiveRelation a

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

overlay :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

connect :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a

type Vertex (ReflexiveRelation a)

type Vertex (ReflexiveRelation a) = a

Symmetric relations

newtype SymmetricRelation a

The SymmetricRelation data type represents a symmetric binary relation over a set of elements. Symmetric relations satisfy all laws of the Undirected type class and, in particular, the commutativity of connect:

connect x y == connect y x

The Show instance produces symmetrically closed expressions:

show (1     :: SymmetricRelation Int) == "vertex 1"
show (1 * 2 :: SymmetricRelation Int) == "edges [(1,2),(2,1)]"

Constructors

SymmetricRelation

Fields

• fromSymmetric :: Relation a

Instances

Ord a => Eq (SymmetricRelation a)

Methods

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

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

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

Methods

(+) :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

(-) :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

(*) :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

negate :: SymmetricRelation a -> SymmetricRelation a

abs :: SymmetricRelation a -> SymmetricRelation a

signum :: SymmetricRelation a -> SymmetricRelation a

fromInteger :: Integer -> SymmetricRelation a

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

Methods

showsPrec :: Int -> SymmetricRelation a -> ShowS

show :: SymmetricRelation a -> String

showList :: [SymmetricRelation a] -> ShowS

Ord a => Undirected (SymmetricRelation a)

Ord a => Graph (SymmetricRelation a)

Associated Types

type Vertex (SymmetricRelation a) :: *

Methods

empty :: SymmetricRelation a

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

overlay :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

connect :: SymmetricRelation a -> SymmetricRelation a -> SymmetricRelation a

type Vertex (SymmetricRelation a)

type Vertex (SymmetricRelation a) = a

Transitive relations

newtype 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

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

Constructors

TransitiveRelation

Fields

• fromTransitive :: Relation a

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

Preorders

newtype PreorderRelation a

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

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

and the self-loop axiom:

vertex x == vertex x * vertex x

For example, the following holds:

path xs == clique xs

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

Constructors

PreorderRelation

Fields

• fromPreorder :: Relation a

Instances

Ord a => Eq (PreorderRelation a)

Methods

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

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

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

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, Show a) => Show (PreorderRelation a)

Methods

showsPrec :: Int -> PreorderRelation a -> ShowS

show :: PreorderRelation a -> String

showList :: [PreorderRelation a] -> ShowS

Ord a => Preorder (PreorderRelation a)

Ord a => Transitive (PreorderRelation a)

Ord a => Reflexive (PreorderRelation a)

Ord a => Graph (PreorderRelation a)

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)

type Vertex (PreorderRelation a) = a