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

Algebra.Graph.Relation.Symmetric

Contents

Description

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

Synopsis

# Data structure

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

Instances

 Ord a => Eq (SymmetricRelation a) Source # Methods (Num a, Ord a) => Num (SymmetricRelation a) Source # Methods (Ord a, Show a) => Show (SymmetricRelation a) Source # MethodsshowList :: [SymmetricRelation a] -> ShowS # Source # Ord a => Graph (SymmetricRelation a) Source # Associated Typestype Vertex (SymmetricRelation a) :: * Source # Methods type Vertex (SymmetricRelation a) Source # type Vertex (SymmetricRelation a) = a

Construct a symmetric relation from a Relation. Complexity: O(1) time.

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]