Copyright | (c) Andrey Mokhov 2016-2017 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
An abstract implementation of symmetric binary relations. Use Algebra.Graph.Class for polymorphic construction and manipulation.
- data SymmetricRelation a
- fromRelation :: Relation a -> SymmetricRelation a
- toRelation :: Ord a => SymmetricRelation a -> Relation a
- neighbours :: Ord a => a -> SymmetricRelation a -> Set a
Data structure
data SymmetricRelation a Source #
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)]"
Ord a => Eq (SymmetricRelation a) Source # | |
(Num a, Ord a) => Num (SymmetricRelation a) Source # | |
(Ord a, Show a) => Show (SymmetricRelation a) Source # | |
Ord a => Undirected (SymmetricRelation a) Source # | |
Ord a => Graph (SymmetricRelation a) Source # | |
type Vertex (SymmetricRelation a) Source # | |
fromRelation :: Relation a -> SymmetricRelation a Source #
Construct a symmetric relation from a Relation
.
Complexity: O(1) time.
toRelation :: Ord a => SymmetricRelation a -> Relation a Source #
Extract the underlying relation. Complexity: O(m*log(m)) time.
Graph properties
neighbours :: Ord a => a -> SymmetricRelation a -> Set a Source #
The set of neighbours of an element x
is the set of elements that are
related to it, i.e. neighbours x == { a | aRx }
. In the context of undirected
graphs, this corresponds to the set of adjacent vertices of vertex x
.
neighbours xempty
== Set.empty
neighbours x (vertex
x) == Set.empty
neighbours x (edge
x y) == Set.fromList
[y] neighbours y (edge
x y) == Set.fromList
[x]