Re: [PATCH 2/2] graph: fix collapse of multiple edges

From: Derrick Stolee <stolee@gmail.com>
Date: Jan 8, 2020, 13:40 UTC
Message-ID: <7a0e4637-85de-589f-df31-915b4603e45a@gmail.com>
In-Reply-To: <20200108072541.GC1675456@coredump.intra.peff.net>

On 1/8/2020 2:25 AM, Jeff King wrote:

Show 40 quoted lines

> On Wed, Jan 08, 2020 at 04:27:55AM +0000, Derrick Stolee via GitGitGadget wrote:
> 
>> Before this change:
>>
>> 	| | | | | | *
>> 	| |_|_|_|_|/|\
>> 	|/| | | | |/ /
>> 	| | | | |/| /
>> 	| | | |/| |/
>> 	| | |/| |/|
>> 	| |/| |/| |
>> 	| | |/| | |
>>
>> By adding the logic for "filling" a horizontal edge between the
>> target column and the current column, we are able to resolve the
>> issue.
>>
>> After this change:
>>
>> 	| | | | | | *
>> 	| |_|_|_|_|/|\
>> 	|/| | | | |/ /
>> 	| | |_|_|/| /
>> 	| |/| | | |/
>> 	| | | |_|/|
>> 	| | |/| | |
> 
> Hmm. Your description and your diagrams make sense to me. But one
> curious thing is that the earlier test you added for 6_* does not need
> modified. Because it continues to show:
> 
>           | | | | * 6_F
>           | |_|_|/|
>           |/| | |/
>           | | |/|
>           | |/| |
>           | * | | 6_D
> 
> rather than adding a horizontal component to the second-parent line.
> That seems inconsistent.

The issue here is that there is not enough room for a second horizontal line. The horizontal line can only start after the previous has completely terminated, that is

           | | | | * 6_F
           | |_|_|/|
           |/| | |/

at this point, the first horizontal line has terminated.

           | | |/|
           | |/| |

The remaining movement for the second line has no room for a horizontal edge. The logic that I added is hit, but the for loop (over j) terminates immediately without a single execution of the loop body.

If there was one more row to the example, then we would have:

           | | | | | * 6_F
           | |_|_|_|/|
           |/| | | |/
           | | |_|/|
           | |/| | |
           | * | | | 6_D

Thanks, -Stolee