algebraic-graphs-0.0.5: A library for algebraic graph construction and transformation

Copyright(c) Andrey Mokhov 2016-2017
LicenseMIT (see the file LICENSE)
Safe HaskellNone




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


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

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 x empty      == Set.empty
neighbours x (vertex x) == Set.empty
neighbours x (edge x y) == Set.fromList [y]
neighbours y (edge x y) == Set.fromList [x]