Reingold-Tilford layout gives overlapping nodes

[szhorvat]

I have a tree on which igraph_layout_reingold_tilford gives overlapping nodes.

Here's what I get:

Notice the overlaps on the right.

I'm calling the function as

igraph_layout_reingold_tilford(&graph, &coord, IGRAPH_ALL, NULL, NULL);

Here's the edge list of the graph, in the same format expected by the C interface. Sorry about not being able to come up with a smaller one.

64, 0, 64, 1, 4, 2, 4, 3, 133, 4, 133, 5, 77, 6, 77, 7, 44, 8, 44, 9, 100, 10, 100, 11, 14, 12, 14, 13, 16, 14, 16, 15, 68, 16, 68, 17, 73, 18, 73, 19, 72, 20, 72, 21, 87, 22, 87, 23, 86, 24, 86, 25, 139, 26, 139, 27, 75, 28, 75, 29, 108, 30, 108, 31, 34, 32, 34, 33, 36, 34, 36, 35, 38, 36, 38, 37, 40, 38, 40, 39, 78, 40, 78, 41, 136, 42, 136, 43, 67, 44, 67, 45, 48, 46, 48, 47, 50, 48, 50, 49, 52, 50, 52, 51, 54, 52, 54, 53, 56, 54, 56, 55, 58, 56, 58, 57, 147, 58, 147, 59, 62, 60, 62, 61, 83, 62, 83, 63, 84, 64, 84, 65, 85, 66, 85, 67, 71, 68, 71, 69, 81, 70, 81, 71, 89, 72, 89, 73, 142, 74, 142, 75, 134, 76, 134, 77, 105, 78, 105, 79, 97, 80, 97, 81, 91, 82, 91, 83, 93, 84, 93, 85, 122, 86, 122, 87, 123, 88, 123, 89, 95, 90, 95, 91, 109, 92, 109, 93, 99, 94, 99, 95, 101, 96, 101, 97, 107, 98, 107, 99, 102, 100, 102, 101, 125, 102, 125, 103, 111, 104, 111, 105, 113, 106, 113, 107, 119, 108, 119, 109, 115, 110, 115, 111, 117, 112, 117, 113, 121, 114, 121, 115, 151, 116, 151, 117, 135, 118, 135, 119, 127, 120, 127, 121, 140, 122, 140, 123, 132, 124, 132, 125, 129, 126, 129, 127, 130, 128, 130, 129, 137, 130, 137, 131, 138, 132, 138, 133, 141, 134, 141, 135, 143, 136, 143, 137, 144, 138, 144, 139, 145, 140, 145, 141, 149, 142, 149, 143, 146, 144, 146, 145, 148, 146, 148, 147, 150, 148, 150, 149, 152, 150, 152, 151

[ntamas]

Thanks, this is a known issue but the problem is that I never managed to come up with an example graph that is small enough so I could start debugging it. This one's also a bit on the large side - it would be great if it could be made a bit smaller. In the worst case, I'll start removing nodes one by one to make it smaller.

[szhorvat]

Is my assumption correct that two nodes should never be closer than distance 1? I.e. the below one is incorrect too, right?

I'm trying to generate random trees to find smaller examples.

[ntamas]

There seems to be a minsep variable in the Reingold-Tilford code which defines the minimum separation between subtrees. It is set to constant 1 so this tree is probably also incorrect.

[szhorvat]

