Copyright | (c) Andrey Mokhov 2016-2017 |
---|---|

License | MIT (see the file LICENSE) |

Maintainer | andrey.mokhov@gmail.com |

Stability | experimental |

Safe Haskell | None |

Language | Haskell2010 |

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

data type -- the Boehm-Berarducci encoding of
algebraic graphs, which is used for generalised graph folding and for the
implementation of polymorphic graph construction and transformation algorithms.
`Fold`

is an instance of type classes defined in modules Algebra.Graph.Class
and Algebra.Graph.HigherKinded.Class, which can be used for polymorphic
graph construction and manipulation.

- data Fold a
- empty :: Graph g => g
- vertex :: Graph g => Vertex g -> g
- edge :: Graph g => Vertex g -> Vertex g -> g
- overlay :: Graph g => g -> g -> g
- connect :: Graph g => g -> g -> g
- vertices :: Graph g => [Vertex g] -> g
- edges :: Graph g => [(Vertex g, Vertex g)] -> g
- overlays :: Graph g => [g] -> g
- connects :: Graph g => [g] -> g
- graph :: Graph g => [Vertex g] -> [(Vertex g, Vertex g)] -> g
- foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold a -> b
- isSubgraphOf :: (Graph g, Eq g) => g -> g -> Bool
- isEmpty :: Fold a -> Bool
- size :: Fold a -> Int
- hasVertex :: Eq a => a -> Fold a -> Bool
- hasEdge :: Ord a => a -> a -> Fold a -> Bool
- vertexCount :: Ord a => Fold a -> Int
- edgeCount :: Ord a => Fold a -> Int
- vertexList :: Ord a => Fold a -> [a]
- edgeList :: Ord a => Fold a -> [(a, a)]
- vertexSet :: Ord a => Fold a -> Set a
- vertexIntSet :: Fold Int -> IntSet
- edgeSet :: Ord a => Fold a -> Set (a, a)
- 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
- mesh :: (Graph g, Vertex g ~ (a, b)) => [a] -> [b] -> g
- torus :: (Graph g, Vertex g ~ (a, b)) => [a] -> [b] -> g
- deBruijn :: (Graph g, Vertex g ~ [a]) => Int -> [a] -> g
- removeVertex :: (Eq (Vertex g), Graph g) => Vertex g -> Fold (Vertex g) -> g
- removeEdge :: (Eq (Vertex g), Graph g) => Vertex g -> Vertex g -> Fold (Vertex g) -> g
- replaceVertex :: (Eq (Vertex g), Graph g) => Vertex g -> Vertex g -> Fold (Vertex g) -> g
- mergeVertices :: Graph g => (Vertex g -> Bool) -> Vertex g -> Fold (Vertex g) -> g
- splitVertex :: (Eq (Vertex g), Graph g) => Vertex g -> [Vertex g] -> Fold (Vertex g) -> g
- transpose :: Graph g => Fold (Vertex g) -> g
- gmap :: Graph g => (a -> Vertex g) -> Fold a -> g
- bind :: Graph g => Fold a -> (a -> g) -> g
- induce :: Graph g => (Vertex g -> Bool) -> Fold (Vertex g) -> g
- simplify :: (Eq g, Graph g) => Fold (Vertex g) -> g
- box :: (Graph g, Vertex g ~ (a, b)) => Fold a -> Fold b -> g

# Boehm-Berarducci encoding of algebraic graphs

The `Fold`

datatype is the Boehm-Berarducci encoding of the core graph
construction primitives `empty`

, `vertex`

, `overlay`

and `connect`

. We define a
`Num`

instance as a convenient notation for working with graphs:

0 == vertex 0 1 + 2 == overlay (vertex 1) (vertex 2) 1 * 2 == connect (vertex 1) (vertex 2) 1 + 2 * 3 == overlay (vertex 1) (connect (vertex 2) (vertex 3)) 1 * (2 + 3) == connect (vertex 1) (overlay (vertex 2) (vertex 3))

The `Show`

instance is defined using basic graph construction primitives:

show (empty :: Fold Int) == "empty" show (1 :: Fold Int) == "vertex 1" show (1 + 2 :: Fold Int) == "vertices [1,2]" show (1 * 2 :: Fold Int) == "edge 1 2" show (1 * 2 * 3 :: Fold Int) == "edges [(1,2),(1,3),(2,3)]" show (1 * 2 + 3 :: Fold Int) == "graph [1,2,3] [(1,2)]"

The `Eq`

instance is currently implemented using the `AdjacencyMap`

as the
*canonical graph representation* and satisfies all axioms of algebraic graphs:

