[A]

graphis a structure amounting to a set of objects in which some pairs of the objects are in some sense “related”.

- Adjacency list
- Adjacency matrix
- Incidence matrix

A graph

`G`

consists of a set`E(G)`

ofedgesand a (disjoint) set`V(G)`

ofvertices, together with a relation ofincidencewhich associates with each edge two vertices, not necessarily distinct, called itsends.

So we have objects (nodes and edges) and a relationship (incidence).

`data Graph nodes edges = Gr (Graph {nodes | edges} incidence)`

- If only it was that simple…

- Using laziness to create a value that depends on itself.
`fibs = 1 : 1 : zipWith (+) fibs (tail fibs)`

Can we use tying the knot at the conceptual/data structural level?

- Assume we have an existing graph data structure
- Define a new graph data structure in terms of the existing one
~~Recurse~~Try to set`new == existing`

- Profit ?!?

Theoretical | Vertices | Arcs |

Existing graph structure | Nodes | Edges |

New graph structure | Objects | Relationships |

```
class Graph g where
type Vertex g
type Arc g
vertices :: g -> Set (Vertex g)
arcs :: g -> Set (Arc g)
incident :: g -> Vertex g -> Set (Arc g)
ends :: g -> Arc g -> Set (Vertex g)
```

```
instance Graph (GrEx node edge) where
type Vertex (GrEx node edge) = node
type Arc (GrEx node edge) = edge
...
```

```
data Node object relationship a where
Object :: object -> Node Object
Relationship :: relationship
-> Node Relationship
getO :: Node o r a -> Maybe o
getR :: Node o r a -> Maybe r
```

```
data Edge = Edge (Node Object)
(Node Relationship)
newtype GrNew object relationship
= GrNew (GrEx (Node object relationship)
Edge)
```

```
instance Graph (GrNew o r) where
type Vertex (GrNew o r) = o
type Arc (GrNew o r) = r
vertices = mapMaybe getO . vertices
arcs = mapMaybe getR . vertices
incident g = mapMaybe getR . incident g
. Object
ends g = mapMaybe getO . incident g
. Relationship
```

```
data Edge = Edge (Node Object)
(Node Relationship)
```

- No object has an edge with another object
- No relationship has an edge with another relationship
- So why are they combined in the same datatype?

- Before:
`G = (object | relationship) + edges`

- Now:
`G = objects + relationships + edges`

`edges`

set?- Explicit realisation of the
`incident`

and`ends`

methods. - Why not attach those values directly to the
`objects`

and`relationships`

? - Convert these
`Set`

s into dictionaries.

- Not quite.
- I’ve augmented it with an
*incidence list*. - Most obvious implementations don’t do this.
- FGL in particular is an optimised adjacency list.

- Most people are used to having to have an arbitrary
`Node`

type. - But what about edges?
- With this, we need to decide upon an identifier for edges as well.

`type Edge = (Node, Node)`

- I’m trying to create an
*arbitrary*(hyper)graph structure. - I believe directionality, labels, planarity, etc. are
*extra*information that provide extra meta-relationships. - To differentiate multiple edges, we can’t just rely on
`(Node, Node)`

.

```
data Simple node
= Gr (Set node) (Set (node, node))
instance Graph (Simple node) where
type Vertex (Simple node) = node
type Arc (Simple node) = (node, node)
...
```

- Recent series of blog posts by Andrey Mokhov.
Adds the following functions:

`vertex :: Vertex g -> g overlay :: g -> g -> g connect :: g -> g -> g`

`vertex n = Gr (singleton n) empty`

```
-- Graph union
overlay (Gr n1 e1) (Gr n2 e2)
= Gr (n1 `union` n2)
(e1 `union` e2)
```

```
-- As with overlay,
-- but add edges from n1 to n2
connect (Gr n1 e1) (Gr n2 e2)
= Gr (n1 `union` n2)
(e1 `union` e2
`union` (zip n1 n2))
```

- Andrey had already used this exact datatype.
- But I’ve “derived” it.

- Probably not that much.
- I just wanted to see where I would get to.

- Try and extend this further if possible.
- Help please!

- Use this to implement a new library.