Copyright	(c) Andrey Mokhov 2016-2022
License	MIT (see the file LICENSE)
Maintainer	andrey.mokhov@gmail.com
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Algebra.Graph.Class

Contents

The core type class
Undirected graphs
Reflexive graphs
Transitive graphs
Preorders
Basic graph construction primitives
Relations on graphs
Standard families of graphs

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 number of vertices in a Graph expression you will need to use a concrete data type, such as Algebra.Graph.Graph or Algebra.Graph.AdjacencyMap .

See Algebra.Graph.HigherKinded.Class for the higher-kinded version of the core graph type class.

Synopsis

class Graph g where
- type Vertex g
- empty :: g
- vertex :: Vertex g -> g
- overlay :: g -> g -> g
- connect :: g -> g -> g
class Graph g => Undirected g
class Graph g => Reflexive g
class Graph g => Transitive g
class ( Reflexive g, Transitive g) => Preorder g
edge :: Graph g => Vertex g -> Vertex g -> g
vertices :: Graph g => [ Vertex g] -> g
overlays :: Graph g => [g] -> g
connects :: Graph g => [g] -> g
edges :: Graph g => [( Vertex g, Vertex g)] -> g
isSubgraphOf :: ( Graph g, Eq g) => g -> g -> Bool
path :: Graph g => [ Vertex g] -> g
circuit :: Graph g => [ Vertex g] -> g
clique :: Graph g => [ Vertex g] -> g
biclique :: Graph g => [ Vertex g] -> [ Vertex g] -> g
star :: Graph g => Vertex g -> [ Vertex g] -> g
tree :: Graph g => Tree ( Vertex g) -> g
forest :: Graph g => Forest ( Vertex g) -> g

The core type class

class Graph g where Source #

The core type class for constructing algebraic graphs, 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.

Associated Types

type Vertex g Source #

The type of graph vertices.

Methods

empty :: g Source #

Construct the empty graph.

vertex :: Vertex g -> g Source #

Construct the graph with a single vertex.

overlay :: g -> g -> g Source #

Overlay two graphs.

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

Connect two graphs.

Instances

Instances details

