Algebra.Graph.Label

A semiring extends a commutative Monoid with operation <.> that acts similarly to multiplication over the underlying (additive) monoid and has one as the identity. This module also provides two convenient aliases: zero for mempty, and <+> for <>, which makes the interface more uniform.

Instances of this type class must satisfy the following semiring laws:

• Associativity of <+> and <.>:

  x <+> (y <+> z) == (x <+> y) <+> z
  x <.> (y <.> z) == (x <.> y) <.> z

• Identities of <+> and <.>:

  zero <+> x == x == x <+> zero
   one <.> x == x == x <.> one

• Commutativity of <+>:

  x <+> y == y <+> x

• Annihilating zero:

  x <.> zero == zero
  zero <.> x == zero

• Distributivity:

  x <.> (y <+> z) == x <.> y <+> x <.> z
  (x <+> y) <.> z == x <.> z <+> y <.> z

An alias for mempty.

An alias for <>.

A star semiring is a Semiring with an additional unary operator star satisfying the following two laws:

star a = one <+> a <.> star a
star a = one <+> star a <.> a

A dioid is an idempotent semiring, i.e. it satisfies the following idempotence law in addition to the Semiring laws:

x <+> x == x

A non-negative value that can be finite or infinite. Note: the current implementation of the Num instance raises an error on negative literals and on the negate method.

A finite non-negative value or Nothing if the argument is negative.

A finite Word.

A non-negative finite value, created unsafely: the argument is not checked for being non-negative, so unsafeFinite (-1) compiles just fine.

The (non-negative) infinite value.

Get a finite value or Nothing if the value is infinite.

A distance is a non-negative value that can be finite or infinite. Distances form a Dioid as follows:

zero  = distance infinite
one   = 0
(<+>) = min
(<.>) = (+)

A non-negative distance.

Get the value of a distance.

A capacity is a non-negative value that can be finite or infinite. Capacities form a Dioid as follows:

zero  = 0
one   = capacity infinite
(<+>) = max
(<.>) = min

A non-negative capacity.

Get the value of a capacity.

A count is a non-negative value that can be finite or infinite. Counts form a Semiring as follows:

zero  = 0
one   = 1
(<+>) = (+)
(<.>) = (*)

A non-negative count.

Get the value of a count.

The power set over the underlying set of elements a. If a is a monoid, then the power set forms a Dioid as follows:

zero    = PowerSet Set.empty
one     = PowerSet $ Set.singleton mempty
x <+> y = PowerSet $ Set.union (getPowerSet x) (getPowerSet y)
x <.> y = PowerSet $ cartesianProductWith mappend (getPowerSet x) (getPowerSet y)

If a is a monoid, Minimum a forms the following Dioid:

zero  = noMinimum
one   = pure mempty
(<+>) = liftA2 min
(<.>) = liftA2 mappend

To create a singleton value of type Minimum a use the pure function. For example:

getMinimum (pure "Hello, " <+> pure "World!") == Just "Hello, "
getMinimum (pure "Hello, " <.> pure "World!") == Just "Hello, World!"

Extract the minimum or Nothing if it does not exist.

The value corresponding to the lack of minimum, e.g. the minimum of the empty set.

A path is a list of edges.

The type of free labels over the underlying set of symbols a. Label values can be manipulated via its Semigroup, Monoid and StarSemiring class instances.

Wrap a value into a Symbol constructor

Wrap a list of values into Symbol constructors terminated by Zero

Check if a Label is zero.

A type synonym for regular expressions, built on top of free labels.

An optimum semiring obtained by combining a semiring o that defines an optimisation criterion, and a semiring a that describes the arguments of an optimisation problem. For example, by choosing o = Distance Int and and a = Minimum (Path String), we obtain the shortest path semiring for computing the shortest path in an Int-labelled graph with String vertices.

We assume that the semiring o is selective i.e. for all x and y:

x <+> y == x || x <+> y == y

In words, the operation <+> always simply selects one of its arguments. For example, the Capacity and Distance semirings are selective, whereas the the Count semiring is not.

The Optimum semiring specialised to finding the lexicographically smallest shortest path.

The Optimum semiring specialised to finding all shortest paths.

The Optimum semiring specialised to counting all shortest paths.

The Optimum semiring specialised to finding the lexicographically smallest widest path.