# Generic Recursion Applied to Algebraic Graphs

It would be such a shame if I couldn’t combine Rust, recursion schemes, and graphs into one blog post (with the added bonus of leaving out C++). So here we go!

Just recently, two articles have surfaced describing generic recursion in Rust. I recommend reading them. There will likely be further posts in the series, but I didn’t want to wait to at least try out the basics of the `recursion`

crate. Thinking of what recursive data structures could be tried, I decided to start by prototyping a Rust adaptation of `alga`

, a Haskell library for algebraic graphs.

## Representation

*small aside: I’m focusing on alga’s Graph type specifically, not the Graph typeclass it defines, of which many more-efficient representations are made an instance, because it was the simplest representation I could use to play with the recursion crate*

Below we have an adapted form of the datatype introduced in the paper *Algebraic Graphs with Class*.

```
#[derive(Debug, Clone)]
pub enum RGraph<Val, A> {
Empty,
Vertex(Val),
Overlay(A, A),
Connect(A, A),
}
```

A `Graph`

can be one of:

`Empty`

: no vertices, no edges`Vertex`

: a single vertex of type`Val`

`Overlay`

: a graph built by taking the union of both sets of vertices, and both sets of edges (*V*_{1}∪*V*_{2},*E*_{1}∪*E*_{2})`Connect`

: a graph constructed by connecting the edges of the two graphs. This is done by unioning in the same way as`Overlay`

, but additionally unioning the resulting edge set with the cross-product of both vertex sets (*V*_{1}∪*V*_{2},*E*_{1}∪*E*_{2}∪*V*_{1}×*V*_{2})

For further detail, I encourage you to check out the paper and library.

## Functors via the `recursion`

crate

With the recursive definition out of the way, let’s make use of the `recursion`

crate’s `RecursionTree`

to make `RGraph`

a functor, wrapping the type with a struct `Graph`

:

```
use recursion::map_layer::MapLayer;
use recursion::recursive_tree::arena_eval::ArenaIndex;
use recursion::recursive_tree::RecursiveTree;
pub type RecursiveGraph<V> = RecursiveTree<RGraph<V, ArenaIndex>, ArenaIndex>;
impl<A, B, V> MapLayer<B> for RGraph<V, A> {
type To = RGraph<V, B>;
type Unwrapped = A;
fn map_layer<F: FnMut(Self::Unwrapped) -> B>(self, mut f: F) -> Self::To {
use RGraph::*;
match self {
Empty => Empty,
Vertex(v) => Vertex(v),
Overlay(a, b) => Overlay(f(a), f(b)),
Connect(a, b) => Connect(f(a), f(b)),
}
}
}
struct Graph<V> {
inner: RecursiveGraph<V>
}
```

## Constructors

With that, we can now use catamorphisms and anamorphisms to destruct and construct this datatype for our purposes, starting with a method to construct a graph from a list of vertices:

```
impl<V: Hash + Eq + Clone + Debug> Graph<V> {
/// Constructs a [`Graph`] from a vector of vertices
pub fn vertices(vs: Vec<V>) -> Self {
Graph {
inner: RecursiveGraph::expand_layers(vs, |mut remaining| {
use RGraph::*;
match remaining.len() {
0 => Empty,
1 => Vertex(remaining.pop().unwrap()),
_ => {
let ending_half =
remaining.split_off(remaining.len() / 2);
Overlay(remaining, ending_half)
}
}
}),
}
}
...
}
```

This function isn’t terribly interesting on its own, it doesn’t add any edges to the graph and is not suited for adding vertices to an already-existing graph, but it is one of the primitive builders provided by `alga`

. We can see that this anamorphism splits the list of vertices in half and overlays them.

We can do something very similar in order to construct a clique (which `alga`

also defines), simply by using `Connect`

instead of `Overlay`

:

```
/// Constructs fully connected graph
pub fn clique(vs: Vec<V>) -> Graph<V> {
Graph {
inner: RecursiveGraph::expand_layers(vs, |mut remaining| {
use RGraph::*;
match remaining.len() {
0 => Empty,
1 => Vertex(remaining.pop().unwrap()),
_ => {
let ending_half =
remaining.split_off(remaining.len() / 2);
Connect(remaining, ending_half)
}
}
}),
}
}
```

## Destructors

To ensure that `vertices`

does the thing it’s supposed to, we can add a method to count the number of vertices in the graph, also known as the graph’s order:

```
/// Gets the number of vertices in the graph
pub fn order(self) -> usize {
use RGraph::*;
self.inner.collapse_layers(|layer: RGraph<V, HashSet<V>>| match layer {
Empty => HashSet::new(),
Vertex(v) => HashSet::from_iter([v]),
Overlay(a, b) => set_union(a, b),
Connect(a, b) => set_union(a, b)
}).len()
}
```

Here we fold the graph layer by layer, unioning the sets of vertices together and getting the cardinality of the set at the end.

As you may have guessed, there isn’t really anything in the representation above preventing one from adding vertices and edges when they are already present. In fact, `alga`

has a function to `simplify`

a representation by pruning redundancies. I’m unsure how often this is needed in practice, but efficiency is not the focus of this blog post in any case.

Speaking of efficiency… `alga`

conducts some of its queries on temporary structures that are more performant, such as adjacency maps. Replicated below:

