Knotted Graphs

Ivan Lazar Miljenovic

25 January, 2017

What is a graph?

Non-graphs

Let’s see some graphs!

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

  • Adjacency list
  • Adjacency matrix
  • 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?

Nodes and edges are bipartite

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 Sets 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.
  • But what about edges?
  • 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

To continue on though, let’s use this simplified example.

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.

  • Adds the following functions:

    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

  • Andrey had already used this exact datatype.
  • 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.
    • Help please!
  • Use this to implement a new library.