mrtlib

A simple library help to find routes in Taipei MRT.

Created from templates made available by Stagehand under a BSD-style license.

Overview

mrtlib models the Taipei MRT (Mass Rapid Transit) network as a graph and provides a depth-first search (DFS) algorithm to enumerate all possible routes between any two stations. Results are sorted so that routes with fewer total hops appear first, and among equal-length routes, those with fewer line changes appear first.

MRT lines included

Route ID	Line name (English)	Line name (Chinese)	Terminal stations
1	Wenhu Line	文湖線	動物園 ↔ 南港展覽館
2	Tamsui-Xinyi Line	淡水信義線	淡水 ↔ 象山
3	Songshan-Xindian Line	松山新店線	松山 ↔ 新店 / 小碧潭
4	Zhonghe-Xinlu Line	中和新蘆線	南勢角 ↔ 迴龍 / 蘆洲
5	Bannan Line	板南線	永寧 ↔ 南港展覽館

Classes

MRTMap

The entry point of the library. On construction it loads the built-in station data and builds an in-memory graph.

Member	Description
Map<String, MRTExit> exits	All stations keyed by their Chinese name.
List<MRTRoute> findRoutes(String from, String to)	Returns all routes between two stations, sorted by transit count then by total stops. Throws an Exception for invalid or identical station names.

MRTExit

Represents a single MRT station (exit node in the graph).

Member	Description
String name	The station name in Chinese.
List<MRTLink> links	Outgoing connections to adjacent stations.

MRTLink

Represents a directed edge in the graph connecting two adjacent stations on the same line.

Member	Description
String routeID	The numeric ID of the MRT line (e.g. "1" for the Wenhu Line).
MRTExit to	The destination station.

MRTRoute

Represents a complete route found by MRTMap.findRoutes.

Member	Description
MRTExit from	The origin station.
List<MRTLink> links	Ordered list of links that form the route.
int transitCount	Total number of links (hops) in the route.
int mrtStationCount	Number of line-change points along the route.

Usage

Finding routes

Create an MRTMap instance and call findRoutes with the Chinese station names of the origin and destination:

import 'package:mrtlib/mrtlib.dart';

void main() {
  final map = MRTMap();

  final routes = map.findRoutes('大安', '忠孝復興');
  print('Found ${routes.length} route(s).');

  for (final route in routes) {
    print(route);
  }
}

Inspecting route details

Each MRTRoute exposes the individual links so you can inspect every hop:

final routes = map.findRoutes('大安', '南港展覽館');
final best = routes.first;          // already sorted, fewest transits first

print('From : ${best.from.name}');
print('Stops: ${best.transitCount}');
print('Line changes: ${best.mrtStationCount}');

for (final link in best.links) {
  print('  -[${link.routeID}]-> ${link.to.name}');
}

Error handling

findRoutes throws an Exception in the following cases:

Condition	Message
Either argument is null	'from is null' / 'to is null'
Both stations are the same	'Begin and destination should be different.'
Origin station not found	'Unable to find this exit as begin.'
Destination station not found	'Unable to find this exit as destination.'

try {
  final routes = map.findRoutes('東京', '京都');
} catch (e) {
  print('Error: $e');
}

Algorithm

MRTMap.findRoutes delegates to an internal _MRTRouteFinder which performs a depth-first search (DFS) over the graph:

1. Starting from the origin station, each adjacent link is followed recursively.
2. Already-visited stations are tracked to prevent cycles.
3. Every time the destination station is reached, the current path is recorded as a new MRTRoute.
4. After all routes are collected, they are sorted with a comparator that prefers routes with fewer total hops (transitCount) and, among ties, fewer line changes (mrtStationCount).