Algebra.Graph.Relation.Symmetric.Internal

This module exposes the implementation of symmetric binary 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.Symmetric instead.

Implementation of symmetric binary relations

newtype Relation a

This data type represents a symmetric binary relation over a set of elements of type a. Symmetric relations satisfy all laws of the Undirected type class, including the commutativity of connect:

connect x y == connect y x

The Show instance lists edge vertices in non-decreasing order:

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 (2 * 1     :: Relation Int) == "edge 1 2"
show (1 * 2 * 1 :: Relation Int) == "edges [(1,1),(1,2)]"
show (3 * 2 * 1 :: Relation Int) == "edges [(1,2),(1,3),(2,3)]"
show (1 * 2 + 3 :: Relation Int) == "overlay (vertex 3) (edge 1 2)"

The total order on graphs is defined using size-lexicographic comparison:

• Compare the number of vertices. In case of a tie, continue.
• Compare the sets of vertices. In case of a tie, continue.
• Compare the number of edges. In case of a tie, continue.
• Compare the sets of edges.

Here are a few examples:

vertex 1 < vertex 2
vertex 3 < edge 1 2
vertex 1 < edge 1 1
edge 1 1 < edge 1 2
edge 1 2 < edge 1 1 + edge 2 2
edge 2 1 < edge 1 3

edge 1 2 == edge 2 1

Note that the resulting order refines the isSubgraphOf relation and is compatible with overlay and connect operations:

isSubgraphOf x y ==> x <= y

empty <= x
x     <= x + y
x + y <= x * y

Constructors

SR (Relation a)

Instances

Ord a => Eq (Relation a)

Defined in Algebra.Graph.Relation.Symmetric.Internal

Methods

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

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

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

Defined in Algebra.Graph.Relation.Symmetric.Internal

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 => Ord (Relation a)

Defined in Algebra.Graph.Relation.Symmetric.Internal

Methods

compare :: Relation a -> Relation a -> Ordering

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

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

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

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

max :: Relation a -> Relation a -> Relation a

min :: Relation a -> Relation a -> Relation a

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

Defined in Algebra.Graph.Relation.Symmetric.Internal

Methods

showsPrec :: Int -> Relation a -> ShowS

show :: Relation a -> String

showList :: [Relation a] -> ShowS

NFData a => NFData (Relation a)

Defined in Algebra.Graph.Relation.Symmetric.Internal

Methods

rnf :: Relation a -> ()

Ord a => ToGraph (Relation a)

See Algebra.Graph.Symmetric.Relation. Warning: this instance is likely to be modified or removed in future.

Defined in Algebra.Graph.ToGraph

Associated Types

type ToVertex (Relation a) :: Type

Methods

toGraph :: Relation a -> Graph (ToVertex (Relation a))

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

isEmpty :: Relation a -> Bool

size :: Relation a -> Int

hasVertex :: ToVertex (Relation a) -> Relation a -> Bool

hasEdge :: ToVertex (Relation a) -> ToVertex (Relation a) -> Relation a -> Bool

vertexCount :: Relation a -> Int

edgeCount :: Relation a -> Int

vertexList :: Relation a -> [ToVertex (Relation a)]

edgeList :: Relation a -> [(ToVertex (Relation a), ToVertex (Relation a))]

vertexSet :: Relation a -> Set (ToVertex (Relation a))

vertexIntSet :: Relation a -> IntSet

edgeSet :: Relation a -> Set (ToVertex (Relation a), ToVertex (Relation a))

preSet :: ToVertex (Relation a) -> Relation a -> Set (ToVertex (Relation a))

preIntSet :: Int -> Relation a -> IntSet

postSet :: ToVertex (Relation a) -> Relation a -> Set (ToVertex (Relation a))

postIntSet :: Int -> Relation a -> IntSet

adjacencyList :: Relation a -> [(ToVertex (Relation a), [ToVertex (Relation a)])]

adjacencyMap :: Relation a -> Map (ToVertex (Relation a)) (Set (ToVertex (Relation a)))

adjacencyIntMap :: Relation a -> IntMap IntSet

adjacencyMapTranspose :: Relation a -> Map (ToVertex (Relation a)) (Set (ToVertex (Relation a)))

adjacencyIntMapTranspose :: Relation a -> IntMap IntSet

dfsForest :: Relation a -> Forest (ToVertex (Relation a))

dfsForestFrom :: [ToVertex (Relation a)] -> Relation a -> Forest (ToVertex (Relation a))

dfs :: [ToVertex (Relation a)] -> Relation a -> [ToVertex (Relation a)]

reachable :: ToVertex (Relation a) -> Relation a -> [ToVertex (Relation a)]

topSort :: Relation a -> Maybe [ToVertex (Relation a)]

isAcyclic :: Relation a -> Bool

toAdjacencyMap :: Relation a -> AdjacencyMap (ToVertex (Relation a))

toAdjacencyMapTranspose :: Relation a -> AdjacencyMap (ToVertex (Relation a))

toAdjacencyIntMap :: Relation a -> AdjacencyIntMap

toAdjacencyIntMapTranspose :: Relation a -> AdjacencyIntMap

isDfsForestOf :: Forest (ToVertex (Relation a)) -> Relation a -> Bool

isTopSortOf :: [ToVertex (Relation a)] -> Relation a -> Bool

Ord a => Undirected (Relation a)

Defined in Algebra.Graph.Class

Ord a => Graph (Relation a)

Defined in Algebra.Graph.Class

Associated Types

type Vertex (Relation a) :: Type

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)

Defined in Algebra.Graph.ToGraph

type ToVertex (Relation a) = a

type Vertex (Relation a)

Defined in Algebra.Graph.Class

type Vertex (Relation a) = a

fromSymmetric :: Relation a -> Relation a

Extract the underlying symmetric Algebra.Graph.Relation. Complexity: O(1) time and memory.

fromSymmetric (edge 1 2)    == edges [(1,2), (2,1)]
vertexCount . fromSymmetric == vertexCount
edgeCount   . fromSymmetric <= (*2) . edgeCount

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
vertexCount (vertex x) == 1
edgeCount   (vertex x) == 0

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

Overlay two graphs. This is a commutative, associative and idempotent 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 a commutative and associative operation with the identity empty, which distributes over 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).

connect x y               == connect y x
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 `div` 2
vertexCount (connect 1 2) == 2
edgeCount   (connect 1 2) == 1

edgeSet :: Ord a => Relation a -> Set (a, a)

The set of edges of a given graph, where edge vertices appear in the non-decreasing order. Complexity: O(m) time.

Note: If you need the set of edges where an edge appears in both directions, use relation . fromSymmetric. The latter is much faster than this function, and takes only O(1) time and memory.

edgeSet empty      == Set.empty
edgeSet (vertex x) == Set.empty
edgeSet (edge x y) == Set.singleton (min x y, max x y)

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

Check if the internal representation of a symmetric relation is consistent, i.e. if (i) all pairs of elements in the relation refer to existing elements in the domain, and (ii) all edges have their symmetric counterparts. 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 (stars xs)    == True