Find the best possible college schedule by generating them all
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
docs/html
src
test
.gitignore
.gitlab-ci.yml
LICENSE
README.md
document.bat
package-lock.json
package.json
phpdox.xml
phpunit.xml
sonar-project.properties
webpack.config.js

README.md

University of Richmond - Schedule Generator

build status coverage report

What It Is

Our app accepts as many courses as a student may want to take along with all the offered sections of each course. Then, with our algorithm, generates all possible non-conflicting schedules.

Where It Is

Right now the PHP version is available at http://mikedombrowski.com/ur/.

Run Your Own

Although there are many customizations that are probably specific to only the University of Richmond, if you wanted to run your own here's how.

  1. Clone this repository
  2. Install dependencies using composer. php composer.phar install or composer install
  3. Edit config.php with the correct installation directory and database login details
  4. Run importer/importExcel.php from a web browser to create the database and import all the data
  5. You now have the same installation that I do. If you are running on data that is not from UR, then you may have to change some things.

PHP API Documentation

Available at https://MikeDombo.github.io/university-schedule-generator/html/index.html

Theory of Operation

The new algorithm implemented by commit 9102865 is the Bron-Kerbosch maximal clique finding algorithm. I realized that the scheduling program could be thought of as a graph where vertices represent a section of a class and edges exist between vertices that are compatible (can be taken together).

Representing the problem as a graph means that possible non-conflicting schedules are maximal cliques. Therefore, to find all possible schedules, I implemented the Bron-Kerbosch maximal clique finding algorithm. This does run faster than my old algorithm and generates fewer total schedules because the old algorithm generated some schedules that were included in larger ones (sub-graphs).

Old Theory of Operation

Prior to commit 9102865 this is the algorithm that was used. Our algorithm is essentially a recursive tree, which is explained more in the image below. Theory of Operation