intermediate HashSet not needed
windwardly opened this issue · 0 comments
windwardly commented
In the file common/topo_sort/src/lib.rs
:
The computation following for node in dag
creates a HashSet containing the keys and parents, which extends the list of dag keys with parents not in the dag as keys. I'll call those non-key parents. Adding the non-key parents doesn't look like it can alter the output.
Non-key parents look like they are already being added to the stack to be processed. See the for child in children {
loop. Note that what are referred to as parents in other files are referred to as children here.
Aside:
- Cool code. I liked reading through and seeing how it worked.
- It's not clear to me why non-key parents are part of the output, as there is not enough information to correctly topo-sort them. If there are non-key parents, then they could be
out of order.