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

Algebra.Graph.HigherKinded.Class

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 defines the core type class Graph, a few graph subclasses, and basic polymorphic graph construction primitives. Functions that cannot be implemented fully polymorphically and require the use of an intermediate data type are not included. For example, to compute the size of a Graph expression you will need to use a concrete data type, such as Algebra.Graph.

See Algebra.Graph.Class for alternative definitions where the core type class is not higher-kinded and permits more instances.

Synopsis

# The core type class

class (Traversable g, MonadPlus g) => Graph g where Source #

The core type class for constructing algebraic graphs is defined by introducing the connect method to the standard MonadPlus class and reusing the following existing methods:

• The empty method comes from the Alternative class and corresponds to the empty graph. This module simply re-exports it.
• The vertex graph construction primitive is an alias for pure of the Applicative type class.
• Graph overlay is an alias for mplus of the MonadPlus type class.

The Graph type class is characterised by the following minimal set of axioms. In equations we use + and * as convenient shortcuts for overlay and connect, respectively.

• overlay is commutative and associative:

      x + y == y + x
x + (y + z) == (x + y) + z
• connect is associative and has empty as the identity:

  x * empty == x
empty * x == x
x * (y * z) == (x * y) * z
• connect distributes over overlay:

x * (y + z) == x * y + x * z
(x + y) * z == x * z + y * z
• connect can be decomposed:

x * y * z == x * y + x * z + y * z

The following useful theorems can be proved from the above set of axioms.

• overlay has empty as the identity and is idempotent:

  x + empty == x
empty + x == x
x + x == x
• Absorption and saturation of connect:

x * y + x + y == x * y
x * x * x == x * x

The core type class Graph corresponds to unlabelled directed graphs. Undirected, Reflexive, Transitive and Preorder graphs can be obtained by extending the minimal set of axioms.

When specifying the time and memory complexity of graph algorithms, n will denote the number of vertices in the graph, m will denote the number of edges in the graph, and s will denote the size of the corresponding Graph expression.

Minimal complete definition

connect

Methods

connect :: g a -> g a -> g a Source #

Connect two graphs.

Instances

 Source # Methodsconnect :: Fold a -> Fold a -> Fold a Source # Source # Methodsconnect :: Graph a -> Graph a -> Graph a Source #

empty :: Alternative f => forall a. f a #

The identity of <|>

vertex :: Graph g => a -> g a Source #

Construct the graph comprising a single isolated vertex. An alias for pure.

overlay :: Graph g => g a -> g a -> g a Source #

Overlay two graphs. An alias for <|>.

# Undirected graphs

class Graph g => Undirected g Source #

The class of undirected graphs that satisfy the following additional axiom.

• connect is commutative:

x * y == y * x

# Reflexive graphs

class Graph g => Reflexive g Source #

The class of reflexive graphs that satisfy the following additional axiom.

• Each vertex has a self-loop:

vertex x == vertex x * vertex x

Or, alternatively, if we remember that vertex is an alias for pure:

pure x == pure x * pure x

Note that by applying the axiom in the reverse direction, one can always remove all self-loops resulting in an irreflexive graph. This type class can therefore be also used in the context of irreflexive graphs.

# Transitive graphs

class Graph g => Transitive g Source #

The class of transitive graphs that satisfy the following additional axiom.

• The closure axiom: graphs with equal transitive closures are equal.

y /= empty ==> x * y + x * z + y * z == x * y + y * z

By repeated application of the axiom one can turn any graph into its transitive closure or transitive reduction.

# Preorders

class (Reflexive g, Transitive g) => Preorder g Source #

The class of preorder graphs that are both reflexive and transitive.

# Basic graph construction primitives

edge :: Graph g => a -> a -> g a Source #

Construct the graph comprising a single edge. Complexity: O(1) time, memory and size.

edge x y               == connect (vertex x) (vertex y)
vertexCount (edge 1 1) == 1
vertexCount (edge 1 2) == 2


