Jeff King <peff <at> peff.net> writes: > PS This would be a much simpler algorithm to write in a depth-first way. > But that would also involve traversing the entire graph down to the > roots, which we try to avoid. Which reminds me of my "tag > --contains" depth first algorithm, and gives me some ideas on how to > make it work in a breadth-first way. So even if my idea here is > flawed, this thinking hasn't been completely fruitless. :) IMHO, using BFS and counting commits is flawed, since the output is hard to understand and quite meaningless for humans. Imagine a merge of two long branches, one with a tag 10 commits deep and the other with a tag 11 commits deep. Do you see any reason for a human to prefer the first one? I do not. I could imagine to always prefer the first branch, which leads to DFS. What is your reason for avoiding traversing to the roots? It could be better to traverse the first branch only to the point where the other started, then traverse the other one, and then continue down the common trunk. This sounds a bit complicated to implement and may be hard to specify in more complicated cases. A rule like "tag T1 can be returned only if there's no tag T2 higher (i.e. newer) in the tree", could possibly solve it. Finally, using a chronological ordering instead of counting commits seems to be the most straightforward to me. An implementation using a priority queue is no less and no more complicated then BFS or DFS. I think, it could be an interesting and easy to comprehend option. In case I'm talking non-sense, pls bare with me, since I'm still a beginner. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html