`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

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. For example, if g is a `Fold`

then *n*, *m* and *s* can be
computed as follows:

n ==`vertexCount`

g m ==`edgeCount`

g s ==`size`

g

Note that `size`

is slightly different from the `length`

method of the
`Foldable`

type class, as the latter does not count `empty`

leaves of the
expression:

`length`

`empty`

== 0`size`

`empty`

== 1`length`

(`vertex`

x) == 1`size`

(`vertex`

x) == 1`length`

(`empty`

+`empty`

) == 0`size`

(`empty`

+`empty`

) == 2

The `size`

of any graph is positive, and the difference `(`

corresponds to the number of occurrences of `size`

g - `length`

g)`empty`

in an expression `g`

.

Converting a `Fold`

to the corresponding `AdjacencyMap`

takes *O(s + m * log(m))*
time and *O(s + m)* memory. This is also the complexity of the graph equality test,
because it is currently implemented by converting graph expressions to canonical
representations based on adjacency maps.

Monad Fold Source # | |

Functor Fold Source # | |

Applicative Fold Source # | |

Foldable Fold Source # | |

Traversable Fold Source # | |

Alternative Fold Source # | |

MonadPlus Fold Source # | |

ToGraph Fold Source # | |

Graph Fold Source # | |

Ord a => Eq (Fold a) Source # | |

Num a => Num (Fold a) Source # | |

(Ord a, Show a) => Show (Fold a) Source # | |

ToGraph (Fold a) Source # | |

Graph (Fold a) Source # | |

type ToVertex (Fold a) Source # | |

type Vertex (Fold a) Source # | |

# Basic graph construction primitives

empty :: Graph g => g Source #

Construct the *empty graph*.
Complexity: *O(1)* time, memory and size.

`isEmpty`

empty == True`hasVertex`

x empty == False`vertexCount`

empty == 0`edgeCount`

empty == 0`size`

empty == 1

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

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

edge x y ==`connect`

(`vertex`

x) (`vertex`

y)`hasEdge`

x y (edge x y) == True`edgeCount`

(edge x y) == 1`vertexCount`

(edge 1 1) == 1`vertexCount`

(edge 1 2) == 2

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

*Overlay* two graphs. This is an idempotent, commutative and associative
operation with the identity `empty`

.
Complexity: *O(1)* time and memory, *O(s1 + s2)* size.

`isEmpty`

(overlay x y) ==`isEmpty`

x &&`isEmpty`

y`hasVertex`

z (overlay x y) ==`hasVertex`

z x ||`hasVertex`

z y`vertexCount`

(overlay x y) >=`vertexCount`

x`vertexCount`

(overlay x y) <=`vertexCount`

x +`vertexCount`

y`edgeCount`

(overlay x y) >=`edgeCount`

x`edgeCount`

(overlay x y) <=`edgeCount`

x +`edgeCount`

y`size`

(overlay x y) ==`size`

x +`size`

y`vertexCount`

(overlay 1 2) == 2`edgeCount`

(overlay 1 2) == 0

connect :: Graph g => g -> g -> g Source #

*Connect* two graphs. This is an associative operation with the identity
`empty`

, which distributes over the overlay and obeys the decomposition axiom.
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 x y) ==`isEmpty`

x &&`isEmpty`

y`hasVertex`

z (connect x y) ==`hasVertex`

z x ||`hasVertex`

z y`vertexCount`

(connect x y) >=`vertexCount`

x`vertexCount`

(connect x y) <=`vertexCount`

x +`vertexCount`

y`edgeCount`

(connect x y) >=`edgeCount`

x`edgeCount`

(connect x y) >=`edgeCount`

y`edgeCount`

(connect x y) >=`vertexCount`

x *`vertexCount`

y`edgeCount`

(connect x y) <=`vertexCount`

x *`vertexCount`

y +`edgeCount`

x +`edgeCount`

y`size`

(connect x y) ==`size`

x +`size`

y`vertexCount`

(connect 1 2) == 2`edgeCount`

(connect 1 2) == 1

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

x . vertices ==`elem`

x`vertexCount`

. vertices ==`length`

.`nub`

`vertexSet`

. vertices == Set.`fromList`

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

# Graph folding

foldg :: b -> (a -> b) -> (b -> b -> b) -> (b -> b -> b) -> Fold a -> b Source #

Generalised graph folding: recursively collapse a `Fold`

by applying
the provided functions to the leaves and internal nodes of the expression.
The order of arguments is: empty, vertex, overlay 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)*.

foldg`empty`

`vertex`

`overlay`

`connect`

== id foldg`empty`

`vertex`

`overlay`

(flip`connect`

) ==`transpose`

foldg [] return (++) (++) ==`toList`

foldg 0 (const 1) (+) (+) ==`length`

foldg 1 (const 1) (+) (+) ==`size`

foldg True (const False) (&&) (&&) ==`isEmpty`

# 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

# Graph properties

isEmpty :: Fold 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 isEmpty (`removeEdge`

x y $`edge`

x y) == False

hasVertex :: Eq a => a -> Fold 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

vertexCount :: Ord a => Fold 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 => Fold a -> [a] Source #

edgeList :: Ord a => Fold a -> [(a, a)] Source #

The sorted list of edges of a graph.
Complexity: *O(s + m * log(m))* time and *O(m)* memory. Note that the number of
edges *m* of a graph can be quadratic with respect to the expression size *s*.

edgeList`empty`

== [] edgeList (`vertex`

x) == [] edgeList (`edge`

x y) == [(x,y)] edgeList (`star`

2 [3,1]) == [(2,1), (2,3)] edgeList .`edges`

==`nub`

.`sort`

edgeList .`transpose`

==`sort`

. map`swap`

. edgeList

vertexIntSet :: Fold 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

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

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`

mesh :: (Graph g, Vertex g ~ (a, b)) => [a] -> [b] -> g 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, Vertex g ~ (a, b)) => [a] -> [b] -> g 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, Vertex g ~ [a]) => Int -> [a] -> g 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) ==`gmap`