Graph () Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex () Source # Methods empty :: () Source # vertex :: Vertex () -> () Source # overlay :: () -> () -> () Source # connect :: () -> () -> () Source #
Graph AdjacencyIntMap Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex AdjacencyIntMap Source # Methods empty :: AdjacencyIntMap Source # vertex :: Vertex AdjacencyIntMap -> AdjacencyIntMap Source # overlay :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap Source # connect :: AdjacencyIntMap -> AdjacencyIntMap -> AdjacencyIntMap Source #
Graph g => Graph ( Maybe g) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( Maybe g) Source # Methods empty :: Maybe g Source # vertex :: Vertex ( Maybe g) -> Maybe g Source # overlay :: Maybe g -> Maybe g -> Maybe g Source # connect :: Maybe g -> Maybe g -> Maybe g Source #
Ord a => Graph ( AdjacencyMap a) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( AdjacencyMap a) Source # Methods empty :: AdjacencyMap a Source # vertex :: Vertex ( AdjacencyMap a) -> AdjacencyMap a Source # overlay :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a Source # connect :: AdjacencyMap a -> AdjacencyMap a -> AdjacencyMap a Source #
Graph ( Graph a) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( Graph a) Source # Methods empty :: Graph a Source # vertex :: Vertex ( Graph a) -> Graph a Source # overlay :: Graph a -> Graph a -> Graph a Source # connect :: Graph a -> Graph a -> Graph a Source #
Ord a => Graph ( Relation a) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( Relation a) Source # Methods empty :: Relation a Source # vertex :: Vertex ( Relation a) -> Relation a Source # overlay :: Relation a -> Relation a -> Relation a Source # connect :: Relation a -> Relation a -> Relation a Source #
Ord a => Graph ( Relation a) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( Relation a) Source # Methods empty :: Relation a Source # vertex :: Vertex ( Relation a) -> Relation a Source # overlay :: Relation a -> Relation a -> Relation a Source # connect :: Relation a -> Relation a -> Relation a Source #
Graph ( Graph a) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( Graph a) Source # Methods empty :: Graph a Source # vertex :: Vertex ( Graph a) -> Graph a Source # overlay :: Graph a -> Graph a -> Graph a Source # connect :: Graph a -> Graph a -> Graph a Source #
Ord a => Graph ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive Associated Types type Vertex ( TransitiveRelation a) Source # Methods empty :: TransitiveRelation a Source # vertex :: Vertex ( TransitiveRelation a) -> TransitiveRelation a Source # overlay :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source # connect :: TransitiveRelation a -> TransitiveRelation a -> TransitiveRelation a Source #
Ord a => Graph ( ReflexiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Reflexive Associated Types type Vertex ( ReflexiveRelation a) Source # Methods empty :: ReflexiveRelation a Source # vertex :: Vertex ( ReflexiveRelation a) -> ReflexiveRelation a Source # overlay :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a Source # connect :: ReflexiveRelation a -> ReflexiveRelation a -> ReflexiveRelation a Source #
Ord a => Graph ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder Associated Types type Vertex ( PreorderRelation a) Source # Methods empty :: PreorderRelation a Source # vertex :: Vertex ( PreorderRelation a) -> PreorderRelation a Source # overlay :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source # connect :: PreorderRelation a -> PreorderRelation a -> PreorderRelation a Source #
Ord a => Graph ( Todo a) Source #
Instance details Defined in Algebra.Graph.Example.Todo Associated Types type Vertex ( Todo a) Source # Methods empty :: Todo a Source # vertex :: Vertex ( Todo a) -> Todo a Source # overlay :: Todo a -> Todo a -> Todo a Source # connect :: Todo a -> Todo a -> Todo a Source #
Graph g => Graph (a -> g) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex (a -> g) Source # Methods empty :: a -> g Source # vertex :: Vertex (a -> g) -> a -> g Source # overlay :: (a -> g) -> (a -> g) -> a -> g Source # connect :: (a -> g) -> (a -> g) -> a -> g Source #
( Graph g, Graph h) => Graph (g, h) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex (g, h) Source # Methods empty :: (g, h) Source # vertex :: Vertex (g, h) -> (g, h) Source # overlay :: (g, h) -> (g, h) -> (g, h) Source # connect :: (g, h) -> (g, h) -> (g, h) Source #
( Dioid e, Eq e, Ord a) => Graph ( AdjacencyMap e a) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( AdjacencyMap e a) Source # Methods empty :: AdjacencyMap e a Source # vertex :: Vertex ( AdjacencyMap e a) -> AdjacencyMap e a Source # overlay :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a Source # connect :: AdjacencyMap e a -> AdjacencyMap e a -> AdjacencyMap e a Source #
Dioid e => Graph ( Graph e a) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex ( Graph e a) Source # Methods empty :: Graph e a Source # vertex :: Vertex ( Graph e a) -> Graph e a Source # overlay :: Graph e a -> Graph e a -> Graph e a Source # connect :: Graph e a -> Graph e a -> Graph e a Source #
( Graph g, Graph h, Graph i) => Graph (g, h, i) Source #
Instance details Defined in Algebra.Graph.Class Associated Types type Vertex (g, h, i) Source # Methods empty :: (g, h, i) Source # vertex :: Vertex (g, h, i) -> (g, h, i) Source # overlay :: (g, h, i) -> (g, h, i) -> (g, h, i) Source # connect :: (g, h, i) -> (g, h, i) -> (g, h, i) Source #

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
```

Instances

Instances details

Undirected () Source #
Instance details Defined in Algebra.Graph.Class
Undirected g => Undirected ( Maybe g) Source #
Instance details Defined in Algebra.Graph.Class
Ord a => Undirected ( Relation a) Source #
Instance details Defined in Algebra.Graph.Class
Undirected ( Graph a) Source #
Instance details Defined in Algebra.Graph.Class
Undirected g => Undirected (a -> g) Source #
Instance details Defined in Algebra.Graph.Class
( Undirected g, Undirected h) => Undirected (g, h) Source #
Instance details Defined in Algebra.Graph.Class
( Undirected g, Undirected h, Undirected i) => Undirected (g, h, i) Source #
Instance details Defined in Algebra.Graph.Class

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
```

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.

Instances

Instances details

Reflexive () Source #
Instance details Defined in Algebra.Graph.Class
Reflexive g => Reflexive ( Maybe g) Source #
Instance details Defined in Algebra.Graph.Class
Ord a => Reflexive ( ReflexiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Reflexive
Ord a => Reflexive ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder
Reflexive g => Reflexive (a -> g) Source #
Instance details Defined in Algebra.Graph.Class
( Reflexive g, Reflexive h) => Reflexive (g, h) Source #
Instance details Defined in Algebra.Graph.Class
( Reflexive g, Reflexive h, Reflexive i) => Reflexive (g, h, i) Source #
Instance details Defined in Algebra.Graph.Class

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.

Instances

Instances details

Transitive () Source #
Instance details Defined in Algebra.Graph.Class
Transitive g => Transitive ( Maybe g) Source #
Instance details Defined in Algebra.Graph.Class
Ord a => Transitive ( TransitiveRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Transitive
Ord a => Transitive ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder
Transitive g => Transitive (a -> g) Source #
Instance details Defined in Algebra.Graph.Class
( Transitive g, Transitive h) => Transitive (g, h) Source #
Instance details Defined in Algebra.Graph.Class
( Transitive g, Transitive h, Transitive i) => Transitive (g, h, i) Source #
Instance details Defined in Algebra.Graph.Class

Preorders

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

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

Instances

Instances details

Preorder () Source #
Instance details Defined in Algebra.Graph.Class
Preorder g => Preorder ( Maybe g) Source #
Instance details Defined in Algebra.Graph.Class
Ord a => Preorder ( PreorderRelation a) Source #
Instance details Defined in Algebra.Graph.Relation.Preorder
Preorder g => Preorder (a -> g) Source #
Instance details Defined in Algebra.Graph.Class
( Preorder g, Preorder h) => Preorder (g, h) Source #
Instance details Defined in Algebra.Graph.Class
( Preorder g, Preorder h, Preorder i) => Preorder (g, h, i) Source #
Instance details Defined in Algebra.Graph.Class

Basic graph construction primitives

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

Construct the graph comprising a single edge.

edge x y == connect (vertex x) (vertex y)

vertices :: Graph g => [ Vertex g] -> g 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
vertices     == overlays . map vertex

overlays :: Graph g => [g] -> g 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

connects :: Graph g => [g] -> g 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
connects       == foldr connect empty

edges :: Graph g => [( Vertex g, Vertex g)] -> g 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

Relations on graphs

isSubgraphOf :: ( Graph g, Eq g) => g -> g -> 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

Standard families of graphs

path :: Graph g => [ Vertex g] -> g 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 => [ Vertex g] -> g 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 => [ Vertex g] -> g 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 => [ Vertex g] -> [ Vertex g] -> g Source #

The biclique on two lists 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 => Vertex g -> [ Vertex g] -> g Source #

The star formed by a centre vertex connected to 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)]
star x ys    == connect (vertex x) (vertices ys)

tree :: Graph g => Tree ( Vertex g) -> g 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 ( Vertex g) -> g 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