# Definitions

## What we use graphs to represent

[A] graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense “related”.

## The usual suspects

• Incidence matrix

## A more formal definition

A graph `G` consists of a set `E(G)` of edges and a (disjoint) set `V(G)` of vertices, together with a relation of incidence which associates with each edge two vertices, not necessarily distinct, called its ends.

## This sounds familiar…

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

## A graph is, well, a graph!

• ``````data Graph nodes edges
= Gr (Graph {nodes | edges}
incidence)``````
• If only it was that simple…

# Tie a knot in it

## Tying the knot

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

## The idea

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

## How to go about it

1. Assume we have an existing graph data structure
2. Define a new graph data structure in terms of the existing one
3. Recurse Try to set `new == existing`
4. Profit ?!?

## Levels

 Theoretical Vertices Arcs Existing graph structure Nodes Edges New graph structure Objects Relationships

## Specification

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

## Existing structure

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

...``````

## New Structure (1)

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

## New Structure (2)

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

newtype GrNew object relationship
= GrNew (GrEx (Node object relationship)
Edge)``````

## New Structure (3)

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

# Unravelling the knot

## Objects & Relationships

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

## Split them apart

• Before: `G = (object | relationship) + edges`
• Now: `G = objects + relationships + edges`

## Do we still need the `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.

## Haven’t you just re-invented adjacency lists?

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

## What does this mean?

• Most people are used to having to have an arbitrary `Node` type.
• With this, we need to decide upon an identifier for edges as well.

## The usual approach

`type Edge = (Node, Node)`

## Why do this?

• 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)`.

# Simple, directed graphs

## Implementation

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

...``````

## Algebra of graphs

• Recent series of blog posts by Andrey Mokhov.

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

## vertex

``vertex n = Gr (singleton n) empty``

## overlay

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

## connect

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

## This is actually how it was already done

• But I’ve “derived” it.

# ex relatio

## Is this new/novel??

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

## What’s next?

• Try and extend this further if possible.