vertices :: Graph g => [a] -> g 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 x
hasVertex x . vertices == elem x
vertexCount . vertices == length . nub
vertexSet   . vertices == Set.fromList


edges :: Graph g => [(a, a)] -> g a Source #

Construct the graph from a list of edges. Complexity: O(L) time, memory and size, where L is the length of the given list.

edges []      == empty
edges [(x,y)] == edge x y


overlays :: Graph g => [g a] -> g 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
isEmpty . overlays == all isEmpty


connects :: Graph g => [g a] -> g a Source #

Connect 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.

connects []        == empty
connects [x]       == x
connects [x,y]     == connect x y
isEmpty . connects == all isEmpty


graph :: Graph g => [a] -> [(a, a)] -> g a Source #

Construct the graph from given lists of vertices V and edges E. The resulting graph contains the vertices V as well as all the vertices referred to by the edges E. Complexity: O(|V| + |E|) time, memory and size.

graph []  []      == empty
graph [x] []      == vertex x
graph []  [(x,y)] == edge x y
graph vs  es      == overlay (vertices vs) (edges es)


# Relations on graphs

isSubgraphOf :: (Graph g, Eq (g a)) => g a -> g a -> Bool Source #

The isSubgraphOf function takes two graphs and returns True if the first graph is a subgraph of the second. Here is the current implementation:

isSubgraphOf x y = overlay x y == y


The complexity therefore depends on the complexity of equality testing of the specific graph instance.

isSubgraphOf empty         x             == True
isSubgraphOf (vertex x)    empty         == False
isSubgraphOf x             (overlay x y) == True
isSubgraphOf (overlay x y) (connect x y) == True
isSubgraphOf (path xs)     (circuit xs)  == True


# Graph properties

isEmpty :: Graph g => g a -> Bool Source #

Check if a graph is empty. A convenient alias for null. Complexity: O(s) time.

