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's newest features are 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?

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

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, 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

The latest version of HDX 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, graph traversals, finding connected components, finding convex hulls, and Dijkstra's algorithm for single-source shortest paths.