Feature request: Layered / Coffman-Graham: Order nodes by model

[Daniel-Khodabakhsh]

Thanks @soerendomroes for answering a previous related question which led me to using the Coffman-Graham algorithm as the node layering strategy (org.eclipse.elk.layered.layering.strategy).

Question:

Is it possible to make the Coffman-Graham algorithm layer the nodes such that the model order is respected?

Currently, using this ordered model:

Link

JSON

{
  id: 'root',
  layoutOptions: {
    'org.eclipse.elk.algorithm': 'layered',
    'separateConnectedComponents': false,
    // hierarchyHandling: 'INCLUDE_CHILDREN',
    'considerModelOrder.strategy': 'NODES_AND_EDGES', // Works only with elk 0.8.X: change at the top right.
    'layering.strategy': 'COFFMAN_GRAHAM',
    'layering.coffmanGraham.layerBound': 6,
    'nodePlacement.strategy': 'SIMPLE' // This may produce edge bends but centers all nodes in their layer bounds.
  },
  children: [
    {id: 'n1', width: 30, height: 30, labels: [{text: 'n1'}]},
    {id: 'n2', width: 30, height: 30, labels: [{text: 'n2'}]},
    {id: 'n3', width: 30, height: 30, labels: [{text: 'n3'}]},
    {id: 'n4', width: 30, height: 30, labels: [{text: 'n4'}]},
    {id: 'n5', width: 30, height: 30, labels: [{text: 'n5'}]},
    {id: 'n6', width: 30, height: 30, labels: [{text: 'n6'}]},
    {id: 'n7', width: 30, height: 30, labels: [{text: 'n7'}]},
    {id: 'n8', width: 30, height: 30, labels: [{text: 'n8'}]},
    {id: 'n9', width: 30, height: 30, labels: [{text: 'n9'}]},
    {id: 'n10', width: 30, height: 30, labels: [{text: 'n10'}]},
    {id: 'n11', width: 30, height: 30, labels: [{text: 'n11'}]},
    {id: 'n12', width: 30, height: 30, labels: [{text: 'n12'}]},
    {id: 'n13', width: 30, height: 30, labels: [{text: 'n13'}]},
    {id: 'n14', width: 30, height: 30, labels: [{text: 'n14'}]},
    {id: 'n15', width: 30, height: 30, labels: [{text: 'n15'}]},
    {id: 'n16', width: 30, height: 30, labels: [{text: 'n16'}]},
    {id: 'n17', width: 30, height: 30, labels: [{text: 'n17'}]},
    {id: 'n18', width: 30, height: 30, labels: [{text: 'n18'}]},
    {id: 'n19', width: 30, height: 30, labels: [{text: 'n19'}]},
    {id: 'n20', width: 30, height: 30, labels: [{text: 'n20'}]},
    {id: 'n21', width: 30, height: 30, labels: [{text: 'n21'}]},
    {id: 'n22', width: 30, height: 30, labels: [{text: 'n22'}]},
    {id: 'n23', width: 30, height: 30, labels: [{text: 'n23'}]},
    {id: 'n24', width: 30, height: 30, labels: [{text: 'n24'}]},
    {id: 'n25', width: 30, height: 30, labels: [{text: 'n25'}]},
    {id: 'n26', width: 30, height: 30, labels: [{text: 'n26'}]},
    {id: 'n27', width: 30, height: 30, labels: [{text: 'n27'}]},
    {id: 'n28', width: 30, height: 30, labels: [{text: 'n28'}]},
    {id: 'n29', width: 30, height: 30, labels: [{text: 'n29'}]},
    {id: 'n30', width: 30, height: 30, labels: [{text: 'n30'}]},
    {id: 'n31', width: 30, height: 30, labels: [{text: 'n31'}]},
    {id: 'n32', width: 30, height: 30, labels: [{text: 'n32'}]},
  ],
  edges: [
    {id: 'e1', sources: ['n1'], targets: ['n2']},
    {id: 'e2', sources: ['n1'], targets: ['n3']},
    {id: 'e3', sources: ['n3'], targets: ['n4']},
    {id: 'e4', sources: ['n20'], targets: ['n21']},
    {id: 'e5', sources: ['n20'], targets: ['n22']},
    {id: 'e6', sources: ['n20'], targets: ['n23']},
  ]
}

the nodes do not appear to follow the order:

What I expected in the above is that nodes 6, 8, 9 should replace nodes 11, 19, and 32, etc.

Edit:

As per the conversation, changing this ticket from a question to a feature request.

This should probably use 'considerModelOrder.strategy' to control how to order the nodes. Currently, none of the options order the nodes according to the model.

[soerendomroes]

That is currently not possible. I see multiple ways to respect the model order here.

I guess you want that all not connected nodes with a small model order should be in one of the first layers. I am not sure how this should work together with the connected parts. Should n5 be placed below n4 and not below n1? Could you sketch your desired solution?

Do you want this:

1  2  4  19 21 31
5  3  14 20 22 32
6  10 15 24 23
7  11 16 25 28
8  12 17 26 29
9  13 18 27 30

[Daniel-Khodabakhsh]

Yes that's right @soerendomroes , that's the exact order I would like. So connected nodes get pushed deeper out of order, but any node that can surface up a layer can in an order-respecting manner, just like you illustrated.

[soerendomroes]

Do you want that nodes with a smaller model order can be in a higher layer as shown above or should the model order interpreted as a constraint such that a node with a smaller model order should be in the same or a lower layer.

[soerendomroes]

To summarize, this currently does not work, but we might be able to add this if we have time. PRs are always welcome, otherwise it might take a few months (or years). What is your use-case for this?

[Daniel-Khodabakhsh]

Gotchya, thanks for the context @soerendomroes !

The use-case is for a tool I am building, where users have the ability to reorder non-child nodes, and nodes are displayed in a scrollable window (with one direction being fixed by the Coffman-Graham bound).

Hummm I might be able to get away with just storing what the user asks to store. Played around with changing the layering.coffmanGraham.layerBound and the strange order persists somewhat consistently. One issue I'm seeing is when I set it to 2, nodes 2, 3, and 4 are buried a bit deeper than they need to be:

[soerendomroes]

Just to document the problem: In its current implementation, Coffman-Graham layering uses PriorityQueues which might reorder elements with same priority (i.e. nodes that are not connected) if the queue changes. This is bad and should be fixed by considering the insertion order (or the model order) as a secondary criterion.

tldr: This poll reorders unconnected nodes.