`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

removeEdge :: (Eq (Vertex g), Graph g) => Vertex g -> Vertex g -> Fold (Vertex g) -> g Source #

Remove an edge from a given graph.
Complexity: *O(s)* time and memory. The worst case size complexity is *O(s^2)*,
although in practice it is usually also linear *O(s)*.

removeEdge x y (`edge`

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 (Vertex g), Graph g) => Vertex g -> Vertex g -> Fold (Vertex g) -> g Source #

The function

replaces vertex `replaceVertex`

x y`x`

with vertex `y`

in a
given graph expression. 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 => (Vertex g -> Bool) -> Vertex g -> Fold (Vertex g) -> g 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 (Vertex g), Graph g) => Vertex g -> [Vertex g] -> Fold (Vertex g) -> g 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)

transpose :: Graph g => Fold (Vertex g) -> g Source #

Transpose a given graph.
Complexity: *O(s)* time, memory and size.

transpose`empty`

==`empty`

transpose (`vertex`

x) ==`vertex`

x transpose (`edge`

x y) ==`edge`

y x transpose . transpose == id transpose .`path`

==`path`

.`reverse`

transpose .`circuit`

==`circuit`

.`reverse`

transpose .`clique`

==`clique`

.`reverse`

transpose (`box`

x y) ==`box`

(transpose x) (transpose y)`edgeList`

. transpose ==`sort`

. map`swap`

.`edgeList`

bind :: Graph g => Fold a -> (a -> g) -> g Source #

Transform a given graph by substituting each of its vertices with a subgraph.
This is similar to Monad's bind `>>=`

but can be used with non-fully-parametric
graphs.

bind`empty`

f ==`empty`

bind (`vertex`

x) f == f x bind (`edge`

x y) f ==`connect`

(f x) (f y) bind (`vertices`

xs) f ==`overlays`

(`map`

f xs) bind x (const`empty`

) ==`empty`

bind x`vertex`

== x bind (bind x f) g == bind x (\y -> bind (f y) g)

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

simplify :: (Eq g, Graph g) => Fold (Vertex g) -> g Source #

Simplify a graph expression. Semantically, this is the identity function,
but it simplifies a given polymorphic graph expression according to the laws
of the algebra. The function does not compute the simplest possible expression,
but uses heuristics to obtain useful simplifications in reasonable time.
Complexity: the function performs *O(s)* graph comparisons. It is guaranteed
that the size of the result does not exceed the size of the given expression.
Below the operator `~>`

denotes the *is simplified to* relation.

simplify == id`size`

(simplify x) <=`size`

x simplify`empty`

~>`empty`

simplify 1 ~> 1 simplify (1 + 1) ~> 1 simplify (1 + 2 + 1) ~> 1 + 2 simplify (1 * 1 * 1) ~> 1 * 1

# Graph composition

box :: (Graph g, Vertex g ~ (a, b)) => Fold a -> Fold b -> g 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`

`transpose`

(box x y) == box (`transpose`

x) (`transpose`

y)`vertexCount`

(box x y) ==`vertexCount`

x *`vertexCount`

y`edgeCount`

(box x y) <=`vertexCount`

x *`edgeCount`

y +`edgeCount`

x *`vertexCount`

y