Graph Modelling

Graph modelling is the step before a graph algorithm: deciding what the vertices are, what the edges are, whether an edge runs one way and whether it has a cost, in a problem that never says graph. It matters because the algorithms are already known, breadth-first search and topological sort from Algorithms and union-find from Data Structures, and the hard part of most graph questions is seeing that they are graph questions at all. The topic opens on four decisions applied to a set of translators, solves a jug puzzle by searching a graph of states that is built only as far as the search reaches, and gives the state search template in Python, Java and TypeScript. It orders courses that have prerequisites, groups library cards into households through the details they share, shows why depth-first search does not find the fewest moves, and ends with an exercise in which the choice of vertex decides what the search counts.