Is the derivative of a graph related to adjacency lists?

Question

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 closely related to the interface of Martin Erwigs Functional Graph Library. Specifically, I want to see at a node a context representing the label of the node and two adjacency lists, one for outgoing, one for incoming.

Node a b = ([(i,b)],a,[(i,b)])

I do see hope, however, as the adjacency representation has some terms in common with the derivative, the lone lable, a, at each hole location, the adjacency representation/dissection of each edge.

Since a derivative isn't the same function as the original, but an integration of the derivative is (kindof), is there some sort of integration analogue which will serve to transform the derivative into a collection of node contexts? Not a direct integration to recover the original structure, mind you, but a structure equivalent to the original but in a more algorithm friendly representation.

If there is, I hope that relationship type structures can be specified by some easy "set of vertices and edges" language and I can derive an efficient library for working with that structure. Such an implemenation could be used to study structures "beyond graph theory": hyper graphs, simplicial complexes...

So. Does this idea seem feasible? Useful? Has there been any study into this type of thing which I could read more about?

Addendum

As commented upon by Curtis F, a set of nodes and edges is not exactly a graph. However, all graphs can be represented by such, and I find it common enough presentation. I've seen (the very coarse specification) $G=(V,E)$ used in research that applies graph theory to optimizations of wireless networks in various ways. Here's an open-access example, DRAND*. This raises the question, what is the link between the presentation and how some software might be implemented based upon the research.

That said, I'm not entirely opposed to changing the input spec from $G=(V,E)$ to something else. For instance, given an index type $I$, node labels, $V$, and edge labels, $E$. Then the graph is (approximately) a function from indexes to a label and edge list.

$$ G = I \to (V * I \to E) $$

This, I'm pretty sure can be expressed (Category theory?) as

$$ G = (V * E^{I})^{I} \tag{1} $$

or

$$ G = V^I * E^{I*I} $$

which can be seen as a set of vertices and edges--given enough caveats. However, its not clear if the derivative of $(1)$ is meaningful:

$$ G' = \ln(V * E^{I}) * (V * E^{I})^{I} * (\ln(E) * V * E^{I}) $$

I for one do think it shows some promise, but I lack the sophistication to go further. I know there must be some work out there exploring the connection further.

* In case the link ever breaks, citation: Rhee, Injong, et al. "DRAND: Distributed randomized TDMA scheduling for wireless ad hoc networks." IEEE Transactions on Mobile Computing 8.10 (2009): 1384-1396.

Answer 1

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.