```
type AdjacencyMap<V> = HashMap<V, HashSet<V>>;
impl<V: Hash + Eq + Clone + Debug> Graph<V> {
...
/// Folds a [`Graph`] to construct an adjacency map
pub fn to_adjacency_map(self) -> AdjacencyMap<V> {
use RGraph::*;
self.inner
.collapse_layers(|layer: RGraph<V, AdjacencyMap<V>>| match layer {
Empty => HashMap::new(),
Vertex(v) => {
let mut map = HashMap::new();
map.insert(v, HashSet::new());
map
}
Overlay(a, b) => union_with(&a, &b, set_union),
Connect(a, b) => unions_with(
vec![
&a,
&b,
&from_iter_with(HashSet::<V>::from_iter(a.keys().cloned()),
|_| {
// every `a` node gets `bs` as neighbors
HashSet::from_iter(b.keys().cloned())
}),
],
set_union,
),
})
}
...
}
```

In the case of an `Overlay`

we combine adjacency lists by unioning the neighbors of identical nodes. In the case of a `Connect`

, the same combination is also unioned with a neighbor set representing a fully connected subgraph of all nodes in `a`

and `b`

.

With this representation available, we can easily query the number of edges in the graph:

```
/// Calculates the number of edges in the graph
pub fn size(self) -> usize {
self.to_adjacency_map().values().map(HashSet::len).sum()
}
```

## Testing the implementation

Finally, to test what we’ve got:

```
#[cfg(test)]
mod tests {
use crate::*;
#[test]
fn test_graph() {
let vs = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
// fully connected graphs have (n)(n-1)/2 edges
assert_eq!(Graph::clique(vs.clone()).size(), (9 * 8 / 2));
assert_eq!(Graph::vertices(vs.clone()).size(), 0);
assert_eq!(Graph::vertices(vs.clone()).order(), 9);
}
}
```

That’s a decent start. Credit to Inanna Malick for making the `recursion`

crate: it was fun to play with!

## Update: working with references (courtesy of Inanna Malick)

It would be nice if we could run multiple passes over the graph, and not have to consume it just to do something like count its nodes. To enable this, a few tweaks have to be made. First, we introduce a recursive definition of `RGraph`

over borrowed data:

This definition allows us to create an implementation of `MapLayer`

that takes a recursive type that owns data (`RGraph`

), and map it to one that refers to that data (`RGraphRef`

):

```
impl<'a, A: Copy + 'a, B: 'a, V: 'a> MapLayer<B> for &'a RGraph<V, A> {
type To = RGraphRef<'a, V, B>;
type Unwrapped = A;
fn map_layer<F: FnMut(Self::Unwrapped) -> B>(self, mut f: F) -> Self::To {
match self {
RGraph::Empty => RGraphRef::Empty,
RGraph::Vertex(v) => RGraphRef::Vertex(v),
RGraph::Overlay(a, b) => RGraphRef::Overlay(f(*a), f(*b)),
RGraph::Connect(a, b) => RGraphRef::Connect(f(*a), f(*b)),
}
}
}
```

Now, when applying our algebra to tear down this recursive structure, it can be in terms of the referenced data. For example, let’s see how our definition of `order`

would change:

```
- pub fn order(self) -> usize {
+ pub fn order(&self) -> usize {
let unique =
- self.inner.collapse_layers(|layer: RGraph<V, HashSet<V>>| {
+ self.inner.as_ref().collapse_layers(|layer: RGraphRef<V, HashSet<&V>>| {
- use RGraph::*;
+ use RGraphRef::*;
match layer {
Empty => HashSet::new(),
Vertex(v) => HashSet::from_iter(vec![v]),
Overlay(a, b) => set_union(a, b),
Connect(a, b) => set_union(a, b),
}
});
unique.len()
}
```

And there you have it!

## Appendix

Below are the definitions of referenced helper functions:

```
fn set_union<V: Eq + Hash + Clone>(u: HashSet<V>, v: HashSet<V>) -> HashSet<V> {
u.union(&v).cloned().collect()
}
/// Constructs a HashMap, determines a key's values by applying
/// a given function to each respective key
fn from_iter_with<K: Eq + Hash, V, F>(
it: impl IntoIterator<Item = K>,
f: F,
) -> HashMap<K, V>
where
F: Fn(&K) -> V,
{
it.into_iter().fold(HashMap::new(), |mut acc, k| {
let v = f(&k);
acc.insert(k, v);
acc
})
}
/// Unions two HashMaps by applying a given function to
/// the values of common keys
fn union_with<'a, K: 'a + Eq + Hash + Clone, V: 'a + Clone, F>(
a: &'a HashMap<K, V>,
b: &'a HashMap<K, V>,
f: F,
) -> HashMap<K, V>
where
F: Fn(V, V) -> V,
{
unions_with([a, b], f)
}
/// Unions multiple HashMaps by applying a given function to
/// the values of common keys
fn unions_with<'a, K: 'a + Eq + Hash + Clone, V: 'a + Clone, F>(
maps: impl IntoIterator<Item = &'a HashMap<K, V>>,
f: F,
) -> HashMap<K, V>
where
F: Fn(V, V) -> V,
{
maps.into_iter().fold(HashMap::new(), |mut acc, map| {
for (k, v) in map.iter() {
if let Some(u) = acc.remove(&k) {
acc.insert(k.clone(), f(u, v.clone()));
} else {
acc.insert(k.clone(), v.clone());
}
}
acc
})
}
```