Copyright | (c) Andrey Mokhov 2016-2018 |
---|---|
License | MIT (see the file LICENSE) |
Maintainer | andrey.mokhov@gmail.com |
Stability | experimental |
Safe Haskell | None |
Language | Haskell2010 |
Algebra.Graph.Labelled
Contents
Description
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 a minimal and experimental implementation of algebraic graphs with edge labels. The API will be expanded in the next release.
Synopsis
- data Graph e a
- empty :: Graph e a
- vertex :: a -> Graph e a
- edge :: e -> a -> a -> Graph e a
- (-<) :: a -> e -> (a, e)
- (>-) :: (a, e) -> a -> Graph e a
- overlay :: Monoid e => Graph e a -> Graph e a -> Graph e a
- connect :: e -> Graph e a -> Graph e a -> Graph e a
- vertices :: Monoid e => [a] -> Graph e a
- edges :: Monoid e => [(e, a, a)] -> Graph e a
- overlays :: Monoid e => [Graph e a] -> Graph e a
- foldg :: b -> (a -> b) -> (e -> b -> b -> b) -> Graph e a -> b
- isSubgraphOf :: (Eq e, Monoid e, Ord a) => Graph e a -> Graph e a -> Bool
- isEmpty :: Graph e a -> Bool
- size :: Graph e a -> Int
- hasVertex :: Eq a => a -> Graph e a -> Bool
- hasEdge :: (Eq e, Monoid e, Ord a) => a -> a -> Graph e a -> Bool
- edgeLabel :: (Eq a, Monoid e) => a -> a -> Graph e a -> e
- vertexList :: Ord a => Graph e a -> [a]
- edgeList :: (Eq e, Monoid e, Ord a) => Graph e a -> [(e, a, a)]
- vertexSet :: Ord a => Graph e a -> Set a
- edgeSet :: (Eq e, Monoid e, Ord a) => Graph e a -> Set (e, a, a)
- removeVertex :: Eq a => a -> Graph e a -> Graph e a
- removeEdge :: (Eq a, Eq e, Monoid e) => a -> a -> Graph e a -> Graph e a
- replaceVertex :: Eq a => a -> a -> Graph e a -> Graph e a
- replaceEdge :: (Eq e, Monoid e, Ord a) => e -> a -> a -> Graph e a -> Graph e a
- transpose :: Graph e a -> Graph e a
- emap :: (e -> f) -> Graph e a -> Graph f a
- induce :: (a -> Bool) -> Graph e a -> Graph e a
- closure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a
- reflexiveClosure :: (Ord a, Semiring e) => Graph e a -> Graph e a
- symmetricClosure :: Monoid e => Graph e a -> Graph e a
- transitiveClosure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a
- type UnlabelledGraph a = Graph Any a
- type Automaton a s = Graph (RegularExpression a) s
- type Network e a = Graph (Distance e) a
- data Context e a = Context {}
- context :: (Eq e, Monoid e) => (a -> Bool) -> Graph e a -> Maybe (Context e a)
Algebraic data type for edge-labeleld graphs
Edge-labelled graphs, where the type variable e
stands for edge labels.
For example, Graph
Bool
a
is isomorphic to unlabelled graphs defined in
the top-level module Algebra.Graph.Graph, where False
and True
denote
the lack of and the existence of an unlabelled edge, respectively.
Instances
Construct the empty graph. An alias for the constructor Empty
.
Complexity: O(1) time, memory and size.
isEmpty
empty == TruehasVertex
x empty == FalsevertexCount
empty == 0edgeCount
empty == 0
vertex :: a -> Graph e a Source #
Construct the graph comprising a single isolated vertex. An alias for the
constructor Vertex
.
Complexity: O(1) time, memory and size.
isEmpty
(vertex x) == FalsehasVertex
x (vertex x) == TruevertexCount
(vertex x) == 1edgeCount
(vertex x) == 0
edge :: e -> a -> a -> Graph e a Source #
Construct the graph comprising a single labelled edge. Complexity: O(1) time, memory and size.
edge e x y ==connect
e (vertex
x) (vertex
y) edgezero
x y ==vertices
[x,y]hasEdge
x y (edge e x y) == (e /=zero
)edgeLabel
x y (edge e x y) == eedgeCount
(edge e x y) == if e ==zero
then 0 else 1vertexCount
(edge e 1 1) == 1vertexCount
(edge e 1 2) == 2
(-<) :: a -> e -> (a, e) infixl 5 Source #
The left-hand part of a convenient ternary-ish operator x-<e>-y
for
creating labelled edges.
x -<e>- y == edge
e x y
(>-) :: (a, e) -> a -> Graph e a infixl 5 Source #
The right-hand part of a convenient ternary-ish operator x-<e>-y
for
creating labelled edges.
x -<e>- y == edge
e x y
overlay :: Monoid e => Graph e a -> Graph e a -> Graph e a Source #
Overlay two graphs. An alias for Connect
zero
.
Complexity: O(1) time and memory, O(s1 + s2) size.
isEmpty
(overlay x y) ==isEmpty
x &&isEmpty
yhasVertex
z (overlay x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(overlay x y) >=vertexCount
xvertexCount
(overlay x y) <=vertexCount
x +vertexCount
yedgeCount
(overlay x y) >=edgeCount
xedgeCount
(overlay x y) <=edgeCount
x +edgeCount
yvertexCount
(overlay 1 2) == 2edgeCount
(overlay 1 2) == 0
Note: overlay
composes edges in parallel using the operator <+>
with
zero
acting as the identity:
edgeLabel
x y $ overlay (edge
e x y) (edge
zero
x y) == eedgeLabel
x y $ overlay (edge
e x y) (edge
f x y) == e<+>
f
Furthermore, when applied to transitive graphs, overlay
composes edges in
sequence using the operator <.>
with one
acting as the identity:
edgeLabel
x z $transitiveClosure
(overlay (edge
e x y) (edge
one
y z)) == eedgeLabel
x z $transitiveClosure
(overlay (edge
e x y) (edge
f y z)) == e<.>
f
connect :: e -> Graph e a -> Graph e a -> Graph e a Source #
Connect two graphs with edges labelled by a given label. An alias for
Connect
.
Complexity: O(1) time and memory, O(s1 + s2) size. Note that the number
of edges in the resulting graph is quadratic with respect to the number of
vertices of the arguments: m = O(m1 + m2 + n1 * n2).
isEmpty
(connect e x y) ==isEmpty
x &&isEmpty
yhasVertex
z (connect e x y) ==hasVertex
z x ||hasVertex
z yvertexCount
(connect e x y) >=vertexCount
xvertexCount
(connect e x y) <=vertexCount
x +vertexCount
yedgeCount
(connect e x y) <=vertexCount
x *vertexCount
y +edgeCount
x +edgeCount
yvertexCount
(connect e 1 2) == 2edgeCount
(connect e 1 2) == if e ==zero
then 0 else 1
vertices :: Monoid e => [a] -> Graph e a Source #
Construct the graph comprising a given list of isolated vertices. Complexity: O(L) time, memory and size, where L is the length of the given list.
vertices [] ==empty
vertices [x] ==vertex
xhasVertex
x . vertices ==elem
xvertexCount
. vertices ==length
.nub
vertexSet
. vertices == Set.fromList
overlays :: Monoid e => [Graph e a] -> Graph e a Source #
Overlay a given list of graphs. Complexity: O(L) time and memory, and O(S) size, where L is the length of the given list, and S is the sum of sizes of the graphs in the list.
overlays [] ==empty
overlays [x] == x overlays [x,y] ==overlay
x y overlays ==foldr
overlay
empty
isEmpty
. overlays ==all
isEmpty
Graph folding
foldg :: b -> (a -> b) -> (e -> b -> b -> b) -> Graph e a -> b Source #
Generalised Graph
folding: recursively collapse a Graph
by applying
the provided functions to the leaves and internal nodes of the expression.
The order of arguments is: empty, vertex and connect.
Complexity: O(s) applications of given functions. As an example, the
complexity of size
is O(s), since all functions have cost O(1).
foldgempty
vertex
connect
==id
foldgempty
vertex
(fmap
flip
connect
) ==transpose
foldg 1 (const
1) (const
(+)) ==size
foldg True (const
False) (const
(&&)) ==isEmpty
foldg False (== x) (const
(||)) ==hasVertex
x foldg Set.empty
Set.singleton
(const
Set.union
) ==vertexSet
Relations on graphs
isSubgraphOf :: (Eq e, Monoid e, Ord a) => Graph e a -> Graph e a -> Bool Source #
The isSubgraphOf
function takes two graphs and returns True
if the
first graph is a subgraph of the second.
Complexity: O(s + m * log(m)) time. Note that the number of edges m of a
graph can be quadratic with respect to the expression size s.
isSubgraphOfempty
x == True isSubgraphOf (vertex
x)empty
== False isSubgraphOf x (overlay
x y) == True isSubgraphOf (overlay
x y) (connect
x y) == True isSubgraphOf x y ==> x <= y
Graph properties
isEmpty :: Graph e a -> Bool Source #
Check if a graph is empty. A convenient alias for null
.
Complexity: O(s) time.
isEmptyempty
== True isEmpty (overlay
empty
empty
) == True isEmpty (vertex
x) == False isEmpty (removeVertex
x $vertex
x) == True isEmpty (removeEdge
x y $edge
e x y) == False
hasVertex :: Eq a => a -> Graph e a -> Bool Source #
Check if a graph contains a given vertex. Complexity: O(s) time.
hasVertex xempty
== False hasVertex x (vertex
x) == True hasVertex 1 (vertex
2) == False hasVertex x .removeVertex
x ==const
False
edgeLabel :: (Eq a, Monoid e) => a -> a -> Graph e a -> e Source #
Extract the label of a specified edge from a graph.
vertexList :: Ord a => Graph e a -> [a] Source #
Graph transformation
removeEdge :: (Eq a, Eq e, Monoid e) => a -> a -> Graph e a -> Graph e a Source #
Remove an edge from a given graph. Complexity: O(s) time, memory and size.
removeEdge x y (edge
e x y) ==vertices
[x,y] removeEdge x y . removeEdge x y == removeEdge x y removeEdge x y .removeVertex
x ==removeVertex
x removeEdge 1 1 (1 * 1 * 2 * 2) == 1 * 2 * 2 removeEdge 1 2 (1 * 1 * 2 * 2) == 1 * 1 + 2 * 2
replaceVertex :: Eq a => a -> a -> Graph e a -> Graph e a Source #
The function
replaces vertex replaceVertex
x yx
with vertex y
in a
given Graph
. If y
already exists, x
and y
will be merged.
Complexity: O(s) time, memory and size.
replaceVertex x x == id replaceVertex x y (vertex
x) ==vertex
y replaceVertex x y ==fmap
(\v -> if v == x then y else v)
emap :: (e -> f) -> Graph e a -> Graph f a Source #
Transform a graph by applying a function to each of its edge labels. Complexity: O(s) time, memory and size.
The function h
is required to be a homomorphism on the underlying type of
labels e
. At the very least it must preserve zero
and <+>
:
hzero
==zero
h x<+>
h y == h (x<+>
y)
If e
is also a semiring, then h
must also preserve the multiplicative
structure:
hone
==one
h x<.>
h y == h (x<.>
y)
If the above requirements hold, then the implementation provides the following guarantees.
emap hempty
==empty
emap h (vertex
x) ==vertex
x emap h (edge
e x y) ==edge
(h e) x y emap h (overlay
x y) ==overlay
(emap h x) (emap h y) emap h (connect
e x y) ==connect
(h e) (emap h x) (emap h y) emapid
==id
emap g . emap h == emap (g . h)
induce :: (a -> Bool) -> Graph e a -> Graph e a Source #
Construct the induced subgraph of a given graph by removing the vertices that do not satisfy a given predicate. Complexity: O(s) time, memory and size, assuming that the predicate takes O(1) to be evaluated.
induce (const
True ) x == x induce (const
False) x ==empty
induce (/= x) ==removeVertex
x induce p . induce q == induce (\x -> p x && q x)isSubgraphOf
(induce p x) x == True
Relational operations
closure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a Source #
Compute the reflexive and transitive closure of a graph over the underlying star semiring using the Warshall-Floyd-Kleene algorithm.
closureempty
==empty
closure (vertex
x) ==edge
one
x x closure (edge
e x x) ==edge
one
x x closure (edge
e x y) ==edges
[(one
,x,x), (e,x,y), (one
,y,y)] closure ==reflexiveClosure
.transitiveClosure
closure ==transitiveClosure
.reflexiveClosure
closure . closure == closurepostSet
x (closure y) == Set.fromList
(reachable
x y)
reflexiveClosure :: (Ord a, Semiring e) => Graph e a -> Graph e a Source #
Compute the reflexive closure of a graph over the underlying semiring by
adding a self-loop of weight one
to every vertex.
Complexity: O(n * log(n)) time.
reflexiveClosureempty
==empty
reflexiveClosure (vertex
x) ==edge
one
x x reflexiveClosure (edge
e x x) ==edge
one
x x reflexiveClosure (edge
e x y) ==edges
[(one
,x,x), (e,x,y), (one
,y,y)] reflexiveClosure . reflexiveClosure == reflexiveClosure
symmetricClosure :: Monoid e => Graph e a -> Graph e a Source #
Compute the symmetric closure of a graph by overlaying it with its own transpose. Complexity: O((n + m) * log(n)) time.
symmetricClosureempty
==empty
symmetricClosure (vertex
x) ==vertex
x symmetricClosure (edge
e x y) ==edges
[(e,x,y), (e,y,x)] symmetricClosure x ==overlay
x (transpose
x) symmetricClosure . symmetricClosure == symmetricClosure
transitiveClosure :: (Eq e, Ord a, StarSemiring e) => Graph e a -> Graph e a Source #
Compute the transitive closure of a graph over the underlying star semiring using a modified version of the Warshall-Floyd-Kleene algorithm, which omits the reflexivity step.
transitiveClosureempty
==empty
transitiveClosure (vertex
x) ==vertex
x transitiveClosure (edge
e x y) ==edge
e x y transitiveClosure . transitiveClosure == transitiveClosure
Types of edge-labelled graphs
type UnlabelledGraph a = Graph Any a Source #
A type synonym for unlabelled graphs.
type Automaton a s = Graph (RegularExpression a) s Source #
A type synonym for automata or labelled transition systems.
type Network e a = Graph (Distance e) a Source #
A network is a graph whose edges are labelled with distances.
Context
The Context
of a subgraph comprises its inputs
and outputs
, i.e. all
the vertices that are connected to the subgraph's vertices (along with the
corresponding edge labels). Note that inputs and outputs can belong to the
subgraph itself. In general, there are no guarantees on the order of vertices
in inputs
and outputs
; furthermore, there may be repetitions.
context :: (Eq e, Monoid e) => (a -> Bool) -> Graph e a -> Maybe (Context e a) Source #
Extract the Context
of a subgraph specified by a given predicate. Returns
Nothing
if the specified subgraph is empty.
context (const
False) x == Nothing context (== 1) (edge
e 1 2) == if e ==zero
then Just (Context
[] []) else Just (Context
[ ] [(e,2)]) context (== 2) (edge
e 1 2) == if e ==zero
then Just (Context
[] []) else Just (Context
[(e,1)] [ ]) context (const
True ) (edge
e 1 2) == if e ==zero
then Just (Context
[] []) else Just (Context
[(e,1)] [(e,2)]) context (== 4) (3 * 1 * 4 * 1 * 5) == Just (Context
[(one
,3), (one
,1)] [(one
,1), (one
,5)])