Metro Maps 2.0

Aline Schaufelberger - 12142881

The Paper: Metro Maps on Octilinear Grid Graphs

Find Solution for Metro Map Generation, octilinear
Integer Linear Program (Optimal Solution)
Approximation Algorithm (faster) - our Implementation

The Approximation Algorithm

Order the input graph edges

Calculate shortest path from possible start nodes to possible end nodes on grid graph

If no Drawing found: Randomize Edge Ordering

Optimize Drawing via Local Search

This is a project extension from the 2022 Project: MetroMaps. The extension consists of adding the river data in the similar octilinear gri style.

The Approximation Algorithm - Edge Routing and Station Placement

establish edge ordering: edges in denser areas of the network are processed earlier
create empty octilinear grid graph O and corresponding auxiliary graph A

use edge ordering to iterate over edges; for each edge:

find candidate nodes for start and endpoint (two disjoint sets S, T)

make temporary changes to A edge costs

find cheapest path S → T using A*

undo temporary changes to A edge costs

make permanent changes to A edge costs

The Approximation Algorithm - Input Edge Ordering

Mark Node with highest LDEG as dangling
While there are dangling nodes: Add all adjacent edges leading to an unprocessed node to the edge ordering
Mark each just added node as dangling, the just processed node as processed

Our Implementation - Technology

Back-End: Python

NetworkX Graph Library
Flask Web Server

Front-End: HTML/JS/CSS

Leaflet Maps Library

Data: Pulled from various Public Transport Providers, JSON, Acea Smart Water Analytics

Our Implementation - Back-End

Python + Flask

Load the River Data into JSON files
Load the Metro and River Data from JSON into a NX Graph
Build NX Octilinear Graph in required Size
Order the Edges
Route the Edges and their Stations
Convert NX Graph to JSON and dispatch to Front-End

Our Implementation - Front-End

Web-Stack + Leaflet

Set up two Maps
Request JSON Graph and unchanged Map from Back-End
Iterate through JSONs, convert all Web Mercator Coordinates to WGS84
Place all Stations and all Lines

Station Hovering is linked
Rivers are in the Background
User can request different Grid Resolutions
User can choose between precalculated and live Graphs
User can select City to show
User can set opacity of River

Reference

Bast, Hannah & Brosi, Patrick & Storandt, Sabine. (2020). Metro Maps on Octilinear Grid Graphs. Computer Graphics Forum. 39. 357-367. 10.1111/cgf.13986.