This one above has 21 nodes. The smallest ones where I can find problems are of size 20 (but those don't show the problem as clearly, visually). This one is:

0, 1, 2, 1, 3, 0, 4, 2, 5, 3, 6, 3, 7, 5, 8, 2, 9, 1, 10, 6, 11, 5, 12, 9, 13, 3, 14, 12, 15, 10, 16, 9, 17, 15, 18, 10, 19, 9, 20, 6

[szhorvat]

These are a few plots of trees where nodes get closer than 1. What they all have in common is that there's a small subtree in the middle separating two larger subtrees on the left and right. This might help construct a small example manually.

https://dl.dropboxusercontent.com/u/38623/bad-trees.pdf

[szhorvat]

OK, here's a test case:

We first start with this, based on the idea from above:

Mathematica, which I suspect to use a closely related algorithm, renders this indistinguishably.

Now we start adding nodes to one of the outer subtrees:

Now the two leaves in the centre are closer than 1. As a comparison, Mathematica does something slightly different here:

Finally, let's add one more leaf:

And we have the incorrect rendering!

For this example I set the root vertex manually instead of letting the algorithm choose it.

For comparison, Mathematica does this:

Here's the edge list I entered manually. 0 is the root.

0, 1,
0, 2,
0, 3,
2, 4,
2, 5,
1, 6,
6, 7,
6, 8,
6, 9,
3, 10,
10, 11,
10, 12,
10, 13,
10, 14,
10, 15

[ntamas]

Thanks a lot, great, this is something that I could actually start investigating (and I guess this is probably as minimal as it gets).

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[ntamas]

I'll try to tackle this before 0.8.3 now that we have a nice reproducible example.

[ntamas]

I have committed a patch here. I think I'm on the right track, but something is still off; this patch fixes the layout of the graphs in this topic, except the very first (large) graph in the first post.

[ntamas]

This is the layout that I get now with the patch:

[szhorvat]

Here's a 10-vertex example that fails after the patch:

[[7, 9], [5, 9], [6, 7], [3, 9], [1, 3], [3, 8], [4, 6], [2, 3], [0, 4]]

This is an edge list in Python format.

I get this:

(note that the vertices are indexed from 1 to 10 in the picture).

I produced this with a random fuzzer. I could not make a smaller example than this, and I could not make any other 10-vetex example. For reference, the fuzzer code:

Do[
 TimeConstrained[
  While[1 == 
    Max@MorphologicalComponents@
      Binarize@Image@
        IGLayoutReingoldTilford[g = IGTreeGame[n], GraphStyle -> "BasicBlack",
          EdgeStyle -> GrayLevel[0, 1]]];
  Print[g],
  60
  ],
 {n, 2, 10}
 ]

[szhorvat]

Another one:

[[1, 2], [1, 7], [6, 7], [1, 4], [1, 5], [0, 1], [1, 8], [3, 7], [6, 9]]

[ntamas]

THis is useful, thanks; will keep on debugging tomorrow.

[ntamas]

Okay, I think I now have a version that works for all the cases outlined in this issue. The original graph looks like this now:

[szhorvat]

This one does not work:

[[5, 13], [9, 13], [7, 9], [7, 10], [0, 10], [0, 6], [3, 6], [4, 6], [2, 9], [0, 1], [6, 8], [0, 14], [10, 11], [8, 12], [6, 15]]

[szhorvat]

16-vertex:

[[1, 11], [4, 11], [2, 4], [2, 12], [6, 12], [6, 9], [4, 7], [4, 13], [3, 11], [3, 5], [0, 7], [6, 15], [6, 10], [9, 14], [6, 8]]

[ntamas]

For the record: pushed another commit that fixes these and many others; the latest counterexample that is not working is [[23, 29], [23, 38], [26, 38], [26, 39], [7, 29], [7, 25], [3, 25], [3, 37], [24, 37], [24, 36], [19, 36], [23, 33], [27, 33], [20, 38], [14, 24], [4, 14], [18, 36], [10, 18], [8, 33], [2, 8], [14, 22], [17, 29], [22, 35], [7, 11], [18, 28], [9, 25], [5, 18], [21, 28], [21, 31], [12, 18], [29, 30], [10, 16], [13, 26], [13, 34], [0, 34], [6, 7], [10, 15], [1, 9], [13, 32]]. I'll have to postpone this until next week.

[ntamas]

@szhorvat This counterexample is now also fixed; please let me know if you can find more with your fuzzer. (I'm still not 100% convinced that all branches of the code are okay -- there are two main branches that are mostly symmetric, depending on whether the left or the right subtree ends when placing two subtrees next to each other, and the latest fix involved only one of the branches).