search

kieler / elkjs

ELK's layout algorithms for JavaScript
Other
1.81k stars 97 forks source link

It doesn't choose the shorter path #304

Closed tylerlong closed 3 weeks ago

tylerlong commented 4 weeks ago

Describe the bug from C to A, why not go from right side? It's shorter. I don't see any disadvantages for going from right side.

Expected behavior from C to A, the edge should go from right side since it is shorter.

Screenshots demo

ELK Version 0.9.3

Additional context

Input

{
  "graph": {
    "id": "root",
    "children": [
      {
        "id": "A",
        "width": 57.6,
        "height": 51.2,
        "labels": [
          {
            "text": "A"
          }
        ],
        "ports": [
          {
            "id": "A_u",
            "x": 28.8,
            "y": 0
          },
          {
            "id": "A_r",
            "x": 57.6,
            "y": 25.6
          },
          {
            "id": "A_d",
            "x": 28.8,
            "y": 51.2
          },
          {
            "id": "A_l",
            "x": 0,
            "y": 25.6
          }
        ],
        "properties": {
          "portConstraints": "FIXED_POS",
          "partition": 0
        }
      },
      {
        "id": "B",
        "width": 57.6,
        "height": 51.2,
        "labels": [
          {
            "text": "B"
          }
        ],
        "ports": [
          {
            "id": "B_u",
            "x": 28.8,
            "y": 0
          },
          {
            "id": "B_r",
            "x": 57.6,
            "y": 25.6
          },
          {
            "id": "B_d",
            "x": 28.8,
            "y": 51.2
          },
          {
            "id": "B_l",
            "x": 0,
            "y": 25.6
          }
        ],
        "properties": {
          "portConstraints": "FIXED_POS",
          "partition": 1
        }
      },
      {
        "id": "C",
        "width": 57.6,
        "height": 51.2,
        "labels": [
          {
            "text": "C"
          }
        ],
        "ports": [
          {
            "id": "C_u",
            "x": 28.8,
            "y": 0
          },
          {
            "id": "C_r",
            "x": 57.6,
            "y": 25.6
          },
          {
            "id": "C_d",
            "x": 28.8,
            "y": 51.2
          },
          {
            "id": "C_l",
            "x": 0,
            "y": 25.6
          }
        ],
        "properties": {
          "portConstraints": "FIXED_POS",
          "partition": 1
        }
      }
    ],
    "edges": [
      {
        "id": "A-B",
        "sources": [
          "A_d"
        ],
        "targets": [
          "B_u"
        ]
      },
      {
        "id": "A-C",
        "sources": [
          "A_d"
        ],
        "targets": [
          "C_u"
        ]
      },
      {
        "id": "C-A",
        "sources": [
          "C_d"
        ],
        "targets": [
          "A_u"
        ]
      }
    ]
  },
  "options": {
    "layoutOptions": {
      "elk.algorithm": "layered",
      "elk.direction": "DOWN",
      "elk.edgeRouting": "SPLINES",
      "elk.layered.spacing.baseValue": "64",
      "elk.edgeLabels.inline": "true",
      "elk.layered.crossingMinimization.forceNodeModelOrder": "true",
      "elk.partitioning.activate": "true"
    }
  }
}

Output

