ChrisCooper/QcumberD — pull request #90 by Mystor (2013-08-07 15:59:26+00:00)
Title: Prereq graph

Fixes ChrisCooper/QcumberD#89

## Features
### Parses Prerequisite text to determine prerequisites, corequisites, recommended courses, and exclusions
This produces JSON which is entered into the `parsed_reqs` field on the Course object.
The following is BCHM 410's JSON:
``` json
{
"prerequisite": {
"items": [
"BCHM 313",
"BCHM 315",
"BCHM 316",
"BCHM 317",
{
"items": [
"BCHM 218",
"MBIO 218"
],
"type": "or"
}
],
"type": "and"
}
}
```
And BIOL 410
``` json
{
"prerequisite": {
"items": [
"BIOL 302",
"BIOL 303"
],
"type": "or"
},
"recommend": {
"items": [
"BIOL 335"
],
"type": "and"
}
}
```

### Generates dotfile code for a specific course's prerequisites
BCHM 410:
``` javascript
digraph "Prerequisite Chart" {
node [
shape=ellipse,
style=filled,
fontname="'Droid Sans', sans-serif",
fontcolor=white
]
"CHEM 212" [ label="CHEM 212", color="forestgreen", fontcolor="white" ]
"CHEM 211" [ label="CHEM 211", color="forestgreen", fontcolor="white" ]
"MBIO 218" [ label="MBIO 218", color="forestgreen", fontcolor="white" ]
"103cf374be597a18316c995d77dc233cc9f2f8424fef71aaaad300d8" [ label="OR", color="white", fontcolor="black" ]
"7b0299e0d1705984bb66efa68397bba64034b5c6148efbfe89bdb24e" [ label="OR", color="white", fontcolor="black" ]
"CHEM 120" [ label="CHEM 120", color="forestgreen", fontcolor="white" ]
"8c8297db09ba9091969d5eaf4a3a71da74bdaea2acb33545d49ec890" [ label="OR", color="white", fontcolor="black" ]
"0820ab6003b0dae94287c1a2303a5f8e9a73c374df55eb488ecb429e" [ label="OR", color="white", fontcolor="black" ]
"9779b5fa943774d7fdc8df89af690c1b4a20865c449f14333dd55419" [ label="OR", color="white", fontcolor="black" ]
"1e38d9b7235deb45b9b2175131bd4d40a08003c5fd20721b6f58eb77" [ label="OR", color="white", fontcolor="black" ]
"df9383e911ce34dae4d5787a64fdd9bef1e27ada00502b0fdfc1524f" [ label="OR", color="white", fontcolor="black" ]
"BIOL 103" [ label="BIOL 103", color="forestgreen", fontcolor="white" ]
"BIOL 102" [ label="BIOL 102", color="forestgreen", fontcolor="white" ]
"834a67ab3b9f48dd81c37627a63b49c23231b9fca468f1abcc777325" [ label="AND", color="white", fontcolor="black" ]
"316a2523747fb6766af0801a68a4214004fedb70d1970c22dda5b94f" [ label="AND", color="white", fontcolor="black" ]
"BCHM 410" [ label="BCHM 410", color="forestgreen", fontcolor="white" ]
"BCHM 313" [ label="BCHM 313", color="forestgreen", fontcolor="white" ]
"CHEM 223" [ label="CHEM 223", color="forestgreen", fontcolor="white" ]
"BCHM 315" [ label="BCHM 315", color="forestgreen", fontcolor="white" ]
"BCHM 316" [ label="BCHM 316", color="forestgreen", fontcolor="white" ]
"CHEM 222" [ label="CHEM 222", color="forestgreen", fontcolor="white" ]
"CHEM 113" [ label="CHEM 113", color="forestgreen", fontcolor="white" ]
"CHEM 112" [ label="CHEM 112", color="forestgreen", fontcolor="white" ]
"CHEM 114" [ label="CHEM 114", color="forestgreen", fontcolor="white" ]
"CHEM 116" [ label="CHEM 116", color="forestgreen", fontcolor="white" ]
"BCHM 317" [ label="BCHM 317", color="forestgreen", fontcolor="white" ]
"CHEM 281" [ label="CHEM 281", color="forestgreen", fontcolor="white" ]
"CHEM 282" [ label="CHEM 282", color="forestgreen", fontcolor="white" ]
"BIOL 205" [ label="BIOL 205", color="forestgreen", fontcolor="white" ]
"APSC 112" [ label="APSC 112", color="forestgreen", fontcolor="white" ]
"a86dcd4240996171ae503222384d7d57e9f7a3fccf06792be1f20295" [ label="AND", color="white", fontcolor="black" ]
"APSC 131" [ label="APSC 131", color="forestgreen", fontcolor="white" ]
"APSC 132" [ label="APSC 132", color="forestgreen", fontcolor="white" ]
"APSC 171" [ label="APSC 171", color="forestgreen", fontcolor="white" ]
"BCHM 218" [ label="BCHM 218", color="forestgreen", fontcolor="white" ]
"APSC 111" [ label="APSC 111", color="forestgreen", fontcolor="white" ]
"df9383e911ce34dae4d5787a64fdd9bef1e27ada00502b0fdfc1524f" -> "CHEM 212"
"9779b5fa943774d7fdc8df89af690c1b4a20865c449f14333dd55419" -> "CHEM 211"
"BCHM 218" -> "103cf374be597a18316c995d77dc233cc9f2f8424fef71aaaad300d8"
"MBIO 218" -> "103cf374be597a18316c995d77dc233cc9f2f8424fef71aaaad300d8"
"CHEM 112" -> "7b0299e0d1705984bb66efa68397bba64034b5c6148efbfe89bdb24e"
"CHEM 114" -> "7b0299e0d1705984bb66efa68397bba64034b5c6148efbfe89bdb24e"
"a86dcd4240996171ae503222384d7d57e9f7a3fccf06792be1f20295" -> "7b0299e0d1705984bb66efa68397bba64034b5c6148efbfe89bdb24e"
"834a67ab3b9f48dd81c37627a63b49c23231b9fca468f1abcc777325" -> "8c8297db09ba9091969d5eaf4a3a71da74bdaea2acb33545d49ec890"
"CHEM 282" -> "8c8297db09ba9091969d5eaf4a3a71da74bdaea2acb33545d49ec890"
"CHEM 211" -> "0820ab6003b0dae94287c1a2303a5f8e9a73c374df55eb488ecb429e"
"CHEM 212" -> "0820ab6003b0dae94287c1a2303a5f8e9a73c374df55eb488ecb429e"
"CHEM 281" -> "0820ab6003b0dae94287c1a2303a5f8e9a73c374df55eb488ecb429e"
"CHEM 112" -> "9779b5fa943774d7fdc8df89af690c1b4a20865c449f14333dd55419"
"CHEM 116" -> "9779b5fa943774d7fdc8df89af690c1b4a20865c449f14333dd55419"
"a86dcd4240996171ae503222384d7d57e9f7a3fccf06792be1f20295" -> "9779b5fa943774d7fdc8df89af690c1b4a20865c449f14333dd55419"
"APSC 131" -> "1e38d9b7235deb45b9b2175131bd4d40a08003c5fd20721b6f58eb77"
"CHEM 120" -> "1e38d9b7235deb45b9b2175131bd4d40a08003c5fd20721b6f58eb77"
"CHEM 112" -> "df9383e911ce34dae4d5787a64fdd9bef1e27ada00502b0fdfc1524f"
"316a2523747fb6766af0801a68a4214004fedb70d1970c22dda5b94f" -> "df9383e911ce34dae4d5787a64fdd9bef1e27ada00502b0fdfc1524f"
"BIOL 102" -> "BIOL 103"
"CHEM 222" -> "834a67ab3b9f48dd81c37627a63b49c23231b9fca468f1abcc777325"
"CHEM 223" -> "834a67ab3b9f48dd81c37627a63b49c23231b9fca468f1abcc777325"
"CHEM 116" -> "316a2523747fb6766af0801a68a4214004fedb70d1970c22dda5b94f"
"APSC 111" -> "316a2523747fb6766af0801a68a4214004fedb70d1970c22dda5b94f"
"APSC 112" -> "316a2523747fb6766af0801a68a4214004fedb70d1970c22dda5b94f"
"APSC 131" -> "316a2523747fb6766af0801a68a4214004fedb70d1970c22dda5b94f"
"BCHM 313" -> "BCHM 410"
"BCHM 315" -> "BCHM 410"
"BCHM 316" -> "BCHM 410"
"BCHM 317" -> "BCHM 410"
"103cf374be597a18316c995d77dc233cc9f2f8424fef71aaaad300d8" -> "BCHM 410"
"CHEM 211" -> "CHEM 223"
"CHEM 212" -> "CHEM 223"
"103cf374be597a18316c995d77dc233cc9f2f8424fef71aaaad300d8" -> "BCHM 315"
"8c8297db09ba9091969d5eaf4a3a71da74bdaea2acb33545d49ec890" -> "BCHM 315"
"BCHM 315" -> "BCHM 316"
"0820ab6003b0dae94287c1a2303a5f8e9a73c374df55eb488ecb429e" -> "CHEM 222"
"CHEM 113" -> "CHEM 114"
"BCHM 315" -> "BCHM 317" [ style="dashed" ]
"BCHM 316" -> "BCHM 317" [ style="dashed" ]
"7b0299e0d1705984bb66efa68397bba64034b5c6148efbfe89bdb24e" -> "CHEM 281"
"CHEM 112" -> "CHEM 282"
"CHEM 281" -> "CHEM 282"
"BIOL 102" -> "BIOL 205"
"BIOL 103" -> "BIOL 205"
"APSC 111" -> "APSC 112"
"APSC 171" -> "APSC 112"
"APSC 131" -> "a86dcd4240996171ae503222384d7d57e9f7a3fccf06792be1f20295"
"APSC 132" -> "a86dcd4240996171ae503222384d7d57e9f7a3fccf06792be1f20295"
"1e38d9b7235deb45b9b2175131bd4d40a08003c5fd20721b6f58eb77" -> "APSC 132"
"BIOL 205" -> "BCHM 218"
}
```

