MatroidJS, a new way to model dependencies in TypeScript

Matroid in a nutshell

A matroid is nothing more than a pair of two sets: E (ground set) and I (independent sets), where elements of I are a subset of E, selected by the dependency rules of the matroid. Hence matroid is also a structure that abstracts and generalises the notion of linear independence of vector spaces. In fact, a finite subsets (E /ground) of a vector space can be viewed as matroids with the independent subset (I) being constructed according to the rules of linear independence. As such, an example of a matroid in the usual 2D vector space would look like E=(0,0), (0,1), (1,0), (-1,-1), (2,2); I=(0,1), (1,0).

On top of vector spaces, matrices and graphs can also be viewed as matroids. MatroidJS encapsulates and utilises the information about the dependencies in the stored data, making results of complex algorithms readily available by design. Let me show how, on an example.

Photo by fabio on Unsplash

Class schedule for students and lecturers

Creating a timetable for the semester is always a challenge. We can have obligatory courses, elective/alternative courses, totally optional but interesting courses, and all these can have multiple options for class occurrences, with different lecturers etc. So we might end up with a couple dozen classes (with the same class held by a different lecturer being considered as a different class) we consider attending in the semester, but naturally we can’t have it all. First of all let’s consider two classes conflicting if they are in the same timeslot, or if they are in consecutive timeslots but in different buildings. But what should we aim for? Should we look for the maximum number of classes we can attend without any conflicts? Should we pick a handful of classes we are sure we want to attend and find out what classes are conflicting with them first? Sounds like a challenge indeed, but luckily a matroid can answer both by design, a `maximum number of classes without conflict` will be called the base of the matroid, while closures tell all the variations of classes we cannot attend given a set of chosen classes.

The model and its matroid

Let’s create a matroid that helps with these issues. First off, we need a basic model of classes.

Now that we have our Class class, we should create matroids for students and lecturers:

Matroid<Class> tells the Matroid class, that ground (E) and independent set (I) will contain Class elements (or Class subsets). The other trick of Matroid is

public abstract hasCircuit(subsetToCheck: T[][] | T[]): boolean;

by which the descendants define the dependency rules (such as linear independence in case of vectors) specific to them. It is called hasCircuit since a minimal dependent subset (a set having at least 2 elements depending on each other) is called a circuit. hasCircuit method check the commented criteria to decide if the provided set (or set of subsets) contains any dependencies or not. Here’s how:

But how does this simple matroid solve that problem?

Basic matroid functions

Bases

By browsing I (independent property of the matroid) we can check independent subsets, or in this case classes that can be attended without a conflict. That’s very useful in itself, but there might be many of these. If we want to get only the independent subsets with the most elements in them, that’s called a base. There can be multiple bases of course, but all have the same number of elements in them. So for classes, let’s say we have an array of classes, called CLASSES, we are interested in. We need a matroid:

matroid = new StudentTimetableMatroid(CLASSES);

then to get the bases, just call the util function findAllBases, that finds all the bases on any matroid regardless of their generic type:

findAllBases(matroid);

The returned set will contain all possible subsets of CLASSES that do not conflict, so the student can decide which suits them best. They could for instance sort the bases by the sum of credit in them, thus getting the most possible credit for the semester, all that with a single call on the matroid.

Closures

A closure of a subset A (on E ground) contains all elements of E with which the rank of the closure won’t exceed the rank of A.

Translated to our example, provided we have the same matroid as before, created with CLASSES, and we are sure we want to attend 2 classes, called subset, we have multiple options. We could filter I for sets containing these two, for classes we can put in our schedule without a conflict, but getting the classes we can’t attend if these two are scheduled could also be interesting. That latter is called a closure.

const closure = matroid.getClosure([subset])
    .filter((closureSubset: Class[]) => closureSubset.includes(CLASS2) && closureSubset.includes(CLASS3))
    .map(closureSubset => closureSubset.filter((claz: Class) => claz !== CLASS2 && claz !== CLASS3))
    .sort((clSubsA: Class[], clSubsB: Class[]) => clSubsB.length - clSubsA.length);

The raw closure can contain some noise, since it has all the subsets of the ground set with rank less than, or equal to 2 in it. That being the case, we first filter for sets containing our 2 classes of the subset, all the rest is formatting for readability of the results. Since we are looking for the classes we cannot attend with the mandatory classes being in our timetable, we map out those 2 from the results, then sort them, for first sets to contain the most elements. Just like that, with a simple getClosure() call we can query the classes conflicting with our mandatory courses by design.

Links

If you are interested in the source, don’t hesitate to check out MatroidJS on github: https://github.com/amdor/matroidJS

Also, if you like the idea of having the dependency rules stored in the same structure as the data, get the package from https://www.npmjs.com/package/matroidjs

or by

npm i matroidjs