When working on an implementation for bug 754777, I noticed that find_smallest_cycle sometimes selects a single node because it's in the mergeable_nodes set and ignore_priority causes the node's children to be dropped. For find_smallest_cycle we need stop passing the ignore_priority parameter to gather_deps, and gradually increase the ignore_priority used to select the mergeable_nodes set.
Ultimately, we'll want find_smallest_cycle to sort all of the edges in order of increasing priority. Then it can traverse this list of edges until it finds a cycle to select.
*** Bug 762787 has been marked as a duplicate of this bug. ***