hypermine icon indicating copy to clipboard operation
hypermine copied to clipboard

Simplify and document expansion functions of Graph

Open patowen opened this issue 1 year ago • 1 comments

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_child to insert_neighbor and renaming populate_shorter_neighbors_of_child to populate_shorter_neighbors_of_neighbor.
  • An unused code path was removed in ensure_neighbor to 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_neighbor is 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 for insert_neighbor).

patowen avatar Jun 30 '24 03:06 patowen

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.

patowen avatar Jun 30 '24 04:06 patowen

Great improvement overall! I don't think I ever actually understood this logic, so this clarity is striking.

Ralith avatar Jul 27 '24 17:07 Ralith

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 renamed shorter_neighbors_of_neighbortoshorter_neighbors_of_subject`.
  • I changed the name of the function populate_shorter_neighbors_of_neighbor with populate_shorter_neighbors_of_subject and updated the function header comment to explain what "subject" means.
  • I removed the comment at the top of the populate_shorter_neighbors_of_subject function 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.

patowen avatar Jul 28 '24 14:07 patowen

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.

patowen avatar Jul 28 '24 14:07 patowen