Basis Lab

Making it fast enough

Model anything made of things and the connections between them as a graph, and run the small number of walks over it that answer most real questions, what can be reached, what is closest, and what order things have to happen in

Graphs and Finding a Path

Points and the links between them, and the four or five traversals that answer nearly every question anyone asks of a network.

8 lessons, written and corrected before you arrived. Reading them here needs no account. The first reads the whole way through; the others open and then stop, because a page nobody owns cannot tell who is reading it. Starting the course gives you your own copy, where every idea has problems standing under it and you can ask about any sentence.

Start reading

This is course 5 of 8 in a reading track: tell in advance which approach survives a million rows. The track is an order, not a gate, and the rest of it is on one page.

  1. 01Things and the Links Between ThemA graph is points and connections, and almost every network question becomes easy once the two decisions about direction and cost have been made honestly.
  2. 02Writing a Graph Downopening onlyThere are two ways to store a graph, a table of every pair or a list of neighbours per point, and the density of the graph decides which one is right.
  3. 03Spreading Out One Ring at a Timeopening onlyVisiting a graph in rings of increasing distance finds the fewest-link route to everything reachable, and the proof of that is one sentence about the order points are met in.
  4. 04Following One Path to the Endopening onlyGoing as deep as possible before backtracking uses almost no memory, gives up the shortest path guarantee, and answers two questions the ring walk cannot.
  5. 05When Some Links Cost Moreopening onlyWeights break the ring walk immediately, and the repair is to serve the waiting line in order of cheapest known cost, which is one substitution and a proof.
  6. 06Doing Things in a Possible Orderopening onlyAn order that respects every dependency comes out of either walk, no such order exists exactly when there is a cycle, and the same question is answered by every build tool.
  7. 07Connecting Everything Cheaplyopening onlyJoining every point for the least total cost is the one problem in this course where taking the cheapest thing available at every step is provably right.
  8. 08When the Graph Does Not Fitopening onlyA graph too large to walk is searched by guessing which direction the destination lies in, and the guess has to satisfy one condition or the answer stops being right.