DFS cycle breaker introduces cycles

[uruuru]

Issue occurred during hierarchical tests.

I was able to reduce the problematic graph to the following. The issue is that a last separate node has an outgoing edge. Maybe it's a problematic combination of external port dummy and inverted port dummy.

e_N83.E141 P188[n(external_port)_N83.P188] -> P190[n_state_0]
n(external_port)_N83.P188 LAST_SEPARATE
n_state_0 NONE

node N83 {
    nodeLabels.placement: "[H_LEFT, V_TOP, OUTSIDE]"
    portConstraints: FREE
    label L83: "LinearStateSpace" {
        layout [ size: 104, 15 ]
    }
    port P188 {
        layout [ size: 8, 8 ]
        index: 2
        side: EAST
    }
    node N84 {
        layout [ size: 44, 46 ]
        nodeLabels.placement: "[H_LEFT, V_TOP, OUTSIDE]"
        portConstraints: FIXED_ORDER
        label L84: "state_0" {
            layout [ size: 44, 15 ]
        }
        port P189 {
            layout [
                position: -8, 19
                size: 8, 8
            ]
            index: 0
            side: WEST
        }
        port P190 {
            layout [
                position: 44, 19
                size: 8, 8
            ]
            index: 1
            side: EAST
        }
    }
    node N85 {
        layout [ size: 41, 41 ]
        nodeLabels.placement: "[H_LEFT, V_TOP, OUTSIDE]"
        portConstraints: FIXED_ORDER
        label L85: "stateAdder_0" {
            layout [ size: 78, 15 ]
        }
        port P191 {
            layout [
                position: -8, 8.333333015441895
                size: 8, 8
            ]
            index: 0
            side: WEST
        }
        port P192 {
            layout [
                position: -8, 24.66666603088379
                size: 8, 8
            ]
            index: -1
            side: WEST
        }
        port P193 {
            layout [
                position: 41, 16.5
                size: 8, 8
            ]
            index: 2
            side: EAST
        }
    }
    node N86 {
        layout [ size: 44, 46 ]
        nodeLabels.placement: "[H_LEFT, V_TOP, OUTSIDE]"
        portConstraints: FIXED_ORDER
        label L86: "state_1" {
            layout [ size: 44, 15 ]
        }
        port P194 {
            layout [
                position: -8, 19
                size: 8, 8
            ]
            index: 0
            side: WEST
        }
        port P195 {
            layout [
                position: 44, 19
                size: 8, 8
            ]
            index: 1
            side: EAST
        }
    }
    node N93 {
        layout [ size: 66, 46 ]
        nodeLabels.placement: "[H_LEFT, V_TOP, OUTSIDE]"
        portConstraints: FIXED_ORDER
        label L93: "feedback_0_1" {
            layout [ size: 81, 15 ]
        }
        port P211 {
            layout [
                position: -8, 19
                size: 8, 8
            ]
            index: 0
            side: WEST
        }
        port P212 {
            layout [
                position: 66, 19
                size: 8, 8
            ]
            index: 1
            side: EAST
        }
    }
    edge E141: N84.P190 -> P188
    edge E148: N85.P193 -> N84.P189
    edge E149: N86.P195 -> P188
    edge E150: N86.P195 -> N93.P211
    edge E174: N93.P212 -> N85.P191
}

[le-cds]

I just tried reproducing this, but it works for me, both when I test this manually and when I push it through the BasicCycleBreakerTest. Is there anything I have to configure for it to reproduce the issue?

[uruuru]

I can't get my Eclipse setup working but the build still complains after a rebase (although that may be a different issue):

2020-06-18T11:28:24.1708891Z testIsAcyclic (21766)(org.eclipse.elk.alg.layered.p1cycles.BasicCycleBreakerTest)  Time elapsed: 0 s
2020-06-18T11:28:24.1709559Z algorithm(org.eclipse.elk.layered) defaults(nodes, ports, edges) layoutConfigurator(depthFirstConfigurator) graphFile(/home/runner/work/elk/elk/elk-models/realworld/ptolemy/hierarchical/tdl_activerearsteeringct_ActiveRearSteeringCT.elkg)  Time elapsed: 0.02 s  <<< FAILURE!
2020-06-18T11:28:24.1709719Z java.lang.AssertionError

The model I posted above does, in fact, work for me as well by now. Were your changes to the layer constraint processor in the meantime and may have altered the behavior?

EDIT: the tests only fails for CycleBreakingStrategy.DEPTH_FIRST, as does the small example above for me.

[le-cds]

I boiled down the graph to this, which reproduces the error in my installation:

node N1 {
    cycleBreaking.strategy: DEPTH_FIRST

    port P1_1

    node N2 {
        port P2_1
        port P2_2
    }
    node N3 {
        port P3_1
        port P3_2
    }
    node N4 {
        port P4_1
    }
    node N5 {
        port P5_1
        port P5_2
    }

    edge N2.P2_2 -> P1_1
    edge N3.P3_2 -> N2.P2_1
    edge N4.P4_1 -> P1_1
    edge N4.P4_1 -> N5.P5_1
    edge N5.P5_2 -> N3.P3_1
}

For some reason, the cycle breaker decides to reverse the edge from N2.P2_2 to the external port. Thus, the external port has an outgoing edge, which triggers the assertion. It remains to be checked why that happens.