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
.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:
- The first line specifies the file format. It consists of three
space-separated entries, the first of which must be
TMG". The second is a version number, which much be
1.0". The third entry is either "
collapsed" indicating whether the edge data is in
simple format or collapsed edge format.
- The second line consists of two numbers: the number of vertices
(waypoints) |V|, and the number of edges, |E|, (road
segments that connect adjacent waypoints).
- The next |V| lines describe the waypoints. Each line
consists of a string describing a
waypoint, followed by its latitude and longitude as floating-point
- The last |E| lines describe the road segments. Each
line consists of two numbers specifying the waypoint numbers
(0-based and in the order read in from this file) connected by this
road segment, followed by a string with the name of the road or
roads that form this segment. For "collapsed" format graphs, a line
describing an edge can optionally have a list of the space-separated
latitudes and longitudes of shaping points that define a more
accurate path (for both mapping and for computing distances) of the
Note that a "simple" format graph is simply a "collapsed" format graph
with no edge shaping points.
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
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
" 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
". 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 "
" and New York
State Route 29 has a corresponding waypoint named "
that graph generation detects as a single waypoint/graph vertex. The
"failsafe" point name is "
series of simplification steps are applied to these default names, and
this particular point ends up renamed as "
most cases, the
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.