Algebra.Graph.Label

Alga is a library for algebraic construction and manipulation of graphs in Haskell. See this paper for the motivation behind the library, the underlying theory, and implementation details.

This module provides basic data types and type classes for representing edge labels in edge-labelled graphs, e.g. see Algebra.Graph.Labelled.

Type classes for edge labels

class Semilattice a where

A bounded join semilattice, satisfying the following laws:

• Commutativity:

  x \/ y == y \/ x

• Associativity:

  x \/ (y \/ z) == (x \/ y) \/ z

• Identity:

  x \/ zero == x

• Idempotence:

  x \/ x == x

Minimal complete definition

zero, (\/)

Methods

zero :: a

(\/) :: a -> a -> a infixl 6

Instances

Semilattice Bool

Defined in Algebra.Graph.Label

Methods

zero :: Bool

(\/) :: Bool -> Bool -> Bool

Ord a => Semilattice (Set a)

Defined in Algebra.Graph.Label

Methods

zero :: Set a

(\/) :: Set a -> Set a -> Set a

Ord a => Semilattice (Distance a)

Defined in Algebra.Graph.Label

Methods

zero :: Distance a

(\/) :: Distance a -> Distance a -> Distance a

class Semilattice a => Dioid a where

A dioid is an idempotent semiring, i.e. it satisfies the following laws:

• Associativity:

  x /\ (y /\ z) == (x /\ y) /\ z

• Identity:

  x /\ one == x
  one /\ x == x

• Annihilating zero:

  x /\ zero == zero
  zero /\ x == zero

• Distributivity:

  x /\ (y \/ z) == x /\ y \/ x /\ z
  (x \/ y) /\ z == x /\ z \/ y /\ z

Minimal complete definition

one, (/\)

Methods

one :: a

(/\) :: a -> a -> a infixl 7

Instances

Dioid Bool

Defined in Algebra.Graph.Label

Methods

one :: Bool

(/\) :: Bool -> Bool -> Bool

(Num a, Ord a) => Dioid (Distance a)

Defined in Algebra.Graph.Label

Methods

one :: Distance a

(/\) :: Distance a -> Distance a -> Distance a

Data types for edge labels

data Distance a

A distance is a non-negative value that can be Finite or Infinite.

Constructors

Finite a

Infinite

Instances

Eq a => Eq (Distance a)

Defined in Algebra.Graph.Label

Methods

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

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

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

Defined in Algebra.Graph.Label

Methods

(+) :: Distance a -> Distance a -> Distance a

(-) :: Distance a -> Distance a -> Distance a

(*) :: Distance a -> Distance a -> Distance a

negate :: Distance a -> Distance a

abs :: Distance a -> Distance a

signum :: Distance a -> Distance a

fromInteger :: Integer -> Distance a

Ord a => Ord (Distance a)

Defined in Algebra.Graph.Label

Methods

compare :: Distance a -> Distance a -> Ordering

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

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

(>) :: Distance a -> Distance a -> Bool

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

max :: Distance a -> Distance a -> Distance a

min :: Distance a -> Distance a -> Distance a

Show a => Show (Distance a)

Defined in Algebra.Graph.Label

Methods

showsPrec :: Int -> Distance a -> ShowS

show :: Distance a -> String

showList :: [Distance a] -> ShowS

(Num a, Ord a) => Dioid (Distance a)

Defined in Algebra.Graph.Label

Methods

one :: Distance a

(/\) :: Distance a -> Distance a -> Distance a

Ord a => Semilattice (Distance a)

Defined in Algebra.Graph.Label

Methods

zero :: Distance a

(\/) :: Distance a -> Distance a -> Distance a