University of Washington Department Connectivity

This is a force-directed graph of the departments of the UW, constructed such that the attraction ¹ between two departments (D₁ and D₂) is proportional to the sum of the number of prerequisite courses in D₂ required for every course in D₁ and vice verse (ie. prerequisites in D₁ for a course in D₂). The area of each department is proportional to the number of courses offered, and departments are colored by the type of credits they most commonly offer ². Click and drag departments in order to interact with the graph.

Note the general arrangement of the graph: the mathematics department, a large golden circle, is at the center of the densest area of the graph, surrounded by various engineering and hard science departments, which are themselves bordered by the softer sciences and humanities. Finally, the edges of the graph are occupied by a nebula of unconnected departments that eschew interdepartmental prerequisites. This is, in general, what one expects a university to look like.

The data-set used to construct this graph is the result of an attempt to build a better course catalog/academic planning system for the UW: I figured that the most elegant way to select my freshman-year courses would involve applying some graph algorithm to the digraph formed by the university’s courses and their prerequisites. Solving for possible academic plans is actually a pretty interesting problem involving starting from a given set of reachable nodes (courses with satisfied prerequisites) and finding a subgraph of the entire course-graph that satisfies a set of constraints (major requirements, desired courses, credits per semester), and minimizes a cost-function (time to graduate, number of courses to take). I was quickly distracted by some other interesting problem, but not before I’d downloaded the UW course catalog, parsed all of the entries (include horrid stuff like either 2.0 in MATH 136, 2.0 in MATH 308, or 2.0 in MATH 318; 2.0 in MATH 324 - mostly successfully), and thrown all of the data into Riak ³. The end result of all of that work is that I have a nice kev/value store containing about 11,000 json blobs of approximately the following format:

    {
     "area": [
       "NW"
      ],
     "name": "CSE 143",
     "description": "Continuation of CSE142",
     "title": "Computer Programming II",
     "credits": {
        "max": 5,
        "min_per": 5,
        "max_per": 5
     },
     "dependencies": {
        "raw": "Prerequisite: CSE142.",
        "all_courses": ["CSE142"],
     },
     "offered": "AWSpS"
    }

As Riak is very much not a traditional SQL database, calculating the connectivity metric between departments takes a little more thought than typing up the necessary SQL queries. In particular, all queries other than key retrieval (including ranges of keys, with secondary indexes) or full text search must be implemented as a map-reduce job distributed over multiple database nodes. Riak further complicates this by offering an odd choice of languages in which to write said map-reduce job: either JavaScript (poorly designed, weakly typed, imperative) or Erlang (better than JavaScript but flawed in its own ways ⁴, obscure, strongly typed, functional). Fortunately, the necessary code for such a simple metric isn’t horridly complicated:

map_phase(Obj,_,_) ->
    %% Deserialize the JSON-encoded course description to the native erlang term:
    Blob = jiffy:decode( riak_object:get_value(Obj)),
    %% Extract the current department - the model module is just a bunch of accessors
    %% that simplify traversing the term.
    Department = strip_name( model:name(Blob)),
    %% Generate a dict counting all external dependencies:
    Dependencies = sets:fold(
		     fun (Course,Dict) ->
			     DependsUpon = strip_name(Course),
			     if
				 DependsUpon /= Department ->
				     dict:update_counter(DependsUpon,1,Dict);
				 true ->
				     Dict
			     end
		     end, dict:new(), model:all_courses( model:dependencies(Blob))
		    ),
    %% We also want to extract the area in which this department most often gives credit
    Areas = dict:from_list([{Area,1} || Area <- model:area(Blob)]),
    %% As this is only the map pass, we need to return a structure that lets us merge
    %% the information from multiple courses in a simple department:
    [dict:from_list([{Department,{Dependencies,Areas,1}}])].
%% The reduce phase is very simple - effectively the (Haskell) mconcat function
%% for something that's obviously a monoid.
merge_sum(Left,Right)-> dict:merge(fun (_,X,Y) -> X + Y end, Left,Right).

reduce_phase([],_)-> [];
reduce_phase([X|Rest],Const) -> reduce_phase(X,Rest,Const).
reduce_phase(X,[],_Const) -> [X];
reduce_phase(X,[Y|Rest],Const) ->
    reduce_phase(dict:merge(fun (_Department, {LDeps,LAreas,LSize},{RDeps,RAreas,RSize}) ->
				    {merge_sum(LDeps, RDeps),
				     merge_sum(LAreas, RAreas),
				     LSize + RSize
				    }
			    end, X, Y)
		 , Rest, Const).