A helper lesson for the course "Build your own arbitrage bot". Lessons 5 to 8 look at currencies as a graph. Here is what that word means, with a map instead of money.
A graph is a map
Take a small neighbourhood. Four places: Home, Park, Cafe, Work. Between some of them there are roads, and each road takes a number of minutes.
- Home to Cafe: 4. Home to Park: 2. Park to Cafe: 1. Cafe to Work: 5. Park to Work: 8.
The places are called nodes (or vertices). The roads are called edges. The minutes on a road are its weight. Together this is a graph. Nothing more. A subway map and a friends network are graphs too, and so is a table of exchange rates: currencies are the nodes, a rate is an edge.
Storing a graph
Store, for each node, the list of roads that leave it. In Python this is a dictionary of lists:
roads = {("Home", "Cafe"): 4, ("Home", "Park"): 2, ("Park", "Cafe"): 1,
("Cafe", "Work"): 5, ("Park", "Work"): 8}
neighbours = {}
for (a, b), minutes in roads.items():
neighbours.setdefault(a, []).append((b, minutes))
print(neighbours["Home"])
[('Cafe', 4), ('Park', 2)]
From Home you can go to Cafe (4 minutes) or Park (2 minutes).
The head-on way: list every route
How do you get from Home to Work fastest? The blunt way is to list every route and take the shortest.
def all_routes(here, goal, route=None, total=0):
route = (route or []) + [here]
if here == goal:
yield route, total
return
for nxt, minutes in neighbours.get(here, []):
if nxt not in route:
yield from all_routes(nxt, goal, route, total + minutes)
for route, total in sorted(all_routes("Home", "Work"), key=lambda x: x[1]):
print(" -> ".join(route), total, "min")
Home -> Park -> Cafe -> Work 8 min
Home -> Cafe -> Work 9 min
Home -> Park -> Work 10 min
The fastest way is through the Park and the Cafe, 8 minutes. The direct looking road Home to Cafe is not the best, because the detour through the Park saves a minute. This is the shortest path problem.
Where the blunt way breaks
Count the routes. A map with 4 places had 3. Add places and roads and the number of routes multiplies: a map where every place connects to 10 others has about 10 × 10 × 10 ... routes of length n, which for 10 steps is 10 billion. Listing them is hopeless. Real graphs have hundreds of nodes.
The clever algorithms of lessons 6 and 7 do not list routes. They keep, for each node, the best total found so far, and improve it step by step. That is the entire idea, and it is why they stay fast.
Your exercise
- Run the code. Add a road ("Cafe", "Park"): 1 in the other direction. Does the number of routes change?
- Add a place "Gym" with roads Home to Gym 3 and Gym to Work 6. What is the fastest route now?
- Draw the map on paper and find the fastest route by eye. Check with the code.
Next: the helper on averages and spreads (arbitrage-prereq-3-mean-stdev).