Is the derivative of a graph related to adjacency lists?

Some of Conor McBride's works, Diff, Dissect, relate the derivative of data types to their "type of one-hole contexts". That is, if you take the derivative of the type you are left with a data type which shows you how the data type looks from the inside at any given point.

So, for instance, if you have a list (in Haskell)

data List a = [] | a : List a

this corresponds to

data List a = 1 + a * List a

and through a little mathematical magic, the derivative is

data ListDeriv a = List a * List a

which is interpreted to mean that at any point in the list there will be a list to the left and a list to the right. We can zip through the original list by using the derivative data structure.

Now, I'm interested in doing something similar with graphs. A common representation of graphs is a set of vertices and edges, which might be naively implemented with a data type such as:

data Gr a b i = Gr [(i,a)] [(i,i,b)]

If I understand it correctly, a derivative of this data type, with respect to the graph index, i, should be something like.

data GrDeriv a b i = d/di (Gr a b i)
     = d\di ( [a*i] * [b*i^2] )
     = (d\di [a*i]) * [b*i^2] ) + [a*i]*(d/di [b*i^2])
     = (a* [a*i] * [a*i]) * [b*i^2] ) 
       + [a*i] * (2*b*i) *[b*i^2]*[b*i^2])
     = InNodes { nodesLeft :: [(a,i)]
               , nodeLbl :: a
               , nodesRight :: [(a,i)]
               , edges :: [(b,i,i)] }
     | InEdges { nodes :: [(a,i)]
               , adjNode :: Either (b,i) (b,i)
               , edgesLeft :: [(b,i,i)]
               , edgesRight :: [(b,i,i)] }

I got this through the use of the product rule and chain rules for derivatives, and although possibly there are some errors, it seems to follow the general scheme. In this structure you will either be focused on Nodes (InNodes constructor) or Edges (In edges) and given the place you will see the relevant data.

But this isn't what I was hoping for. I was hoping for a construct more clos

Your type Gr does not really correspond to graphs, because it includes many instances that are clearly not graphs, because the edge indices need not be actual vertex indices.

For example,

$$ V = \{A, B\} \;\;\;\; E = \{(C, D, e)\} $$

is not a graph, but is allowed in your type as

Gr [(1, A), (2, B)] [(3, 4, e)]

Rather, your Gr corresponds literally to a list of labeled indexes and a separate, unrelated, list of labeled pairs of indices. This is why you get such a "literal" derivative of Gr that doesn't correspond to "holes" in graphs.

There's also the unfortunate problem of caring about the order of vertices/edges (visible in the nodesLeft/Right and edgesLeft/Right distinctions) but this can be fixed by using a Set instead of a list.

Here is a type expressed in Haskell that I think more closely corresponds to (non-empty) graphs:

data Graph v e = Lone v | Joined v (Graph (v, ([e], [e])) e)

For simplicity, I'll instead consider complete, simple, undirected graphs:

data Graph v e = Lone v | Joined v (Graph (v, e) e)

(To relax complete-ness, let e = Bool mark edge presence)

Note that Graph is recursive (and in fact, parametrically recursive). This is what allows us to restrict ourselves the type to just graphs and not just adjacency lists combined with vertex lists.

Written more algebraically,

$$ G(v, e) = v + v G(v e, e) $$

Since $e$ doesn't vary with $v$, I'm going to eliminate the second argument to $G$:

$$ G(v) = v + v G(v e) $$

By repeatedly expanding, we get the fixed point

$$G(v) = v^1 e^{\binom 1 2} + v^2 e^{\binom 2 2} + v^3 e^{\binom 3 2} + v^4 e^{\binom 4 2} + \dots$$

This makes sense, since a (complete) graph is either

• One vertices and no edges

• Two vertices and one edge

• Three vertices and three edges

• Four vertices and four choose 2 = 6 edges

• ....

Call the type of size $k$ graphs $G_k(v) = v^k e^{\binom k 2} $. Then $G(v) = G_1(v) + G_2(v) + \dots$

which has derivative

$$ \frac d {dv} G(v)
= \sum_{i=1} G_i'(v)
$$

The derivative $$
G_k'(v)
= \frac d {dv} \left[ v^k e^{\frac {k(k-1)} 2} \right]
= k v^{k-1} e^{\frac {k(k-1)} 2}
$$

Note that $G_{k-1}(v) = v^{k-1} e^{\frac {(k-1)(k-2)} 2}$, so that $G_k'(v) = G_{k-1}(v) k e^{k-1} $

That is, the derivative of a $k$-node graph is a $k-1$ node graph, combined with the $k-1$ edges from the removed node to the $k-1$ remaining nodes, and the index $k$ that the node occupied in the list of vertices.

data SimpleGraph v e = Lone v | Joined v (SimpleGraph (v, e) e)

data SimpleGraphHole v e = Empty
                         | InsertLater v (SimpleGraphHole (v, e) e)
                         | InsertHere (SimpleGraph (v, e) e)

Fixing Order in this graph

This version of the Graph data structure is fundamentally a linked-list, and so it encodes the order of vertices. While that could be fixed in your adjacency-list version by using a Set, it's not so direct here.

I think you can modify a tree data-structure to do the same kind of parametric recursion, with the root playing the role the "head" does in SimpleGraph. By the interface of the resulting tree-sets, the order/underlying structure becomes invisible (or even canonical, if you aren't interested in fast updates).

Your Proposed Derivative

You proposed a derivative type; I'll change it to conflate the labels and indices as I did: ([(v,e)], [(v,e)])

This can be integrated as $ \int \frac 1 {(1 - ve)^2}$ which is
$ C + \frac v {1 - ve} $, or just (v, [(v, e)]). This doesn't have enough information to reconstruct an entire graph, because the "edge" information only identifies a single vertex.

StackExchange Computer Science Q#70301, answer score: 7