Algebra.Graph.Relation.Symmetric

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

Data structure

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

Instances

Ord a => Eq (SymmetricRelation a)

Defined in Algebra.Graph.Relation.InternalDerived

Methods

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

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

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

Defined in Algebra.Graph.Relation.InternalDerived

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)

Defined in Algebra.Graph.Relation.InternalDerived

Methods

showsPrec :: Int -> SymmetricRelation a -> ShowS

show :: SymmetricRelation a -> String

showList :: [SymmetricRelation a] -> ShowS

NFData a => NFData (SymmetricRelation a)

Defined in Algebra.Graph.Relation.InternalDerived

Methods

rnf :: SymmetricRelation a -> ()

Ord a => Undirected (SymmetricRelation a)

Defined in Algebra.Graph.Relation.InternalDerived

Ord a => Graph (SymmetricRelation a)

Defined in Algebra.Graph.Relation.InternalDerived

Associated Types

type Vertex (SymmetricRelation a) :: Type

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)

Defined in Algebra.Graph.Relation.InternalDerived

type Vertex (SymmetricRelation a) = a

fromRelation :: Relation a -> SymmetricRelation a

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

toRelation :: Ord a => SymmetricRelation a -> Relation a

Extract the underlying relation. Complexity: O(m*log(m)) time.

Graph properties

neighbours :: Ord a => a -> SymmetricRelation a -> Set a

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]