isEmpty empty                       == True
isEmpty (overlay empty empty)       == True
isEmpty (vertex x)                  == False
isEmpty (removeVertex x $vertex x) == True  hasVertex :: (Eq a, Graph g) => a -> g a -> Bool Source # Check if a graph contains a given vertex. A convenient alias for elem. Complexity: O(s) time. hasVertex x empty == False hasVertex x (vertex x) == True hasVertex x . removeVertex x == const False  hasEdge :: (Eq (g a), Graph g, Ord a) => a -> a -> g a -> Bool Source # Check if a graph contains a given edge. Complexity: O(s) time. hasEdge x y empty == False hasEdge x y (vertex z) == False hasEdge x y (edge x y) == True hasEdge x y == elem (x,y) . edgeList  vertexCount :: (Ord a, Graph g) => g a -> Int Source # The number of vertices in a graph. Complexity: O(s * log(n)) time. vertexCount empty == 0 vertexCount (vertex x) == 1 vertexCount == length . vertexList  vertexList :: (Ord a, Graph g) => g a -> [a] Source # The sorted list of vertices of a given graph. Complexity: O(s * log(n)) time and O(n) memory. vertexList empty == [] vertexList (vertex x) == [x] vertexList . vertices == nub . sort  vertexSet :: (Ord a, Graph g) => g a -> Set a Source # The set of vertices of a given graph. Complexity: O(s * log(n)) time and O(n) memory. vertexSet empty == Set.empty vertexSet . vertex == Set.singleton vertexSet . vertices == Set.fromList vertexSet . clique == Set.fromList  vertexIntSet :: Graph g => g Int -> IntSet Source # The set of vertices of a given graph. Like vertexSet but specialised for graphs with vertices of type Int. Complexity: O(s * log(n)) time and O(n) memory. vertexIntSet empty == IntSet.empty vertexIntSet . vertex == IntSet.singleton vertexIntSet . vertices == IntSet.fromList vertexIntSet . clique == IntSet.fromList  # Standard families of graphs path :: Graph g => [a] -> g a Source # The path on a list of vertices. Complexity: O(L) time, memory and size, where L is the length of the given list. path [] == empty path [x] == vertex x path [x,y] == edge x y  circuit :: Graph g => [a] -> g a Source # The circuit on a list of vertices. Complexity: O(L) time, memory and size, where L is the length of the given list. circuit [] == empty circuit [x] == edge x x circuit [x,y] == edges [(x,y), (y,x)]  clique :: Graph g => [a] -> g a Source # The clique on a list of vertices. Complexity: O(L) time, memory and size, where L is the length of the given list. clique [] == empty clique [x] == vertex x clique [x,y] == edge x y clique [x,y,z] == edges [(x,y), (x,z), (y,z)] clique (xs ++ ys) == connect (clique xs) (clique ys)  biclique :: Graph g => [a] -> [a] -> g a Source # The biclique on a list of vertices. Complexity: O(L1 + L2) time, memory and size, where L1 and L2 are the lengths of the given lists. biclique [] [] == empty biclique [x] [] == vertex x biclique [] [y] == vertex y biclique [x1,x2] [y1,y2] == edges [(x1,y1), (x1,y2), (x2,y1), (x2,y2)] biclique xs ys == connect (vertices xs) (vertices ys)  star :: Graph g => a -> [a] -> g a Source # The star formed by a centre vertex and a list of leaves. Complexity: O(L) time, memory and size, where L is the length of the given list. star x [] == vertex x star x [y] == edge x y star x [y,z] == edges [(x,y), (x,z)]  tree :: Graph g => Tree a -> g a Source # The tree graph constructed from a given Tree data structure. Complexity: O(T) time, memory and size, where T is the size of the given tree (i.e. the number of vertices in the tree). tree (Node x []) == vertex x tree (Node x [Node y [Node z []]]) == path [x,y,z] tree (Node x [Node y [], Node z []]) == star x [y,z] tree (Node 1 [Node 2 [], Node 3 [Node 4 [], Node 5 []]]) == edges [(1,2), (1,3), (3,4), (3,5)]  forest :: Graph g => Forest a -> g a Source # The forest graph constructed from a given Forest data structure. Complexity: O(F) time, memory and size, where F is the size of the given forest (i.e. the number of vertices in the forest). forest [] == empty forest [x] == tree x forest [Node 1 [Node 2 [], Node 3 []], Node 4 [Node 5 []]] == edges [(1,2), (1,3), (4,5)] forest == overlays . map tree  mesh :: Graph g => [a] -> [b] -> g (a, b) Source # Construct a mesh graph from two lists of vertices. Complexity: O(L1 * L2) time, memory and size, where L1 and L2 are the lengths of the given lists. mesh xs [] == empty mesh [] ys == empty mesh [x] [y] == vertex (x, y) mesh xs ys == box (path xs) (path ys) mesh [1..3] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(2,'b')), ((2,'a'),(2,'b')) , ((2,'a'),(3,'a')), ((2,'b'),(3,'b')), ((3,'a'),(3,'b')) ]  torus :: Graph g => [a] -> [b] -> g (a, b) Source # Construct a torus graph from two lists of vertices. Complexity: O(L1 * L2) time, memory and size, where L1 and L2 are the lengths of the given lists. torus xs [] == empty torus [] ys == empty torus [x] [y] == edge (x, y) (x, y) torus xs ys == box (circuit xs) (circuit ys) torus [1,2] "ab" == edges [ ((1,'a'),(1,'b')), ((1,'a'),(2,'a')), ((1,'b'),(1,'a')), ((1,'b'),(2,'b')) , ((2,'a'),(1,'a')), ((2,'a'),(2,'b')), ((2,'b'),(1,'b')), ((2,'b'),(2,'a')) ]  deBruijn :: Graph g => Int -> [a] -> g [a] Source # Construct a De Bruijn graph of a given non-negative dimension using symbols from a given alphabet. Complexity: O(A^(D + 1)) time, memory and size, where A is the size of the alphabet and D is the dimention of the graph.  deBruijn 0 xs == edge [] [] n > 0 ==> deBruijn n [] == empty deBruijn 1 [0,1] == edges [ ([0],[0]), ([0],[1]), ([1],[0]), ([1],[1]) ] deBruijn 2 "0" == edge "00" "00" deBruijn 2 "01" == edges [ ("00","00"), ("00","01"), ("01","10"), ("01","11") , ("10","00"), ("10","01"), ("11","10"), ("11","11") ] transpose (deBruijn n xs) == fmap reverse$ deBruijn n xs
vertexCount (deBruijn n xs) == (length $nub xs)^n n > 0 ==> edgeCount (deBruijn n xs) == (length$ nub xs)^(n + 1)


