Below is a correction of the first proposed algorithm:
>--o1--o2--o3--G --X1
> \ \
> x1--x2--x3--x4--X2--B--
> \ /
> y1--y2--y3
>
Step 1a. (Unchanged) keep only the commits that:
a) are ancestor of the "bad" commit (including the "bad" commit itself),
b) are not ancestor of a "good" commit (excluding the "good" commits).
The following graph results:
x1--x2--x3--x4--X2--B--
\ /
y1--y2--y3
Step 1b. (New) Mark all commits of the resulting graph as unconfirmed
(unconfirmed=node without good ancestors).
Mark as confirmed all descendants of commits that user marked
explicitly as good (e.g if user already marked its parent/grand
parent/... as good right before starting bisect run).
Step 1c. From all unconfirmed root commits build a set SET_GOOD of
those with any good parents in the original graph (root commit =
commit without parents in the resulting graph) and one SET_BAD for
commits with only BAD parents. To build a set means to ask explicitly
the user (or the command passed in git bisect run) whether any of its
parents is good. In the example above find out whether x1 has any good
parents or no parent at all and if so add it to SET_GOOD, otherwise to
SET_BAD.
Mark as confirmed each commit in SET_GOOD and all its descendants.
For every commit in SET_BAD delete all paths from it until to the next
confirmed commit. In the example above if x1 is in SET_BAD delete the
path x1-x3 and x1-y3. If any new root commits result (commit x4), redo
step 1c with them.
Step2. Continue the existing algorithm.
If this improvement works (i.e you do not find any bugs in it and it
is feasible to implement, which seems to me) the following would be
its advantages:
1. An assumption less, as we explicitly check the assumption.
2. It might be quicker, because we delete parts of graph that cannot
contain transitions.
3. It returns more exact results.
VG