Card 01/ 08
Graph Modelling: Finding the Graph a Problem Never Mentions
Decide what the things are, what links them, whether a link runs one way and what it costs: then the question names the graph algorithm.
A problem is a graph problem when it has things, links between pairs of those things, and a question about reaching one thing from another, putting the things in an order, or sorting them into groups, even when the word graph never appears. Modelling it takes four decisions: what a vertex is, what an edge is, whether an edge has a direction, and whether it has a weight, a cost attached to crossing it. Once those are made, the question names the algorithm. A translation agency has eight translators, each working between two languages in either direction: Portuguese and Spanish, Portuguese and French, Spanish and English, French and German, English and Japanese, German and Japanese, Japanese and Korean, English and Korean. A document in Portuguese must reach Korean, each translator passing it to the next.
What is the fewest number of translations that takes the document from Portuguese to Korean?
3: Portuguese to Spanish, Spanish to English, English to Korean. The route through French and German is one translation longer.
The languages are the vertices and the translators are the edges, since a translator links exactly two languages. The diagram draws them.
Each item in the wording takes one of the four decisions.
| Item | Vertex or edge | Direction | Weight |
|---|---|---|---|
| A language | Vertex | Not applicable | Not applicable |
| A translator | Edge between two languages | None: works both ways | None: every translation counts as one |
The edges have no weight, and the question asks for the fewest of them, so the algorithm is breadth-first search, the Graph Traversal topic in Algorithms. From Portuguese it reaches Spanish and French after one translation, English and German after two, and Japanese and Korean after three. The other questions a graph answers each have their own algorithm.
| Question | Algorithm |
|---|---|
| Fewest edges from one vertex to another | Breadth-first search |
| Cheapest route when edges have different weights | Dijkstra's algorithm |
| An order in which every edge points forwards | Topological sort |
| Which vertices are joined, directly or through others | Union-find, or a search from each unreached vertex |
| Can one vertex be reached from another at all | Any search |
Modelling is like drawing a map from a stranger's directions: you decide which places become dots and which roads become lines, and only then can you plan a route. The likeness breaks at the size. A map is drawn whole before anyone reads it, while the graph in many problems is too large to draw, every arrangement of a puzzle for instance, so the search builds only the part of it that it reaches.
← → move through sections and cards