- Forward


Representing Road Networks
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • A great deal is known about the theory of graphs
  • It seems quite natural to represent transportation road networks using graphs
  • But, some important issues arise
A Simple Road Network
Back SMYC Forward
  • Properties:
    • One intersection
    • Four dead ends
    • Four street segments
  • Illustration:
    • network1-streets
One Representation
Back SMYC Forward
  • Vertexes/Nodes:
    • The intersection
    • The dead ends
  • Edges/Arcs/Links:
    • The street segments
  • Visualization:
    • network1-primal
Limitations of this Representation
Back SMYC Forward
  • Turn restrictions
  • Turn delays
Another Representation
Back SMYC Forward
  • Vertexes/Nodes:
    • The street segments
  • Edges/Arcs/Links:
    • The turning movements
  • Visualization:
    • network1-dual
Including Directionality
Back SMYC Forward

The First Representation with Two-Way Streets

network1-diprimal
Including Directionality (cont.)
Back SMYC Forward

The Second Representation with Two-Way Streets

network1-didual
U-Turns
Back SMYC Forward

One Approach

network1-uturnnodes
U-Turns (cont.)
Back SMYC Forward

Another Approach

network1-uturnarcs
Origins and Destinations
Back SMYC Forward
  • An Observation:
    • Trips often start from and end at the middle of street segements
  • One Approach:
    • Dummy origin and destination nodes
    • dummyod
There's Always More to Learn
Back -