Map-based Educational Tools for Algorithm Learning (METAL)

led by Dr. James D. Teresco

Motivation

Nearly any topic in a data structures or algorithms course will be
more interesting for students if they can apply what they are learning
to real-world data and visualize results in a meaningful way. When
using graph data, it needs to be small enough to be manageable, but
large enough to be interesting. This might consist of a small road
system, airline flight schedules, or even the layout of a campus or
building. Map-based Educational Tools for
Algorithm Learning (METAL) is a system that
allows students to experiment with graph algorithms using
the Google Maps API
and highway routing data from
the Travel Mapping (TM) Project.
Students can implement graph algorithms and display, in Google Maps,
the results of computations using those algorithms. METAL also
provides interactive algorithm visualization capabilities intended to
aid student understanding of graph and other algorithms.

Wouldn't it be more fun and interesting
to work with this graph
than this one?

The Travel Mapping Project

The Travel Mapping Project (and
its predecessor, CHM) has
gathered information about the routes of highways across much of the
world. The project allows travelers to track the segments of roads
they have traveled (or, in the project's terminology, "clinched"), to
see representations of their travels in map form, and to compare the
extent of their travels with those of other project users. The data
that describes the highways needs to be at a fine enough granularity
to allow users to specify their travels with a reasonable level of
accuracy, but coarse enough to be able to present (in both list and
map form) the endpoints of road segments available to be marked as
clinched. Each route is added to the project ("plotted") by listing
the latitude/longitude coordinates of the route's endpoints and at
major intersections along the route (the "waypoints" of the route).
Project volunteers plot the highways at an appropriate level of
granularity using public domain data sources such as route logs from
state departments of transportation, map data from
the OpenStreetMap project,
and government satellite images.

Generating Graphs from TM Data

The TM data is used to generate a graph that represents a group of
highways. A preprocessing program reads the set of waypoints for each
route and matches up shared intersections based on coordinates. The
waypoints (of all routes in a system) are the graph vertices and the
road segments connecting adjacent waypoints are the graph edges. Each
vertex is labeled with a string based on its route name(s) and
waypoint name and stores its coordinates; edges are labeled with the
name of the route that connects its endpoints. Distances (edge
lengths or weights) are computed easily from the coordinates. The
accuracy of the routings of highways is not perfect -- curved road
segments are approximated by a series of straight segments -- but it
is this "imperfection" in the data that makes it perfect for use in
this project. The data is accurate enough to be plottable on a map,
but small enough to be manageable for use in many graph algorithms
studied in a data structures or algorithms course.

Graph Data

TM's data is updated daily, and
an updated collection of
graphs is generated almost as frequently from this data. These graphs
represent the highways in various regions, countries, and highway
systems, and are provided in
two formats. The highway systems
available in TM vary in size, meaning graph data can be generated at a
variety of scales. They vary in size from just a handful of vertices
and edges for systems in small island nations to hundreds of thousands
for the entire data set.

The Highway Data Examiner

Google has made an application programmer interface (API) available to
allow customized plots of data in Google Maps. It is implemented as a
set of Javascript classes and methods, and is fairly easy to learn and
use. It requires free registration to obtain an API key. However,
students, or instructors for that matter, need not learn the Google
Maps API or obtain their own key to make use of this system. The
Highway Data Examiner (HDX) is built using the Google Maps API, and
that allows plotting of the TM and derived data.

Usage in Class Assignments

These graph data files can be used as input for class examples or
assignments in a data structures, algorithms, or other courses. This
data was first used in a laboratory assignment for a data structures
course at Mount Holyoke College where students were required to build
a graph structure representing a highway system then perform
Dijkstra's algorithm to compute the shortest route between two
specified waypoints. Student programs generated output files listing
the road segments along the shortest path. These were then uploaded
to a course web server, where an instructor-provided program used the
Google Maps API to visualize their results. Students were able to
develop and debug their programs using small data sets like the Hawaii
Interstates, then use those programs to compute much more complex
routes using the larger data sets. The software has been updated and
extended and used in several courses at Siena College and The College
of Saint Rose. Successful assignments include the creation of custom
classes to store the information about the points and connections
between them, storing these points and connection in a data structure
and then searching within and sorting those points (a great way to
motivate comparators), finding convex hulls, performing graph
traversals, and more advanced graph algorithms including Dijkstra's
algorithm.

Interactive Algorithm Visualization

An enhanced version of HDX has been developed which includes support
for interactive algorithm visualization. After
loading a graph data file into HDX, a user can select the "Algorithm
Visualization" option. From there, an algorithm can be chosen, along with
any needed parameters (e.g., a starting vertex for a traversal). A set
of controls are used to start, pause, reset, or change the speed of
the simulation. During the simulation, the data is displayed in both
tabular and map form. Our expanding set of algorithms supported
include simple vertex- and edge-based searches and graph traversals.