Map-based Educational Tools for Algorithm Learning (METAL)

led by Dr. James D. Teresco

METAL's Data

At the heart of everything METAL does is its set of graphs of highway data. These graphs represent the highways in various regions, countries, and highway systems, and are provided in several formats. The typical METAL user need not be concerned with how this data is generated, but for those interested, the source of the data and a bit about how it is generated are described here.

The Travel Mapping Project

The Travel Mapping Project (and its defunct 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 government agencies, map data from the OpenStreetMap project, and government satellite images. Some volunteers even gather route coordinates manually with their own GPS devices.

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.