Original Validator
The design of the core validator as written per the original implementation (still holds true). Copied and truncated from https://github.com/ez314/Degree-Validator .
Requirement design and limitations
Representing requirements
Based on Orion, each requirement has an hour requirement and a total # of courses requirement. However, as far as I can tell the "number of courses" requirement is useless. So, each requirement can be thought of as a set of rules that determine what courses can satisfy that requirement, and the total number of hours that must be used to do so.
...
Stacking these together makes it pretty robust in determining whether a course is capable of filling a requirement.
Representing electives as requirements
Any requirement can be represented by a comprehensive name list, but this is not very scalable. Instead, electives are represented with the "Not" matcher. For example, CS guided electives are "Not" CS preparatory courses "Or" CS core courses, while also being ("And") "Level" 3 or 4 CS "Department" classes.
...
One potential optimization is to cache the results of each matcher with each course, so that the same sub-tree does not need to be traversed multiple times across different checks. This optimization is left un-implemented because the matching algorithm is already quite fast.
Requirement groups
We also know that some courses cannot be repeated between requirement groups. For example, a 010 cannot be double-dipped as a 090 core, while MATH 2417 can be double-dipped in both the core curriculum and CS curriculum. To handle this, break requirements up into "requirement groups", where courses cannot be used to fill more than one requirement per requirement group. I'm pretty sure this is how Orion does it, because it separates out all the double-dip courses into their own separate requirements from the "CS Preparatory" requirement.
...
The set of core curriculum classes, major-required courses (which are not allowed to overlap with core curriculum), guided electives, and free electives. Note that we must extract stuff like MATH 2413/MATH 2417 and ECS 3390 to a separate requirement outside of the major requirements, because these are also used to satisfy the core curriculum.
The Upper Level Hour Requirement states you must take, in total, 51 upper-level courses. This by itself is a requirement group, because classes used by this requirement can also be used by any other requirement.
Manual assignments (Bypasses)
Sometimes, we may want to manually assign a course to a requirement. For example, to specify what would be an arbitrary choice to the algorithm, or to allow something that doesn't normally happen. One common example of this is replacing CS 1136 with hours from a different CS course.
...
It is probably good design to add a lot of warnings when users want to bypass. For example, we might want to warn users if they are manually assigning a course that doesn't satisfy the requirement's Matcher. Or, if they try to assign more hours than are available in a course. Or if they try to assign more hours than are needed by a requirement.
For now, no warnings have been implemented. If users try to over-assign, the algorithm allows them to do so and should not crash.
Max flow design and limitations
We want to allocate courses toward requirement groups in such a way that minimizes the number of unused courses. This optimization problem can be done with max flow.
here is a pretty good writeup of how to re-think course allocation as maximum flow in a bipartite graph: https://www.zirayhao.com/posts/course-match
Course Splitting
However, Dartmouth works on a trimester system and all of their courses are 1 hour. So, they don't need to worry about splitting course hours between requirements.
...
Unfortunately, solving the Minimum-Edge Cost Flow (MECF) problem is NP-hard, even for bipartite matching with 0/1 costs. More work needs to be done to optimize this second problem in an efficient manner.
Fractional hours
THe modified push-relabel algorithm supported by Google OR tools only does integer increments of flow, so if you have a fractional bypass, it may not come up with a full solution (unless the solution can be achieved with only integer flows).
...