# Graph transformation

removeVertex :: (Eq a, Graph g) => a -> g a -> g a Source #

Remove a vertex from a given graph. Complexity: O(s) time, memory and size.

removeVertex x (vertex x)       == empty
removeVertex x . removeVertex x == removeVertex x


replaceVertex :: (Eq a, Graph g) => a -> a -> g a -> g a Source #

The function replaceVertex x y replaces vertex x 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            == mergeVertices (== x) y


mergeVertices :: Graph g => (a -> Bool) -> a -> g a -> g a Source #

Merge vertices satisfying a given predicate with a given vertex. Complexity: O(s) time, memory and size, assuming that the predicate takes O(1) to be evaluated.

mergeVertices (const False) x    == id
mergeVertices (== x) y           == replaceVertex x y
mergeVertices even 1 (0 * 2)     == 1 * 1
mergeVertices odd  1 (3 + 4 * 5) == 4 * 1


splitVertex :: (Eq a, Graph g) => a -> [a] -> g a -> g a Source #

Split a vertex into a list of vertices with the same connectivity. Complexity: O(s + k * L) time, memory and size, where k is the number of occurrences of the vertex in the expression and L is the length of the given list.

splitVertex x []                  == removeVertex x
splitVertex x [x]                 == id
splitVertex x [y]                 == replaceVertex x y
splitVertex 1 [0,1] \$ 1 * (2 + 3) == (0 + 1) * (2 + 3)


induce :: Graph g => (a -> Bool) -> g a -> g 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


# Graph composition

box :: Graph g => g a -> g b -> g (a, b) Source #

Compute the Cartesian product of graphs. Complexity: O(s1 * s2) time, memory and size, where s1 and s2 are the sizes of the given graphs.

box (path [0,1]) (path "ab") == edges [ ((0,'a'), (0,'b'))
, ((0,'a'), (1,'a'))
, ((0,'b'), (1,'b'))
, ((1,'a'), (1,'b')) ]


Up to an isomorphism between the resulting vertex types, this operation is commutative, associative, distributes over overlay, has singleton graphs as identities and empty as the annihilating zero. Below ~~ stands for the equality up to an isomorphism, e.g. (x, ()) ~~ x.

box x y               ~~ box y x
box x (box y z)       ~~ box (box x y) z
box x (overlay y z)   == overlay (box x y) (box x z)
box x (vertex ())     ~~ x
box x empty           ~~ empty
vertexCount (box x y) == vertexCount x * vertexCount y
edgeCount   (box x y) <= vertexCount x * edgeCount y + edgeCount x * vertexCount y


# Conversion between graph data types

class ToGraph t where Source #

The ToGraph type class captures data types that can be converted to polymorphic graph expressions. The conversion method toGraph semantically acts as the identity on graph data structures, but allows to convert graphs between different data representations.

      toGraph (g     :: Graph a  ) :: Graph a   == g
show (toGraph (1 * 2 :: Graph Int) :: Fold Int) == "edge 1 2"


Minimal complete definition

toGraph

Methods

toGraph :: Graph g => t a -> g a Source #

Instances

 Source # MethodstoGraph :: Graph g => Fold a -> g a Source # Source # MethodstoGraph :: Graph g => Graph a -> g a Source #