Search code examples
javascriptalgorithmd3.jsgraphclass-diagram

Class diagram - optimal node positioning

I am trying to build a class diagram model viewer using d3.js and d3.dag

A most crucial part of this viewer is that it should be able to optimally position nodes so that we won't have link crossing (whenever possible) and plus should be able to clearly see what's connected to what

We know:

  • Width of each node
  • Height of each node
  • Links starting coordinate
  • Links ending coordinate
  • Links all corner coordinates

We want:

  • To see connections ending (Can be achieved manually moving nodes).

  • To minimize links crossing (If it's possible)

What I need is kinda theoretical.

Is there any known algorithm which can solve the problem above (Language does not matter, I just need theoretical reference)

Putting examples below

  • What's the current situation
  • What can I achieve by myself
  • What would be perfect

Example 1.

Current

enter image description here

Achievable

enter image description here

Perfect

enter image description here

Example 2.

Current

enter image description here

Achievable

enter image description here

Perfect

enter image description here

Example 3.

Current

enter image description here

Achievable And Perfect

enter image description here

Example 4.

Current

enter image description here

Achievable

enter image description here

Perfect

enter image description here

Example 5.

Current

enter image description here

Achievable

enter image description here

Perfect

enter image description here

Example 6.

Current

enter image description here

Perfect

enter image description here

Update

Traditional (node to node link ) crossing is already minimized in this case (thanks to d3-dag). The issue is that we don't have the only node to node relationship, we also have a node row to row relationship and in this case, d3-dag fails

Solution

  • I used d3-dag to topologically sort nodes, and then repositioned them vertically, top if odd and bottom if even

    Although it's not an algorithm I was looking for, it improved the visual look of components dramatically and made much more readable

    Old enter image description here

    New enter image description here

    Old enter image description here New enter image description here

    Old enter image description here New enter image description here