BKNodePlacer MIN_LAYERS_FOR_CONFLICTS should be 4

[vibridi]

In the Layered graph plugin at the line https://github.com/eclipse/elk/blob/master/plugins/org.eclipse.elk.alg.layered/src/org/eclipse/elk/alg/layered/p4nodes/bk/BKNodePlacer.java#L294

it seems the constant MIN_LAYERS_FOR_CONFLICTS should be 4 instead of 3. Or the inequality should not be strictly less.

        // change to <= or change const to 4
        if (numberOfLayers < MIN_LAYERS_FOR_CONFLICTS) {
            return;
        }

A type 1 conflict in Brandes-Köpf is defined as a crossing between an inner edge and a non-inner edge. Given that an edge is "inner" when it connects two virtual nodes, and that virtual nodes result from breaking edges spanning more layers, an inner edge can occur only when there's >= 4 layers.

// L1 ---N1---N2---N3---
//       |
// L2 ---V1---------------
//       |
// L3---V2----------------
//       |
// L4---N4----------------

Probably not a big deal since I guess with 3 layers the routine BKNodePlacer#markConflicts would simply mark no conflicts.

Please can you confirm if my understanding is correct? Thank you

[soerendomroes]

I think there can even be an inner edge if we have only two layers since north or south port dummy nodes might be introduced in layouts such as this one.

// L1   V1-N1
//       |
// L2   V2-N2

Since I am not sure whether there are other cases where this might be relevant, I cannot give you a definitive answer. However, a value of at least 3 seems to be necessary to even execute the implemented algorithm.

Thank you for your feedback, if you find examples were this part does produce errors or does not behave as expected, we always appreciate the feedback.

[vibridi]

Thank you! I missed that the north-south port routine can add extra virtual nodes with flat edges, in that case the constant set to 3 makes sense. I'll go ahead and close this issue for now. Thanks again