This is then rendered, either using Viz.js on the client (this branch) or using GraphViz through pydot on the server [this branch](https://github.com/Mystor/QcumberD/tree/prereq-graph-native). This gets you a result like the following:

![image](https://f.cloud.github.com/assets/1261662/925538/17f65354-ff7a-11e2-9aae-191be6f61fb3.png)

### Small link to visualize the prerequisite graph on the course's detail page
![image](https://f.cloud.github.com/assets/1261662/922248/0d85fe70-ff1f-11e2-859f-f7ec5e50b385.png)

## Decisions to be made before merging
* Should Viz.js be used on the client or GraphViz on the server?
* What should the page look like with the graph on it?
* Where should the link to visualize the prerequisites for the class go?
* How should parser inaccuracies be handled

## Testing status
I have run the parser on all subjects through HIST, however, I haven't had the chance to scrape the remainder of the subjects yet. It doesn't hang on any of these.
As Django requests run on a non-main thread, I cannot use the timeout code which I found to prevent the code from hanging. I don't think that the code should ever hang, however it did frequently in development.
Parsing shouldn't take more than about a minute or two, it is pretty fast.
There are a few inaccuracies in the parsed json. Usually this is due to ambiguously worded prerequisite text or course numbers stated without the subject. (example `ABC xxx and ABC yyy or ABC zzz` or `ABC xxx; yyy; zzz`). Not sure how to fix either of these problems.