To Be Determined - 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₁ ∪ V₂, E₁ ∪ E₂)
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₁ ∪ V₂, E₁ ∪ E₂ ∪ V₁ × V₂)

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:

pub enum RGraphRef<'a, Val, A> {
    Empty,
    Vertex(&'a Val),
    Overlay(A, A),
    Connect(A, A),
}

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

Generic Recursion Applied to Algebraic Graphs