Card 07/ 08
Practice: Storing a Small Rail Network
Six stations and the lines between them, with travel times in minutes.
A rail network is a graph whose vertices are stations and whose edges are the lines between them, each labelled with its travel time. This exercise covers naming such a graph's properties, building its adjacency list with the times kept on the entries, and choosing a representation when the network grows to a whole country.
A graph is a set of vertices and the edges between pairs of them. An adjacency list keeps one list per vertex, holding its neighbours; an adjacency matrix is a grid with one row and one column per vertex.
The diagram shows six stations and seven lines, with each line's travel time in minutes. Trains run both ways on every line.
- Say whether the graph is directed or undirected, weighted or unweighted, and cyclic or acyclic, with a reason for each.
- Write its adjacency list, keeping each line's travel time with the neighbour, and count the entries.
- Count the cells an adjacency matrix of this network would need.
- The rail operator extends the network to 2,500 stations, each on about three lines. Choose a representation, giving the two storage counts.
An answer: the properties, the list and the choice
The graph is undirected, because trains run both ways, so every line is stored under both of its stations. It is weighted, because every line carries a time. It is cyclic: North, Market, Castle and back to North is one cycle.
The adjacency list stores each neighbour with the minutes to reach it. Seven lines give 14 entries, and a matrix would need 36 cells, with the time in a cell for each line and a value such as infinity for no line.
| Station | Neighbours, with minutes |
|---|---|
| North | Market 12, Castle 9 |
| Market | North 12, Harbour 7, Castle 5 |
| Castle | North 9, Market 5, Mill 14 |
| Harbour | Market 7, Airport 20 |
| Mill | Castle 14, Airport 11 |
| Airport | Harbour 20, Mill 11 |
For the whole network, choose the adjacency list. With 2,500 stations on about three lines each, the list holds about 7,500 entries and the matrix 6,250,000 cells, nearly all of them empty. A journey planner mostly asks which stations are one line away from this one, which the list answers by reading one short list and the matrix only by scanning a row of 2,500 cells. The run below builds the list and counts both.
lines = [
("North", "Market", 12),
("North", "Castle", 9),
("Market", "Harbour", 7),
("Market", "Castle", 5),
("Castle", "Mill", 14),
("Harbour", "Airport", 20),
("Mill", "Airport", 11),
]
stations = ["North", "Market", "Castle", "Harbour", "Mill", "Airport"]
network = {station: [] for station in stations}
for a, b, minutes in lines:
network[a].append((b, minutes))
network[b].append((a, minutes))
for station in stations:
print(f"{station}: " + ", ".join(f"{other} {minutes}" for other, minutes in network[station]))
print("stations:", len(stations), "| lines:", len(lines))
print("list entries:", sum(len(n) for n in network.values()), "| matrix cells:", len(stations) ** 2)
print("North - Market - Castle - North is a cycle:",
any(o == "Market" for o, _ in network["North"])
and any(o == "Castle" for o, _ in network["Market"])
and any(o == "North" for o, _ in network["Castle"]))
country_stations, lines_per_station = 2_500, 3
country_entries = country_stations * lines_per_station
print(f"{country_stations:,} stations with {lines_per_station} lines each: list entries {country_entries:,}, matrix cells {country_stations ** 2:,}")North: Market 12, Castle 9
Market: North 12, Harbour 7, Castle 5
Castle: North 9, Market 5, Mill 14
Harbour: Market 7, Airport 20
Mill: Castle 14, Airport 11
Airport: Harbour 20, Mill 11
stations: 6 | lines: 7
list entries: 14 | matrix cells: 36
North - Market - Castle - North is a cycle: True
2,500 stations with 3 lines each: list entries 7,500, matrix cells 6,250,000← → move through sections and cards