Simplify and document expansion functions of Graph
This PR accomplishes a few things, all in the spirit of hopefully reducing the mental load of understanding all the algorithms that allow Graph to grow:
- The term "parent" no longer depends on the graph's generation order. It now refers to the node along the first descender in enum order.
- Uses of the term "parent" and "child" were removed whenever they didn't refer to the above meaning of "parent". This includes renaming
insert_childtoinsert_neighborand renamingpopulate_shorter_neighbors_of_childtopopulate_shorter_neighbors_of_neighbor. - An unused code path was removed in
ensure_neighborto cover the impossible scenario of a not-yet-generated shorter neighbor. Removing this code-path turned it into a one-liner. - The most conceptually difficult function in the algorithm,
populate_shorter_neighbors_of_neighboris now documented in detail. For simplification purposes, it was also altered to return all shorter neighbors, including the passed in argument (as it previously excluded this argument, resulting in extra logic forinsert_neighbor).
I believe some of the comments I've written don't make sense, although it's hard to tell in what way they don't make sense and how to improve them, so I hope that peer review will help here.
Great improvement overall! I don't think I ever actually understood this logic, so this clarity is striking.
Ah, the "Compare" button isn't as useful this time because it also includes all the changes from master that were included. I'll list out the changes I made:
- At the top of
insert_neighbor, I added the comment
// To help improve readability, we use the term "subject" to refer to the not-yet-created neighbor node, since the term.
// "neighbor" is already used in many other places.
- In
insert_neighbor, I renamedshorter_neighbors_of_neighbortoshorter_neighbors_of_subject`. - I changed the name of the function
populate_shorter_neighbors_of_neighborwithpopulate_shorter_neighbors_of_subjectand updated the function header comment to explain what "subject" means. - I removed the comment at the top of the
populate_shorter_neighbors_of_subjectfunction explaining the use of "subject", as the concept is no longer introduced there. - I added the following addendum to
populate_shorter_neighbors_of_subject's long comment:
// Note that this shorter neighbor might not yet be in the graph, which is why we call `ensure_neighbor`
// here instead of `neighbor`. This means that nodes in the graph will be recursively created as necessary.
- I used
shorter_neighbors_of_subject.into_iter().flatten()as suggested.
I realize that my note about calling ensure_neighbor instead of neighbor was unnecessarily verbose for what is already a long and dense explanation, so I replaced it with the (and recursively create if needed) parenthetical, which accomplishes the same thing in far fewer words.