What to hand in

algo with net and dense, passing go test ./..., plus a report.

1. The shape of your network

Report, at n = 1,000 / 10,000 / 100,000: nodes, edges, mean and median degree, component count, largest component, and the diameter of that component.

Then vary -trails and -length and find the point at which the largest component covers 90% of the library. What has to change — more trails or longer ones? Explain in terms of what each flag does to the graph.

2. Which search for which question

Six questions. For each: BFS, DFS, or either — and one sentence why.

• is book B reachable from book A at all?
• how many borrows separate A and B?
• give me every book reachable from A
• how many separate islands does the library have?
• find any book 10 or more hops from A
• is the network one piece?

At least one should be "either", and for that one say which you would actually write and why.

3. Representation, decided with numbers

Step 7 measured the list against the matrix on your network. Now find the crossover.

Hold V at 1,000 and raise the edge count until the matrix wins on memory. What mean degree is that? Express it as a fraction of V.

Then say which of the two transit graphs would be near that line, and which is nowhere near it.

4. The model follows the question

Step 8's point was that transit leaves time out of the stop graph on purpose.

Design a graph for each of these three questions about your library. Nodes, edges, and what an edge means — no code.

• which books are borrowed together most often?
• which book should be recommended after this one?
• which two books could no reader have borrowed in the same visit?

At least one of them cannot be an unweighted graph. Say which, and why — that is the whole of lesson 15's premise.

5. The one thing BFS cannot do

BFS answers "fewest hops" because every hop costs the same.

Write down, in your own words, exactly what breaks if the edges of your library network carried different costs — say, days between borrows. Not "it would be slower": say what BFS's layer argument depends on and which part of it stops being true.

Then predict what would have to replace the queue. You built it in lesson 13.