Map-based Educational Tools for Algorithm Learning (METAL)

led by Dr. James D. Teresco

Graph File Formats

A graph file format called "Travel Mapping Graph", using a .tmg extension has been defined for the graphs generated by the Travel Mapping Project. Files are plain ASCII text and simply describe a list of vertices (waypoints from TM data) and edges (connections from TM data) in a format intended to be easy to read by programs in any language that wish to make use of the data.
The Travel Mapping Graph file format can represent graph data in either a "simple" or "collapsed" form. The reasons for the two formats are described below.
The data is in ".tmg" files which have the following format: Note that a "simple" format graph is simply a "collapsed" format graph with no edge shaping points.

"Hidden" Waypoints

Travel Mapping highway data uses a series of waypoints to define each highway. Waypoints are added to a route for its endpoints and at major intersections or, for freeways, interchanges. The route is then approximated by straight line segments connecting pairs of consecutive waypoints. On many routes, this is sufficient to form a good approximation of the route. However, on more rural and especially curvy roads, additional resolution is needed to obtain a reasonable approximation. In those cases, waypoints are added at selected minor intersections. In cases where no appropriate minor intersections are located on a stretch of highway, a "hidden waypoint" will be added. In the TM data, these are denoted by starting their label with a "+". These are not points where a traveler is likely to begin or end his or her travel on the route, so they are not displayed to users of the TM project itself.

Simple vs. Collapsed Graphs

It is in the handling of these hidden waypoints where the two graph file formats differ. The "simple" format treats the hidden waypoints no differently than any other. They become graph vertices, and each graph edge is a simple, straight line connection between two vertices that represent waypoints that are adjacent to each other in the underlying TM data. In the "collapsed" format, each hidden waypoint and its incident edges are "collapsed" into their neighboring edges. The coordinate pair of the hidden waypoint is then listed as a shaping point along the new, collapsed edge.
Most users of TM graph data are likely to want to use the collapsed format graphs. Since graph vertices that represent hidden waypoints necessarily cannot be at intersections (if they were, the waypoints would not be marked as hidden), each such vertex would have a degree of 2, and would not add significantly to the structure of the graph. One reason a user of these graphs might choose simple format would be if they did not wish to keep track of shaping points with their graph edges.

Waypoint Names

Waypoint/vertex names in the graph data are derived automatically from the names of intersections and other points in the TM highway data. For example, the TM data for New York State Route 30 has a waypoint named "GolfCouRd" for its intersection with Golf Course Road in the Town of Amsterdam. When that waypoint is named in the highway data graph, it is given the name "NY30@GolfCouRd". The majority of waypoints are named with this convention. This process is complicated by waypoints along highways that run concurrent with each other (i.e., a road with more than one designation) or at the intersection of two or more highways. In these cases, a label that includes information about all concurrent or intersecting routes is generated. In some cases, long and complicated names result. For example, the TM data for New York State Route 30 has a waypoint named "NY29" and New York State Route 29 has a corresponding waypoint named "NY30" that graph generation detects as a single waypoint/graph vertex. The "failsafe" point name is "NY29@NY30&NY30@NY29". A series of simplification steps are applied to these default names, and this particular point ends up renamed as "NY29/NY30". In most cases, the automatic name simplification leads to reasonable names for the waypoints,but some remain overly complex. Improving the automatic naming of the points in the graph data is an ongoing effort. Fortunately, other than having to read and occasionally type a long waypoint name, these more complicated names do not affect the actual graph structure.