CityGraph - erchiggins/graphattan GitHub Wiki

Basic CityGraph Model

Vertex

The Vertex is the basic building block of the CityGraph, representing a location at which a pedestrian's path can branch. Multiple Vertices may be present at the intersection of n streets/paths/other non-pedestrian routes, so several Vertices in the CityGraph will have the same Intersection. The position of a Vertex represents the pedestrian's location, not the geographic center of the Intersection of which the Vertex is a corner.

Intersection

The Intersection describes an area in which zero or many streets, paths, or other non-pedestrian routes cross. For the present iteration of this model, these 'routes' are represented as Strings and Intersections do not play a significant role in the traversal, but are instead merely labels for groups of functionally connected Vertices. Many Vertices may be associated with the same Intersection.

Edge

An Edge connects two Vertices, its "source" and "destination." As the CityGraph is undirected, every Edge has a counterpart with its "source" and "destination" flipped so that the traversal may occur in either direction. The weight of the Edge denotes its length in feet, which is not necessarily the same as the difference in (x,y) positions of the source and destination Vertices. The Edge may either be a CROSSING or a SIDEWALK, which has consequences for its availability as a path during a traversal of the map.

CityGraph

CityGraph is an undirected weighted graph representing the pedestrian walkways available in section of a city, implemented with adjacency lists. The position of a Vertex must be unique within the CityGraph, enforcing a strictly two-dimensional (though not necessarily simply connected) graph. Vertex objects form the entry set of the CityGraph map, so duplicate Vertices cannot be added. A list of Edges accompanies each Vertex. Duplicate Edges are allowed (parallel paths).

UML Diagram of walk.graphattan.graph Package