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 Leaflet Maps 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's newest features are interactive code-level 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?

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. Those interested can
read more about where it comes from and how it is
generated. The highway systems available
in Travel Mapping (TM), from which
METAL derives its data, 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

Leaflet is an open-source JavaScript library that provides interactive
maps. It is an attractive alternative to services like Google Maps or
Bing which have significant usage restrictions. The
Highway Data Examiner (HDX) is built using Leaflet,
and that allows plotting of the TM and derived data, and supports
interactive algorithm visualizations.

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

HDX includes support for interactive algorithm visualization. After
loading a graph data file into HDX. 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, and with HDX's new
action-based framework, an algorithm's code can be simulated
line-by-line. Our expanding set of algorithms supported include
simple vertex- and edge-based searches, closest pairs, graph
traversals, finding connected components, finding convex hulls,
Dijkstra's algorithm for single-source shortest paths, and Prim's
algorithm for minimum spanning trees.