{
  "id": "root",
  "children": [
    {
      "id": "A",
      "width": 57.6,
      "height": 51.2,
      "labels": [
        {
          "text": "A",
          "x": 0,
          "y": 0,
          "width": 0,
          "height": 0
        }
      ],
      "ports": [
        {
          "id": "A_u",
          "x": 28.8,
          "y": 0,
          "width": 0,
          "height": 0
        },
        {
          "id": "A_r",
          "x": 57.6,
          "y": 25.6,
          "width": 0,
          "height": 0
        },
        {
          "id": "A_d",
          "x": 28.8,
          "y": 51.2,
          "width": 0,
          "height": 0
        },
        {
          "id": "A_l",
          "x": 0,
          "y": 25.6,
          "width": 0,
          "height": 0
        }
      ],
      "properties": {
        "portConstraints": "FIXED_POS",
        "partition": 0
      },
      "$H": 16,
      "x": 104.8,
      "y": 44
    },
    {
      "id": "B",
      "width": 57.6,
      "height": 51.2,
      "labels": [
        {
          "text": "B",
          "x": 0,
          "y": 0,
          "width": 0,
          "height": 0
        }
      ],
      "ports": [
        {
          "id": "B_u",
          "x": 28.8,
          "y": 0,
          "width": 0,
          "height": 0
        },
        {
          "id": "B_r",
          "x": 57.6,
          "y": 25.6,
          "width": 0,
          "height": 0
        },
        {
          "id": "B_d",
          "x": 28.8,
          "y": 51.2,
          "width": 0,
          "height": 0
        },
        {
          "id": "B_l",
          "x": 0,
          "y": 25.6,
          "width": 0,
          "height": 0
        }
      ],
      "properties": {
        "portConstraints": "FIXED_POS",
        "partition": 1
      },
      "$H": 286,
      "x": 44,
      "y": 159.2
    },
    {
      "id": "C",
      "width": 57.6,
      "height": 51.2,
      "labels": [
        {
          "text": "C",
          "x": 0,
          "y": 0,
          "width": 0,
          "height": 0
        }
      ],
      "ports": [
        {
          "id": "C_u",
          "x": 28.8,
          "y": 0,
          "width": 0,
          "height": 0
        },
        {
          "id": "C_r",
          "x": 57.6,
          "y": 25.6,
          "width": 0,
          "height": 0
        },
        {
          "id": "C_d",
          "x": 28.8,
          "y": 51.2,
          "width": 0,
          "height": 0
        },
        {
          "id": "C_l",
          "x": 0,
          "y": 25.6,
          "width": 0,
          "height": 0
        }
      ],
      "properties": {
        "portConstraints": "FIXED_POS",
        "partition": 1
      },
      "$H": 293,
      "x": 165.6,
      "y": 159.2
    }
  ],
  "edges": [
    {
      "id": "A-B",
      "sources": [
        "A_d"
      ],
      "targets": [
        "B_u"
      ],
      "sections": [
        {
          "id": "A-B_s0",
          "startPoint": {
            "x": 133.6,
            "y": 95.2
          },
          "endPoint": {
            "x": 72.8,
            "y": 159.2
          },
          "bendPoints": [
            {
              "x": 133.6,
              "y": 95.2
            },
            {
              "x": 78.88,
              "y": 127.19999999999999
            }
          ],
          "incomingShape": "A_d",
          "outgoingShape": "B_u"
        }
      ],
      "container": "root"
    },
    {
      "id": "A-C",
      "sources": [
        "A_d"
      ],
      "targets": [
        "C_u"
      ],
      "sections": [
        {
          "id": "A-C_s0",
          "startPoint": {
            "x": 133.6,
            "y": 95.2
          },
          "endPoint": {
            "x": 194.4,
            "y": 159.2
          },
          "bendPoints": [
            {
              "x": 133.6,
              "y": 95.2
            },
            {
              "x": 188.32,
              "y": 127.19999999999999
            }
          ],
          "incomingShape": "A_d",
          "outgoingShape": "C_u"
        }
      ],
      "container": "root"
    },
    {
      "id": "C-A",
      "sources": [
        "C_d"
      ],
      "targets": [
        "A_u"
      ],
      "sections": [
        {
          "id": "C-A_s0",
          "startPoint": {
            "x": 194.4,
            "y": 210.39999999999998
          },
          "endPoint": {
            "x": 133.6,
            "y": 44
          },
          "bendPoints": [
            {
              "x": 194.4,
              "y": 210.39999999999998
            },
            {
              "x": 194.39999999999998,
              "y": 226.39999999999998
            },
            {
              "x": 163.99999999999994,
              "y": 234.39999999999995
            },
            {
              "x": 133.59999999999997,
              "y": 242.39999999999995
            },
            {
              "x": 72.80000000000001,
              "y": 242.39999999999995
            },
            {
              "x": 42.40000000000002,
              "y": 237.0666666666666
            },
            {
              "x": 12,
              "y": 231.7333333333333
            },
            {
              "x": 12,
              "y": 221.06666666666666
            },
            {
              "x": 12,
              "y": 201.86666666666662
            },
            {
              "x": 12,
              "y": 182.66666666666663
            },
            {
              "x": 12,
              "y": 154.9333333333333
            },
            {
              "x": 12,
              "y": 134.13333333333333
            },
            {
              "x": 12,
              "y": 113.33333333333331
            },
            {
              "x": 12,
              "y": 99.46666666666665
            },
            {
              "x": 12,
              "y": 85.59999999999998
            },
            {
              "x": 12,
              "y": 71.73333333333332
            },
            {
              "x": 12,
              "y": 57.86666666666666
            },
            {
              "x": 12,
              "y": 45.599999999999994
            },
            {
              "x": 12,
              "y": 33.33333333333333
            },
            {
              "x": 12,
              "y": 22.666666666666664
            },
            {
              "x": 32.266666666666666,
              "y": 17.333333333333332
            },
            {
              "x": 52.53333333333333,
              "y": 12
            },
            {
              "x": 93.06666666666666,
              "y": 12
            },
            {
              "x": 113.3333333333333,
              "y": 20
            },
            {
              "x": 133.59999999999997,
              "y": 28
            },
            {
              "x": 133.6,
              "y": 44
            }
          ],
          "incomingShape": "C_d",
          "outgoingShape": "A_u"
        }
      ],
      "container": "root"
    }
  ],
  "$H": 13,
  "x": 0,
  "y": 0,
  "width": 235.2,
  "height": 254.39999999999998
}
tylerlong commented 4 weeks ago

I think maybe it looks more "balanced"? Feel free to close if it's by design.

soerendomroes commented 4 weeks ago

Hi, should you please replicate the issue in elklive? Your json does not seem to be a valid graph.

The issue occurs since we do not optimize for shorter edges when trying to find the correct path for the feedback edge since this stage of the algorithm optimizes for edge crossings. Moreover, I think that finding the shortest path for all feedback edges that might be in a graph is generally a hard problem.

So in short: The algorithm does not optimize for shortest edges.

Another thing I noticed: You seem to set "elk.layered.crossingMinimization.forceNodeModelOrder": "true" without setting a model order strategy. You should do that if you want this option to work correctly, as specified here.

tylerlong commented 4 weeks ago

should you please replicate the issue in elklive?

Click here

tylerlong commented 4 weeks ago

Another thing I noticed: You seem to set "elk.layered.crossingMinimization.forceNodeModelOrder": "true" without setting a model order strategy. You should do that if you want this option to work correctly, as specified here.

Thanks for bringing this up. This part is very confusing. I didn't set "model order strategy" but so far the node orders are always preserved.

And the doc says:

The node order given by the model does not change to produce a better layout. E.g. if node A is before node B in the model this is not changed during crossing minimization. This assumes that the node model order is already respected before crossing minimization. This can be achieved by setting considerModelOrder.strategy to NODES_AND_EDGES.

I don't understand why do I need to specify NODES_AND_EDGES if I only want to preserve node order.

soerendomroes commented 4 weeks ago

Hi, the position for the long edge will be fixed for the new release which will happen at some point, as seen here.

Currently, you can set a long edge ordering strategy, as seen here to solve your problem, as seen here.

The node and edge strategy does only determine the pre-sorting before crossing minimization happens. Since this might otherwise be randomized. It is hence only a tie-breaker and does not constrain anything. If you however only use forceNodeModelOrder, the order of comparisons might occur such that their transitive closure violates the node order. Hence, you should use either NODES_AND_EDGES or PREFER_NODES (which did not exist at the time of writing the docs and I forget to update it). For graphs that have no dangling nodes (source nodes that are not in the first layer) this should however not cause problems.

If there are more questions, feel free to ask.

tylerlong commented 3 weeks ago

I am all good now. I am going to close this one. I reported another issue here: https://github.com/kieler/elkjs/issues/305